1. 线性表
线性表的定义：
由零个或多个数据元素组成的有限序列
注意：
- 首先它是一个序列，也就是说元素之间是有先来后到之分。
- 若元素存在多个，则第一个元素无前驱，而最后一个元素无后继，其他元素都有且只有一个前驱和后继。
- 线性表强调是有限的，事实上无论计算机发展到多强大，他所能处理的元素都是有限的。
线性表的形式化定义：
模拟考题：
- 请问公司的组织架构是否属于线性关系？
分析：一般公司的总经理管理几个总监，每个总监管理几个经理，每个经理都有各自的下属和员工。
那这样的组织架构当然不是线性关系了，事实上后面你就会知道，这是一个树状结构。注意线性关系的条件是如果存在多个元素，则第一个元素无前驱，而最后一个元素无后继，其他元素都有且只有一个前驱和后继。 - 那么班里同学之间的友谊是否属于线性关系？
当然也不是了，因为每个人都会跟许多同学建立纯纯的友谊关系。 - 情侣之间的爱情关系呢？
当然是扯淡，这要是线性关系，也就不会有所谓的第三者插足了。。。你们的爱情关系定会是线性关系！ - 最后一题，一个班级的点名册，是不是线性表？看下表：
| 学号 | 姓名 | 性别 | 职位 |
|---|---|---|---|
| 1 | 张三 | 男 | 班长 |
| 2 | 花花 | 女 | 副班长 |
| 3 | 丽丽 | 女 | 音乐课代表 |
| 4 | 萱萱 | 女 | 美术课代表 |
| 5 | 明明 | 男 | 小组长 |
线性表的分类：
2. 数组：
数组就是 存储在连续内存空间 的数据项的集合，目的就是将多个 具有相同数据类型 的数据存储在一段连续的内存空间。这样就可以很容易的通过数组的 首地址 和 偏移量（offset） 计算数组中每一个元素的地址，数组的第一个元素的存储位置是整个数组的首地址（通常由数组的名称表示），默认起始地址的索引为 0，两个索引之间的差值为偏移量。
想象一下，你（0 号）站在地面，你的若干个朋友（编号 1，2，3，4，5）分别站在一段楼梯的不同台阶上，那么你只需要知道你的朋友上了几个台阶，就可以确定他（她）的位置。
那么你就是首地址（索引为 0），而你与你的每一位朋友之间的台阶数就是该朋友相对于你的偏移量，比如 4 号朋友的偏移量就是 4 （两个索引的差值），你要找到你的 4 号朋友就需要上 4 个台阶。
为什么是相同数据类型呢？因为只有相同数据类型才可以通过首地址和偏移量来确定其他元素的地址。
图 1-2 可以看作是 图 1-1 楼梯的俯视图，您在楼梯的底部。数组中的每个元素都可以通过索引唯一标识（就像您在上面的示例中通过上台阶的步数确定朋友的方式类似）。
数组大小
在 C 语言中，数组具有固定的大小。一旦指定大小，便无法更改，既无法缩小，也无法扩展。因为，如果我们对数组进行扩展，我们无法确保获得的下一个内存位置是空闲的（可分配的）。对数组进行缩小也不起作用，因为数组在声明时会获得一块静态的内存空间，只有编译器才可以销毁它。
数组中的索引类型：
0 (基于 0 的索引)：数组的第一个元素用下标 0 索引。1 (基于 1 的索引)：数组的第一个元素被下标 1 索引。n (基于 n 的索引)：数组的基索引可以自由选择。通常编程语言允许基于 n 的索引，也允许负索引值和其他标量数据类型，如枚举，或者字符可以用作数组索引。
注意：我们的文章中的数组的第一个元素的下标均为 0 。
数组中的元素存储在连续的内存空间。
C 语言测试数组中元素存储在连续内存空间的 demo：
/*
* C 程序说明数组存储在连续的内存空间
*/
#include <stdio.h>
int main()
{
/* 包含 10 个整数的整型数组
* 如果 arr[0] 存储在地址 x,则 arr[1] 存储在 x+sizeof(int),
* arr[2] 存储在 arr[1] 的地址 + sizeof(int)
*/
int arr[10]; // 大家也可以换成char double float long等类型
int i;
printf("编译器中整型的大小：%lu\n",sizeof(int));
for (i = 0; i < 10; i++)
// '&' 表示取变量的地址.
printf("arr[%d] 的地址为: %p\n", i, &arr[i]);
return 0;
}
输出：
编译器中整型的大小：4
arr[0] 的地址为: 0028FF14
arr[1] 的地址为: 0028FF18
arr[2] 的地址为: 0028FF1C
arr[3] 的地址为: 0028FF20
arr[4] 的地址为: 0028FF24
arr[5] 的地址为: 0028FF28
arr[6] 的地址为: 0028FF2C
arr[7] 的地址为: 0028FF30
arr[8] 的地址为: 0028FF34
arr[9] 的地址为: 0028FF38
3. 队列
队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
与栈相反，队列是一种先进先出（First In First Out，FIFO）的线性表。
队列的链式存储结构队列既可以用链表来实现，也可以用顺序表来实现，跟栈相反的是，栈一般我们用顺序表来实现，而队列我们常用链表来实现，简称链队列。
typedef struct QNode {
ElemType data;
struct QNode *next;
}QNode, *QueuePrt;
typedef struct {
QueuePrt front,rear; //对头与队尾指针
} LinkQueue;
我们将队头指针指向链队列的头结点，而队尾指针指向终端结点。（注：头结点不是必须的，但是为了方便操作，我们加上了）
空队列的时候，front和rear都指向头结点
创建一个队列
创建一个队列要完成两个任务：一是在内存中创建一个头结点，二是将队列的头指针和尾指针都指向这个生成的头结点，此时生成一个空队列。
initQueue(LinkQueue *q)
{
q->front=q->rear=(QueuePtr)malloc(sizeof(QNode));
if( !q->front)
exit(0)
q->front->next = NULL;
}
入队列操作
入队列操作过程如下：
出队列操作
出队列操作就是将队列中的第一个元素移动，队头指针不发生变化，改变头结点的next指针即可。
出队列的操作过程如下：
如果原队列中只有一个元素，那么我们就应该处理一下队尾指针。
DeleteQueue(LinkQueue *q, ElemType *e)
{
QueuePtr p;
if( q->front == q->rear )
{
return;
}
p = q->front->next;
*e = p->data;
q->front->next = p->next;
if( q->rear == p)
q->rear = q->front;
free(p);
}
销毁一个队列
由于链队列建立在内存的动态区，因此当一个队列不再有用时应当把它销毁掉，以免过多地占用内存空间。
DestroyQueue(LinkQueue *q)
{
while(q->front) {
q->rear = q->front->next;
free(q->front);
q->front=q->rear;
}
}
4. 树
4.1 树的概念
树(Tree)是n(n>=0)个结点的有限集。当n=0时成为空树，在任意一棵非空树中：
有且仅有一个特定的称为根(Root)的结点；
当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、...、Tm，其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。
n>0时，根结点是唯一的，坚决不可能存在多个根结点。
m>0时，子树的个数是没有限制的，但它们互相是一定不会相交的。
比如，下图中的就不符合树的定义：
树中结点的分类：
如图中所示，每一个圈圈我们就称为树的一个结点。结点拥有的子树数称为结点的度-(Degree)，树的度取树内各结点的度的最大值。
- 度为0的结点称为叶结点(Leaf)或终端结点；
- 度不为0的结点称为分支结点或非终端结点，除根结点外，分支结点也称为内部结点。
树中结点之间的关系：
结点的子树的根称为结点的孩子(Child)，相应的，该结点称为孩子的双亲(Parent)，同一双亲的孩子之间互称为兄弟(Sibling)。
结点的祖先是从根到该结点所经分支上的所有结点
结点的层次：
结点的层次(Level)从根开始，根为第一层，根的孩子为第二层。
其双亲在同一层的结点互为堂兄弟。
树中结点的最大层次称为树的深度(Depth)或高度。
4.2二叉树
世上树有万千种，唯有二叉课上讲。这里的二叉是二叉树，因为二叉树使用的范围最广，最具有代表意义，因此不论教材还是考试都以二叉树为主。
二叉树（Binary Tree）是n（n>=0）个结点的有限集合，该集合或者为空集（空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
这个定义显然是递归形式的，所以咱看上去有点晕，因为自古有“神使用递归，人使用迭代！“ 递归在树的相关操作中简直方便的不要不要！
二叉树的特点
每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。（注意：不是都需要两棵子树，而是最多可以有两棵，没有子树或者有一棵子树也都是可以的。）
左子树和右子树是有顺序的，次序不能颠倒。
-
即使树中某结点只有一棵子树，也要区分它是左子树还是右子树，下面是完全不同的二叉树：
image.png
二叉树的五种基本形态
image.png
若只从形态上来考虑，拥有三个结点的普通树只有两种情况：两层或者三层。而对于二叉树来说，由于要区分左右，所以就演变成五种形态（这也是为什么考试面试笔试总选择二叉树进行考察）：
满二叉树
如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。
满二叉树除了满足普通二叉树的性质，还具有以下性质（请注意图中的标注）：
满二叉树中第 n 层的节点数为
个。
深度为 k 的满二叉树必有
个节点 ，叶子数为
。
满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。
完全二叉树
如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。
完全二叉树除了具有普通二叉树的性质，它自身也具有一些独特的性质，比如说，n 个结点的完全二叉树的深度为 ⌊⌋+1（后面有证明）。
二叉树的性质
二叉树的性质一：在二叉树的第i层上至多有
个结点(i>=1)
二叉树的性质二：深度为k的二叉树至多有
个结点(k>=1)
