数据结构的基本框架及基础操作

---

索引：

1、线性表

2、堆栈

3、队列

4、堆栈与队列的联合运用

5、树

---

一、线性表

线性表

（一）顺序存储（从下标0开始储存）

（一）顺序存储

1、结构定义：

结构定义

typedef struct lnode *ptrl;  // 定义指向结构体lnode的指针类型ptrl
struct lnode  // 定义结构体lnode
{
    element data[maxsize];  // 数据数组，存储元素
    int last;  // 记录最后一个元素的位置
};
typedef ptrl list;  // 定义list类型为指向lnode的指针

2、基础操作集

基础操作集

①初始化函数（list init()）：

list init()  // 初始化列表
{
    list l = (list)malloc(sizeof(struct lnode));  // 分配列表节点内存
    l->last = -1;  // 初始化最后一个元素位置为 -1，表示列表为空
    return l;  // 返回初始化后的列表
}

②查找（element find(list l, element x)）：

element find(list l, element x)  // 查找元素 x 在列表中的位置
{
    int i = 0;
    while (i <= l->last && l->data[i] != x)  // 遍历列表查找元素 x
        i++;
    if (i > l->last)  // 如果未找到 x，返回 -1
        return -1;
    return i+1;  // 返回元素 x 在列表中的位置
}

③插入（int insert(list l, element x, int i)）：

int insert(list l, element x, int i)  // 在位置 i 插入元素 x
{
    int j;
    if (l->last == maxsize - 1)  // 检查列表是否已满
    {
        printf("表满");
        return -1;
    }
    if (i < 0 || i > l->last + 1)  // 检查插入位置是否合法
    {
        printf("插入位序不合法\n");
        return -1;
    }
    for (j = l->last; j >= i - 1; j--)  // 移动元素以腾出插入位置
        l->data[j + 1] = l->data[j];
    l->data[i - 1] = x;  // 在位置 i 插入元素 x
    l->last++;  // 更新列表的最后一个元素位置
    return 1;
}

④删除（element deletel(list l, int i)）：

element deletel(list l, int i)  // 删除位置 i 的元素
{
    int j;
    if (i < 0 || i > l->last)  // 检查删除位置是否合法
    {
        printf("位序%d不存在", i);
        return -1;
    }
    for (j = i; j <= l->last; j++)  // 移动元素以覆盖被删除的元素
        l->data[j - 1] = l->data[j];
    l->last--;  // 更新列表的最后一个元素位置
    return 1;
}

3、示例代码：

示例代码

#include<stdio.h>
#include<stdlib.h>
#define maxsize 100  // 定义列表的最大大小
typedef int element;  // 定义元素类型为 int
typedef struct lnode *ptrl;  // 定义指向 lnode 结构体的指针类型 ptrl
struct lnode  // 定义列表节点结构体
{
    element data[maxsize];  // 存储列表元素的数组
    int last;  // 列表中最后一个元素的位置
};
typedef ptrl list;  // 定义列表类型为 ptrl

list init();  // 初始化列表
element find(list l, element x);  // 查找元素 x 在列表中的位置
int insert(list l, element x, int i);  // 在位置 i 插入元素 x
element deletel(list l, int i);  // 删除位置 i 的元素

int main() {
    list l = init();  // 初始化一个列表
    int i;
    int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};  // 定义并初始化数组 a
    for (i = 0; i < 10; i++)  // 将数组 a 中的元素插入到列表中
    {
        int x = a[i];
        l->data[i] = x;  // 将元素存储到列表中，从索引 0 开始
        l->last++;  // 更新列表的最后一个元素位置
    }

    insert(l, 80, 7);  // 在位置 7 插入元素 80
    for (i = 0; i <= l->last; i++)
        printf("%d ", l->data[i]);
    printf("\n");

    printf("%d\n",find(l,80));  // 查找元素 80 在列表中的位置 

    deletel(l, 7);  // 删除位置 7 的元素
    for (i = 0; i <= l->last; i++)
        printf("%d ", l->data[i]);
    printf("\n");

    return 0;
}

list init()  // 初始化列表
{
    list l = (list)malloc(sizeof(struct lnode));  // 分配列表节点内存
    l->last = -1;  // 初始化最后一个元素位置为 -1，表示列表为空
    return l;  // 返回初始化后的列表
}

element find(list l, element x)  // 查找元素 x 在列表中的位置
{
    int i = 0;
    while (i <= l->last && l->data[i] != x)  // 遍历列表查找元素 x
        i++;
    if (i > l->last)  // 如果未找到 x，返回 -1
        return -1;
    return i+1;  // 返回元素 x 在列表中的位置
}

int insert(list l, element x, int i)  // 在位置 i 插入元素 x
{
    int j;
    if (l->last == maxsize - 1)  // 检查列表是否已满
    {
        printf("表满");
        return -1;
    }
    if (i < 0 || i > l->last + 1)  // 检查插入位置是否合法
    {
        printf("插入位序不合法\n");
        return -1;
    }
    for (j = l->last; j >= i - 1; j--)  // 移动元素以腾出插入位置
        l->data[j + 1] = l->data[j];
    l->data[i - 1] = x;  // 在位置 i 插入元素 x
    l->last++;  // 更新列表的最后一个元素位置
    return 1;
}

int deletel(list l, int i)  // 删除位置 i 的元素
{
    int j;
    if (i < 0 || i > l->last)  // 检查删除位置是否合法
    {
        printf("位序%d不存在", i);
        return -1;
    }
    for (j = i; j <= l->last; j++)  // 移动元素以覆盖被删除的元素
        l->data[j - 1] = l->data[j];
    l->last--;  // 更新列表的最后一个元素位置
    return 1;
}

（二）链式存储（带头结点）

（二）顺序存储

1、结构定义：

结构定义

typedef struct lnode *ptrl;  // 定义指向 lnode 结构体的指针类型 ptrl
struct lnode  // 定义列表节点结构体
{
    element data;  // 数据域
    ptrl next;  // 指向下一个节点的指针
};
typedef ptrl list; 

2、基础操作集

基础操作集

①初始化函数（list init()）：

list init()  
{
    list l = (list)malloc(sizeof(struct lnode));  // 分配列表节点内存
    l->next = NULL;  // 初始化为空列表
    return l;  // 返回初始化后的列表
}

②判断列表是否为空（int isempty(list l)）：

int isempty(list l) 
{
    return l->next == NULL;  // 若第一个节点为空，则列表为空
}

③获取列表长度（int length(list l)）：

int length(list l) 
{
    list p = l->next;  // 指针 p 指向链表的第一个元素
    int cnt = 0;  // 计数器
    while (p)  // 遍历链表
    {  
        p = p->next;  // 移动到下一个节点
        cnt++;  // 计数
    }
    return cnt;  // 返回链表长度
}

④按值查找节点（list findx(list l, element x)）：

list findx(list l, element x)  
{
    list p = l->next;  // 指针 p 指向链表的第一个元素
    while (p && p->data != x)  // 遍历链表，寻找值为 x 的节点
    {  
        p = p->next;  // 移动到下一个节点
    }
    return p;  // 返回找到的节点，若未找到返回 NULL
}

⑤按序号查找节点值（element findp(list l, int k)）：

element findp(list l, int k)  
{
    list p = l->next;  // 指针 p 指向链表的第一个元素
    int i = 0;  // 计数器
    while (p && i < k) 
    {  // 遍历链表，直到找到第 k 个节点
        p = p->next;  // 移动到下一个节点
        i++;  // 计数
    }
    if (i == k && p)  // 如果找到第 k 个节点
        return p->data;  // 返回节点的数据
    return -1;  // 未找到则返回 -1
}

⑥在位置 i 插入元素 x（int insert(list l, element x, int i)）：

 int insert(list l, element x, int i)  
{
    int j = 0;  // 计数器
    list p = l;  // 指针 p 指向链表头节点
    while (p && j < i - 1) {  // 寻找第 i-1 个节点
        p = p->next;  // 移动到下一个节点
        j++;  // 计数
    }

    if (p == NULL || j != i - 1) {  // 检查插入位置是否合法
        printf("插入位置参数错误\n");  // 插入位置错误提示
        return -1;  // 返回错误码
    }
    list t = (list)malloc(sizeof(struct lnode));  // 分配新节点内存
    t->data = x;  // 设置新节点的数据
    t->next = p->next;  // 新节点指向插入位置的下一个节点
    p->next = t;  // 插入新节点
    return 1;  // 返回成功码
}

⑦删除位置 i 的元素（int deletel(list l, int i)）：

