本篇文章是对二次学习C语言12——文件操作 二次学习C语言14——预处理及模块化 二次学习C语言15——链表 二次学习C语言17——栈、队列、二叉树的部分补充说明，感兴趣的话可以了解一下，这一系列C语言blog不会很仔细，主要是帮助有一些C语言基础但想快速回顾一下的友友；但也不会质量很差，不然就失去了它存在的意义。还是很希望大家在相应blog评论区多多指出疑惑或分享实际问题的，这样我们就可以共同进步啦！

表栈、队列、二叉树

一、二叉树

• 二叉树的遍历

分三种：

1. 先序遍历，根 左 右
2. 中序遍历，左 根 右
3. 后序遍历，左 右 根

	* 先序遍历（根左右）：ABCDEFGHK
A为根先左B，B为根仅右C，C为根仅左D，D无左右，
A为根后右E，E为根仅右F，F为根仅左G，G为根先左H后右K
下面以对应规则类推* 中序遍历（左 根 右）：BDCAEHGKF* 后序遍历（左 右 根）：DCBHKGFEA

• 树

树型结构是以分支关系定义的层次结构，它是一种重要的非线性结构。

树（tree） 是由一个或多个结点组成的有限集合T 。

1. 一个特定的结点称为该树的根（root）结点
2. 结点之外的其余结点可分为m（m ≥ 0）个互不相交的有限集合 T1 ,T2 ,…,Tm ，且其中每一个集合本身又是一棵树，称之为根的子树（subtree）。

注意：
树的递归定义刻画了树的固有特性：一棵非空树是由若干棵子树构成的，而子树又可由若干棵更小的子树构成。

树结构的基本术语如下。

结点的度(Degree)：树中的一个结点拥有的子树数目，如：A结点的度为2

树的度：是指该树中结点的最大度数。如树T的度为2。

叶子结点(Leaf) 或终端结点：度为零的结点。如D、H、K都是叶子结点。

分支结点或非终端结点：度不为零的结点。A、B、C、E、F、G都是分支结点。

孩子结点或儿子：树中某个结点的子树之根。如A的孩子结点为B、E。

双亲结点或父亲：孩子结点的上层结点。

兄弟结点(Sibling)：同一个双亲的孩子。

结点的层数(Level)：从根起算，根的层数为1，它的孩子的层数为2……若某结点在第i层，它的孩子结点就在第i+1层。

树的高度(Height)或深度(Depth)：树中结点的最大层数。如树T的高度为5

有序树(OrderedTree)：将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，二叉树就是有序树。（二叉树的左子树和右子树是严格区分并且不能随意颠倒的）

• 二叉树的性质

1. 性质1： 二叉树第i层上的结点数目最多为2ⁱ-1(i≥1)。
2. 性质2： 深度为k的二叉树至多有2^k-1个结点(k≥1)。
3. 性质3： 在任意一棵二叉树中，若叶子结点（即度为0的结点）的个数为n₀，度为1的结点数为n₁，度为2的结点数为n₂，则n_o=n₂+1。

满二叉树(FullBinaryTree) ：一棵深度为k且有2^k-1个结点的二叉树称为满二叉树。

其特点：
1.每一层上的结点数都达到最大值。即如果高度确定，它是具有最多结点数的二叉树。

2.满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。

完全二叉树(Complete BinaryTree) :若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。

其特点：
1.满二叉树是完全二叉树，完全二叉树不一定是满二叉树。
2.在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。
3.在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。

二叉树的存储结构有多种，最常用的有两种：是顺序存储结构和链表存储结构。

优点和缺点：
① 对完全二叉树而言，顺序存储结构既简单又节省存储空间。

② 一般的二叉树采用顺序存储结构时，虽然简单，但易造成存储空间的浪费。

③ 在对顺序存储的二叉树做插入和删除结点操作时，要大量移动结点。

二、表栈

• 线性表

  最简单、最常用的一种数据结构，是具有相同数据类型的n（n≥0）个数据元素（结点）的有限序列。通常记为：（a1，a2，…，an ）。其中n称为线性表的长度，当n=0的时表示空表。

  • ①顺序表

  用一段连续的内存空间来存储线性表的数据元素，C语言中是通过数组来实现

  • ②链表

即二次学习C语言15——链表

• 栈（zhan）

==堆栈（Stack）==可以看成是一种“特殊的“线性表，这种线性表上的插入和删除运算限定在表的某一端进行的。

