完整word版数据结构期末复习知识点兼容版良心出品必属精品.docx
《完整word版数据结构期末复习知识点兼容版良心出品必属精品.docx》由会员分享，可在线阅读，更多相关《完整word版数据结构期末复习知识点兼容版良心出品必属精品.docx（51页珍藏版）》请在冰点文库上搜索。
完整word版数据结构期末复习知识点兼容版良心出品必属精品
《数据结构》期末复习
复习要点：
第一章
1.相关基本概念：
数据、数据元素（基本单位）、数据项（最小单位）、算法及其特征等；
◎数据：
所有能输入到计算机中并被计算机程序处理的符号总称。
◎数据元素：
基本单位。
◎数据项：
最小单位。
◎算法特征（5点）：
有穷性；确定性；可行性；输入；输出。
2.逻辑结构、存储结构（物理结构）及其类型；
◎逻辑结构有四种基本类型：
集合、线性结构、树形结构和网状结构。
◎数据元素之间的关系有两种不同的表示方法：
顺序映象和非顺序映象，并由此得到两种不同的存储结构：
顺序存储结构和链式存储结构。
◎注：
期中考题目
数据结构分为两大类，即为逻辑结构和存储结构。
其中逻辑结果又分为线性结构和非线性结构，存储结构一共有四种（顺序、链接、索引、散列）。
3.算法分析：
语句频度（执行次数）计算、时间和空间复杂度分析。
表示方法
◎语句频度：
直接写次数。
◎时间复杂度：
O（执行次数）,如：
O（n）。
◎空间复杂度：
O（所需空间）
第二章
1.顺序表（数组）插入、删除、有序表合并算法及其移动次数计算；
12
13
21
24
28
30
42
77
数据元素
序号12345678
表示L.elem[0][1][2][3][4][5][6][7]
◎顺序表插入
算法思想：
如果要在序号5前插入元素e，需要将序号5～8向后移动一个位置。
▲移动次数为4次，公式n-i+1
◎顺序表删除
算法思想：
如果要删除序号5元素，需要将6～8依次向前移动一位
▲移动次数为3次，公式n-i
◎有序表合并
LA=（3,5,8,11）
LB=（2,6,8,9,11,15,20）
则LC=（2,3,5,6,8,8,9,11,11,15,20）
算法思想（以非递减为例）：
La和Lb非递减排列，La与Lb中元素逐个比较，较小的先插入Lc中。
▲注：
非递减是指递增排序，但元素有可能相等，与之相对的有非递增排序。
▲移动次数为（La.length+Lb.length）
2.链表（有无头节点、单双、循环）插入（前、后）、删除（前、本身、后）的指针挂接、建立（不带头节点）算法。
◎单链表
▲每个节点有数据域和指针域datanext
头a1a2a3a4a5a6
带头节点L→
→
→
→
→
→
→
P↑
a1a2a3a4a5a6
不带头节点L→
→
→
→
→
→
P↑
单循环链表
●在P（a3）节点前插入S节点
（1）Q=P;//先让Q指向a3
（2）P=L;//P指向第一个节点（带头结点指向头结点，不带头结点指向a1）
（3）while（P->next!
=Q）P=P->next;//找到a3的前驱a2，P指向a2
（4）S->next=P->next;//P->next为a3，让S->next等于a3
（5）P->next=S;//a2指针域指向节点S
●在P（a3）节点后插入S节点
（1）S-next=P->next;
（2）P->next=S;
●删除P（a3）前一个节点
（1）Q=P;
（2）P=L;
（3）while（P->next->next!
=Q）P=P->next;//找到a1
（4）P->next=P->next->next;//让a1指针域指向a3，从而删除a2
●删除P（a3）节点
（1）Q=P;
（2）P=L;
（3）while（P->next!
=Q）P=P->next;//找到a2
（4）P->next=P->next->next;//让a2指针域指向a4，从而删除a3
●删除P（a3）后一个节点
（1）P->next=P->next->next;//让a3指针域指向a5，从而删除a4
◎双链表
▲每个节点有前驱指针、数据域、后继指针priordatanext
双循环链表
头a1a2a3a4
●在P（a2）节点前插入S节点
▲技巧：
先让S->prior和S->next与链表建立关系
注：
步骤（4）必须在步骤（3）后面
（1）S->next=P;//先让S->next指向a2
（2）S->prior=P->prior;//S->prior指向a1
（3）P->prior->next=S;//再把a1->next指向S
（4）P->prior=S;//a2->prior指向S
●在P（a2）节点后插入S节点
注：
步骤（4）必须在步骤（3）后面
（1）S->prior=P;
（2）S->next=P->next;
（3）P->next->prior=S;//a3->prior指向S
（4）P->next=S;
●删除P（a2）前一个节点a1
（1）Q=P->prior;//Q指向要被删除的a1;
（2）P->prior=P->prior->prior;//P->priro指向头
（3）P->prior->next=P;//头->next指向P
（4）free（Q）;//释放a1的存储空间
●删除P（a2）节点
（1）P->next->prior=p->prior;
（2）P->prior->next=p->next;
（3）free（P）;
●删除P（a2）后一个节点a3
（1）Q=P->next;
（2）P->next=P->next->next;//a2->next指向a4
（3）P->next->prior=P;//a4->prior=P
（4）free（Q）;//释放a3存储空间
◎建立（不带头节点）单链表
读程序：
设n为2（i取0，1）
i=0时，
p↑L↑q↑
i=1时，
→
L↑q↑p↑L↑q↑p↑
→
L↑q↑p↑
第三章
1.栈的进出序列、栈、队列、循环队列的满/空条件;
▲由于栈的插入、删除操作是限制在栈顶进行的，因而后进栈的元素必然是先出栈，0.所以栈是“后进先出”表。
▲由于队列的输入、输出操作分别在队的两端进行，因此先入队的元素必然先输出，故队列又称为“先进先出”表
◎栈的进出序列
例题：
进栈序列为123，可能得到的出栈序列是什么？
答：
共五种123/132/213/231/321
进出栈情况（以132序列为例）：
1进栈→1出栈，输出1→2进栈→3进栈→3出栈→2出栈输出32
◎栈、队列、循环队列的满/空条件
栈空条件：
s.top=s.base;栈满条件：
s.top-s.base=stacksize;
队空条件：
Q.front=Q.rear;队满条件：
q->rear-q->front=MAXSIZE
循环队列空条件：
Q.front=Q.rear
循环队列满条件：
为避免在队满是队头指针和队尾指针也是重合的情况，规定队列中
还有一个空的存储单元时为队满，即为Q.front=（Q.rear+1）MODmaxsize（MOD为取余
运算符）。
因而，这种循环队列不适合用动态数组作为存储结构。
2.栈、队列的存储结构、基本操作算法（双向栈）;
◎栈存储结构
●顺序栈
typedefstruct{
SElemType*base;
SElemType*top;
intstacksize;
}SqStack;
●链式栈
◎队列存储结构
●顺序存储结构
●链式存储结构
◎双向栈
存储结构：
typedef struct{
Elemtype *base[2];
Elemtype *top[2];
}BDStacktype; //双向栈类型
初始化：
StatusInit_Stack（BDStacktype&tws,intm）//初始化一个大小为m的双向栈tws
{
tws.base[0]=（Elemtype*）malloc（sizeof（Elemtype）*m）;
tws.base[1]=tws.base[0]+m;
tws.top[0]=tws.base[0];
tws.top[1]=tws.base[1];
returnOK;
}//Init_Stack
入栈：
Statuspush（BDStacktype&tws,inti,Elemtypex）
//x入栈,i=0表示低端栈,i=1表示高端栈
{
if（tws.top[0]>tws.top[1]）returnOVERFLOW;
//注意此时的栈满条件
if（i==0）*tws.top[0]++=x;
elseif（i==1）*tws.top[1]--=x;
elsereturnERROR;
returnOK;
}//push
出栈：
Statuspop（BDStacktype&tws,inti,Elemtype&x）
//x出栈,i=0表示低端栈,i=1表示高端栈
{
if（i==0）
{
if（tws.top[0]==tws.base[0]）returnOVERFLOW;
x=*--tws.top[0];
}
elseif（i==1）
{
if（tws.top[1]==tws.base[1]）returnOVERFLOW;
x=*++tws.top[1];
}
elsereturnERROR;
returnOK;
}//pop
第四章
1.字符串模式匹配的简单算法；
intIndex（SStringS,SStringT,intpos）
{//算法4.5
//返回子串T在主串S中第pos个字符之后的位置。
//若不存在，则函数值为0。
//其中，T非空，1≤pos≤StrLength（S）。
inti=pos;
intj=1;
while（i<=S[0]&&j<=T[0]）{
if（S[i]==T[j]）{//继续比较后继字符
++i;
++j;
}
else{//指针后退重新开始匹配
i=i-j+2;//此时i为上次开始比较位置的下一位
j=1;
}
}
if（j>T[0]）returni-T[0];
elsereturn0;
}//Index
2.计算NEXT。
j：
1234567
串：
abcabaa
next[j]：
0111232
▲技巧：
第一二个肯定是0，1！
如果要计算next[4]，找的字符串必须是以第3个字符c为结尾，第1个字符a为开头的。
以第6个为例，a前一个字母是b，以第5个字符b为结尾的ab刚好和以第1个字符为
开头的ab匹配，所以next[6]=2+1=3。
第五章
1.二维数组的地址（下标）换算；
习题5.1假设有二维数组A6*8，每个元素用相邻的6个字节存储，存储器按字节编址。
已知A的起始存储位置（基地址）为1000，计算：
（1）数组A的体积（即存储量）
6*8*6=288字节
（3）按行存储是，元素a14的第一个字节的地址
1000+（8*1+4）*6=1072
基址+（每行的元素个数*行数+当前列序）*每个元素所占存储单元
（4）按列存储时，元素a47的第一个字节的地址
1000+（6*7+4）*6=6276
基址+（每列的元素个数*列数+当前行序）*每个元素所占存储单元
习题5.2假设按低下标优先存储整数组A9*3*5*8时，第一个元素的字节地址是100，每个整数占四个字节。
问下列元素的存储地址是什么？
（2）a1111地址：
100+（3*5*8*1+5*8*1+8*1+1）*4=776
（3）a3125地址：
100+（3*5*8*3+5*8*1+8*2+5）*4=1784
（4）a8247地址：
100+（3*5*8*8+5*8*2+8*4+7）*4=4416
2.特殊矩阵（三角、其他有规律）压缩为一维的下标计算；
◎下三角矩阵压缩为一维数组（记忆公式）
▲技巧：
推荐把公式
（2）背下来（i,j,R范围都是从0开始），其他根据范围变化公式
（1）若1<=j,j<=n,0<=R<=n（n+1）/2-1
当i>=j时，k=i（i-1）/2+j-1;
当i（2）若0<=i,j<=n-1,0<=R<=n（n+1）/2-1
//注意i,j是0到n-1，下面的公式相当于把
（1）中i变成i+1,j变成j+1
当i>=j时，k=（i+1）i/2+j;
当j（3）若1<=j,j<=n,1<=R<=n（n+1）/2
//注意R是1到n（n+1）/2，下面公式相当于把
（1）中k变成k-1
当i>=j时，k=i（i-1）/2+j;
当i（4）若0<=j,j<=n-1,1<=R<=n（n+1）/2
当i>=j时，k=（i+1）i/2+j+1;
当i3.稀疏矩阵的三元组表示。
4.稀疏矩阵应用的算法。
（略）
第六章
1.二叉树的性质；
性质1：
。
性质2：
深度为k的二叉树至多有
个结点（k1）。
性质3：
对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
性质4：
。
性质5：
如果对一棵有n个结点的完全二叉树的结点按层序编号，
则对任一结点i（1in），有：
（1）如果i=1，则结点i是二叉树的根，无双亲；
如果i>1，则其双亲是i/2。
（2）如果2i>n，则结点i无左孩子；
如果2in，则其左孩子是2i。
（3）如果2i+1>n，则结点i无右孩子；
如果2i+1n，则其右孩子是2i+1。
2.二叉树的先序、中序、后序、层次遍历过程；树的先序、后序、层次遍历过程；
二叉树遍历过程：
先（根）序遍历：
根→左子树→右子树
中（根）序遍历：
左子树→根→右子树
后（根）序遍历：
左子树→右子树→根
层次遍历：
从上到下，从左往右，逐个遍历
树的遍历过程：
先根（次序）遍历：
先访问根结点，然后依次先根遍历根的每棵子树（根→子树）
后跟（次序）遍历：
先依次后根遍历每棵子树，然后访问根结点（子树→根）
层次遍历：
从上到下，从左往右，逐个遍历
▲注：
树与二叉树相互转化后
树的先根遍历相当于二叉树的先序遍历
树的后根遍历相当于二叉树的中序遍历
3.给出两个遍历序列，画出树（二叉树、树）
习题6.23画出和下列已知序列对应的树T：
（1）树的先根次序访问序列为GFKDAIEBCHJ;
（2）树的后根次序访问序列为DIAEKFCJHBG。
注：
树的后根遍历相当于二叉树的中序遍历
由
（1）知G为根；
G为根，联系
（2）知G无右子树；
观察
（1），F为G左子树；
根据
，观察
（2）知DIAEK在F左边，
CJHB在F右边；
观察
（1），K为F左子树；
根据
，观察
（2）知K无右子树；
观察
（1），D为K左子树；
根据
，观察
（2）知D无左子树；
观察
（1），A为D右子树；
观察
（2），IE分别为A左右子树；
F的右子树自行观察判断。
4.二叉树与树相互转换；
◎树转化成二叉树：
规则：
树的最左孩子变成二叉树左子树，该左孩子的兄弟变成二叉树左子树的右子树
注：
原树中B为A最左孩子，C,D为B兄弟，变成二叉树后C成为B右子树，D成为C右子树。
◎二叉树转化成树
5.求哈夫曼树和给出编码、带权路径长度计算。
习题6.26假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07,0.19,0.02,0.06,0.32,0.21,0.10。
试为这8个字母设计哈夫曼编码，并求带权路径长度
设这8个结点为A、B、C、D、E、F、G、H，其相应的权为7、19、2、6、32、3、21、10。
①当前未用权：
7、19、2、6、32、3、21、10，选出2、3构造出5。
⑵当前未用权：
7、19、6、32、21、10、5，选出5、6构造出11。
③当前未用权：
7、19、32、21、10、11，选出7、10构造出17。
④当前未用权：
19、32、21、11、17，选出11、17构造出28。
⑤当前未用权：
19、32、21、28，选出19、21构造出40。
⑥当前未用权：
32、28、40，选出32、28构造出60。
⑦剩下权：
40、60，构造出100
▲编码：
树的左分支为0，右分支为1。
得到哈夫曼编码为A:
1101B:
01C:
11111D:
1110E:
10F:
11110G:
00H:
1100
带权路径长度：
（7*4+19*2+2*5+6*4+32*2+3*5+21*2+10*4）/100=2.61
▲注：
该公式为：
A路径长*A权+B路径长*B权+…+H路径长*H权，因为设的权值是原来的100倍，所以结果除以100。
第七章
1.邻接矩阵、邻接表存储结构及其特征；
2.求最小生成树（Prim、Kruskal）；
◎普里姆（Prim）：
以点为基础
①从V1开始，找到最小边（V1,V3）；
②寻找与V1、V3相关联的最小边，找到（V3,V6）；
③寻找与V1、V3、V6相关联的最小边，找到（V6，V4）；
④寻找与V1、V3、V6、V4相关联的最小边，此时有（V4,V1）和（V3,V2），因为（V4,V1）与原来的边构成圈，所以选择（V3,V2）。
（如果（V4,V1）不与原来的边构成圈，则二条边任选一条）；
⑤寻找与V1、V3、V6、V4、V2相关联，并且不与原来边构成圈的最小边，找到（V2,V5）；
◎克鲁斯卡尔（Kruskal）（避圈法）：
以边为基础
方法介绍：
依次寻找权最小边，避免生成一个圈，所有点联通时生成最小树。
3.拓扑排序；
步骤：
（1）在有向图中选一个没有前驱的顶点且输出之。
（2）从图中删除该顶点和所有以它为尾的弧。
输出：
V6V1V4V2V5
注：
拓扑排序不唯一。
4.求最短路径过程（Dijkstra、Floyd）。
◎迪杰斯特拉（Dijkstra）
习题7.11试利用Dijkstra算法求题7.11图中从顶点a到其他各顶点间的最短路径，写
出执行算法过程中各步状态。
求解过程：
K=1时，找a能直接到达的点，有b,c,d，（a,c）权最小，（a,c）为a到c最短路径，将c放如终点集S；
K=2时，找a能直接到达的点，或通过（a,c）能到达的点，（a,c,f）权最小，（a,c,f）为a到f的最短路径，将f放入终点集S；
K=3时，找a能直接到达的点，或通过（a,c）能到达的点，或通过（a,c,f）能到达的点，
（a,c,e）权最小，（a,c,e）为a到e最短路径，将e放入终点集S；
K=4时，找a能直接到达的点，或通过（a,c）能到达的点，或通过（a,c,f）能到达的点，或通过（a,c,e）能到达的点，（a,c,f,d）为a到d最短路径，将d放入终点集S；
K=5时，找a能直接到达的点，或通过（a,c）能到达的点，或通过（a,c,f）能到达的点，或通过（a,c,e）能到达的点，或通过（a,c,f,d）能到达的点，（a,c,f,d,g）权最小，为a到g最短路径，将g放入终点集S；
K=6时，只剩下（a,b），（a,b）为a到b最短路径，将b放入终点集S。
◎弗洛伊德（Floyd）
注：
D
（1）[i][j]是从Vi到Vj的中间顶点的序号不大于1的最短路径的长度；D（k）[i][j]是从Vi到Vj的中间顶点的序号不大于k的最短路径的长度；D（n-1）[i][j]就是从Vi到Vj的最短路径的长度。
D（-1）栏中，Vi→Vj不允许有转折点。
直接填邻接矩阵。
D（0）栏中，Vi→Vj只允许通过V0转折，或者不转折。
通过V0转折权值小于原权值，就把原权值替换掉。
D
（1）栏中，Vi→Vj只允许通过V0、V1转折，或者不转折。
如果转折后权值小于原权值，替换。
D
（2）栏中，Vj→Vj允许通过V0、V1、V2转折，或者不转折，如果转折后权值小于原权值，替换。
此时p
（2）中就是各点间的最短路径。
第九章
1.以下所有查找成功平均查找长度
2.顺序查找；折半查找；
◎顺序查找：
从表中最后一个记录开始，逐个进行比较。
▲平均查找长度
等概率时，平均查找长度ASL=（n+1）/2
不等概率时，ASL=nP1+（n-1）P2+…+2Pn-1+Pn
◎折半查找：
指针low和high分别指示待查元素所在范围的下界和上界，mid=（low+high）/2，
如果要找的值大于S[mid]，则让mid=（mid+1+high）/2，继续比较；
如果要找的值小于S[mid]，则让mid=（low+mid-1）/2，继续比较。
▲平均查找长度
等概率条件下，ASL=
（n+1）-1
当n>50时，有近似结果ASL=
（n+1）-1
3.二叉排序树的插入（建立）、删除、平衡过程；
◎二叉排序树建立
（1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）它的左、右子树也分别为二叉排序树。
▲注：
中序遍历二叉排序树，得到从小到大序列
根据字母的先后确定大小
插入Jan；
F小于J，Feb成为Jan左子树；
M大于J，Mar成为Jan右子树；
Apr小于Jan，且Apr小于Feb，Apr成为Feb左子树；
May大于Jan，且May大于Mar，May成为Mar右子树；
June大于Jan，且June小于Mar，June成为Mar左子树。
剩下的略。
◎二叉排序树删除（）
升级会员 