int deletel(list l, int i)  
{
    int j = 0;  // 计数器
    list p = l;  // 指针 p 指向链表头节点
    while (p && j < i - 1) {  // 寻找第 i-1 个节点
        p = p->next;  // 移动到下一个节点
        j++;  // 计数
    }
    if (p == NULL || j != i - 1 || p->next == NULL) {  // 检查删除位置是否合法
        printf("删除位置参数错误\n");  // 删除位置错误提示
        return -1;  // 返回错误码
    }
    list t = p->next;  // 指向要删除的节点
    p->next = t->next;  // 跳过要删除的节点
    free(t);  // 释放要删除节点的内存
    return 1;  // 返回成功码
}

3、示例代码：

示例代码

#include<stdio.h>
#include<stdlib.h>

// 定义元素类型为 int
typedef int element;  

// 定义指向 lnode 结构体的指针类型 ptrl
typedef struct lnode *ptrl;  

// 定义列表节点结构体
struct lnode  
{
    element data;  // 数据域
    ptrl next;  // 指向下一个节点的指针
};
typedef ptrl list;  

list init();  // 初始化列表
int isempty(list l);  // 判断列表是否为空
int length(list l);  // 获取列表长度
list findx(list l, element x);  // 按值查找节点
element findp(list l, int k);  // 按序号查找节点值
int insert(list l, element x, int i);  // 在位置 i 插入元素 x
int deletel(list l, int i);  // 删除位置 i 的元素

int main() {
    // 初始化列表
    list l = init();
    int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int i;

    // 插入元素
    for(i = 0; i < 10; i++) 
        insert(l, a[i], i + 1);  // 在位置 i+1 插入元素 a[i]

    // 输出链表中的元素
    ptrl p = l->next;  // 指针 p 指向链表的第一个元素
    while (p != NULL) 
    {
        printf("%d ", p->data);
        p = p->next;  // 移动到下一个节点
    }

    printf("\n链表长度: %d\n", length(l));

    p = findx(l, 7);  // 查找值为 7 的节点
    printf("%d\n", p->data);

    printf("%d\n", findp(l, 7));  // 按序号查找第 7 个节点的数据

    // 删除第 7 个节点并打印链表
    if (deletel(l, 7)) 
    {
        p = l->next;  // 指针 p 指向链表的第一个元素
        while (p != NULL) 
        {
            printf("%d ", p->data);
            p = p->next;  // 移动到下一个节点
        }
    }

    return 0;
}

// 初始化列表
list init()  
{
    list l = (list)malloc(sizeof(struct lnode));  // 分配列表节点内存
    l->next = NULL;  // 初始化为空列表
    return l;  // 返回初始化后的列表
}

// 判断列表是否为空
int isempty(list l) 
{
    return l->next == NULL;  // 若第一个节点为空，则列表为空
}

// 获取列表长度
int length(list l) 
{
    list p = l->next;  // 指针 p 指向链表的第一个元素
    int cnt = 0;  // 计数器
    while (p)  // 遍历链表
    {  
        p = p->next;  // 移动到下一个节点
        cnt++;  // 计数
    }
    return cnt;  // 返回链表长度
}

// 按值查找节点
list findx(list l, element x)  
{
    list p = l->next;  // 指针 p 指向链表的第一个元素
    while (p && p->data != x)  // 遍历链表，寻找值为 x 的节点
    {  
        p = p->next;  // 移动到下一个节点
    }
    return p;  // 返回找到的节点，若未找到返回 NULL
}

// 按序号查找节点值
element findp(list l, int k)  
{
    list p = l->next;  // 指针 p 指向链表的第一个元素
    int i = 0;  // 计数器
    while (p && i < k) 
    {  // 遍历链表，直到找到第 k 个节点
        p = p->next;  // 移动到下一个节点
        i++;  // 计数
    }
    if (i == k && p)  // 如果找到第 k 个节点
        return p->data;  // 返回节点的数据
    return -1;  // 未找到则返回 -1
}

// 在位置 i 插入元素 x
int insert(list l, element x, int i)  
{
    int j = 0;  // 计数器
    list p = l;  // 指针 p 指向链表头节点
    while (p && j < i - 1) {  // 寻找第 i-1 个节点
        p = p->next;  // 移动到下一个节点
        j++;  // 计数
    }

    if (p == NULL || j != i - 1) {  // 检查插入位置是否合法
        printf("插入位置参数错误\n");  // 插入位置错误提示
        return -1;  // 返回错误码
    }
    list t = (list)malloc(sizeof(struct lnode));  // 分配新节点内存
    t->data = x;  // 设置新节点的数据
    t->next = p->next;  // 新节点指向插入位置的下一个节点
    p->next = t;  // 插入新节点
    return 1;  // 返回成功码
}

// 删除位置 i 的元素
int deletel(list l, int i)  
{
    int j = 0;  // 计数器
    list p = l;  // 指针 p 指向链表头节点
    while (p && j < i - 1) {  // 寻找第 i-1 个节点
        p = p->next;  // 移动到下一个节点
        j++;  // 计数
    }
    if (p == NULL || j != i - 1 || p->next == NULL) {  // 检查删除位置是否合法
        printf("删除位置参数错误\n");  // 删除位置错误提示
        return -1;  // 返回错误码
    }
    list t = p->next;  // 指向要删除的节点
    p->next = t->next;  // 跳过要删除的节点
    free(t);  // 释放要删除节点的内存
    return 1;  // 返回成功码
}

（三）题目运用示例（非PTA）：

题目运用示例

作者 幻梦

单位 无

有两组按升序排序的数据，请将这两组数据按升序合并成一组

输入格式:

输入第1行为n，m，分别表示两组数据的个数；

第2行给出n个整数，以升序排列；

第2行给出m个整数，以升序排列；

输出格式:

按升序输出合并后的一组数据

输入样例:

5 6
1 3 5 7 9
0 2 4 6 8 10

输出样例:

0 1 2 3 4 5 6 7 8 9 10 

答案示例：

#include<stdio.h>
#include<stdlib.h>

// 定义元素类型为 int
typedef int element;  

// 定义指向 lnode 结构体的指针类型 ptrl
typedef struct lnode *ptrl;  

// 定义列表节点结构体
struct lnode  
{
    element data;  // 数据域
    ptrl next;  // 指向下一个节点的指针
};
typedef ptrl list;  

list init();  // 初始化列表
int isempty(list l);  // 判断列表是否为空
int length(list l);  // 获取列表长度
list findx(list l, element x);  // 按值查找节点
element findp(list l, int k);  // 按序号查找节点值
int insert(list l, element x, int i);  // 在位置 i 插入元素 x
int deletel(list l, int i);  // 删除位置 i 的元素

int main() {
    list l1=init(),l2=init();
    int m,n,i,j,x;
    scanf("%d%d",&m,&n);

    for(i=0;i<m;i++)
    {
        scanf("%d",&x);
        insert(l1,x,i+1);
    }
    for(i=0;i<n;i++)
    {
        scanf("%d",&x);
        insert(l2,x,i+1);
    }

    list p1=l1->next,p2=l2->next;
    while(p1&&p2)
    {
        if(p1->data>p2->data)
        {
            printf("%d ",p2->data);
            p2=p2->next;
        }

        else if(p1->data<p2->data)
        {
            printf("%d ",p1->data);
            p1=p1->next;
        }
        else if(p1->data==p2->data)
        {
            printf("%d ",p2->data);
            p2=p2->next;
            p1=p1->next;
        }
    }
    if(p1)
    {
        while(p1)
        {
            printf("%d ",p1->data);
            p1=p1->next;
        }
    }
    else
    {
        while(p2)
        {
            printf("%d ",p2->data);
            p2=p2->next;
        }
    }

    return 0;
}

// 初始化列表
list init()  
{
    list l = (list)malloc(sizeof(struct lnode));  // 分配列表节点内存
    l->next = NULL;  // 初始化为空列表
    return l;  // 返回初始化后的列表
}

// 判断列表是否为空
int isempty(list l) 
{
    return l->next == NULL;  // 若第一个节点为空，则列表为空
}

// 获取列表长度
int length(list l) 
{
    list p = l->next;  // 指针 p 指向链表的第一个元素
    int cnt = 0;  // 计数器
    while (p)  // 遍历链表
    {  
        p = p->next;  // 移动到下一个节点
        cnt++;  // 计数
    }
    return cnt;  // 返回链表长度
}

// 按值查找节点
list findx(list l, element x)  
{
    list p = l->next;  // 指针 p 指向链表的第一个元素
    while (p && p->data != x)  // 遍历链表，寻找值为 x 的节点
    {  
        p = p->next;  // 移动到下一个节点
    }
    return p;  // 返回找到的节点，若未找到返回 NULL
}

// 按序号查找节点值
element findp(list l, int k)  
{
    list p = l->next;  // 指针 p 指向链表的第一个元素
    int i = 0;  // 计数器
    while (p && i < k) 
    {  // 遍历链表，直到找到第 k 个节点
        p = p->next;  // 移动到下一个节点
        i++;  // 计数
    }
    if (i == k && p)  // 如果找到第 k 个节点
        return p->data;  // 返回节点的数据
    return -1;  // 未找到则返回 -1
}

