数据结构
绪论
数据：所有能输入到计算机中并可以被计算机处理的信号。
数据元素：用于完整地描述一个对象，是数据的基本单位 。
数据项：组成数据元素的、有独立含义的、不可分割的最小单位 。
数据对象：性质相同的数据元素的集合，是数据的一个子集。
数据结构：相互之间存在一个或多种特定关系的数据元素的集合。
逻辑结构：从具体问题抽象出来的数学模型。
存储结构：逻辑结构在计算机中的存储表示。分顺序存储结构和链式存储结构。
抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。
时间复杂度
O(1) < O(logn) < O(n) < O(nlogn) < O(n*n) < O(n*n*n)
O(2的n次方) < O(n!) < O(n的n次方)
冒泡排序
最好时间复杂度：O(n) -> 一轮冒泡就排好
最坏时间复杂度：O(n*n)
线性表
顺序表的基本操作
顺序表的存储结构
#include <stdio.h> #include <stdlib.h> #define MAXSIZE 100 #define OVERFLOW -1 typedef struct { int *elem; // 存储空间的基地址 int length; // 当前长度 }SqList; // 顺序表的结构类型为SqList
初始化
// 初始化 int InitList(SqList *L) { L->elem = (int *)malloc(sizeof(int) * MAXSIZE); // 分配内存 if (!L->elem) { exit(OVERFLOW); } // 分配内存失败退出程序 L->length = 0; // 创建一个空顺序表 return 0; }
// 调用 int main() { int L; int result = InitList(&L); if (result==0) { printf("Init successfully!"); } else { printf("Init error!"); } return 0; }
取值（按位置查找值）
时间复杂度O(1)
// 取值 // 使用 int *value 而不是 int value 的原因是函数需要将找到的元素值返回给调用者。 // 使用指针可以实现这一点，而不需要通过函数的返回值来传递多个结果。 int GetElem(SqList *L, int i, int *e) { if (i < 1 || i > L->length) { return -1; // 判断i的合法性 } *e = L->elem[i-1]; // 第i-1个位置存储的第i个数据元素 return 0; }
// 主函数调用 int main() { // 顺序表赋值 L.elem[0] = 10; L.elem[1] = 20; L.length = 2; int value, result2 = 1; result2 = GetElem(&L, 1, &value); // 查找顺序表第一个元素 if (result2 == 0) { printf("索引1处的值为%d\n",value); } else { printf("索引超出范围"); } return 0; }
查找（按值查找位置）
O(n)
// 按值查找位置 int LocateElem(SqList *L, int e) { for(int i=0;i < L->length; i++) { if(L->elem[i] == e) { return i + 1; } } return 0; }
int main(){ L.elem = 20; L.length = 2; // 按值查找 int elem = 20; int pos = LocateElem(&L, elem); if ( pos != 0 ) { printf("%d在顺序表中的位置是%d", elem, pos); } else { printf("值未找到"); } return 0; }
插入
最好：O(1) 在最后一个位置插入
最坏：O(n) 在第一个位置插入
平均：O(n)
// 插入 int ListInsert(SqList *L, int i, int e) { if( i<1 || i>L->length+1 ) { // 位置不合法 printf("位置不合法！\n"); return -1; } if( L->length == MAXSIZE ) { // 存储空间已满 printf("存储空间已满！\n"); return -1; } for(int j = L->length-1; j >= i-1; j-- ) // 将i后的元素依次向后移动 { L->elem[j+1] = L->elem[j]; // 插入位置之后元素后移 } L->elem[i-1] = e; // 插入元素 ++L->length; return 0; }
// 调用 int main() { // 插入元素 int position = 3; int a = 6; L.length = 5; printf("原先的顺序表元素为:\n"); for(int j = 0; j < 5; j++) { L.elem[j] = j+1; printf("%d", L.elem[j]); } printf("\n插入后的顺序表元素为:\n"); int r = ListInsert(&L, position, a); if (r == 0) { printf("插入成功！\n"); for(int k = 0; k < 6; k++) { printf("%d",L.elem[k]); } } else { printf("插入失败！\n"); } return 0; }
删除
最好：O(1) 删除最后一个位置
最坏：O(n) 删除第一个位置
平均：O(n)
// 删除 void ListDelete(SqList *L, int i) { if( i < 1 || i > L->length) { printf("位置不合法!\n"); } for(int j = i; j <= L->length-1; j++) { L->elem[j-1] = L->elem[j]; // 前移 } --L->length; }
int main() { // 删除元素 int d = 3; ListDelete(&L, d); printf("删除后的顺序表内容为:\n"); for(int i = 0; i < L.length; i++) { printf("%d",L.elem[i]); } return 0; }
链表的基本操作
单链表
单链表操作完整代码
#include <stdio.h> #include <stdlib.h> typedef struct { int data; // 数据域 struct LNode *next; // 指针域，指向下一个节点 }LNode; typedef LNode* LinkList; // 定义链表类型 // 初始化 LinkList InitList() { LinkList L = (LinkList)malloc(sizeof(LNode)); // 生成头结点 if(L == NULL) { printf("链表初始化失败！\n"); exit(0); } L->next = NULL; // 头指针设置为空 printf("链表初始化成功！\n"); return L; } // 前插法创建单链表 void CreateList_H(LinkList *L, int n) { // 先创建一个空链表 *L = InitList(); for(int i = 0; i < n; ++i) { LNode *p = (LinkList)malloc(sizeof(LNode)); // 生成新结点 scanf("%d", &p->data); // 输入元素值赋给新结点的数据域 p->next = (*L)->next; // 将新结点*p插入到头结点之后 (*L)->next = p; } } // 尾插法创建单链表 void CreateList_R(LinkList *L ,int n) { *L = InitList(); LNode *r = *L; // 尾指针r指向头结点 for(int i = 0; i < n; ++i) { LNode *p = (LinkList)malloc(sizeof(LNode)); scanf("%d", &p->data); // 输入元素值赋给新结点的数据域 p->next = NULL; // 新结点的下个结点指向空，也就是新结点为尾结点 r->next = p; // 原来的尾结点的下一个结点指向新结点 r = p; // 尾指针指向新结点 } } // 取值 int GetElem(LinkList L, int i, int *e) { LinkList p = L->next; int j = 1; // 计数器 while(p && j < i) { p = p->next; ++j; } if(!p || j > i) { return -1; } *e = p->data; return 0; } // 查找 LinkList *LocateListElem(LinkList L, int e) { LinkList p = L->next; while(p && p->data != e) { p = p->next; } return p; } // 插入 int ListInsert(LinkList *L, int i, int e) {// 在带头结点的单链表L中第i个位置插入值为e的新结点 //LNode *p = *L; LinkList p = *L; int j = 0; while(p && (j < i-1)) { p = p->next; // 查找第i-1个结点，p指向该结点 ++j; // } if( !p || j > i - 1) { return -1; } //LNode *s = (LinkList)malloc(sizeof(LNode)); LinkList s = (LinkList)malloc(sizeof(LNode)); if (s == NULL) { return -1; // 内存分配失败 } s->data = e; s->next = p->next; p->next = s; return 0; } // 删除 int ListDelete(LinkList *L, int i) { LinkList p = *L; int j = 0; while( (p->next) && (j < i-1) ) { p = p->next; ++j; } // 当i>n或者i<1时，位置不合理 if( !(p->next) || (j > i-1) ) { return -1; } LNode *q = p->next; // 临时保存被删除结点的地址以备释放 p->next = q->next; // 改变删除结点前驱结点的指针，也就是让i-1个结点直接指向被删除结点（q）的下一个结点（q->next） free(q); return 0; } // 打印链表 void PrintList(LinkList L) { LNode *p = L->next; // 从首元结点 while(p != NULL) { printf("%d -> ", p->data); p = p->next; } printf("NULL\n"); } // 释放链表 void DestroyList(LinkList *L) { if(*L == NULL) { return; } LNode *p = (*L)->next; while(p != NULL){ LNode *temp = p; p = p->next; free(temp); } free(*L); // 释放头结点 *L = NULL; // 设置链表指针为NULL } int main() { LinkList list; int n; printf("请输入链表中元素的数量："); scanf("%d", &n); printf("创建链表，请输入%d个元素：\n",n); //CreateList_H(&list, n); CreateList_R(&list, n); printf("插入的元素为：\n"); PrintList(list); int m = 2; int e; if (GetElem(list, m, &e) == 0) { printf("第%d个位置的元素为：%d\n", m, e); } else { printf("获取元素失败\n"); } // 查找数据为m的位置 printf("数据为%d的地址是%p\n", m , LocateListElem(list, m)); // 插入 int pos = 3; int elem = 18; int result = ListInsert(&list, pos, elem); if(result == 0) { printf("插入成功！\n"); printf("在第%d位置插入了%d\n",pos, elem); PrintList(list); } else { printf("插入失败\n"); } // 删除 int r = ListDelete(&list, pos); if(result == 0) { printf("删除成功！\n"); printf("删除了第%d个位置\n",pos); PrintList(list); } else { printf("删除失败\n"); } DestroyList(&list); // 释放链表 }
链表包括两个域：
数据域：存储数据元素信息
指针域：存储直接后继存储位置
单链表的存储结构
#include <stdio.h> #include <stdlib.h> typedef struct { int data; // 数据域 struct LNode *next; // 指针域，指向下一个节点 }LNode; typedef LNode* LinkList; // 定义链表类型 LNode： 用于表示链表中的一个节点。 用于创建新的节点。 用于访问节点的成员（如 data 和 next）。 LinkList： 用于表示链表的头指针。 用于传递和返回链表的头指针。 用于遍历链表。 整个程序中LNode*等价于LinkList
单链表初始化
// 初始化 LinkList InitList() { LinkList L = (LinkList)malloc(sizeof(LNode)); // 生成头节点 if(L == NULL) { printf("链表初始化失败！\n"); exit(0); } L->next = NULL; // 头指针设置为空 printf("链表初始化成功！\n"); return L; }
// 调用 int main() { LinkList list = InitList(); free(list); return 0; }
取值（按位置查找值）
步骤：
指针p指向首元节点，用j做计数器初值赋值为1
从首元节点开始依次顺着链域向下访问，只要指向当前结点的指针p不为空，并且没有到达序号为i的结点，则做以下循环
退出循环时，如果p为空，或者计数器j大于i，说明指定的序号i值不合法（即i大于表长n或者i小于等于0），取值失败返回-1.
当j=i时，p所指向的结点就是要找的第i个结点，用e来保存当前的数据域。
// 取值 int GetElem(LinkList L, int i, int *e) { LinkList p = L->next; int j = 1; // 计数器 while(p && j < i) { p = p->next; ++j; } if(!p || j > i) { return -1; } *e = p->data; return 0; }
// 调用 int m = 2; int e; if (GetElem(list, m, &e) == 0) { printf("第%d个位置的元素为：%d\n", m, e); } else { printf("获取元素失败\n"); }
查找（按值查找结点地址）
步骤：
用p指向首元结点
从首元结点依次顺着链域next向下查找，只要当前结点指针p不为空，并且p所指向结点的数据域不等于e，则执行p指向下一个结点操作
返回p。若查找成功，p此时即为结点的地址值。否则p为NULL。
// 查找 LinkList *LocateListElem(LinkList L, int e) { LinkList p = L->next; while(p && p->data != e) { p = p->next; } return p; }
前插法创建单链表
步骤：
创建一个只有头结点的空链表，就是InitList()做的事情
根据带创建链表，循环n次，执行以下操作
生成新结点*p
输入元素赋值给*p的数据域
将新结点*p插入到头结点之后
// 前插法创建单链表 void CreateList_H(LinkList *L, int n) { // 先创建一个空链表 *L = InitList(); for(int i = 0; i < n; ++i) { // LNode *p = (LNode *)malloc(sizeof(LNode)); LNode *p = (LinkList)malloc(sizeof(LNode)); // 生成新结点 scanf("%d", &p->data); // 输入元素值赋给新结点的数据域 p->next = (*L)->next; // 将新结点*p插入到头结点之后 (*L)->next = p; } }
后插法创建单链表
步骤：
创建一个只有头结点的空链表，就是InitList()做的事情
尾指针r初始化，指向头结点
根据创建链表，循环n次以下操作
生成新结点*p
输入元素赋值给*p的数据域
将新结点*p插入到尾结点*r之后
尾指针r指向新的尾结点*p
// 尾插法创建单链表 void CreateList_R(LinkList *L ,int n) { *L = InitList(); LNode *r = *L; // 尾指针r指向头结点 for(int i = 0; i < n; ++i) { LNode *p = (LinkList)malloc(sizeof(LNode)); scanf("%d", &p->data); // 输入元素值赋给新结点的数据域 p->next = NULL; // 新结点的下个结点指向空，也就是新结点作为尾结点 r->next = p; // 原来的尾结点的下一个结点指向新结点 r = p; // 尾指针指向新结点 } }
插入
步骤：
找第i-1个位置的结点，然后指针p指向该结点
生成一个新结点*s
将*s的数据域置为e
*s的指针域指向第i个结点（s->next = p->next）
*p的指针域指向新结点*s（p->next = s）
// 插入 int ListInsert(LinkList *L, int i, int e) {// 在带头结点的单链表L中第i个位置插入值为e的新结点 //LNode *p = *L; LinkList p = *L; int j = 0; while(p && (j < i-1)) { p = p->next; // 查找第i-1个结点，p指向该结点 ++j; // } if( !p || j > i - 1 ) { return -1; } //LNode *s = (LNode *)malloc(sizeof(LNode)); LinkList s = (LinkList)malloc(sizeof(LNode)); if (s == NULL) { return -1; // 内存分配失败 } s->data = e; s->next = p->next; p->next = s; return 0; }
// 调用 int pos = 3; int elem = 18; int result = ListInsert(&list, pos, elem); if(result == 0) { printf("插入成功！\n"); printf("在第%d位置插入了%d\n",pos, elem); PrintList(list); } else { printf("插入失败\n"); }
删除
步骤：
找ai-1，指针p指向该结点
临时保存待删除结点ai的地址在q中，以备释放
将结点*p的指向ai的后继节点
释放ai的空间
// 删除 int ListDelete(LinkList *L, int i) { LinkList p = *L; int j = 0; while( (p->next) && (j < i-1) ) { p = p->next; ++j; } // 当i>n或者i<1时，位置不合理 if( !(p->next) || (j > i-1) ) { return -1; } LNode *q = p->next; // 临时保存被删除结点的地址以备释放 p->next = q->next; // 改变删除结点前驱结点的指针，也就是让i-1个结点直接指向被删除结点（q）的下一个结点（q->next） free(q); return 0; } // 为什么循环条件使用p->next而不是p？ 如果使用p作为循环条件，即while(p && j < i-1)，这可能会导致以下问题： 1.当i为1时：如果要删除第一个节点，即i=1，那么在第一次迭代之前，j已经等于0了，此时j < i-1就不成立了，循环不会执行，p仍然是头指针。这意味着我们无法进入循环去访问p->next，也就不能进行删除操作。 2.遍历至链表末尾：使用p->next作为条件可以保证我们在到达链表的最后一个元素时停止，因为最后一个元素的next是指向NULL的。如果我们只检查p，则会一直遍历到p为NULL为止，这样我们就无法访问p->next来进行删除操作。
// 删除 int r = ListDelete(&list, pos); if(result == 0) { printf("删除成功！\n"); printf("删除了第%d个位置\n",pos); PrintList(list); } else { printf("删除失败\n"); }
查看链表元素
// 打印链表 void PrintList(LinkList L) { LNode *p = L->next; // 从首元结点 while(p != NULL) { printf("%d -> ", p->data); p = p->next; } printf("NULL\n"); }
释放单链表
// 释放链表 void DestroyList(LinkList *L) { if(*L == NULL) { return; } LNode *p = (*L)->next; while(p != NULL){ LNode *temp = p; p = p->next; free(temp); } free(*L); // 释放头结点 *L = NULL; // 设置链表指针为NULL }
双向链表
双向链表初始化
双向链表结构体
#include <stdio.h> #include <stdlib.h> typedef struct DuLNode { int data; // 数据域 struct DuLNode *prior; // 直接前驱 struct DuLNode *next; // 直接后驱 }DuLNode; typedef DuLNode* DuList;
从后向前查看链表元素
先设置头结点，然后找尾结点
从前向后就不用找尾结点了
// 从后向前打印双向链表 void PrintList_E(DuList L) { DuList p = L->next; // 头结点 // 找最后一个结点 while (p->next != NULL) { p = p->next; } while(p != NULL) { printf("%d -> ", p->data); p = p->prior; } printf("NULL\n"); }
插入
// 插入 int ListInsert(DuList *L, int i, int e) { DuList p = LocateListElem(*L, i); if(!p) { return -1; } DuList s = (DuList)malloc(sizeof(DuLNode)); s->data = e; s->prior = p->prior; if (p->prior != NULL) { p->prior->next = s; } s->next = p; p->prior = s; return 0; }
// 调用，第三个位置插入19 int main() { DuList list; //InitDuList(); int n; printf("请输入双向链表中元素的数量："); scanf("%d", &n); CreateList_H(&list, n); PrintList(list); int pos = 3; int e = 19; // 插入 int result = ListInsert(&list, pos, e); if(result == 0) { printf("\n插入成功！\n"); printf("在第%d个位置插入了%d\n", pos, e); PrintList(list); } else { printf("插入失败！"); } return 0; }
删除
// 删除 void ListDelete_DuL(DuList *L, int i) { DuList p = LocateListElem(*L, i); if(!p) return; p->prior->next = p->next; p->next->prior = p->prior; free(p); }
栈和队列
顺序栈的基本操作
完整代码
#include <stdio.h> #include <stdlib.h> #define MAXSIZE 100 #define ERROR -1 typedef struct { int *base; // 栈底指针 int *top; // 栈顶指针 int stacksize; // 栈可用的最大容量 }SqStack, *Stack; // 初始化 Stack InitStack() { Stack s = (Stack)malloc(sizeof(SqStack)); if (s == NULL) { printf("栈内存分配失败！\n"); exit(1); } // 为栈底分配内存 s->base = (int *)malloc(MAXSIZE * sizeof(int)); if(s->base == NULL) { free(s); printf("栈内存分配失败！\n"); exit(1); } s->top = s->base; s->stacksize = MAXSIZE; printf("栈初始化成功！\n"); return s; } // 入栈 int Push(Stack s, int e) { // 插入元素e为新的栈顶元素 if(s->top-s->base == s->stacksize) { printf("栈满！\n"); return ERROR; } *s->top = e; s->top++; // 栈顶上移 return 0; } // 出栈 int Pop(Stack s, int *e) { if(s->top == s->base) { printf("栈空！\n"); return ERROR; } s->top--; // 栈顶指针下移 *e = *s->top; // 栈顶元素赋值给e return 0; } // 取栈顶元素 int GetTop(Stack s, int *e) { // 返回栈顶元素，不修改栈顶指针 if(s->top != s->base) // 如果栈非空 { *e = *(s->top - 1); return 0; } return ERROR; } int main() { Stack s = InitStack(); int n; // 栈长 printf("请输入栈长："); scanf("%d", &n); // 入栈 for(int i = 0; i < n; i++) { int e; printf("输入入栈元素："); scanf("%d", &e); if(Push(s, e) == 0) { printf("入栈成功：%d\n", e); } else { printf("入栈失败：%d", e); } } // 出栈 for(int i = 0; i < n; i++) { int e; if(Pop(s, &e) == 0){ printf("出栈成功，元素为%d\n",e); int topElem; if(GetTop(s, &topElem) == 0) { printf("此时栈顶元素为：%d\n", topElem); } else { printf("栈空，无法获取栈顶元素！\n"); } } else printf("出栈失败！\n"); } return 0; }
特点：先入后出，后入先出
#include <stdio.h> #include <stdlib.h> #define MAXSIZE 100 #define ERROR -1 typedef struct { int *base; // 栈底指针 int *top; // 栈顶指针 int stacksize; // 栈可用的最大容量 }SqStack, *Stack;
初始化
// 初始化 Stack InitStack() { Stack s = (Stack)malloc(sizeof(SqStack)); if (s == NULL) { printf("栈内存分配失败！\n"); exit(1); } // 为栈底分配内存 s->base = (int *)malloc(MAXSIZE * sizeof(int)); if(s->base == NULL) { free(s); printf("栈内存分配失败！\n"); exit(1); } s->top = s->base; s->stacksize = MAXSIZE; printf("栈初始化成功！\n"); return s; }
入栈
步骤：
判断栈是否满（s->top - s->base == 0）
将新元素压入栈顶，栈顶指针加一
// 入栈 int Push(Stack s, int e) { // 插入元素e为新的栈顶元素 if(s->top-s->base == s->stacksize) { printf("栈满！\n"); return ERROR; } *s->top = e; s->top++; // 栈顶上移 return 0; }
出栈
步骤：
判断栈是否为空（s->top == s->base）
栈顶指针减一，栈顶元素出栈
// 出栈 int Pop(Stack s, int *e) { if(s->top == s->base) { printf("栈空！\n"); return ERROR; } s->top--; // 栈顶指针下移 *e = *s->top; // 栈顶元素赋值给e return 0; }
获取栈顶元素
// 取栈顶元素 int GetTop(Stack s, int *e) { // 返回栈顶元素，不修改栈顶指针 if(s->top != s->base) // 如果栈非空 { *e = *(s->top - 1); return 0; } return ERROR; }
// 出栈 for(int i = 0; i < n; i++) { int e; if(Pop(s, &e) == 0){ printf("出栈成功，元素为%d\n",e); int topElem; if(GetTop(s, &topElem) == 0) { printf("此时栈顶元素为：%d\n", topElem); } else { printf("栈空，无法获取栈顶元素！\n"); } } else printf("出栈失败！\n"); }
循环队列的基本操作
完整代码
#include <stdio.h> #include <stdlib.h> #define MAXQSIZE 100 #define ERROR -1 typedef struct { int *base; // 存储空间基地址 int front; // 头指针 int rear; // 尾指针 }SqQueue, *Queue; // 初始化 Queue InitQueue() { Queue q = (Queue)malloc(sizeof(SqQueue)); q->base = (Queue)malloc(MAXQSIZE * sizeof(SqQueue)); if(!q->base) { printf("队列初始化失败！\n"); exit(0); } q->rear = 0; q->front = q->rear; return q; } // 求队列长度 int QueueLength(Queue q) { // 对于非循环队列，差值可能为负数，所以需要和MAXQSIZE求余 return (q->rear - q->front + MAXQSIZE) % MAXQSIZE; } // 入队 int EnQueue(Queue q, int e) { if(( q->rear + 1 ) % MAXQSIZE == q->front) return ERROR; q->base[q->rear] = e; // 新元素插入队尾 q->rear = (q->rear + 1) % MAXQSIZE; // 队尾指针加1 return 0; } // 出队 int DeQueue(Queue q, int *e) { if( q->front == q->rear) return ERROR; *e = q->base[q->front]; // 保存队头元素 q->front = (q->front + 1) % MAXQSIZE; // 队头指针加1 return 0; } // 取循环队列队头元素 int GetHead(Queue q) { if(q->front != q->rear) return q->base[q->front]; } int main() { Queue q = InitQueue(); int n, e; printf("请输入队列的长度："); scanf("%d", &n); for(int i = 0; i < n; i++) { printf("入队元素："); scanf("%d", &e); int result = EnQueue(q, e); if(result == 0) { printf("成功入队！\n"); printf("此时队列长度为：%d\n", QueueLength(q)); } else { printf("入队失败！\n"); } } printf("\n\n"); // 出队 for(int j = 0; j < n; j++) { if(DeQueue(q, &e) == 0) { printf("此时队列长度为：%d\n", QueueLength(q)); // 显示当前队列元素 int head = GetHead(q); if(head != ERROR) { printf("出队元素：%d\n", e); printf("当前队头元素为：%d\n",head); printf("\n"); } else printf("队列为空，无法取队头元素！\n"); } else printf("出队失败！\n"); } free(q->base); free(q); return 0; }
特点：先入先出，后入后出
循环队列判断
队空：Q.front = Q.rear
队满：(Q.rear + 1)%MAXSIZE == Q.front
少用一个存储位置，约定一个位置为空
结构体
#include <stdio.h> #include <stdlib.h> #define MAXQSIZE 100 #define ERROR -1 typedef struct { int *base; // 存储空间基地址 int front; // 头指针 int rear; // 尾指针 }SqQueue, *Queue;
初始化
// 初始化 Queue InitQueue() { Queue q = (Queue)malloc(sizeof(SqQueue)); q->base = (Queue)malloc(MAXQSIZE * sizeof(SqQueue)); if(!q->base) { printf("队列初始化失败！\n"); exit(0); } q->rear = 0; q->front = q->rear; return q; }
求队列长度
对于非循环队列，差值可能为负数，所以需要和MAXQSIZE求余
// 求队列长度 int QueueLength(Queue q) { // 对于非循环队列，差值可能为负数，所以需要和MAXQSIZE求余 return (q->rear - q->front + MAXQSIZE) % MAXQSIZE; }
入队
步骤：
判断队列是否为满
将新元素插入队尾
队尾指针加1（q->rear + 1） % MAXSIZE
// 入队 int EnQueue(Queue q, int e) { if(( q->rear + 1 ) % MAXQSIZE == q->front) return ERROR; q->base[q->rear] = e; // 新元素插入队尾 q->rear = (q->rear + 1) % MAXQSIZE; // 队尾指针加1 return 0; }
出队
步骤：
判断队空
保存队头元素
队头指针加1
// 出队 int DeQueue(Queue q, int *e) { if( q->front == q->rear) return ERROR; *e = q->base[q->front]; // 保存队头元素 q->front = (q->front + 1) % MAXQSIZE; // 队头指针加1 return 0; }
取队头元素
// 取循环队列队头元素 int GetHead(Queue q) { if(q->front != q->rear) return q->base[q->front]; }
树和二叉树
树的基本术语
结点 ：树中的一个独立单元。
结点的度 ：结点拥有的子树数。
树的度 ：树内各结点度的最大值。
度为3，不含根节点
叶子 ：度为0的结点。
非终端结点 ：度不为0的结点。
内部节点
双亲和孩子 ：结点的子树的根称为该结点的孩子，该结点称为孩子的双亲。
兄弟 ：同一个双亲的孩子之间互称兄弟。
例如H I J互为兄弟
祖先 ：从根到该结点所经分支上的所有节点。
子孙 ：以某结点为根的子树中的任意一个结点都称为该结点的子孙。
层次 ：结点的层次从根开始定义，根为第一层，根的孩子为第二层。树中任一结点的层次等于其双亲结点的层次加一。
堂兄弟 ：双亲在同一层的结点互为堂兄弟。
树的深度 ：树中结点的最大层次。
有序树和无序树 ：如果将树中结点的各个子树看成从左到右是有次序的（即不能互换），则称该树为有序树，否则为无序树。
森林 ：是m棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。
二叉树
性质
在二叉树的第i层上至多有2^(i-1)个结点（i >= 1）
深度为k的二叉树至多有2^k - 1个结点
对任何一个二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1
具有n个结点的完全二叉树的深度为(不大于log2n的最大整数 + 1)
如果对一棵有n个结点的完全二叉树（其深度为不大于log2n的最大整数 + 1）的结点按层次编号（从第1层到第不大于log2n的最大整数 + 1层，每层从左到右），则对任一结点i（ 1 <= i <= n ），有
如果i为1，则结点i是二叉树的根，无双亲；如果i > 1, 则其双亲PARENT[i]是不大于i/2的最大整数
如果2i > n，则结点i无左孩子；否则其左孩子LCHILD(i)是结点2i
如果2i + 1 > n, 则结点i无右孩子；否则其右孩子RCHILD(i)是结点2i + 1
满二叉树 ：深度为k且含有2^k - 1个结点的二叉树。每一层上的结点数都是最大的结点数
完全二叉树 ：深度为k的，有n个结点的二叉树。
特点是：
叶子结点只可能在层次最大的两层出现
对任一结点，若其右分支下的子孙的最大层次为l，则其左分支下的子孙的最大层次必为l或l + 1
