1.栈、数组和队列的应用
1.1.栈
1.1.1.栈的定义：
#define MAXSIZE typedef struct Stack{ int data[MAXSIZE]; int top; }Stack;
1.1.2.栈的基本操作的代码实现：
1.建立栈：
void InitStack(Stack &s){ s.top = -1; }
2.入栈（push）：
bool Push(Stack &s, int e){ if (s.top == MAXSIZE - 1) return false; //判断是否栈已满 s.data[++s.top] = e; //将栈顶指针先+1，然后将e存入栈顶 return true; }
3.出栈（pop）：
bool Pop(Stack &s, int &e){ if (s.top == -1) return false; //判断是否栈空 s.data[s.top--] = e; //先将栈顶元素赋值给e，然后栈顶指针-1 return true; }
4.判断栈空：
bool IsEmpty(Stack s){ if (s.top == -1) return true; //判断栈顶指针是否为-1 else return false; }
5.查看栈顶元素：
bool GetTop(Stack S, int &e){ if (s.top == -1) return false; //判断是否栈空 e = s.data[s.top]; return true; }
1.1.3.栈的数据结构的手绘
1.1.4.栈的基本操作的手绘
1.2.队列
1.2.1.队列的定义
1.顺序栈：
#define MAXSIZE 100 typedef struct SqQueue{ int data[MAXSIZE]; int front, rear; }SqQueue;
2.链栈：
typedef struct LNode{ //链式队列结点的定义 struct LNode *next; int data; }*LinkList, LNode; typedef struct LinkQueue{ //链式队列的定义 LNode *front, *rear; //头尾指针 }LinkQueue;
1.2.2.顺序队列的基本操作（循环队列）
1.建立队列：
void InitQueue(SqQueue &Q){ Q.rear = 0; //将front和rear都置为0, Q.front = 0; }
2.入队：rear对队列的最大容量取余，且不能使用Q.rear++
bool EnQueue(SqQueue &Q, int e){ if ((Q.rear + 1)) % MAXSIZE = Q.front) return false; //判断是否队满 Q.data[Q.rear] = e; Q.rear = (Q.rear + 1) % MAXSIZE; return true; }
3.出队：front对队列的最大容量取余，且不能使用Q.front++
bool DeQueue(SqQueue &Q, int &e){ if (Q.front == Q.rear) return false; //队空 e = Q.data[Q.front++]; return true; }
4.判断对空：
bool IsEmpty(SqQueue Q){ if (Q.front == Q.rear) return true; //队空时rear和front指向同一个地方 else return false; }
5.得到队首元素：
bool GetFront(SqQueue Q, int &e){ if (Q.front == Q.rerar) return false; //队空 e = Q.data[Q.front]; return true; }
1.2.3.链式队列的基本操作
1.队列初始化：在申明一个链式队列后，只有头尾结点指针，需要申明一个头结点
void InitQueue(LinkQueue &Q){ Q.front = Q.rear = (LNode*)malloc(sizeof(LNode)); //申明一个头结点 Q.front->next = NULL; //将next指针置空 }
2.入队：
void EnQueue(LinkQueue &Q, int e){ LNode *p = (LNode*)malloc(sizeof(LNode)); //申明一个新结点p p->data = e; //e赋值给p的数据域 p->next = NULL; //p的next指针置空 Q.rear->next = p; //将p插入到队尾 Q.rear = p; //将rear指向p }
3.出队：需要判断是否队中只有一个元素
bool DeQueue(LinkQueue &Q, int &e){ if (Q.rear == Q.front) return false; //队空 LNode *p = Q.front->next; //申明LNode类型的指针p指向队首元素 e = p->data; //将p的数据域赋值给e if (Q.rear = p) { //队中只有元素p Q.rear = Q.front; Q.front->next; } else Q.front->next = p->next; //对中不止有元素p，则front的next指针指向p的下一个元素 free(p); return true; }
4.判断对空：队首指针和队尾指针指向同一个地方时对空
bool IsEmpty(LinkQueue Q){ if (Q.front == Q.rear) return true; else return false; }
1.2.4.队列的数据结构的手绘
1.2.5.队列的基本操作的手绘
1.循环队列：
2.链式队列：
①front指针始终指向头结点，rear在队中有元素时始终指向队尾元素
②初始状态和队空时：front和rear都只指向头结点
1.3.数组
申明n个元素的数组：
int *arr = (int*)malloc(sizeof(int) * n); memset(arr, 0, sizeof(int) * n);
2.树
2.1.树的数据结构定义和手绘
2.1.1.二叉树
1.顺序结构：通常用于存放完全二叉树
#define MAXSIZE 100 typedef struct TreeNode{ int value; //当前结点的值 bool IsEmpty; //表示当前的结点是否为空 }TreeNode;
2.单向链：
typedef struct BiTNode{ int value; //当前结点的值 struct BiTNode *lchild, *rchild; //指向当前结点左右子树的指针 }BiTNode, *BiTree;
3.双向链：双亲节点指向孩子结点，孩子结点也指向双亲结点
typedef struct BiTNode{ struct BiTNode *lchild, *rchild, *parent; //parent指针指向该结点的双亲结点 int value; }BiTNode, *BiTree;
2.1.2.多叉树
408数据结构学习笔记——树、森林_江南江南江南丶的博客-CSDN博客
1.双亲表示法（并查集）
#define MAXSIZE 100 typedef struct PNode{ int value; //该结点的值 int parent; //伪指针，用于指向双亲结点（双亲结点的数组下标） }PNode; typedef struct PTree{ PNode node[MAXSIZE]; //申明一片PNode类型个数为MAXSIZE的数组用于存储树 int n; //表示该树中的结点个数 }PTree;
2.孩子表示法：
typedef struct CTNode{ //链式存储，存放该结点的每个孩子结点的信息（非孩子结点的数据） int child; //该结点的孩子结点在数组中的下标 struct CTNode *next; //指向该孩子结点的下个孩子结点 }CTNode; typedef struct CTBox{ //定义具体结点，存放结点数据，并且存放该元素的第一个孩子结点 int data; CTNode *firstChild; }CTBox; typedef struct CTree{ //顺序存储结点 CTBox nodes[MAXSIZE]; //定义一个CTBox类型长度为MAXSIZE的数组 int n, r; //n为结点的总个数，r为根节点的数组下标 }CTree;
3.孩子兄弟表示法：
typedef struct CSNode { int value; //结点数据 struct CSNode *firstChild, *nextChild; }CSNode, *CSTree;
2.2.二叉树的基本操作
408数据结构学习笔记——二叉树的遍历和线索二叉树_江南江南江南丶的博客-CSDN博客
1.先序遍历：
void PreOrder(BiTree T){ if (T) { visit(T); PreOrder(T->lchild); PreOrder(T->rchild); } }
2.中序遍历：
void InOrder(BiTree T) { if (T) { InOrder(T->lchild); visit(T); InOrder(T->rchild); } }
3.后序遍历：
void PostOrder(BiTree T) { if (T）{ PostOrder(T->lchild); PostOrder(T->rchild); visit(T); } }
4.层次遍历：
typedef struct BiTNode{ int value; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; typdef struct LinkNode{ BiTNode *data; struct LinkNode *next; }LinkNode; typdef struct LinkQueue{ LinkNode *front, *rear; }LinkQueue; void LevelOrder(BiTree T) { LinkQueue Q; InitQueue(Q); //初始化队列 BiTNode *p; EnQueue(Q, T); //根结点入队 while(!IsEmpty(Q)) { DeQueue(Q, p); //出队队首元素 visit(p); //访问p if (p->lchild) EnQueue(Q, p->lchild); //左子树入队 if (p->rchild) EnQueue(Q, p->rchild); //右子树入队 } }