// 在位置 i 插入元素 x
int insert(list l, element x, int i)  
{
    int j = 0;  // 计数器
    list p = l;  // 指针 p 指向链表头节点
    while (p && j < i - 1) {  // 寻找第 i-1 个节点
        p = p->next;  // 移动到下一个节点
        j++;  // 计数
    }

    if (p == NULL || j != i - 1) {  // 检查插入位置是否合法
        printf("插入位置参数错误\n");  // 插入位置错误提示
        return -1;  // 返回错误码
    }
    list t = (list)malloc(sizeof(struct lnode));  // 分配新节点内存
    t->data = x;  // 设置新节点的数据
    t->next = p->next;  // 新节点指向插入位置的下一个节点
    p->next = t;  // 插入新节点
    return 1;  // 返回成功码
}

// 删除位置 i 的元素
int deletel(list l, int i)  
{
    int j = 0;  // 计数器
    list p = l;  // 指针 p 指向链表头节点
    while (p && j < i - 1) {  // 寻找第 i-1 个节点
        p = p->next;  // 移动到下一个节点
        j++;  // 计数
    }
    if (p == NULL || j != i - 1 || p->next == NULL) {  // 检查删除位置是否合法
        printf("删除位置参数错误\n");  // 删除位置错误提示
        return -1;  // 返回错误码
    }
    list t = p->next;  // 指向要删除的节点
    p->next = t->next;  // 跳过要删除的节点
    free(t);  // 释放要删除节点的内存
    return 1;  // 返回成功码
}

---

二、堆栈（顺式）

堆栈

1、结构定义：

结构定义

typedef struct snode *ptrs; // 定义指向 snode 结构体的指针类型 ptrs
struct snode
{ 
    element *data; // 指向堆栈数据的指针 
    int top; // 栈顶索引 
    int maxsize; // 栈的最大容量
};
typedef ptrs stack; // 定义堆栈指针类型为 stack

2、基础操作集

基础操作集

①创建栈（stack creats(int max)）：

stack creatS(int max)  // 创建一个新的顺序栈，参数为栈的最大容量
{
    stack s = (stack)malloc(sizeof(struct snode));  // 分配堆栈节点内存
    s->data = (element*)malloc(sizeof(element) * max);  // 分配存储栈数据的内存
    s->top = -1;  // 初始化栈顶索引为 -1，表示栈为空
    s->maxsize = max;  // 设置栈的最大容量
    return s;  // 返回创建的栈
}

②入栈操作（void push(stack s, element x)）：

void push(stack s, element x)  // 入栈操作
{
    if (isfull(s))  // 检查栈是否已满
    {
        printf("栈满\n");  // 栈满时打印提示信息
        return;  // 退出函数
    }
    s->data[++(s->top)] = x;  // 将元素 x 入栈，栈顶索引加 1
}

③出栈操作（element pop(stack s)）：

element pop(stack s)  // 出栈操作
{
    if (isempty(s))  // 检查栈是否为空
    {
        printf("栈空\n");  // 栈为空时打印提示信息
        return -1;  // 返回 -1 表示栈空错误标志
    }
    return s->data[(s->top)--];  // 返回栈顶元素，并将栈顶索引减 1
}

④检查栈是否为空（int isempty(stack s)）：

int isempty(stack s)  // 检查栈是否为空
{
    return s->top == -1;  // 栈顶索引为 -1 表示栈为空
}

⑤检查栈是否已满（int isfull(stack s)）：

int isfull(stack s)  // 检查栈是否已满
{
    return s->top == s->maxsize - 1;  // 栈顶索引等于最大容量减 1 表示栈已满
}

3、示例代码：

示例代码

#include <stdio.h>
#include <stdlib.h>

typedef int element;  // 定义 element 类型为 int

typedef struct snode *ptrs;  // 定义指向 snode 结构体的指针类型 ptrs
struct snode
{
    element *data;  // 指向堆栈数据的指针
    int top;  // 栈顶索引
    int maxsize;  // 栈的最大容量
};
typedef ptrs stack;  // 定义堆栈指针类型为 stack

stack creatS(int max);  // 函数声明：创建栈
void push(stack s, element x);  // 函数声明：入栈操作
element pop(stack s);  // 函数声明：出栈操作
int isempty(stack s);  // 函数声明：检查栈是否为空
int isfull(stack s);  // 函数声明：检查栈是否已满

int main() {
    int max = 5;  // 定义栈的最大容量为 5
    stack s = creatS(max);  // 创建一个最大容量为 5 的栈

    int i;
    int k[max + 1] = {2, 3, 5, 6, 4, 7};  // 初始化一个包含 6 个整数的数组
    for (i = 0; i < max + 1; i++)
    push(s, k[i]);  // 将数组中的每个元素入栈

    for (i = 0; i < max + 1; i++)  // 尝试弹出比max更多的元素
    {  
        int result = pop(s);  // 从栈中弹出每个元素
        if (result != -1)
        printf("%d ", result);  // 如果结果不是错误标志则打印
    }

    return 0;
}

// 创建一个新的顺序栈，参数为栈的最大容量
stack creatS(int max)
{
    stack s = (stack)malloc(sizeof(struct snode));  // 分配堆栈节点内存
    s->data = (element*)malloc(sizeof(element) * max);  // 分配存储栈数据的内存
    s->top = -1;  // 初始化栈顶索引为 -1，表示栈为空
    s->maxsize = max;  // 设置栈的最大容量
    return s;  // 返回创建的栈
}

// 将元素 x 入栈
void push(stack s, element x)
{
    if (isfull(s))  // 检查栈是否已满
    {
        printf("栈满\n");  // 栈满时打印提示信息
        return;  // 退出函数
    }
    s->data[++(s->top)] = x;  // 将元素 x 入栈，栈顶索引加 1
}

// 从栈中弹出一个元素
element pop(stack s)
{
    if (isempty(s))  // 检查栈是否为空
    {
        printf("栈空\n");  // 栈为空时打印提示信息
        return -1;  // 返回 -1 表示栈空错误标志
    }
    return s->data[(s->top)--];  // 返回栈顶元素，并将栈顶索引减 1
}

// 检查栈是否为空
int isempty(stack s)
{
    return s->top == -1;  // 栈顶索引为 -1 表示栈为空
}

// 检查栈是否已满
int isfull(stack s)
{
    return s->top == s->maxsize - 1;  // 栈顶索引等于最大容量减 1 表示栈已满
}

4、题目运用示例（PTA）：

题目运用示例

7-3 有趣的括号

作者 Drizzle

单位 山东科技大学

括号()的组合千奇百怪，Drizzle 想知道各种组合的括号可以是否合法
合法要求：每个同类型的左括号必须有与之对应的同类的右括号以正确的顺序闭合

要求:

输入：输入一个括号字符串
输出：输出是否合法，是则True，否则False

示例:

输入：

(){}[]

输出：

True

范围:

对于 100% 的数据：括号字符串长度 ≤ 100

代码长度限制：16 KB

时间限制：400 ms

内存限制：64 MB

栈限制：8192 KB

答案示例：

#include <stdio.h>
#include <stdlib.h>
typedef char element;
typedef struct snode *ptrs;
struct snode
{
    element *data;
    int top;
    int maxsize;
};
typedef ptrs stack;

stack creatS(int max);//建栈 
void push(stack s,element x);//入栈
element pop(stack s);//出栈
int sisempty(stack s);//检查空栈

int main() {
    int i=0,f=1,cnt1=0,cnt2=0;
    char s[1000];
    stack s1=creatS(100);
    gets(s);
    while(s[i])
    {
        if(s[i]=='('||s[i]=='{'||s[i]=='[')
        {
            cnt1++;
            push(s1,s[i]);
        }

        if(s[i]==')'||s[i]=='}'||s[i]==']')
        {
            cnt2++;
            c1=pop(s1);
            c2=s[i];

            if(c1!='('&&c2==')'||c1!='{'&&c2=='}'||c1!='['&&c2==']')
            f=0;
        }
        i++;
    }
    if(f&&cnt1==cnt2)
    printf("True");
    else
    printf("False");
    return 0;
}
stack creatS(int max)//建栈
{
    stack s=(stack)malloc(sizeof(struct snode));
    s->data=(element*)malloc(sizeof(element)*max);
    s->top=-1;
    s->maxsize=max;
    return s;
}
void push(stack s,element x)//入栈
{
    s->data[++(s->top)]=x;
}
element pop(stack s)//出栈
{
    return s->data[(s->top)--];
}
int isempty(stack s)//检查空栈
{
    if(s->top==-1)
    return 1;
    return 0;
}

