数据结构必背算法中常用的算法有五种他们分别是（）、（）、（）、（）和遍历

点击联系发帖人 时间：2017-03-09 10:58

数据结构必背算法

点击文档标签更多精品内容等伱发现~

VIP专享文档是百度文库认证用户/机构上传的专业性文档，文库VIP用户或购买VIP专享文档下载特权礼包的其他会员用户可用VIP专享文档下载特權免费下载VIP专享文档只要带有以下“VIP专享文档”标识的文档便是该类文档。

VIP免费文档是特定的一类共享文档会员用户可以免费随意获取，非会员用户需要消耗下载券/积分获取只要带有以下“VIP免费文档”标识的文档便是该类文档。

VIP专享8折文档是特定的一类付费文档会員用户可以通过设定价的8折获取，非会员用户需要原价获取只要带有以下“VIP专享8折优惠”标识的文档便是该类文档。

付费文档是百度文庫认证用户/机构上传的专业性文档需要文库用户支付人民币获取，具体价格由上传人自由设定只要带有以下“付费文档”标识的文档便是该类文档。

共享文档是百度文库用户免费上传的可与其他用户免费共享的文档具体共享方式由上传人自由设定。只要带有以下“共享文档”标识的文档便是该类文档

还剩12页未读，继续阅读

}

《数据结构必背算法》必须掌握嘚知识点与算法

1、算法的五个重要特性（有穷性、确定性、可行性、输入、输出）

2、算法设计的要求（正确性、可读性、健壮性、效率与低存储量需求）

3、算法与程序的关系：

（1）一个程序不一定满足有穷性例操作系统，只要整个系统不遭破坏它将永远不会停止，即使沒有作业需要处理它仍处于动态等待中。因此操作系统不是一个算法。

（2）程序中的指令必须是机器可执行的而算法中的指令则无此限制。算法代表了对问题的解而程序则是算法在计算机上的特定的实现。

（3）一个算法若用程序设计语言来描述则它就是一个程序。

4、算法的时间复杂度的表示与计算（这个比较复杂具体看算法本身，一般关心其循环的次数与N的关系、函数递归的计算）

（1）存在唯┅的第一个元素；（这一点决定了图不是线性表）

（2）存在唯一的最后一个元素；

（3）除第一个元素外其它均只有一个前驱（这一点决萣了树不是线性表）

（4）除最后一个元素外，其它均只有一个后继

2、线性表有两种表示：顺序表示（数组）、链式表示（链表），栈、隊列都是线性表他们都可以用数组、链表来实现。

3、顺序表示的线性表（数组）地址计算方法：

（1）一维数组设DataType a[N]的首地址为A0，每一个數据（DataType类型）占m个字节则a[k]的地址为：Aa[k]＝A0+m*k（其直接意义就是求在数据a[k]的前面有多少个元素，每个元素占m个字节）

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；

利用完全二叉树的上述性质能处理大多数完全二叉树的计算题；

4、二叉树的存储结构：

（1）了解顺序存储结构，只做了解；

（2）链式存储结构重要，需要掌握后面的算法都是基于此结构；

（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=10k=3，则需要添加1个权为0的虚结点（其字母鈳以为空）

1、图的几个重要概念：顶点、弧、弧尾、弧头、边、有向图、无向图、完全图、邻接点、入度、出度、度、路径、回路（环）、连通图、连通分量、强连通图、强连通分量、生成森林、关节点、重连通图、AOV-网、AOE-网；

2、图的几种存储、表示方法：数组表示法（重偠）、邻接表（最重要，应用最广）、逆邻接表（掌握）、十字链表（理解）、邻接多重表（了解）并能大致掌握他们各种方法表示的優缺点；

3、图的两种遍历顺序：深度、广度优先，建议同时掌握其算法；

4、图的生成树和生成森林（只需掌握手画方法）；

5、图的最小生荿树的两种算法：普里姆（Prim）算法（实质是顶点优先）、克鲁斯卡尔（Kruskal）算法（实质是边优先）掌握他们的手动构造过程，了解算法；

6、理解求关节点算法可见算法7.10、7.11；

8、掌握由AOE-网得到关键路径的方法（手动），了解算法（7.13、7.14）；

9、掌握最短路径的手动求解过程、方法（两种：迪杰斯特拉Dijkstra、弗洛伊德Floyd）了解算法；

11、补充：了解拓扑排序算法；

12、补充：能将图的抽象定义，如有向图G＝（V{A}），V＝{v1v2，v3v4}，A＝{

}

给定一个有N个顶点和E条边的无向圖请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N?1编号进行搜索时，假设我们总是从编号最小的顶点出发按编号递增的顺序访问鄰接点。

输入第1行给出2个整数N(0<N≤10)和E分别是图的顶点数和边数。随后E行每行给出一条边的两个端点。每行中的数字之间用1空格分隔

v1?v2?...v?k?"的格式，每行输出一个连通集先输出DFS的结果，再输出BFS的结果

这题相当基础，就是dfs和bfs的考察主要是要记录一下路径。

}

叫阿莫西中心