《数据结构》必须掌握的知识点与算法
第一章绪论
1、算法的五个重要特性（有穷性、确定性、可行性、输入、输出）
2、算法设计的要求（正确性、可读性、健壮性、效率与低存储量需求）
3、算法与程序的关系：
（1）一个程序不一定满足有穷性。例操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。
（2）程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。
（3）一个算法若用程序设计语言来描述，则它就是一个程序。
4、算法的时间复杂度的表示与计算（这个比较复杂，具体看算法本身，一般关心其循环的次数与N的关系、函数递归的计算）
第二章线性表
1、线性表的特点：
（1）存在唯一的第一个元素；（这一点决定了图不是线性表）
（2）存在唯一的最后一个元素；
（3）除第一个元素外，其它均只有一个前驱（这一点决定了树不是线性表）
（4）除最后一个元素外，其它均只有一个后继。
2、线性表有两种表示：顺序表示（数组）、链式表示（链表），栈、队列都是线性表，他们都可以用数组、链表来实现。
3、顺序表示的线性表（数组）地址计算方法：
（1）一维数组，设DataType a[N]的首地址为A0，每一个数据（DataType 类型）占m个字节，则a[k]的地址为：A a[k]＝A0+m*k（其直接意义就是求在数据a[k]的前面有多少个元素，每个元素占m个字节）
（2）多维数组，以三维数组为例，设DataType a[M][N][P]的首地址为A000，每一个数据（DataType类型）占m个字节，则在元素a[i][j][k]的前面共有元素个数为：M*N*i+N*j+k，其其地址为：
A a[i][j][k]＝A000+m*(M*N*i+N*j+k)；
4、线性表的归并排序：
设两个线性表均已经按非递减顺序排好序，现要将两者合并为一个线性表，并仍然接非递减顺序。可见算法2.2
5、掌握线性表的顺序表示法定义代码，各元素的含义；
6、顺序线性表的初始化过程，可见算法2.3
7、顺序线性表的元素的查找。
8、顺序线性表的元素的插入算法，注意其对于当原来的存储空间满了后，追加存储空间（就是每次增加若干个空间，一般为10个）的处理过程，可见算法2.4
9、顺序线性表的删除元素过程，可见算法2.5
10、顺序线性表的归并算法，可见算法2.7
11、链表的定义代码，各元素的含义，并能用图形象地表示出来，以利分析；
12、链表中元素的查找
13、链表的元素插入，算法与图解，可见算法2.9
14、链表的元素的删除，算法与图解，可见算法2.10
15、链表的创建过程，算法与图解，注意，链表有两种（向表头生长、向表尾生长，分别用在栈、队列中），但他们的区别就是在创建时就产生了，可见算法2.11
16、链表的归并算法，可见算法2.12
17、建议了解所谓的静态单链表（即用数组的形式来实现链表的操作），可见算法2.13
18、循环链表的定义，意义
19、循环链表的构造算法（其与单链表的区别是在创建时确定的）、图解
20、循环链表的插入、删除算法、图解
21、双向链表的定义，意义
22、双向链表的构造算法（其与单链表的区别是在创建时确定的）、图解
23、双向链表的插入、删除算法、图解，可见算法2.18、2.19
24、补充：在循环链表中，只设立一个表尾指针比只设立一个表头指针更方便些，为什么？
第三章栈和队列
1、栈的顺序表示与实现
2、栈的链表表示与实现
3、栈的入栈、出栈操作算法
4、栈的几个经典应用（迷宫、表达式求值）
5、栈与递归的实现，如Hanoi塔问题
6、队列链式表示与实现
7、链式队列的入队、出队操作算法
8、循环队列的表示（顺序表示）和实现，特别注意其判满、判空方法、入队操作、出队操作的实现（特别重要，考得频率很大）
9、补充：共享栈的方法与实现（即两个栈共享一个空间，他们采用栈顶相向，迎面增长的存储方式）
10、补充：用两个栈来模拟一个队列的思路、算法
11、补充：表达式（前缀、后缀、中缀）的表达互换，这个操作要求对栈在表达式求值中的应用相当熟练，并要求对后面的二叉树相当熟练
12、补充：了解双端队列（只需了解）
13、补充：链栈比顺序栈的优点与缺点
14、补充：一系列元素依次入栈再出栈的顺序，经典题目为：有5个元素，其入栈次序为A、B、C、D、E，以下哪种出栈的顺序是不可能的？
15、补充：了解用循环链表实现队列，注意在该循环链表中只有一个头指针或一个表尾指针（只需了解）
16、补充：根据给出的数学公式，写出对应的递归算法，最经典的就是用递归求阶乘。
第六章 树和二叉树
1、几个重要的概念：树、森林、子树、根、终端结点（叶子）、非终端结点、双亲、孩子、兄弟、堂兄弟、度、深度、有序树、无序树、二叉树、k 叉树、完全二叉树、满二叉树、线索二叉树；
2、二叉树的5种基本形态；
3、二叉树的5个重要性质：
（1）在二叉树的第i 层上至多有2i －1个结点（i ≥1）；
（2）深度为k 的二叉树至多有2k －1个结点，（k ≥1）
（3）对任何一棵二叉树T ，如果其终端结点（叶子）数为n 0，度为2的结点数为n 2，则n 0=n 2+1；
（4）具有n 个结点的完全二叉树的深度为⎣⎦1log 2+n ； （5）如果对一棵有n 个结点的完全二叉树（其深度为⎣⎦1log 2+n ）的结点按性层序编号（从第1层到第⎣⎦1log 2+n 层，每层从左到右），则对任一结点i （1≤i ≤n ），有：
（i ）如果i =1，则结点i 是二叉树的根，无双亲；如果i >1,则其双亲Parent （i ）是结点⎣⎦2i
（ii ）如果2i >n ，则结点i 无左孩子（结点i 为叶子结点）；否则其左孩子LChild （i ）是结点2i ；
（iii ）如果2i +1>n ，则结点i 无右孩子；否则其右孩子RChild （i ）是结点2i +1
利用完全二叉树的上述性质，能处理大多数完全二叉树的计算题；
4、二叉树的存储结构：
（1）了解顺序存储结构，只做了解；
（2）链式存储结构，重要，需要掌握，后面的算法都是基于此结构；
5、二叉树的遍历：
（1）能对任意一棵二叉树进行手动前序、中序、后序遍历；
（2）能将由前序+中序、后序+中序给出的序列还原成一棵二叉树；
（3）能将一个数学表达式用中序方法将其用二叉树画出来，并能写出其前缀（波兰式）、中缀、后缀（逆波兰式）表达出来；
6、二叉树的遍历递归算法（注意前、中、后序三个算法只有细微的差别），可见算法6.1，而他们的非递归算法不作要求；
7、建立二叉树链表的递归算法，可见算法6.4；
8、线索二叉树的存储结构图；
9、能用手画出任意二叉树对应的线索二叉树（中序、后序线索）；
10、线索二叉树的非递归遍历算法，可见算法6.5；
11、理解线索二叉树的中序线索化过程算法，可见算法6.6；
12、手动写出任意森林、树的深度优先、广度优先遍历顺序；
13、森林、二叉树的转换过程，能用手画出即可；
14、哈夫曼树的相关概念：路径长度、带权路径长度WPL 、权值；