---

三、队列（顺式&循环队列）：

队列

1、结构定义：

结构定义

typedef struct qnode *ptrq;  // 定义指向 qnode 结构体的指针类型 ptrq
struct qnode  // 定义队列节点结构体
{
    element *data;  // 指向队列数据的指针
    int front, rear;  // 队列的头和尾索引
    int Maxsize;  // 队列的最大容量
};
typedef ptrq queue;  // 定义队列指针类型为 queue

2、基础操作集：

基础操作集

①创建队列（queue creat(int max)）：

queue creatQ(int max)  // 创建一个新的队列，参数为队列的最大容量
{
    queue q = (queue)malloc(sizeof(struct qnode));  // 分配队列节点内存
    q->data = (element*)malloc(sizeof(element) * max);  // 分配存储队列数据的内存
    q->front = 0;  // 初始化队列的头索引为 0
    q->rear = 0;  // 初始化队列的尾索引为 0
    q->Maxsize = max;  // 设置队列的最大容量
    return q;  // 返回创建的队列
}

②入队操作（void add(queue q, element x)）：

void add(queue q, element x)  // 将元素 x 入队
{
    if (isfull(q))  // 检查队列是否已满
    {
        printf("队满");  // 队满时打印提示信息
        return;  // 退出函数
    }
    q->rear = (q->rear + 1) % q->Maxsize;  // 更新队尾索引，循环队列实现
    q->data[q->rear] = x;  // 将元素 x 入队
}

③出队操作（element deleteq(queue q)）：

element deleteq(queue q)  // 从队列中删除一个元素
{
    if (isempty(q))  // 检查队列是否为空
    {
        printf("队空");  // 队列为空时打印提示信息
        return 0;  // 返回 0 表示删除失败
    }
    q->front = (q->front + 1) % q->Maxsize;  // 更新队头索引，循环队列实现
    return q->data[q->front];  // 返回队头元素
}

④检查队列是否已满（int isfull(queue q)）：

int isfull(queue q)  // 检查队列是否已满
{
    if ((q->rear + 1) % q->Maxsize == q->front)  // 判断队尾索引加 1 后是否等于队头索引
    return 1;  // 返回 1 表示队列已满
    return 0;  // 返回 0 表示队列未满
}

⑤检查队列是否为空（int isempty(queue q)）：

int isempty(queue q)  // 检查队列是否为空
{
    if (q->rear == q->front)  // 判断队尾索引是否等于队头索引
    return 1;  // 返回 1 表示队列为空
    return 0;  // 返回 0 表示队列不为空
}

3、示例代码：

示例代码

#include <stdio.h>
#include <stdlib.h>

typedef char element;  // 定义 element 类型为 char

typedef struct qnode *ptrq;  // 定义指向 qnode 结构体的指针类型 ptrq
struct qnode  // 定义队列节点结构体
{
    element *data;  // 指向队列数据的指针
    int front, rear;  // 队列的头和尾索引
    int Maxsize;  // 队列的最大容量
};
typedef ptrq queue;  // 定义队列指针类型为 queue

queue creatQ(int max);  // 函数声明：创建队列
void add(queue q, element x);  // 函数声明：入队操作
element deleteq(queue q);  // 函数声明：出队操作
int isfull(queue q);  // 函数声明：检查队列是否已满
int isempty(queue q);  // 函数声明：检查队列是否为空

int main() {
    int max = 5;  // 定义队列的最大容量为 5
    queue q = creatQ(max);  // 创建一个最大容量为 5 的队列

    char c[6] = {'+', '*', '/', '-', '!', '%'};  // 初始化一个包含 6 个字符的数组
    int i;
    for (i = 0; i < max; i++)
    add(q, c[i]);  // 将数组中的每个元素入队
    printf("\n");

    for (i = 0; i < max; i++)
    printf("%c ", deleteq(q));  // 从队列中删除每个元素并打印

    return 0;
}

// 顺序队列：循环队列
queue creatQ(int max)  // 创建一个新的队列，参数为队列的最大容量
{
    queue q = (queue)malloc(sizeof(struct qnode));  // 分配队列节点内存
    q->data = (element*)malloc(sizeof(element) * max);  // 分配存储队列数据的内存
    q->front = 0;  // 初始化队列的头索引为 0
    q->rear = 0;  // 初始化队列的尾索引为 0
    q->Maxsize = max;  // 设置队列的最大容量
    return q;  // 返回创建的队列
}

void add(queue q, element x)  // 将元素 x 入队
{
    if (isfull(q))  // 检查队列是否已满
    {
        printf("队满");  // 队满时打印提示信息
        return;  // 退出函数
    }
    q->rear = (q->rear + 1) % q->Maxsize;  // 更新队尾索引，循环队列实现
    q->data[q->rear] = x;  // 将元素 x 入队
}

element deleteq(queue q)  // 从队列中删除一个元素
{
    if (isempty(q))  // 检查队列是否为空
    {
        printf("队空");  // 队列为空时打印提示信息
        return 0;  // 返回 0 表示删除失败
    }
    q->front = (q->front + 1) % q->Maxsize;  // 更新队头索引，循环队列实现
    return q->data[q->front];  // 返回队头元素
}

int isfull(queue q)  // 检查队列是否已满
{
    if ((q->rear + 1) % q->Maxsize == q->front)  // 判断队尾索引加 1 后是否等于队头索引
    return 1;  // 返回 1 表示队列已满
    return 0;  // 返回 0 表示队列未满
}

int isempty(queue q)  // 检查队列是否为空
{
    if (q->rear == q->front)  // 判断队尾索引是否等于队头索引
    return 1;  // 返回 1 表示队列为空
    return 0;  // 返回 0 表示队列不为空
}

4、题目运用示例（PTA）：

题目运用示例

7-2 队的基本操作

作者 唐艳琴

单位 中国人民解放军陆军工程大学

给定一个初始为空的队（队存储空间长度为10）和一系列进队、出队操作，请编写程序输出经过这些操作后队中的元素。队中元素值均为整数。（采用循环队列完成，禁用一个空间方法）

输入格式:

输入第1行为1个正整数n，表示操作个数；

第2行为给出的n个整数，非0元素表示进队，且此非0值即为进队元素，0元素表示出队。

输出格式:

第一行按出队顺序输出所有出队元素，以一个空格隔开；如果队空时做出队操作会输出”EMPTY”，如果队满时做进队操作会输出”FULL”。

第二行中输出队中所有元素，以一个空格隔开。

末尾均有一个空格。

输入样例:

12
3 1 2 0 0 -1 0 0 0 4 5 0

输出样例:

3 1 2 -1 EMPTY 4 
5

代码长度限制：16 KB

时间限制：400 ms

内存限制：64 MB

栈限制：8192 KB

答案示例：

#include <stdio.h>
#include <stdlib.h>

typedef int element;

typedef struct qnode *ptrq;
struct qnode
{
    element *data;
    int front, rear;
    int Maxsize;
};
typedef ptrq queue;

queue creatQ(int max);
int add(queue q, element x);
element deleteq(queue q);
int isfull(queue q);
int isempty(queue q);

int main() {
    int max = 10;
    queue q = creatQ(max);
    int i,s,m,l=0,x;
    scanf("%d",&m);
    for (i = 0; i < m; i++)
    {
        scanf("%d",&s);
        if(s != 0)
        {
            x = add(q, s);
            if(!x)
            printf("FULL ");
            else
            l++;
        }
        else
        {
            int x = deleteq(q);
            if(x != 0)
            {
                printf("%d ",x);
                l--;
            }
            else
            printf("EMPTY ");
        }
    }
    printf("\n");
    for(i=0;i<l;i++)
    printf("%d ",deleteq(q));
    return 0;
}

queue creatQ(int max)
{
    queue q = (queue)malloc(sizeof(struct qnode));
    q->data = (element*)malloc(sizeof(element) * max);
    q->front = 0;
    q->rear = 0;
    q->Maxsize = max;
    return q;
}

int add(queue q, element x)
{
    if (isfull(q))
    return 0;
    q->rear = (q->rear + 1) % q->Maxsize;
    q->data[q->rear] = x;
    return 1;
}

element deleteq(queue q)
{
    if (isempty(q))
    return 0;
    q->front = (q->front + 1) % q->Maxsize;
    return q->data[q->front];
}

int isfull(queue q)
{
    if ((q->rear + 1) % q->Maxsize == q->front)
    return 1;
    return 0;
}

int isempty(queue q)
{
    if (q->rear == q->front)
    return 1;
    return 0;
}

---

四、堆栈与队列的联合运用

堆栈与队列的联合运用

作者 幻梦

单位 无

题目：

