数据结构笔记
1、每个程序所花费的运行次数称为该程序的“时间复杂度”。判断该程序执行效率是否良好。
2、
时间复杂度
渐进式表达法
3、内存的位置：
以行为主来表示:
Data[i][j]的内存位置 = 数组第一个元素位置 ＋ [( i * 每一行的元素个数) + j] * (所声明数据类型所占的大小)
以列为主表示
Data[i][j]的内存位置 = 数组第一个元素位置 ＋ [( j * 每一行的元素个数) + i] * (所声明数据类型所占的大小)
4、稀疏数组
数组中大部分的内容值都未被使用（或都为零），在数组中仅有少部分的空间使用。因此造成内存空间的浪费，为了节省内存空间，并不影响数组中原有的内容值，采用一种压缩的方式来表示稀疏数组的内容。
稀松数组
5、上三角数组
一种方阵住对角线的左下方元素全部都为0的数组。
上三角数组（以行为主）
上三角数组（以列为主）
6、下三角数组
下三角数组（以行为主）
下三角数组（以列为主）
7、数组使用的是静态的内存空间配置，静态内存就是程序设计者必需在程序设计时，就要把所需的内存空间大小和数据类型给定义出。
8、链表
链表是一种有序的列表，链表的内容通常是存储于内存中分散的位置上。链表串连的方式有两种：一种是利用数组结构串连的有序列表。如利用两个数组，一个存放数据，另一个存放链表的关系。
9、堆栈的输出和输入都是从堆栈的顶端进行，遵循“先进后出”的原则。
10、中序表达式的表示法，处理过程。
（1）
（2）
11、前序表达式的表示法
前序表达式的表示法
12、后序表达式的表示法
后序表达式的表示法
与前序表达式的唯一不同是读取表达式的方向相反。
13、堆栈的应用
（1）子程序之调用：在跳往子程序前，会先将下一个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，再回到原来的程序中。
（2）处理递归调用：和子程序的调用类似，只是除了存储下一个指令的地址外，也将参数，区域变量等数据存入堆栈中。
（3）表达式之转换与求值。
（4）二叉树的遍历。
（5）图形的深度优先追踪法。
建立堆栈可使用的两种结构：数组结构和链表结构。队列一样。
14、队列
在有序列表中数据的输出、输入是分别由不同端进行处理，输出端称为前端，输入端称为后端，这样会使得先存入的数据会先被取出，也就是具有先进先出FIFO的特性。队列本身是有序列表。
队列的应用：
（1）图形的广度优先搜索法
（2）优先队列，此种队列在取出元素时是根据所存元素的某项特性值或优先权而取出具最小或最大数值的元素。
（3）操作系统中的工作调度，若工作的优先权相同，则采用先到先做的原则。
（4）用于“spooling”，先将输出数据写在磁盘上，再由打印机把先存入者先处理的顺利将数据输出。
15、从队列中取出数据项称为“delqueue”，delqueue的操作分为4个步骤“
（1）检查队列中是否有数据存在。
（2）若头指针front等于尾指针rear，则表示队列中无数据。
（3）若头指针front不等于尾指针rear，则将队头指针往前移front＋1。
（4）取出队头指针所指的数组元素内容。
16、递归
递归简单的定义就是子程序或函数重复的调用自己，并传入不同的变量来执行的一种程序设计技巧，而递归在程序设计及解题上也是一种有力、重要的工具，帮助程序设计者解决复杂的问题，并精简程序结构。
17、解递归问题的步骤：
（1）了解题意是否适合用递归来解题。
（2）决定了递归结束条件。
（3）决定递归执行部分。
18、用递归设计一个求费氏级数的程序。
程序构思：
递归结束条件：当N<=1，返回费氏级数值为N。
递归执行部分: 当N>1时，返回费氏级数值为Fib(N-1)+Fib(N-2)。
程序：
int Fib(int N){
if (N <= 1)
return N;
else
return Fib(N - 1) + Fib(N - 2);
}
void main(){
int Number;
int Result;
printf("The Fibonacci Numbers \n");
printf("Please enter a number:");
scanf("%d", &Number);
Result = Fib(Number);
printf("Fibonacci Numbers of %d = %d\n", Number , Result);
}
19、递归程序设计时，必须要有递归结束条件，否则将死循环。
递归程序利用堆栈来记录函数调用后的返回地址。
递归程序的时间复杂度和控件复杂度比非递归程序有效率。
20、树状结构是由一个或多个节点所构成之有限集合。每棵树必有一特定节点，称作根节点。根节点之下可以有零个以上的子节点（可以没有），而各子节点也可为子树，拥有自己的子节点。
21、
树的相关名称及意义
树的相关名称及意义
22、二叉树
二叉树是树的一种，二叉树中的节点至多只能有两个子节点。
二叉树的定义：（1）由有限个节点所构成之集合，此集合可以为空的。
（2）二叉树的根节点下可分成两个子树，称为左子树和右子树，左子树和右子树亦称为二叉树。
23、二叉树和树的比较
（1）二叉树可为空，而树不可以（至少要有根节点）。
（2）二叉树的子树有顺序关系，而树没有。
（3）二叉树的分支度必为0、1或2，而树的分支度可以大于2。
24、二叉树的相关特色
歪斜树
满二叉树
完全二叉树
24、二叉树节点的表示法，常用的3种：
（1）二叉树数组表示法
（2）二叉树结构数组表示法
（3）二叉树链表表示法
其中“数组表示法”和“结构数组表示法”是属于静态内存空间配置，而“链表表示法”是利用列表结构的方式，属于动态内存空间配置。
25、二叉树数组表示法
二叉树数组表示法
26、建立二叉树节点数据的原则：
（1）以第一个建立之元素为根节点。
（2）依序将元素值与根节点做比较
（a）若元素值大于根节点值，则将元素值往根节点之右子节点移动，若此右子节点为空，则将元素存入，否则就重复比较，直到找到适当之空节点为止。
（b）若元素值小于根节点值，则将元素值往根节点之左子节点移动，若此子节点为空，则将元素值存入，否则就重复比较，直到找到适当之空节点为止。
27、二叉树数组表示法的优点：对于任一个节点都能很容易的找到其父节点、子节点及兄弟，而且每个节点的存储空间不大，只占用数组的一个内存空间。但当二叉树之深度和节点树之比例偏高时（二叉树分布不平均，如歪斜树），则内存的利用率会偏低，容易造成空间的浪费。
28、二叉树结构数组表示法
二叉树中的节点最多只能有两个子节点，我们可用结构的类型来声明节点的存储方法。此结构包含3个字段，其中一个字段是用来存放节点的数据内容，而另两个字段则是分别存放左子树和右子树在数组中的索引值。
结构数组的类型
二叉树的结构声明如下：
struct tree{
int left;
char data;
int right;
}
typedef struct tree treenode;
treenode b_tree[15];
声明完成后，b_tree即是用来存放二叉树各节点之结构数组。在结构数组中，会将根节点置于数组结构中索引值为0之处，将节点值存在data字段，而left及right字段则分别存储左右子树在数组结构中的索引值，若子树不存在则存值－1。
例
29、二叉树链表表示法
链表的节点结构
二叉树链表结构的声明如下：
struct tree{
struct tree *left;
int data;
struct tree *right;
}
typedef struct tree treenode;
treenode *b_tree;
30、二叉树的遍历
二叉树是一种特殊的数据结构，每个节点其下又各有左、右两个分支。“二叉树的遍历”是以固定的顺序，有系统地抽取二叉树中的各节点，且每个节点均恰好被抽取一次。
二叉树的遍历是以递归的方式进行，依递归的调用顺序之不同，可分为下列3种不同的遍历方式：
1、前序遍历方式
2、中序遍历方式。
3、后序遍历方式。
31、二叉树的前序遍历
前序遍历是先遍历根节点，在遍历左子树，最后才遍历右子树，若一棵二叉树如下，则前序遍历的顺序为：DLR，也就是说每当遍历一个节点就先处理该节点，之后先向左方前进，直到无法前进才往右方走。
例子
例
32、二叉树的中序遍历
中序遍历是先遍历左子树，再遍历根节点，最后才遍历右子树。若一棵二叉树如下，则前序遍历的顺序为：LDR，也就是说一开始先往左方前进，直到无法前进才处理节点，之后再往右方前进。
中序遍历
例子
33、二叉树的后序遍历
后序遍历是先遍历左子树，再遍历右子树，最后才遍历根节点。若一棵二叉树如下，则前序遍历的顺序为：LRD，也就是说一开始先往左方前进，直到无法前进才再往节点的右方前进，最后才处理节点。
例
例子
34、二叉树的查找
二叉查找树的条件：每个节点的数据要大于左子节点的数据，且要小于右子节点的数据。
二叉树的查找
35、二叉树的节点删除
先判断欲删除的节点是否存在于该二叉树中。我们在删除一个节点后，必须要维持满足二叉查找树数据排列的原则：左子节点<节点<右子节点。
当欲删除一无左子树也无右子树的节点时，需要考虑到两种情况：
（1）为根节点
如欲删除无左、右子树的根节点，只需将根节点指针root指向NULL即可。
（2）非根节点
若一节点为无左、右子树的非根节点，那么该节点必为叶节点。如果节点为父节点的左子节点，则将父节点的zuo zhi左指针指向NULL，相同的，若节点为父节点的右子节点，则将父节点的右指针指向NULL。
