数据结构知识点总结整理资料.docx
《数据结构知识点总结整理资料.docx》由会员分享，可在线阅读，更多相关《数据结构知识点总结整理资料.docx（23页珍藏版）》请在冰点文库上搜索。
数据结构知识点总结整理资料
数据结构知识点总结整理资料
数据结构知识点总结整理
0、常考基础必知必会
A.排序:
排序有几种,各种排序的比较,哪些排序是稳定的,快排的算法;
B.查找:
哈希查找、二叉树查找、折半查找的对比,哈希映射和哈希表的区别?
C.链表和数组的区别,在什么情况下用链表什么情况下用数组?
D.栈和队列的区别?
E.多态,举例说明;overload和override的区别?
F.字符串有关的函数,比如让你写一个拷贝字符串的函数啊,或者字符串反转啊什么的。
strcpy
和memcpy?
G.继承、多继承?
H.面向对象有什么好处?
I.说说static的与众不同之处,如果一个变量被声明为static,它会被分配在哪里?
在什么时候
分配空间等?
J.什么是虚函数、纯虚函数、虚的析构函数,用途?
K.内存泄漏及解决方法?
网络部分:
OSI模型7层结构,TCP/IP模型结构?
B.TCP/UDP区别?
C.TCP建立连接的步骤?
D.香农定理?
1、二叉树三种遍历的非递归算法（背诵版）本贴给出二叉树先序、中序、后序三种遍历的非递归算法,此三个算法可视为标准算法,
直接用于考研答题。
1.先序遍历非递归算法
#definesize100
typedefstruct
BitreeElem[size];inttop;
SqStack;
voidPreOrderUnrecBitreet
SqStacks;StackInits;pt;whilep!
null||!
StackEmptyswhilep!
null//遍历左子树visitep-data;pushs,p;pp-lchild;//endwhileif!
StackEmptys//通过下一次循环中的内嵌while实现右子树遍历ppops;pp-rchild;//endif//endwhile//PreOrderUnrec
2.中序遍历非递归算法
#definesize100
typedefstruct
BitreeElem[size];inttop;
SqStack;
voidInOrderUnrecBitreet
SqStacks;StackInits;pt;whilep!
null||!
StackEmptyswhilep!
null//遍历左子树pushs,p;pp-lchild;//endwhileif!
StackEmptysppops;visitep-data;//访问根结点pp-rchild;//通过下一次循环实现右子树遍历//endif//endwhile
//InOrderUnrec
3.后序遍历非递归算法
#definesize100
typedefenumL,Rtagtype;
typedefstructBitreeptr;tagtypetag;
stacknode;
typedefstruct
stacknodeElem[size];inttop;
SqStack;
//后序遍历
voidPostOrderUnrecBitreet
SqStacks;stacknodex;StackInits;pt;dowhilep!
null//遍历左子树x.ptrp;x.tagL;//标记为左子树pushs,x;pp-lchild;while!
StackEmptys&&s.Elem[s.top].tagRxpops;px.ptr;visitep-data;//tag为R,表示右子树访问完毕,故访问根结点if!
StackEmptyss.Elem[s.top].tagR;//遍历右子树ps.Elem[s.top].ptr-rchild;while!
StackEmptys;
//PostOrderUnrec
4.层次遍历算法
//二叉树的数据结构
structBinaryTree
intvalue;//不写模板了,暂时用整形代替节点的数据类型BinaryTree*left;BinaryTree*right;
;
BinaryTree*root;//已知二叉树的根节点
//层次遍历
voidLevelconstBinaryTree*root
Queue*bufnewQueue;//定义一个空队列,假设此队列的节点数据类型也是整形
的BinaryTreet;//一个临时变量buf.push_backroot;//令根节点入队whilebuf.emptyfalse//当队列不为空pbuf.front;//取出队列的第一个元素coutp-value'';ifp-left!
NULL//若左子树不空,则令其入队q.pushp-left;ifp-right!
NULL//若右子树不空,则令其入队q.pushp-right;buf.pop;//遍历过的节点出队coutendl;
2、线性表
（1）性表的链式存储方式及以下几种常用链表的特点和运算:
单链表、循环链表,双向链表,
双向循环链表。
（2）单链表的归并算法、循环链表的归并算法、双向链表及双向循环链表的插入和删除算法等
都是较为常见的考查方式。
（3）单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储结构的各自好
处。
3、栈与队列
你可以问一下自己是不是已经知道了以下几点:
1栈、队列的定义及其相关数据结构的概念,包括:
顺序栈,链栈,共享栈,循环队列,
链队等。
栈与队列存取数据（请注意包括:
存和取两部分）的特点。
2递归算法。
栈与递归的关系,以及借助栈将递归转向于非递归的经典算法:
n!
阶乘问题,
fib数列问题,hanoi问题,背包问题,二叉树的递归和非递归遍历问题,图的深度遍历与栈的
关系等。
其中,涉及到树与图的问题,多半会在树与图的相关章节中进行考查。
3栈的应用:
数值表达式的求解,括号的配对等的原理,只作原理性了解,具体要求考查
此为题目的算法设计题不多。
4循环队列中判队空、队满条件,循环队列中入队与出队（循环队列在插入时也要判断其
是否已满,删除时要判断其是否已空）算法。
【循环队列的队空队满条件为了方便起见,约定:
初始化建空队时,令frontrear0,当队空时:
frontrear,当队满时:
frontrear亦成立,因此只凭等式frontrear无法判断队空还是队满。
有两种方法处理上述问题:
（1）另设一个标志位以区别队列是空还是满。
（2）少用一个元素空间,约定以“队列头指针front在队尾指针rear的下一个位置上”作
为队列“满”状态的标志。
队空时:
frontrear,队满时:
rear+1%sizefront】如果你已经对上面的几点了如指掌,栈与队列一章可以不看书了。
注意,我说的是可以不
看书,并不是可以不作题哦。
////////////////////////////////////////////////////////////////////////////////////////////////
循环队列的主要操作:
1创建循环队列2初始化循环队列3判断循环队列是否为空4判断循环队列是否为满5入队、出队//空出头尾之间的一个元素不用#include#include#defineSIZE100typedefstructintelem[SIZE];intfront,rear;Quque;//定义队头intinitQueQuque**q//初始化*q-front0;*q-rear0;intisFullQuque*qifq-frontq-rear+1%SIZE//判满空出一个元素不用刘勉刚return1;elsereturn0;intinsertQueQuque**q,intelemifisFull*qreturn-1;*q-elem[*q-rear]elem;*q-rear*q-rear+1%SIZE;//插入return0;intisEmptyQuque*qifq-frontq-rear//判空return1;elsereturn0;intdeleteQueQuque**q,int*pelemifisEmpty*qreturn0;*pelem*q-elem[*q-front];*q-front*q-front+1%SIZE;return0;
4、串
串一章需要攻破的主要堡垒有:
1.串的基本概念,串与线性表的关系（串是其元素均为字符型数据的特殊线性表）,空串与空
格串的区别,串相等的条件;
2.串的基本操作,以及这些基本函数的使用,包括:
取子串,串连接,串替换,求串长等等。
运用串的基本操作去完成特定的算法是很多学校在基本操作上的考查重点。
3.顺序串与链串及块链串的区别和联系,实现方式。
4.KMP算法思想。
KMP中next数组以及nextval数组的求法。
明确传统模式匹配算法的不足,
明确next数组需要改进。
可能进行的考查方式是:
求next和nextval数组值,根据求得的next
或nextval数组值给出运用KMP算法进行匹配的匹配过程。
5、多维数组和广义表
矩阵包括:
对称矩阵,三角矩阵,具有某种特点的稀疏矩阵等。
熟悉稀疏矩阵的三种不同存储方式:
三元组,带辅助行向量的二元组,十字链表存储。
掌握将稀疏矩阵的三元组或二元组向十字链表进行转换的算法。
6、树与二叉树
树一章的知识点包括:
二叉树的概念、性质和存储结构,二叉树遍历的三种算法（递归与非递归）,在三种基本
遍历算法的基础上实现二叉树的其它算法,线索二叉树的概念和线索化算法以及线索化后的查找
算法,最优二叉树的概念、构成和应用,树的概念和存储形式,树与森林的遍历算法及其与二叉
树遍历算法的联系,树与森林和二叉树的转换。
1二叉树的概念、性质和存储结构
考查方法可有:
直接考查二叉树的定义,让你说明二叉树与普通双分支树左右子树无序的区别;
考查满二叉树和完全二叉树的性质,普通二叉树的五个性质:
A.第i层的最多结点数,
B.深度为k的二叉树的最多结点数,
C.n0n2+1的性质,
D.n个结点的完全二叉树的深度,
E.顺序存储二叉树时孩子结点与父结点之间的换算关系（root从1开始,则左为:
2*i,右为:
2*i+1）。
二叉树的顺序存储和二叉链表存储的各自优缺点及适用场合,二叉树的三叉链表表示方法。
2二叉树的三种遍历算法这一知识点掌握的好坏,将直接关系到树一章的算法能否理解,进而关系到树一章的算法
设计题能否顺利完成。
二叉树的遍历算法有三种:
先序,中序和后序。
其划分的依据是视其每个
算法中对根结点数据的访问顺序而定。
不仅要熟练掌握三种遍历的递归算法,理解其执行的实际
步骤,并且应该熟练掌握三种遍历的非递归算法。
由于二叉树一章的很多算法,可以直接根据三
种递归算法改造而来（比如:
求叶子个数）,所以,掌握了三种遍历的非递归算法后,对付诸如:
“利用非递归算法求二叉树叶子个数”这样的题目就下笔如有神了。
3可在三种遍历算法的基础上改造完成的其它二叉树算法:
求叶子个数,求二叉树结点总数,求度为1或度为2的结点总数,复制二叉树,建立二叉
树,交换左右子树,查找值为
n的某个指定结点,删除值为n的某个指定结点,诸如此类等等
等等。
如果你可以熟练掌握二叉树的递归和非递归遍历算法,那么解决以上问题就是小菜一碟了。
4线索二叉树:
线索二叉树的引出,是为避免如二叉树遍历时的递归求解。
众所周知,递归虽然形式上比
较好理解,但是消耗了大量的内存资源,如果递归层次一多,势必带来资源耗尽的危险,为了避
免此类情况,线索二叉树便堂而皇之地出现了。
对于线索二叉树,应该掌握:
线索化的实质,三
种线索化的算法,线索化后二叉树的遍历算法,基本线索二叉树的其它算法问题（如:
查找某一
类线索二叉树中指定结点的前驱或后继结点就是一类常考题）。
5最优二叉树（哈夫曼树）:
最优二叉树是为了解决特定问题引出的特殊二叉树结构,它的前提是给二叉树的每条边赋
予了权值,这样形成的二叉树按权相加之和是最小的。
最优二叉树一节,直接考查算法源码的很
少,一般是给你一组数据,要求你建立基于这组数据的最优二叉树,并求出其最小权值之和,此
类题目不难,属送分题。
6树与森林:
二叉树是一种特殊的树,这种特殊不仅仅在于其分支最多为2以及其它特征,一个最重要
的特殊之处是在于:
二叉树是有序的!
即:
二叉树的左右孩子是不可交换的,如果交换了就成了
另外一棵二叉树。
树与森林的遍历,不像二叉树那样丰富,他们只有两种遍历算法:
先根与
后根（对于森林而言称作:
先序与后序遍历）。
此二者的先根与后根遍历与二叉树中的遍历算法
是有对应关系的:
先根遍历对应二叉树的先序遍历,而后根遍历对应二叉树的中序遍历。
二叉树、
树与森林之所以能有以上的对应关系,全拜二叉链表所赐。
二叉树使用二叉链表分别存放他的左
右孩子,树利用二叉链表存储孩子及兄弟（称孩子兄弟链表）,而森林也是利用二叉链表存储孩
子及兄弟。
7、图1.图的基本概念:
图的定义和特点,无向图,有向图,入度,出度,完全图,生成子图,路径
长度,回路,（强）连通图,（强）连通分量等概念。
2.图的几种存储形式:
邻接矩阵,（逆）邻接表,十字链表及邻接多重表。
在考查时,有
的学校是给出一种存储形式,要求考生用算法或手写出与给定的结构相对应的该图的另一种存储
形式。
3.考查图的两种遍历算法:
深度遍历和广度遍历深度遍历和广度遍历是图的两种基本的遍历算法,这两个算法对图一章的重要性等同于
“先序、中序、后序遍历”对于二叉树一章的重要性。
在考查时,图一章的算法设计题常常是基
于这两种基本的遍历算法而设计的,比如:
“求最长的最短路径问题”和“判断两顶点间是否存
在长为K的简单路径问题”,就分别用到了广度遍历和深度遍历算法。
4.生成树、最小生成树的概念以及最小生成树的构造:
PRIM算法和KRUSKAL算法。
考查时,一般不要求写出算法源码,而是要求根据这两种最小生成树的算法思想写出其构
造过程及最终生成的最小生成树。
5.拓扑排序问题:
拓扑排序有两种方法,一是无前趋的顶点优先算法,二是无后继的顶点优先算法。
换句话
说,一种是“从前向后”的排序,一种是“从后向前”排。
当然,后一种排序出来的结果是“逆
拓扑有序”的。
6.关键路径问题:
这个问题是图一章的难点问题。
理解关键路径的关键有三个方面:
一是何谓关键路径;
二是最早时间是什么意思、如何求;
三是最晚时间是什么意思、如何求。
简单地说,最早时间是通过“从前向后”的方法求的,而最晚时间是通过“从后向前”的方法求
解的,并且,要想求最晚时间必须是在所有的最早时间都已经求出来之后才能进行。
在实际设计关键路径的算法时,还应该注意以下这一点:
采用邻接表的存储结构,求最早
时间和最晚时间要采用不同的处理方法,即:
在算法初始时,应该首先将所有顶点的最早时间全
部置为0。
关键路径问题是工程进度控制的重要方法,具有很强的实用性。
7.最短路径问题:
与关键路径问题并称为图一章的两只拦路虎。
概念理解是比较容易的,关键是算法的理解。
最短路径问题分为两种:
一是求从某一点出发到其余各点的最短路径（单源最短路径）;二是求
图中每一对顶点之间的最短路径。
这个问题也具有非常实用的背景特色,一个典型的应该就是旅
游景点及旅游路线的选择问题。
解决第一个问题用DIJSKTRA算法,解决第二个问题用FLOYD
算法,注意区分。
8、查找（search）
先弄清楚以下几个概念:
关键字、主关键字、次关键字的含义;静态查找与动态查找的含义及区
别;平均查找长度ASL的概念及在各种查找算法中的计算方法和计算结果,特别是一些典型结
构的ASL值,应该记住。
一般将search分为三类:
在顺序表上的查找;在树表上的查找;在哈希表上的查找。
（1）线性表上的查找:
主要分为三种线性结构:
顺序表?
?
传统查找方法:
逐个比较;
有序顺序表?
?
二分查找法（注意适用条件以及其递归实现方法）;
索引顺序表?
?
对索引结构,采用索引查找算法。
注意这三种表下的ASL值以及三种算法的实
现。
（2）树表上的查找:
树表主要分为以下几种:
二叉排序树（即二叉查找树）,平衡二叉查找树（AVL树）,B
树,键树。
其中,尤以前两种结构为重,也有部分名校偏爱考B树的。
由于二叉排序树与平衡
二叉树是一种特殊的二叉树。
二叉排序树,简言之,就是“左小右大”,它的中序遍历结果是一个递增的有序序列。
平衡二叉
排序树是二叉排序树的优化,其本质也是一种二叉排序树,只不过,平衡排序二叉树对左右子树
的深度有了限定:
深度之差的绝对值不得大于1。
对于二叉排序树,“判断某棵二叉树是否二叉
排序树”这一算法经常被考到,可用递归,也可以用非递归。
平衡二叉树的建立也是一个常考点,
但该知识点归根结底还是关注的平衡二叉树的四种调整算法,调整的一个参照是:
调整前后的中
序遍历结果相同。
B树是二叉排序树的进一步改进,也可以把B树理解为三叉、四叉.排序树。
除B树的查
找算法外,应该特别注意一下B树的插入和删除算法,因为这两种算法涉及到B树结点的分裂
和合并,是一个难点。
键树（keywordtree）,又称数字搜索树（digitalsearchtree）或字
符树。
trie树也可说等同于键树或属于键树的一种。
键树特别适用于查找英文单词的场合。
一般
不要求能完整描述算法源码,多是根据算法思想建立键树及描述其大致查找过程。
（3）基于哈希表的查找算法:
哈希译自“hash”一词,意为“散列”或“杂凑”。
哈希表查找的基本思想是:
根据当前
待查找数据的特征,以记录关键字为自变量,设计一个function,该函数对关键字进行转换后,
其解释结果为待查的地址。
基于哈希表的考查点有:
哈希函数的设计,冲突解决方法的选择及冲
突处理过程的描述。
9、内部排序
考查你对书本上的各种排序算法及其思想以及其优缺点和性能指标（时间复杂度）能否了如指掌。
排序方法分类有:
插入、选择、交换、归并、计数等五种排序方法。
（1）插入排序中又可分为:
直接插入、折半插入、2路插入（?
）、希尔排序。
这几种插
入排序算法的最根本的不同点,说到底就是根据什么规则寻找新元素的插入点。
直接插入是依次
寻找,折半插入是折半寻找,希尔排序,是通过控制每次参与排序的数的总范围“由小到大”的
增量来实现排序效率提高的目的。
（2）交换排序,又称冒泡排序,在交换排序的基础上改进又可以得到快速排序。
快速排序的思
想,一语以敝之:
用中间数将待排数据组一分为二。
（3）选择排序可以分为:
简单选择、树选择、堆排序。
选择排序相对于前面几种排序算法
来说,难度大一点。
这三种方法的不同点是,根据什么规则选取最小的数。
简单选择,是通过简单的数组遍历方案确定最小数;
树选择,是通过“锦标赛”类似的思想,让两数相比,不断淘汰较大（小）者,最终选出最小（大）
数;
而堆排序,是利用堆这种数据结构的性质,通过堆元素的删除、调整等一系列操作将最小数选出
放在堆顶。
堆排序中的堆建立、堆调整是重要考点。
（4）归并排序,是通过“归并”这种操作完成排序的目的,既然是归并就必须是两者以上的数
据集合才可能实现归并。
所以,在归并排序中,关注最多的就是2路归并。
算法思想比较简单,
有一点,要铭记在心:
归并排序是稳定排序。
（5）基数排序,是一种很特别的排序方法,也正是由于它的特殊,所以,基数排序就比较
适合于一些特别的场合,比如扑克牌排序问题等。
基数排序,又分为两种:
多关键字的排序（扑
克牌排序）,链式排序（整数排序）。
基数排序的核心思想也是利用“基数空间”这个概念将问
题规模规范、变小,并且,在排序的过程中,只要按照基排的思想,是不用进行关键字比较的,
这样得出的最终序列就是一个有序序列。
本章各种排序算法的思想以及伪代码实现,及其时间复杂度都是必须掌握的。
//////////////////////////////////////////////稳定性分析
////////////////////////////////////////////////
排序算法的稳定性,通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序
后它们两个的前后位置顺序相同。
稳定性的好处:
若排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,第
一个键排序的结果可以为第二个键排序所用。
基数排序就是这样,先按低位排序,逐次按高位排
序,低位相同的元素其顺序再高位也相同时是不会改变的。
另外,如果排序算法稳定,对基于比
较的排序算法而言,元素交换的次数可能会少一些个人感觉,没有证实。
分析一下常见的排序算法的稳定性,每个都给出简单的理由。
1冒泡排序冒泡排序就是把小的元素往前调或者把大的元素往后调。
比较是相邻的两个元素比较,交
换也发生在这两个元素之间。
所以,如果两个元素相等,我想你是不会再无聊地把他们俩交换一
下的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也
不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。
2选择排序选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里
面给第二个元素选择第二小的,依次类推,直到第n-1个元素,第n个元素不用选择了,因为
升级会员 