给定一个递增数列，利用堆栈和队列，分别将其中的奇数按降序输出，其中的偶数按增序输出。

输入格式：

输入第1行为1个正整数n，表示数列长度；

第2行为给出的长度为n个整数的递增数列。

输出格式：

第1行按降序输出数列中的所有奇数；

第2行按增序输出数列中的所有偶数；

输入样例:

11
2 3 4 5 7 8 12 13 14 17 18

输出样例:

17 13 7 5 3 
2 4 8 12 14 18 

答案示例：

#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct snode *ptrs;
struct snode
{
    element *data;
    int top;
    int maxsize;
};
typedef ptrs stack;
stack creatS(int max); 
void push(stack s,element x);
element pop(stack s);
int sisempty(stack s);

typedef struct qnode *ptrq;
struct qnode
{
    element *data;
    int front,rear;
    int Maxsize;
};
typedef ptrq queue;
queue creatQ(int max);
void add(queue q,element x);
element deleteq(queue q);
int qisfull(queue q);

int main()
{
    int max=1000,n;
    queue q=creatQ(max);
    stack s=creatS(max);
    scanf("%d",&n);

    int m,i,scnt=0,qcnt=0;
    for(i=0;i<n;i++)
    {
        scanf("%d",&m);
        if(m%2==1)
        {
            push(s,m);
            scnt++;
        }
        else
        {
            add(q,m);
            qcnt++;
        }
    }
    for(i=0;i<scnt;i++)
    printf("%d ",pop(s));

    printf("\n");
    for(i=0;i<qcnt;i++)
    printf("%d ",deleteq(q));
    return 0;
}

stack creatS(int max)
{
    stack s=(stack)malloc(sizeof(struct snode));
    s->data=(element*)malloc(sizeof(element)*max);
    s->top=-1;
    s->maxsize=max;
    return s;
}
void push(stack s,element x)
{
    s->data[++(s->top)]=x;
}
element pop(stack s)
{
    return s->data[(s->top)--];
}
int isempty(stack s)
{
    if(s->top==-1)
    return 1;
    return 0;
}

queue creatQ(int max)
{
    queue q=(queue)malloc(sizeof(struct qnode));
    q->data=(element*)malloc(sizeof(element)*max);
    q->front=0;
    q->rear=0;
    q->Maxsize=max;
    return q;
}
void add(queue q,element x)
{
    q->rear=(q->rear+1)%q->Maxsize;
    q->data[q->rear]=x;
}
element deleteq(queue q)
{
    q->front=(q->front+1)%q->Maxsize;
    return q->data[q->front];
}
int qisfull(queue q)
{
    if((q->rear+1)%q->Maxsize==q->front)
    return 1;
    return 0;
}

---

五、二叉树

二叉树

（一）普通二叉树的创建

5.1普通二叉树的创建

1、结构定义：

5.1.1结构定义

typedef struct tnode *ptrt;
typedef ptrt bintree;
struct tnode {
    element data;
    bintree ltree;
    bintree rtree;
};

2、三种创建方法

三种创建方法

（1）先序遍历+数组创建

先序遍历+数组创建

①函数定义：

void creatT(bintree &T)
{
    int a;
    scanf("%d",&a);
    if(a==0)
    {
        T=NULL;
        return;
    }
    bintree t=(bintree)malloc(sizeof(struct tnode));
    t->data=a;
    T=t;
    creatT(T->ltree);
    creatT(T->rtree);
}

②示例代码（输出所有节点）：

输入样例：

1 3 5 0 0 8 0 0 2 0 0

输出样例：

1 3 5 8 2

代码：

// 先序遍历创建树 
#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct tnode *ptrt;
typedef ptrt bintree;
struct tnode
{
    element data;
    bintree rtree;
    bintree ltree;
};
void creatT(bintree &T);
void precheck(bintree T);

int main() {
    bintree t;
    creatT(t);
    precheck(t);
    return 0;
}

void creatT(bintree &T)
{
    int a;
    scanf("%d",&a);
    if(a==0)
    {
        T=NULL;
        return;
    }
    bintree t=(bintree)malloc(sizeof(struct tnode));
    t->data=a;
    T=t;
    creatT(T->ltree);
    creatT(T->rtree);
}
void precheck(bintree T)
{
    if(T)
    {
        printf("%d ",T->data);
        precheck(T->ltree);
        precheck(T->rtree);       
    }

}

（2）先序遍历+中序遍历

先序遍历+中序遍历

①函数定义：

// 创建二叉树函数，参数为前序遍历数组、中序遍历数组和数组大小
bintree creatT(char pre[], char in[], int size)
{
    if (size == 0)  // 如果大小为0，返回空指针
    return NULL;
    // 分配新节点的内存
    bintree t = (bintree)malloc(sizeof(struct tnode));
    // 将先序遍历的第一个元素赋值给新节点的数据域
    t->data = pre[0];

    char *p;  // 用于遍历中序数组的指针
    int k = 0;  // 用于计算左子树的节点数
    for (p = in; p < in + size; p++)  // 遍历中序数组
    {
        if (*p == pre[0])  // 找到根节点在中序数组中的位置
        break;
        k++;  // 计算左子树的节点数
    }
    // 递归创建左子树
    t->ltree = creatT(pre + 1, in, k);
    // 递归创建右子树
    t->rtree = creatT(pre + k + 1, in + k + 1, size - k - 1);
    return t;  // 返回创建的树节点
}

②示例代码（输出其后序遍历）：

输入样例：

9
ABDFGHIEC
FDHGIBEAC

输出样例：

FHIGDEBCA

代码

#include <stdio.h>
#include <stdlib.h>
typedef char element;
typedef struct tnode *ptrt;
typedef ptrt bintree;
struct tnode {
    element data;   // 数据域
    bintree ltree;  // 左子树指针
    bintree rtree;  // 右子树指针
};

// 创建二叉树函数，参数为前序遍历数组、中序遍历数组和数组大小
bintree creatT(char pre[], char in[], int size)
{
    if (size == 0)  // 如果大小为0，返回空指针
    return NULL;
    // 分配新节点的内存
    bintree t = (bintree)malloc(sizeof(struct tnode));
    // 将先序遍历的一个元素赋值给新节点的数据域
    t->data = pre[0];

    char *p;  // 用于遍历中序数组的指针
    int k = 0;  // 用于计算左子树的节点数
    for (p = in; p < in + size; p++)  // 遍历中序数组
    {
        if (*p == pre[0])  // 找到根节点在中序数组中的位置
        break;
        k++;  // 计算左子树的节点数
    }
    // 递归创建左子树
    t->ltree = creatT(pre + 1, in, k);
    // 递归创建右子树
    t->rtree = creatT(pre + k + 1, in + k + 1, size - k - 1);
    return t;  // 返回创建的树节点
}
// 显示二叉树的后序遍历
void show(bintree t)
{
    if (t)
    {
        show(t->ltree);   // 递归遍历左子树
        show(t->rtree);   // 递归遍历右子树
        printf("%c", t->data);  // 输出当前节点的数据
    }
}

int main() {
    char pre[1000], in[1000];  // 定义先序和中序遍历数组
    int m, i;  // 定义节点数和循环变量
    scanf("%d", &m);  // 读取节点数
    getchar();  // 消耗换行符
    for (i = 0; i < m; i++)
    scanf("%c", &pre[i]);  // 读取先序遍历数组
    getchar();  // 消耗换行符
    for (i = 0; i < m; i++)
    scanf("%c", &in[i]);  // 读取中序遍历数组
    // 创建二叉树
    bintree t = creatT(pre, in, m);
    // 显示二叉树的后序遍历
    show(t);
    return 0;
}

（3）层序遍历

层序遍历

①函数定义：

创建节点（bintree creatT(element x) ）：

// 创建二叉树节点
bintree creatT(element x)
{
    bintree tnode = (bintree)malloc(sizeof(struct tnode)); // 分配内存并创建新节点
    tnode->data = x; // 设置节点数据
    tnode->ltree = NULL; // 初始化左子树为空
    tnode->rtree = NULL; // 初始化右子树为空
    return tnode; // 返回新创建的节点
}

创建二叉树（bintree buildTree(element arr[], int size)）：

// 根据层序遍历序列构建完全二叉树
bintree buildTree(element arr[], int size)
{
    int i;
    if (size == 0) return NULL; // 如果序列为空，返回 NULL
    bintree *tnode = (bintree*)malloc(size * sizeof(bintree)); // 分配指针数组空间

    for (i = 0; i < size; i++)
        tnode[i] = creatT(arr[i]); // 为序列中的每个元素创建节点
    int j = 1;
    for (i = 0; i < size && j < size; i++) {
        if (tnode[i] != NULL) // 如果当前节点不为空
        {
            if (j < size) tnode[i]->ltree = tnode[j++]; // 设置左子树
            if (j < size) tnode[i]->rtree = tnode[j++]; // 设置右子树
        }
    }
    bintree root = tnode[0]; // 根节点为第一个元素
    free(tnode);
    return root; // 返回根节点
}