栈先进后出（FILO）的特点也可以描述为后进先出，简称为LIFO表。

1. 通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。
2. 当表中没有元素时称为空栈。
3. 退栈：删除。
4. 进栈：插入。

三、队列

队列(Queue) 是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。

1. 允许删除的一端称为队头（Front）。

2. 允许插入的一端称为队尾（Rear）。

3. 当队列中没有元素时称为空队列。

4. 队列简称为FIFO表。

链表

一、单向链表

在链表结构中，每个节点仅存储本身需要存储的数据和下一个节点地址的这种链表结构，我们称为单向链表结构

数组与链表对比①：

数组在进行数据的插入，删除操作时，为了保证内存数据的连续性，往往需要做大量的数据搬移工作，所以时间复杂度是O(n)。

在链表中插入或删除数据时，因为链表结构中的节点并不需要连续的存储空间，所以在链表中进行数据的插入和删除时并不需要搬移节点。对于链表的删除和插入操作，我们只需要调整相邻节点的后继指针即可，所以对应的时间复杂度是O(1)。

数组与链表对比②：

数组的内存数据是连续的，当我们需要访问第k个元素时，通过基地址（base_address）和数据类型大小就可以随机访问到数据所在的内存地址，时间复杂度是O(1)。

对于链表来讲，因为链表中各个节点的数据在内存中时分散的，不像数组那样是连续的存储空间，所以要访问链表中的第k个元素，只能从头结点开始，根据节点间的后继指针或引用逐一遍历，直到找到相应的节点，所以链表的随机访问的性能没有数组好，时间复杂度为O(n)。

二、循环链表、双向链表和双向循环链表

将单链表的尾节点从指向空地址NULL调整为指向头结点Head，就形成了循环链表。

和单链表相比，循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时，就特别适合采用循环链表。

双向链表支持两个方向，每个节点不止只有一个后继指针或者引用Next指向后继节点，还有一个前驱指针或者引用Prev指向前面的节点

从双向链表的结构看，双向链表可以在O(1)的时间复杂度下找到前驱节点，基于此特性，在某些特殊的场景下，对节点的删除和插入操作，双向链表比单向链表会更高效.

上面我们说了单向链表、循环链表、双向链表，我们将循环链表和双向链表整合在一起，就形成了双向循环链表。

不过，数组和链表的对比，并不能局限于时间复杂度。而且，在实际的软件开发中，不能仅仅利用复杂度分析就决定使用哪个数据结构来存储数据，一切都要根据具体情况具体分析，合适最好。

预处理

一、预处理

编译预处理是在对源程序正式编译之前的处理，以“#”开头，如文件包含“#include”、宏定义“#define”等。预处理命令不是C语言本身的组成部分，不能直接对它进行编译。所有的预处理指令都是在编译之前完成的，不占用程序运行时间。

二、宏定义

• 注意事项：

1. 宏名习惯采用大写，以便与普通变量区分；

2. 宏定义不是C语句，所以不能在行尾加分号；否则，宏展开时，会将分号也算在内

3. 在宏展开时，预处理程序仅按宏定义简单替换宏名，不做任何检查。如果有错误，只能由编译器在编译宏展开后的源程序时发现。

4. 宏定义的位置是任意的，宏名的有效范围是从定义命令处到本模块结束。通常写在文件开头处。

5. 宏调用时，是原样替换，不进行任何转换。

• #define常量定义与typede数据类型定义的异同点：

#define P_INT int* //在编译前执行 (原样替换)

typedef int* P_INT //在编译时执行

相同点：都是定义了一个int指针类型的别名

不同点：用#define时，P_INT a, b;相当于int* a, b;即int*a; int b;此时b不是int *,而是int

用typedef时，P_INT a, b;相当于int *a; int *b;

文件

文件操作补充

• 文件操作的两种方式

1. 基于文件描述符¹的文件操作，无缓冲区，也称为低级文件的操作，属于底层文件系统，函数90多个。

2. 基于文件指针的访问操作，带缓冲区，称为高级的文件操作，属于高级文件系统，也是标准C文件操作库函数， ANSI C库函数 300多个.

注意：在实操中，我使用的是fwrite与fread，故生成的数据文件打开后是无法正常阅读的，全是二进制数（相当于一层加密）；若想正常阅读生成的数据文件，可使用fprintf与fscanf

---

1. 文件描述符：就是数字，0,1,2分别表示标准输入，标准输出，标准出错 ↩︎