数据结构学习02：受限线性表与树形结构

1. 栈 (Stack)与队列 (Queue)栈和队列本质上是一种特殊的表状结构它们与普通表的区别在于普通表可以在任意位置进行插入和删除 。而栈和队列只能在指定的位置进行插入和删除操作 。栈 (Stack)核心特性栈是一种先进后出 (LIFO)后进先出 (FILO) 的数据结构 。基本概念栈顶与栈底允许入栈和出栈的一端称为栈顶 不允许入栈和出栈的一端称为栈底 。栈针用于指向栈顶位置的指针或下标 。常见分类按照生长方向向高地址增长的称为增栈 向低地址增长的称为减栈 。按照栈针指向栈针指向入栈位置称为空栈 栈针指向栈顶当前元素位置称为满栈 。综合分类空增栈、满增栈、空减栈、满减栈 。操作与实现核心操作包括将数据插入栈顶的入栈压栈 以及从栈顶取出数据的出栈弹栈 。可以通过顺序栈或链式栈来实现 。队列 (Queue)核心特性队列是一种先进先出 (FIFO)后进后出的数据结构 。基本概念数据从队尾入队插入 从队头出队取出 。常见实现包括循环队列和链式队列 。递归思想创建二叉树非递归思想遍历二叉树2. 二叉树 (Binary Tree)树是用来描述数据一对多关系的数据结构 。二叉树是其中最常用的一种其树形结构中每个节点最多有2个后继节点 。节点与关系组成树形结构的数据称为节点 。根节点只有后继没有前驱 。叶子节点只有前驱没有后继 。分支节点既有前驱又有后继最多一个前驱可有多个后继 。数据来源的方向称为前驱祖先后续的方向称为后继子孙 。节点左右两侧的子节点分别称为左孩子和右孩子 。属性度量度前驱或者后继的个数 。入度均为1 出度为后续节点的个数 。层、高度与深度根节点在第一层往下层数递增 。节点深度是距离根节点的节点个数 节点高度是距离该节点最远的叶子节点的距离 。整体上树的高度、深度和层数是等价的 。特殊形态与数学特性满二叉树所有的叶子节点都在同一层 。完全二叉树将二叉树所有节点展开后编号连续 。特性第 $k$ 层最多有 $2^{k-1}$ 个节点 前 $k$ 层最多共有 $2^k-1$ 个节点 。二叉树的遍历深度优先遍历 (DFS)前序遍历根左右 、中序遍历左根右 、后续遍历左右根 。广度优先遍历 (BFS)层序遍历 。3.代码实现1.顺序循环队列main.c#includestdio.h#includeseqqueue.hint main(void){SeqQueue_t *pSeqQueue NULL;int i 0;pSeqQueue CreateSeqQueue(10);while (!IsFullSeqqueue(pSeqQueue)){EnterSeqQueue(pSeqQueue, i);i 2;}while (!IsEmptySeqqueue(pSeqQueue)){printf(%d , QuistSeqQueue(pSeqQueue));}printf(\n);DestorySeqQueue(pSeqQueue);return 0;}seqqueue.c#includestdio.h#includestdlib.h#includeseqqueue.hSeqQueue_t *CreateSeqQueue(int len){SeqQueue_t *pSeqQueue NULL;pSeqQueue malloc(sizeof(SeqQueue_t));if (pSeqQueue NULL){perror(fail to malloc);return NULL;}pSeqQueue-Maxlen len;pSeqQueue-Head 0;pSeqQueue-Tail 0;pSeqQueue-pData malloc(sizeof(DataType) * len);if (pSeqQueue-pData NULL){perror(fail to malloc);return NULL;}return pSeqQueue;}int IsEmptySeqqueue(SeqQueue_t *pSeqQueue){return pSeqQueue-Head pSeqQueue-Tail ? 1 : 0;}int IsFullSeqqueue(SeqQueue_t *pSeqQueue){return ((pSeqQueue-Tail 1) % pSeqQueue-Maxlen pSeqQueue-Head) ? 1 : 0;}int EnterSeqQueue(SeqQueue_t *pSeqQueue, DataType TmpData){if (IsFullSeqqueue(pSeqQueue)){return -1;}pSeqQueue-pData[pSeqQueue-Tail] TmpData;pSeqQueue-Tail (pSeqQueue-Tail 1) % pSeqQueue-Maxlen;return 0;}DataType QuistSeqQueue(SeqQueue_t *pSeqQueue){DataType TmpData 0;if (IsEmptySeqqueue(pSeqQueue)){return -1;}TmpData pSeqQueue-pData[pSeqQueue-Head];pSeqQueue-Head (pSeqQueue-Head 1) % pSeqQueue-Maxlen;return TmpData;}int DestorySeqQueue(SeqQueue_t **ppSeqQueue){free((*ppSeqQueue)-pData);free(*ppSeqQueue);*ppSeqQueue NULL;return 0;}