②示例代码

输入样例：

8
91 71 2 34 10 15 55 18

输出样例：

91 71 34 18 10 2 15 55

代码

#include <stdio.h>
#include <stdlib.h>
#define max 1000
typedef int element;
typedef struct tnode *ptrt; // 定义指向 tnode 结构的指针类型 ptrt
typedef ptrt bintree; // 定义 bintree 类型为指向 tnode 结构的指针
struct tnode { 
    element data; // 节点数据
    bintree ltree; // 指向左子树的指针
    bintree rtree; // 指向右子树的指针
};

// 创建二叉树节点
bintree creatT(element x)
{
    bintree tnode = (bintree)malloc(sizeof(struct tnode)); // 分配内存并创建新节点
    tnode->data = x; // 设置节点数据
    tnode->ltree = NULL; // 初始化左子树为空
    tnode->rtree = NULL; // 初始化右子树为空
    return tnode; // 返回新创建的节点
}

// 根据层序遍历序列构建完全二叉树
bintree buildTree(element arr[], int size)
{
    int i;
    if (size == 0) return NULL; // 如果序列为空，返回 NULL
    bintree *tnode = (bintree*)malloc(size * sizeof(bintree)); // 分配指针数组空间

    for (i = 0; i < size; i++)
        tnode[i] = creatT(arr[i]); // 为序列中的每个元素创建节点
    int j = 1;
    for (i = 0; i < size && j < size; i++) {
        if (tnode[i] != NULL) // 如果当前节点不为空
        {
            if (j < size) tnode[i]->ltree = tnode[j++]; // 设置左子树
            if (j < size) tnode[i]->rtree = tnode[j++]; // 设置右子树
        }
    }
    bintree root = tnode[0]; // 根节点为第一个元素
    free(tnode);
    return root; // 返回根节点
}

// 先序遍历二叉树并输出结果
void precheck(bintree root)
{
    if (root)
    {
        printf("%d ", root->data); // 输出当前节点数据
        precheck(root->ltree); // 递归遍历左子树
        precheck(root->rtree); // 递归遍历右子树
    }
}

int main() {
    int n;
    scanf("%d", &n); // 输入元素个数
    int i;
    element arr[max]; // 定义存储元素的数组
    for (i = 0; i < n; i++)
        scanf("%d", &arr[i]);
    bintree root = buildTree(arr, n); // 构建二叉树
    precheck(root); // 先序遍历并输出结果
    return 0;
}oot = buildTree(arr, n);
    precheck(root);
    return 0;
}

（二）平衡二叉树

平衡二叉树

（1）基础操作集：

基础操作集

①创建新节点（avlt newNode(int val)）：

avlt newNode(int val){
    avlt node = (avlt)malloc(sizeof(Node));
    node->val = val;
    node->height = 1;
    node->left = NULL;
    node->right = NULL;
    return node;
}

②获取树的高度（int getHeight(avlt node)）：

int getHeight(avlt node) {
    if (node == NULL)
        return 0;
    return node->height;
}

③辅助函数（int max(int a, int b)）：

int max(int a, int b) {
    return (a > b)?a:b;
}

④获取平衡因子（int getBalance(avlt node)）：

int getBalance(avlt node) {
    return getHeight(node->left) - getHeight(node->right);
}

⑤先序遍历（void preOrder(avlt root)）：

void preOrder(avlt root){
    if (root == NULL)
        return;
    printf("%d ", root->val);
    preOrder(root->left);
    preOrder(root->right);
}

⑥中序遍历（void midOrder(avlt root)）：

void midOrder(avlt root) {
    if (root == NULL)
        return ;
    midOrder(root->left);
    printf("%d ", root->val);
    midOrder(root->right);
}

⑦查找（avlt find(avlt root, int key, int* counter)）：

avlt find(avlt root, int key, int* counter){
    avlt cur = root;
    while(cur != NULL){
        if (key < cur->val){
            cur = cur->left;
            (*counter)++;
        }
        else if (key > cur->val) {
            cur = cur->right;
            (*counter)++;
        }else
            return cur;
    }
    // 找了一圈，没找到
    return NULL;
}

⑧左旋函数（void preOrder(avlt root)）：

avlt leftRoate(avlt root){
    // 1.当前结点的右子树会作为新树的根结点
    // 2.当前结点root会作为新树的根结点newroot->left的左子树
    //如果，新的树根，原来有左子树，原来的左子树，就作为旧根结点的右子树
    avlt newroot = root->right;
    // T2保存新树根原来的左子树
    avlt T2 = newroot->left;
    // 当前结点会作为新树根的左子树
    newroot->left = root;
    root->right = T2;
    // 更新树高，root newroot
    root->height = 1 + max(getHeight(root->left), getHeight(root->right));
    newroot->height = 1 + max(getHeight(newroot->left), getHeight(newroot->right));

    return newroot;
}

⑨右旋函数（void preOrder(avlt root)）：

avlt rightRotate(avlt root){
    avlt newroot = root->left;
    avlt T2 = newroot->right;
    newroot->right = root;
    root->left = T2;
    //更新树高
    root->height = 1 + max(getHeight(root->left), getHeight(root->right));
    newroot->height = 1 + max(getHeight(newroot->left), getHeight(newroot->right));
    return newroot;
}

⑩插入结点（avlt insertNode(avlt node, int key)）：

avlt insertNode(avlt node, int key){
    if (node == NULL)
        return newNode(key);
    if (key < node->val)
        node->left = insertNode(node->left, key);
    else if (key > node->val)
        node->right = insertNode(node->right, key);
    else
        return node;
    //更新树高
    node->height = 1 + max(getHeight(node->left), getHeight(node->right));
    // 获取当前结点的平衡因子
    int balance = getBalance(node);
    // 我们是否需要调整这个树，是看平衡因子是不是绝对值大于1
    // LL型失衡
    if (balance > 1 && getBalance(node->left) > 0)
        return rightRotate(node);
    // LR型失衡
    if (balance > 1 && getBalance(node->left) < 0) {
        node->left = leftRoate(node->left);
        return rightRotate(node);
    }
    // RR型失衡
    if (balance < -1 && getBalance(node->right) < 0)
        return leftRoate(node);
    // RL型失衡
    if (balance < -1 && getBalance(node->right) > 0){
        node->right = rightRotate(node->right);
        return leftRoate(node);
    }
    return node;
}

⑪删除结点（avlt deleteNode(avlt node,int key)）：

avlt deleteNode(avlt node,int key)
{
    if(node==NULL)
        return node;
    if(key<node->val)
    {
        node->left=deleteNode(node->left,key);
    }
    else if(key>node->val)
    {
        node->right=deleteNode(node->right,key);
    }
    else if(key==node->val)
    {
        //删除的是叶节点 
        if(node->left==NULL&&node->right==NULL)
        {
            avlt temp=node;
            node=NULL;
            free(temp);
        }
        //删除的是只有右孩子的节点 
        else if(node->left==NULL&&node->right!=NULL)
        {
            avlt temp=node;
            node=node->right;
            free(temp);
        }
        //删除的是只有左孩子的节点 
        else if(node->left!=NULL&&node->right==NULL)
        {
            avlt temp=node;
            node=node->left;
            free(temp);
        }
        //删除的是有左右孩子的节点 
        else if(node->left!=NULL&&node->right!=NULL)
        {
            avlt cur=node->right;
            while(cur->left!=NULL)
            {
                cur=cur->left;
            }
            node->val=cur->val;
            node->right=deleteNode(node->right,cur->val);
        }
    }
    if(node==NULL)
        return node;
    //更新树高
    node->height = 1 + max(getHeight(node->left), getHeight(node->right));
    // 获取当前结点的平衡因子
    int balance = getBalance(node);
    // 我们是否需要调整这个树，是看平衡因子是不是绝对值大于1
    // LL型失衡
    if (balance > 1 && getBalance(node->left) >= 0)
        return rightRotate(node);
    // LR型失衡
    if (balance > 1 && getBalance(node->left) < 0) {
        node->left = leftRoate(node->left);
        return rightRotate(node);
    }
    // RR型失衡
    if (balance < -1 && getBalance(node->right) <= 0)
        return leftRoate(node);
    // RL型失衡
    if (balance < -1 && getBalance(node->right) > 0){
        node->right = rightRotate(node->right);
        return leftRoate(node);
    }
    return node;
}

（2）完整代码示例：

完整代码示例

代码：

