《数据结构》必须掌握的知识点与算法
《数据结构》必须掌握的知识点与算法
第⼀章 绪论
1、算法的五个重要特性（有穷性、确定性、可⾏性、输⼊、输出）
2、算法设计的要求（正确性、可读性、健壮性、效率与低存储量需求）
3、算法与程序的关系：
（1）⼀个程序不⼀定满⾜有穷性。例操作系统，只要整个系统不遭破坏，它将永远不会停⽌，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是⼀个算法。
（2）程序中的指令必须是机器可执⾏的，⽽算法中的指令则⽆此限制。算法代表了对问题的解，⽽程序则是算法在计算机上的特定的实现。
（3）⼀个算法若⽤程序设计语⾔来描述，则它就是⼀个程序。
4、算法的时间复杂度的表⽰与计算（这个⽐较复杂，具体看算法本⾝，⼀般关⼼其循环的次数与N的关系
、函数递归的计算）
第⼆章 线性表
1、线性表的特点：
（1）存在唯⼀的第⼀个元素；（这⼀点决定了图不是线性表）
（2）存在唯⼀的最后⼀个元素；
（3）除第⼀个元素外，其它均只有⼀个前驱（这⼀点决定了树不是线性表）
（4）除最后⼀个元素外，其它均只有⼀个后继。
2、线性表有两种表⽰：顺序表⽰（数组）、链式表⽰（链表），栈、队列都是线性表，他们都可以⽤数组、链表来实现。
3、顺序表⽰的线性表（数组）地址计算⽅法：
（1）⼀维数组，设DataType  a[N]的⾸地址为A0，每⼀个数据（DataType类型）占m个字节，则a[k]的地址为：Aa[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，其其地址为：
Aa[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，如果其终端结点（叶⼦）数为n0，度为2的结点数为n2，则n0=n2+1；
（4）具有n个结点的完全⼆叉树的深度为；
（5）如果对⼀棵有n个结点的完全⼆叉树（其深度为）的结点按性层序编号（从第1层到第层，每层从左到右），则对任⼀结点
i（1≤i≤n），有：
（i）如果i=1，则结点i是⼆叉树的根，⽆双亲；如果i>1，则其双亲Parent（i）是结点
（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、权值；
15、⼆叉哈夫曼树的构造过程，能⽤⼿动构造，并能将构造好的树⽤编码表⽰出来；
16、了解哈夫曼树的构造算法，可见算法6.12，只需要了解，⽆需掌握；
17、记住树的记数公式：对⼀棵有n个结点的有棵不同的⼆叉树
18、补充：⼆叉排序树、插⼊、删除结点的操作（在查⼀章中有详述）；
19、补充：满⼆叉树、完全⼆叉树⽤数组存储⽅式，其元素、结点对应关系；
20、补充：求⼆叉树的⾼度（深度）算法；
21、补充：将⼆叉树中左、右孩⼦交换的算法；
22、补充：将⽤数组存储的完全⼆叉树转换成链式结构的算法；
23、补充：对⽤数组存储的完全⼆叉树进⾏⾮递归的前序、中序、后序遍历算法；
24、补充：求⼆叉树中叶⼦数、度为1的、度为2的结点数算法；
25、补充：对于K叉树，其结点总数为N，求出该树的最⼤⾼度、⾼⼩⾼度；
26、补充：构造结点数为n的k叉哈夫曼树（其所有的结点要么度为0，要么度为k），注意⼀般都需要增加m个权为0的结点（称为虚结点），其中如果叶⼦结点数⽬不⾜以构成正则的k叉树（树中只有度为k或0的结点），即不满⾜(n-1)MOD(k-1)=0（其中MOD是取余运算），需要添加权为0的结点，添加的个数为m=k-(n-1)MOD(k-1)-1。添加的位置应该是距离根结点的最远处。假设n=10，k=3，则需要添加1个权为0的虚结点（其字母可以为空）。
第七章 图
1、图的⼏个重要概念：顶点、弧、弧尾、弧头、边、有向图、⽆向图、完全图、邻接点、⼊度、出度、度、路径、回路（环）、连通图、连通分量、强连通图、强连通分量、⽣成森林、关节点、重连通图、AOV-⽹、AOE-⽹；
2、图的⼏种存储、表⽰⽅法：数组表⽰法（重要）、邻接表（最重要，应⽤最⼴）、逆邻接表（掌握）、⼗字链表（理解）、邻接多重表（了解），并能⼤致掌握他们各种⽅法表⽰的优缺点；
3、图的两种遍历顺序：深度、⼴度优先，建议同时掌握其算法；
4、图的⽣成树和⽣成森林（只需掌握⼿画⽅法）；
5、图的最⼩⽣成树的两种算法：普⾥姆（Prim）算法（实质是顶点优先）、克鲁斯卡尔（Kruskal）算
法（实质是边优先），掌握他们的⼿动构造过程，了解算法；
6、理解求关节点算法，可见算法7.10、7.11；
7、了解拓扑排序；
8、掌握由AOE-⽹得到关键路径的⽅法（⼿动），了解算法（7.13、7.14）；
9、掌握最短路径的⼿动求解过程、⽅法（两种：迪杰斯特拉Dijkstra、弗洛伊德Floyd），了解算法；
10、补充：Prim算法、Kruskal算法、Dijkstra算法、Floyd算法的时间复杂度；
11、补充：了解拓扑排序算法；
12、补充：能将图的抽象定义，如有向图G＝（V，{A}），V＝{v1，v2，v3，v4}，A＝{

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。