#include <stdio.h>
#include <stdlib.h>
// 定义树结构
typedef struct Node* ptravlt;
typedef ptravlt avlt;
struct Node{
    int val;// 数据域
    int height;// 树高
    avlt left;
    avlt right;
}Node;
avlt newNode(int val);//定义函数生成新的结点，返回值是指向这个结点的指针
int getHeight(avlt node);// 获取树的高度
int max(int a, int b);
int getBalance(avlt node);// 获取平衡因子
void preOrder(avlt root);// 先序遍历
void midOrder(avlt root);// 中序遍历
avlt find(avlt root, int key, int* counter);// 查找
avlt leftRoate(avlt root);//左旋函数
avlt rightRotate(avlt root);//右旋函数
avlt insertNode(avlt node, int key);// 插入结点
avlt deleteNode(avlt node,int key);// 删除结点
int main(){
    avlt root = NULL;
    int a[7]={10,20,30,40,50,60,70};
    int i;
    for(i=0;i<7;i++)
        root = insertNode(root, a[i]);
    int counter = 0;
    avlt result = find(root, 70, &counter);
    printf("找了几次:%d\n", counter);
    printf("查找到的地址:%d 该地址的值:%d \n", result, result->val);
    printf("-------先序遍历结果--------\n");
    preOrder(root);
    printf("\n-------中序遍历结果--------\n");
    midOrder(root);
    printf("\n");
    counter = 0;
    root = deleteNode(root, 10);
    root = deleteNode(root, 20);
    root = deleteNode(root, 30);
    result = find(root, 40, &counter);
    printf("找了几次:%d\n", counter);
    printf("查找到的地址:%d 该地址的值:%d \n", result, result->val);
    printf("-------先序遍历结果--------\n");
    preOrder(root);
    printf("\n-------中序遍历结果--------\n");
    midOrder(root);
    printf("\n");

    return 0;
}
//定义函数生成新的结点，返回值是指向这个结点的指针
avlt newNode(int val){
    avlt node = (avlt)malloc(sizeof(Node));
    node->val = val;
    node->height = 1;
    node->left = NULL;
    node->right = NULL;
    return node;
}
// 获取树的高度
int getHeight(avlt node) {
    if (node == NULL)
        return 0;
    return node->height;
}
int max(int a, int b) {
    return (a > b)?a:b;
}
// 获取平衡因子
int getBalance(avlt node) {
    return getHeight(node->left) - getHeight(node->right);
}
// 先序遍历
void preOrder(avlt root){
    if (root == NULL)
        return;
    printf("%d ", root->val);
    preOrder(root->left);
    preOrder(root->right);
}
// 定义中序遍历
void midOrder(avlt root) {
    if (root == NULL)
        return ;
    midOrder(root->left);
    printf("%d ", root->val);
    midOrder(root->right);
}
// 定义函数查找
avlt find(avlt root, int key, int* counter){
    avlt cur = root;
    while(cur != NULL){
        if (key < cur->val){
            cur = cur->left;
            (*counter)++;
        }
        else if (key > cur->val) {
            cur = cur->right;
            (*counter)++;
        }else
            return cur;
    }
    // 找了一圈，没找到
    return NULL;
}
//定义左旋函数
avlt leftRoate(avlt root){
    // 1.当前结点的右子树会作为新树的根结点
    // 2.当前结点root会作为新树的根结点newroot->left的左子树
    //如果，新的树根，原来有左子树，原来的左子树，就作为旧根结点的右子树
    avlt newroot = root->right;
    // T2保存新树根原来的左子树
    avlt T2 = newroot->left;
    // 当前结点会作为新树根的左子树
    newroot->left = root;
    root->right = T2;
    // 更新树高，root newroot
    root->height = 1 + max(getHeight(root->left), getHeight(root->right));
    newroot->height = 1 + max(getHeight(newroot->left), getHeight(newroot->right));

    return newroot;
}
//定义右旋函数
avlt rightRotate(avlt root){
    avlt newroot = root->left;
    avlt T2 = newroot->right;
    newroot->right = root;
    root->left = T2;
    //更新树高
    root->height = 1 + max(getHeight(root->left), getHeight(root->right));
    newroot->height = 1 + max(getHeight(newroot->left), getHeight(newroot->right));
    return newroot;
}
// 定义插入结点的函数
avlt insertNode(avlt node, int key){
    if (node == NULL)
        return newNode(key);
    if (key < node->val)
        node->left = insertNode(node->left, key);
    else if (key > node->val)
        node->right = insertNode(node->right, key);
    else
        return node;
    //更新树高
    node->height = 1 + max(getHeight(node->left), getHeight(node->right));
    // 获取当前结点的平衡因子
    int balance = getBalance(node);
    // 我们是否需要调整这个树，是看平衡因子是不是绝对值大于1
    // LL型失衡
    if (balance > 1 && getBalance(node->left) > 0)
        return rightRotate(node);
    // LR型失衡
    if (balance > 1 && getBalance(node->left) < 0) {
        node->left = leftRoate(node->left);
        return rightRotate(node);
    }
    // RR型失衡
    if (balance < -1 && getBalance(node->right) < 0)
        return leftRoate(node);
    // RL型失衡
    if (balance < -1 && getBalance(node->right) > 0){
        node->right = rightRotate(node->right);
        return leftRoate(node);
    }
    return node;
}
avlt deleteNode(avlt node,int key)
{
    if(node==NULL)
        return node;
    if(key<node->val)
    {
        node->left=deleteNode(node->left,key);
    }
    else if(key>node->val)
    {
        node->right=deleteNode(node->right,key);
    }
    else if(key==node->val)
    {
        //删除的是叶节点 
        if(node->left==NULL&&node->right==NULL)
        {
            avlt temp=node;
            node=NULL;
            free(temp);
        }
        //删除的是只有右孩子的节点 
        else if(node->left==NULL&&node->right!=NULL)
        {
            avlt temp=node;
            node=node->right;
            free(temp);
        }
        //删除的是只有左孩子的节点 
        else if(node->left!=NULL&&node->right==NULL)
        {
            avlt temp=node;
            node=node->left;
            free(temp);
        }
        //删除的是有左右孩子的节点 
        else if(node->left!=NULL&&node->right!=NULL)
        {
            avlt cur=node->right;
            while(cur->left!=NULL)
            {
                cur=cur->left;
            }
            node->val=cur->val;
            node->right=deleteNode(node->right,cur->val);
        }
    }
    if(node==NULL)
        return node;
    //更新树高
    node->height = 1 + max(getHeight(node->left), getHeight(node->right));
    // 获取当前结点的平衡因子
    int balance = getBalance(node);
    // 我们是否需要调整这个树，是看平衡因子是不是绝对值大于1
    // LL型失衡
    if (balance > 1 && getBalance(node->left) >= 0)
        return rightRotate(node);
    // LR型失衡
    if (balance > 1 && getBalance(node->left) < 0) {
        node->left = leftRoate(node->left);
        return rightRotate(node);
    }
    // RR型失衡
    if (balance < -1 && getBalance(node->right) <= 0)
        return leftRoate(node);
    // RL型失衡
    if (balance < -1 && getBalance(node->right) > 0){
        node->right = rightRotate(node->right);
        return leftRoate(node);
    }
    return node;
}

（三）哈夫曼树

哈夫曼树

（1）基础操作集：

基础操作集

①查找最小的权重（void select(htree ht,int x,int m1,int m2)）：

// 选择赫夫曼树中权重最小的两个节点
void select(htree ht, int x, int *m1, int *m2)
{
    double min1 = 99999999;  // 初始最小权重1
    double min2 = 99999999;  // 初始最小权重2

    int j;
    for(j = 1; j <= x; j++)
    {
        if(ht[j].weight < min1 && ht[j].parent == 0)
        {
            min1 = ht[j].weight;
            *m1 = j;
        }
    }

    int k;
    for(k = 1; k <= x; k++) 
    {
        if(ht[k].weight < min2 && k != *m1 && ht[k].parent == 0)
        {
            min2 = ht[k].weight;
            *m2 = k;
        }
    }
}

②创建哈夫曼树（void creath(htree ht,int n)）：

// 创建赫夫曼树
void creath(htree ht, int n)
{
    int i;
    for(i = n+1; i <= 2*n-1; i++)
    {
        int m1, m2;
        select(ht, i-1, &m1, &m2);  // 选择最小的两个节点
        ht[i].weight = ht[m1].weight + ht[m2].weight;  // 新节点权重为两个最小节点权重之和
        ht[i].lchild = m1;  // 左孩子为第一个最小节点
        ht[i].rchild = m2;  // 右孩子为第二个最小节点
        ht[m1].parent = i;  // 更新父节点
        ht[m2].parent = i;  // 更新父节点
    }
}

③编码（void hcode(htree ht,char hc,int n)）：**

// 生成赫夫曼编码
void hcode(htree ht, char **hc, int n)
{
    char *cd = (char*)malloc(n * sizeof(char));  // 动态分配存储编码的数组
    cd[n-1] = '\0';  // 编码字符串的末尾
    int now = 1;
    int p = 0;
    int start;
    int i = 0;
    while (i < n)
    {
        start = n-1;  // 编码字符数组的末尾
        now = i + 1;  // 当前节点
        p = ht[now].parent;  // 获取当前节点的父节点

        // 生成每个字符的赫夫曼编码
        while (p != 0)
        {
            start--;
            if (ht[p].lchild == now)
            {
                cd[start] = '0';  // 左孩子编码为'0'
            }
            else
            {
                cd[start] = '1';  // 右孩子编码为'1'
            }
            now = p;
            p = ht[now].parent;
        }

        // 为每个字符分配空间存储其赫夫曼编码
        hc[i+1] = (char*)malloc((n-start) * sizeof(char));
        strcpy(hc[i+1], &cd[start]);  // 拷贝编码到赫夫曼编码数组
        i++;
    }
    free(cd);  // 释放动态分配的编码数组
}

④先序打印（void printh(htree ht,char hc,int index)）：**

// 打印赫夫曼树
void printh(htree ht, char **hc, int index)
{
    if (index >= 1) 
    {
        if (ht[index].lchild == 0 && ht[index].rchild == 0)
        {
            // 打印叶子节点的字符和对应的赫夫曼编码
            printf("%c:%s\n", ht[index].s, hc[index]);
            return;
        }
        printh(ht, hc, ht[index].lchild);  // 递归打印左子树
        printh(ht, hc, ht[index].rchild);  // 递归打印右子树
    }
}

⑤破译编码内容（void search(htree ht,int n,char *pwd)）：

// 解析输入的赫夫曼编码并打印出对应的字符
void search(htree ht, int n, char *pwd) 
{
    printf("译码为:");  // 输出译码提示
    int len = strlen(pwd);  // 获取输入编码的长度
    int i = 0;
    int node = 2 * n - 1;  // 从根节点开始解析

    while (i < len)
    {
        if (pwd[i] == '0')
        {
            node = ht[node].lchild;  // 走向左孩子
            i++;
            if (ht[node].lchild == 0 && ht[node].rchild == 0)
            {
                // 若到达叶子节点，打印对应字符并回到根节点继续解析
                printf("%c", ht[node].s);
                node = 2 * n - 1;
            }
        }
        else if (pwd[i] == '1')
        {
            node = ht[node].rchild;  // 走向右孩子
            i++;
            if (ht[node].lchild == 0 && ht[node].rchild == 0)
            {
                // 若到达叶子节点，打印对应字符并回到根节点继续解析
                printf("%c", ht[node].s);
                node = 2 * n - 1;
            }
        }
    }
}

（2）完整代码示例：

完整代码示例

输入样例：

5
c:4
x:7
z:1
s:2
a:8
011110110001101

输出样例：

a:0
x:10
z:1100
s:1101
c:111
译码为:acxzas

代码：

#include <stdio.h>
#include <stdlib.h>

#define N 30        // 定义N为30
#define Max 2*N-1   // 定义Max为2*N-1

// 定义赫夫曼树节点结构体
typedef struct {
    double weight;        // 节点权重
    char s;               // 节点字符
    int parent, lchild, rchild;  // 父节点，左孩子，右孩子
} Htnode, htree[Max+1];  // 定义Htode类型和赫夫曼树类型

void select(htree ht, int x, int *m1, int *m2);  // 选择权重最小的两个节点
void creath(htree ht, int n);                    // 创建赫夫曼树
void hcode(htree ht, char **hc, int n);          // 生成赫夫曼编码
void printh(htree ht, char **hc, int index);     // 打印赫夫曼树

int main() {
    htree ht;                // 赫夫曼树数组
    int n;                   // 字符数量
    scanf("%d", &n);         // 输入字符数量
    getchar();               // 吃掉换行符
    char *hc[n+1];           // 用于存储赫夫曼编码的数组
    int i;                   // 循环变量

    // 输入字符及其权重
    for(i = 1; i <= n; i++)
    {
        scanf("%c:%lf", &ht[i].s, &ht[i].weight);
        getchar();           // 吃掉换行符
        ht[i].lchild = 0;    // 初始化左孩子
        ht[i].rchild = 0;    // 初始化右孩子
        ht[i].parent = 0;    // 初始化父节点
    }

    char pwd[99999];          // 存储输入编码的数组
    creath(ht, n);            // 创建赫夫曼树
    hcode(ht, hc, n);         // 生成赫夫曼编码
    printh(ht, hc, 2*n-1);    // 打印赫夫曼树

    printf("请输入需要破译的编码:");
    scanf("%s", pwd);         // 输入编码
    search(ht, n, pwd);       // 解析输入的编码
    return 0;
}

// 选择赫夫曼树中权重最小的两个节点
void select(htree ht, int x, int *m1, int *m2)
{
    double min1 = 99999999;  // 初始最小权重1
    double min2 = 99999999;  // 初始最小权重2

    int j;
    for(j = 1; j <= x; j++)
    {
        if(ht[j].weight < min1 && ht[j].parent == 0)
        {
            min1 = ht[j].weight;
            *m1 = j;
        }
    }

    int k;
    for(k = 1; k <= x; k++) 
    {
        if(ht[k].weight < min2 && k != *m1 && ht[k].parent == 0)
        {
            min2 = ht[k].weight;
            *m2 = k;
        }
    }
}

// 创建赫夫曼树
void creath(htree ht, int n)
{
    int i;
    for(i = n+1; i <= 2*n-1; i++)
    {
        int m1, m2;
        select(ht, i-1, &m1, &m2);  // 选择最小的两个节点
        ht[i].weight = ht[m1].weight + ht[m2].weight;  // 新节点权重为两个最小节点权重之和
        ht[i].lchild = m1;  // 左孩子为第一个最小节点
        ht[i].rchild = m2;  // 右孩子为第二个最小节点
        ht[m1].parent = i;  // 更新父节点
        ht[m2].parent = i;  // 更新父节点
    }
}

// 生成赫夫曼编码
void hcode(htree ht, char **hc, int n)
{
    char *cd = (char*)malloc(n * sizeof(char));  // 动态分配存储编码的数组
    cd[n-1] = '\0';  // 编码字符串的末尾
    int now = 1;
    int p = 0;
    int start;
    int i = 0;
    while (i < n)
    {
        start = n-1;  // 编码字符数组的末尾
        now = i + 1;  // 当前节点
        p = ht[now].parent;  // 获取当前节点的父节点

        // 生成每个字符的赫夫曼编码
        while (p != 0)
        {
            start--;
            if (ht[p].lchild == now)
            {
                cd[start] = '0';  // 左孩子编码为'0'
            }
            else
            {
                cd[start] = '1';  // 右孩子编码为'1'
            }
            now = p;
            p = ht[now].parent;
        }

        // 为每个字符分配空间存储其赫夫曼编码
        hc[i+1] = (char*)malloc((n-start) * sizeof(char));
        strcpy(hc[i+1], &cd[start]);  // 拷贝编码到赫夫曼编码数组
        i++;
    }
    free(cd);  // 释放动态分配的编码数组
}

// 打印赫夫曼树
void printh(htree ht, char **hc, int index)
{
    if (index >= 1) 
{
        if (ht[index].lchild == 0 && ht[index].rchild == 0)
        {
            // 打印叶子节点的字符和对应的赫夫曼编码
            printf("%c:%s\n", ht[index].s, hc[index]);
            return;
        }
        printh(ht, hc, ht[index].lchild);  // 递归打印左子树
        printh(ht, hc, ht[index].rchild);  // 递归打印右子树
    }
}

// 解析输入的赫夫曼编码并打印出对应的字符
void search(htree ht, int n, char *pwd) 
{
    printf("译码为:");  // 输出译码提示
    int len = strlen(pwd);  // 获取输入编码的长度
    int i = 0;
    int node = 2 * n - 1;  // 从根节点开始解析

    while (i < len)
    {
        if (pwd[i] == '0')
        {
            node = ht[node].lchild;  // 走向左孩子
            i++;
            if (ht[node].lchild == 0 && ht[node].rchild == 0)
            {
                // 若到达叶子节点，打印对应字符并回到根节点继续解析
                printf("%c", ht[node].s);
                node = 2 * n - 1;
            }
        }
        else if (pwd[i] == '1')
        {
            node = ht[node].rchild;  // 走向右孩子
            i++;
            if (ht[node].lchild == 0 && ht[node].rchild == 0)
            {
                // 若到达叶子节点，打印对应字符并回到根节点继续解析
                printf("%c", ht[node].s);
                node = 2 * n - 1;
            }
        }
    }
}

---