数据结构期末复习资料1.docx
- 文档编号:14533644
- 上传时间:2023-06-24
- 格式:DOCX
- 页数:24
- 大小:51.99KB
数据结构期末复习资料1.docx
《数据结构期末复习资料1.docx》由会员分享,可在线阅读,更多相关《数据结构期末复习资料1.docx(24页珍藏版)》请在冰点文库上搜索。
数据结构期末复习资料1
第一章
1、数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。
数据结构(DataStructure):
相互之间存在一种或多种特定关系的数据元素的集合。
2、数据结构的形式定义:
二元组Data_Structure=(D,S)其中,D是数据元素的有限集,S是D上关系的有限集。
3、数据元素之间关系的映像:
1、顺序映像(顺序存储结构):
以相对的存储位置表示后继关系。
2、非顺序映像(链式存储结构):
借助指针元素存储地址的指针表示数据元素之间的逻辑关系。
任何一个算法的设计取决于数据(逻辑)结构,其实现取决于物理结构。
4、算法的定义:
对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作。
特性:
有穷性、确定性、可行性、输入、输出
5、算法的评价——衡量算法优劣的标准
正确性(correctness):
满足具体问题的需求
可读性(readability):
易读、易理解
健壮性(robustness):
当输入数据非法时,算法能够做出反应或进行处理
效率与低存储量:
执行时间短、存储空间小
作业的答案:
试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。
第二章
1、线性表是一种最简单的线性结构。
线性结构是一个数据元素的有序(次序)关系
特点:
存在唯一的一个“第一个”的数据元素;存在唯一的一个“最后一个”的数据元素;除第一个数据元素外,均有唯一的前驱;除最后一个数据元素外,均有唯一的后继
2、线性表类型的实现——顺序映像定义:
用一组地址连续的存储单元依次存放线性表中的数据元素。
⏹以“存储位置相邻”表示有序对
LOC(ai)=LOC(ai-1)+l其中l是一个数据元素所占存储量
LOC(ai)=LOC(a1)+(i-1)×l
⏹特点:
1、实现逻辑上相邻—物理地址相邻2、实现随机存取
3、若假定在线性表中任何一个位置上进行插入的概率都是相等的,则移动元素的期望值为:
若假定在线性表中任何一个位置上进行删除的概率都是相等的,则移动元素的期望值为:
4、线性表类型的实现——链式映像线性链表特点:
用一组地址任意的存储单元存放线性表中的数据元素。
5、在单链表中第i个结点之前进行插入的基本操作为:
找到线性表中第i-1个结点,然后修改其指向后继的指针。
s=(LinkList)malloc(sizeof(LNode));//生成新结点
s->data=e;s->next=p->next;p->next=s;//插入
在单链表中删除第i个结点的基本操作为:
找到线性表中第i-1个结点,修改其指向后继的指针。
q=p->next;p->next=q->next;e=q->data;free(q);
5、循环链表:
最后一个结点的指针域的指针又指回第一个结点的链表。
和单链表的差别仅在于:
判别链表中最后一个结点的条件不再是“后继是否为空”,而是“后继是否为头结点”。
6、双向链表的操作特点:
1、“查询”和单链表相同;2、“插入”和“删除”时需要同时修改两个方向上的指针
“插入”:
s->next=p->next;p->next=s;s->next->prior=s;s->prior=p;(s是插入的结点)
删除:
p->next=p->next->next;p->next->prior=p;(要删除的是p的下一个结点)
课后作业
P13:
2.3、2.5
P15:
2.8、2.9
(2)
第三章
1、栈、队列的特点:
☐从数据元素间的逻辑关系看是线性表
☐从操作方式与种类看不同于线性表:
栈与队列是操作受限的线性表
2、栈的基本概念栈---是限制仅在线性表的一端进行插入和删除运算的线性表。
栈顶(TOP)--允许插入和删除的一端。
栈底(bottom)--不允许插入和删除的一端。
空栈--表中没有元素。
栈--又称为后进先出的线性表
3、栈中元素的特性:
1、具有线性关系2、后进先出
4、栈的进栈出栈规则:
a)按序进栈:
有n个元素1,2,…,n,它们按1,2,…,n的次序进栈(i进栈时,1~(i-1)应该已经进栈);
b)栈顶出栈:
栈底最后出栈;
c)时进时出:
元素未完全进栈时,即可出栈。
5、栈的表示与实现
顺序栈即栈的顺序存储结构:
一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。
1、附设一个栈底指针base,总是指向栈底。
2、附设一个栈顶指针top。
空栈时,top=base;非空栈时,总是指向栈顶元素+1的位置。
☐插入一个栈顶元素,指针top增1;
☐删除一个栈顶元素,指针top减1;
☐非空栈中的栈顶指针始终在栈顶元素的下一个位置上
链栈:
注意:
链栈中指针的方向指向前驱结点!
6、队列
⏹队列:
只允许在表的一端进行插入,而在表的另一端进行删除的线性表。
☐队尾(rear)——允许插入的一端
☐队头(front)——允许删除的一端
⏹队列特点:
先进先出(FIFO)
7、队列类型的实现
⏹链队列——队列的链式表示和实现
⏹顺序队列——队列的顺序表示和实现用一组连续的存储单元依次存放队列中的元素
8、顺序队列运算时的头、尾指针变化
设两个指针front,rear,约定:
rear指示队尾元素;front指示队头元素前一位置初值front=rear=0
空队列条件:
Q.front==Q.rear
队列满:
Q.rear-Q.front=m
入队列:
Q.base[rear++]=x;
出队列:
x=Q.base[++front];
存在问题:
设数组维数为M,则:
⏹当rear-front=m时,再有元素入队发生溢出——真溢出
⏹当rear已指向队尾,但队列前端仍有空位置时,再有元素入队发生溢出——假溢出!
9、循环队列:
将数组首尾相接(即:
base[0]连在base[m-1]之后)。
入/出队列运算
利用“模运算”,则:
Ø入队:
Q.rear=(Q.rear+1)%m
Ø出队:
Q.front=(Q.front+1)%m
队满和队空判断条件:
少用一个元素空间:
队空:
Q.rear=(Q.front)
队满:
(Q.rear+1)%m=Q.front
10、栈和队列是限定插入和删除只能在表的“端点”进行的线性表。
a)栈具有“后进先出”的特性;
b)队列具有“先进先出”的特性。
11、栈的链式存储不需头结点。
课后作业
1.用栈结构计算中缀式2+(4-3)*6,画出计算过程栈的结构。
2.简述以下算法的功能(栈和队列的元素类型均为int)
voidalgo3(Queue&Q){
StackS;intd;
InitStack(S);
while(!
QueueEmpty(Q)){
DeQueue(Q,d);Push(S,d);
}
while(!
StackEmpty(S)){
Pop(S,d);EnQueue(Q,d);
}
}
第六章
本章小结
⏹二叉树的结构特性,各性质相应的证明方法。
⏹二叉树的各种存储结构的特点及适用范围。
⏹遍历二叉树是二叉树各种操作的基础,遍历的具体算法与所采用的存储结构有关。
⏹树和森林与二叉树的转换。
⏹最优二叉树的特性,掌握建立最优树和哈夫曼编码的方法。
-、树的定义
1、树型结构:
(非线性结构)至少存在一个数据元素有两个或两个以上的直接前驱(或直接后继)元素的数据结构。
树的定义:
是n(n≥0)个结点的有限集合T,对于任意一棵非空树,它满足:
有且仅有一个特定的称为根(root)的结点;当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,….,Tm,其中每个集合本身又是一棵树,称为根的子树。
上述树的定义是一个递归定义。
2、基本术语
结点:
包含一个数据元素及若干指向其子树的分支。
结点的度:
结点拥有的子树数。
叶子(或终端)结点:
度为零的结点。
分支(或非终端)结点:
度大于零的结点树的度:
树中所有结点的度的最大值结点的层次:
根结点的层次为1,第l层的结点的子树的根结点的层次为l+1。
树的深度:
树中叶子结点所在的最大层次。
任何一棵非空树是一个二元组Tree=(root,F)其中:
root被称为根结点F被称为子树森林
二、二叉树
1、二叉树的定义是n(n>=0)个结点的有限集合,它或为空树(n=0),或由一个根结点和至多两棵称为根的左子树和右子树的互不相交的二叉树组成。
注:
二叉树中不存在度大于2的结点,并且二叉树的子树有左子树和右子树之分。
2、二叉树的五种基本形态:
空树只含根结点右子树为空树左子树为空树左右子树均不为空树
3、二叉树的性质
性质1:
在二叉树的第i层上至多有2i-1个结点(i≥1)。
其中2i-1为2的i-1次方
性质2:
深度为k的二叉树上至多含2k-1个结点(k≥1)。
其中2k-1为2的k次方减一
性质3:
对任何一棵二叉树,若它含有n0个叶子结点、n2个度为2的结点,则必存在关系式:
n0=n2+1。
证明:
设二叉树上结点总数n=n0+n1+n2,∵二叉树上分支总数b=n1+2n2,①而b=n-1=n0+n1+n2–1②由①②,n0=n2+1。
除根结点外,其余结点都有一个分支进入,设b为分支总数,则n=b+1
性质4:
具有n个结点的完全二叉树的深度为log2n+1。
其中log2n为不大于log2n的最大整数
性质5:
若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号,则对完全二叉树中任意一个编号为i的结点:
(1)若i=1,则该结点是二叉树的根,无双亲,否则,编号为i/2的结点为其双亲结点;
(2)若2i>n,则该结点无左孩子,否则,编号为2i的结点为其左孩子结点;
(3)若2i+1>n,则该结点无右孩子结点,否则,编号为2i+1的结点为其右孩子结点。
4、两类特殊的二叉树:
满二叉树:
指的是深度为k且含有2k-1个结点的二叉树。
其中2k-1为2的k次方减一
特点:
是每一层上的结点数都是最大结点数。
完全二叉树:
树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。
特点:
⑴叶子结点只可能在层次最大的两层出现;⑵对任一结点,若其右分支下的子孙的最大层次为l,则其左
分支下的子孙的最大层次为l或l+1。
⏹性质练习:
1.一棵二叉树在其第五层中有17个结点,可不可能?
第i层上至多有2i-1个结点,则25-1=16。
所以,不可能。
2.二叉树的根结点属于第0层还是属于第1层?
第1层
3.已知一棵二叉树有20个结点,其中6个结点为叶子,则该树中度为2的结点数为5?
度为0的结点为6?
由性质3:
n0=n2+1,则n2=n0-1=6-1=5。
4.已知一棵完全二叉树中编号为101的结点有LC和RC结点,则其LC结点编号为202,RC结点编号为203?
由性质5,可知左孩子为2i,右孩子为2i+1
5.一棵深度为h的完全k叉树,如果按层次自顶向下、同一层自左向右、顺序从1开始对全部结点进行编号,试问:
该树上最多有多少个结点?
最少有多少个结点?
由性质1和定义,可知除第h层外,其余各层都是满的,所以:
1+k+k2+...+kh-2=(kh-1-1)/(k-1),则最多有:
(kh-1-1)/(k-1)+kh-1=(kh-1)/(k-1);
最少有:
(kh-1-1)/(k-1)+1
三、二叉树的存储结构
1、顺序存储结构:
特点:
一组地址连续的存储单元存储各结点(定义一个一维数组);自根而下、自左而右存储结点;按完全二叉树上的结点位置进行编号和存储。
缺点:
空间利用率太低!
2、链式存储结构:
二叉链表:
结点结构至少包含:
数据域和左右孩子指针域lchilddatarchild
三叉链表:
结点结构至少包含:
数据域、左右孩子指针域、双亲指针parentlchilddatarchild
四、遍历二叉树和线索二叉树
1、遍历二叉树:
顺着某一条搜索路径巡访二叉树中的结点,使得每个结点均被访问一次,而且仅被访问一次。
基本操作是访问结点
先(根)序的遍历算法:
若二叉树为空树,则空操作;否则,⑴访问根结点;⑵先序遍历左子树;⑶先序遍历右子树。
中(根)序的遍历算法:
若二叉树为空树,则空操作;否则,⑴中序遍历左子树;⑵访问根结点;⑶中序遍历右子树。
后(根)序的遍历算法:
若二叉树为空树,则空操作;否则,⑴后序遍历左子树;⑵后序遍历右子树;⑶访问根结点。
2、建立二叉树的存储结构:
基本要点:
以“遍历”为基本出发点;不同的遍历方法相应地有不同的建立算法代码
如何由二叉树的先序和中序序列建树?
?
?
3、线索二叉树
指向该线性序列中的“前驱”和“后继”的指针,称作“线索”。
包含“线索”的存储结构,
称作“线索链表”。
与其相应的二叉树,称作“线索二叉树”
遍历二叉树的结果是,求得结点的一个线性序列。
线索化的实质是将二叉链表中的空指针改为指向前驱或着后续的线索,而前驱或者后续的信息只有在遍历时才能得到,因而线索化的过程即为在遍历的过程中修改空指针的过程。
四、树和森林
1、树的存储结构
①双亲表示法:
用一组连续空间存储树的结点,并附设一个指示器指示其双亲结点的位置。
其中根节点的值为-1
②孩子链表表示法:
树结点表和孩子结点表为了快速查找每个结点的孩子结点
③树的二叉链表(孩子-兄弟)存储表示法:
又称二叉树表示法,即以二叉链表作树的存储结构。
链表中结点的两个链域分别指向结点的第一个孩子结点和下一个兄弟结点。
左边孩子右边兄弟
与孩子-兄弟链表对应的二叉树:
转化后,二叉树的右子树必为空!
2、森林与二叉树的转换
给定一棵树,可以找到惟一的一棵二叉树与之对应。
——用二叉链表作为存储结构(依据)
把森林中第二棵树的根结点看成第一棵树的根结点的兄弟,即作为二叉树的右子树,则同样可以导出森林和二叉树的对应关系。
注意:
和树对应的二叉树,其左、右子树的概念已改变为:
左是孩子,右是兄弟。
3、树和森林的遍历
两种遍历树的方法:
①先根(次序)遍历:
若树不空,则先访问根结点,然后依次先根遍历各棵子树。
②后根(次序)遍历:
若树不空,则先依次后根遍历各棵子树,然后访问根结点。
森林的遍历:
森林由三部分构成:
森林中第一棵树的根结点;森林中第一棵树的子树森林;森林中其它树构成的森林。
遍历森林:
先序遍历:
若森林不空,则访问森林中第一棵树的根结点;先序遍历森林中第一棵树的子树森林;先序遍历森林中(除第一棵树之外)其余树构成的森林。
即:
依次从左至右对森林中的每一棵树进行先根遍历。
中序遍历:
若森林不空,则中序遍历森林中第一棵树的子树森林;访问森林中第一棵树的根结点;中序遍历森林中(除第一棵树之外)其余树构成的森林。
即:
依次从左至右对森林中的每一棵树进行后根遍历。
五、哈夫曼树及其应用
1、最优二叉树(哈夫曼树)
结点的路径长度:
从根结点到该结点的路径上分支的数目。
树的路径长度:
树中每个结点的路径长度之和。
树的带权路径长度:
树中所有叶子结点的带权路径长度之和WPL(T)=∑wklk(对所有叶子结点)
在所有含n个叶子结点、并带相同权值的m叉树中,必存在一棵其带权路径长度取最小值的树,称为“最优树”。
2、如何构造最优树?
(赫夫曼算法)以二叉树为例:
⑴根据给定的n个权值{w1,w2,…,wn},构造n棵二叉树的集合F={T1,T2,…,Tn},其中每棵二叉树中均只含一个带权值为wi的根结点,其左、右子树为空树;
⑵在F中选取其根结点的权值最小的两棵二叉树,分别作为左、右子树构造一棵新的二叉树,并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;
⑶从F中删去这两棵树,同时加入刚生成的新树;
⑷重复
(2)和(3)两步,直至F中只含一棵树为止。
3、采用二叉树设计二进制前缀编码规定:
左分支用“0”表示;右分支用“1”表示。
4、算法实现:
由于哈夫曼树中没有度为1的结点,则一棵有n个叶子结点的哈夫曼树共有2n-1个结点(因n2=n0-1),可以存储在一个大小为2n-1的一维数组中。
5、编码需要从叶子到根;译码需要从根到叶子
课后作业
P38:
6.5P39:
6.6(要求:
写出推导过程)
1.某二叉树的先序遍历结点访问顺序是abdgcefh,中序遍历的访问顺序是dgbaechf,则其后序遍历的结点访问顺序是()。
2.P41:
6.23
P41:
6.23,然后将该树转化为对应的二叉树。
6.26
第7章图
本章小结
⏹图是一种复杂的非线性结构。
⏹图的存储表示方法:
邻接矩阵邻接表十字链表——有向图邻接多重表——无向图
⏹图的遍历:
深度优先、广度优先
⏹图的遍历的应用:
最小生成树、拓扑排序及关键路径、最短路径等问题各种算法思想!
一、图的定义和基本术语
1、图的定义
图形结构:
较线性表和树更为复杂的数据结构。
结点之间的关系是任意的,图中任意两个数据元素都可能相关。
图的结构定义:
图:
是由一个顶点集V和一个顶点间的关系集合组成的数据结构。
Graph=(V,VR)
其中,V={x|x某个数据对象},是顶点的有穷非空集合;
2、顶点之间关系的有穷集合,也叫做边(edge)或弧(Arc)集合。
“弧”是有方向的,
3、由顶点集和弧集构成的图为有向图。
由顶点集和边集构成的图称作无向图
基本术语
①有(无)向网:
弧(边)上带权的图
②假设图中有n个顶点,e条边,则含有e=n(n-1)/2条边的无向图称作完全图;含有e=n(n-1)条弧的有向图称作有向完全图;若边或弧的个数e ③和顶点v关联的边的数目定义为边的度 对有向图来说,顶点的出度: 以顶点v为弧尾的弧的数目;顶点的入度: 以顶点v为弧头的弧的数目。 顶点的度(TD)=出度(OD)+入度(ID) 4若图G中任意两个顶点之间都有路径相通,则称此图为连通图; 若无向图为非连通图,则图中各个极大连通子图称作此图的连通分量。 对有向图来说,若任意两个顶点之间都存在一条有向路径,则称此有向图为强连通图。 否则,其各个强连通子图称作它的强连通分量。 假设一个连通图有n个顶点和e条边,其中n-1条边和n个顶点构成一个极小连通子图,称该极小连通子图为此连通图的生成树。 比较: 连通分量和生成树! 连通分量: 非连通图的极大连通子图而生成树: 连通图的极小连通子图 二、图的存储结构对图中所有顶点使用一个一维数组来存放 1、图的数组(邻接矩阵)存储表示 无向图的邻接矩阵是对称的,有向图的邻接矩阵可能是不对称的。 借助于邻接矩阵容易求得顶点的度: ①在无向图中,统计第i行(列)1的个数可得顶点i的度。 ②在有向图中统计第i行1的个数可得顶点i的出度;统计第j列1的个数可得顶点j的入度。 2、图的邻接表存储表示 单链表中每个结点由三个域组成邻接点域(adjvex): 指示与顶点vi邻接的点在图中的位置;链域(nextarc): 指示下一条边或弧的结点;数据域(info): 存储和边或弧相关的信息,如权值等。 3、有向图的十字链表存储表示 将有向图的邻接表和逆邻接表结合起来的一种链表从横向上看是邻接表,从纵向上看是逆邻接表。 4、无向图的邻接多重表存储表示 三、图的遍历 从图中某个顶点出发游历图,访遍图中其余顶点,并且使图中的每个顶点仅被访问一次的过程。 1、深度优先搜索 连通图的深度优先搜索遍历: 深度优先搜索遍历连通图的过程类似于树的先根遍历 非连通图的深度优先搜索遍历 深度优先遍历图的实质: 对每个顶点查找其邻接点的过程! 2、广度优先搜索 广度优先遍历图的实质: 通过边或弧找邻接点的过程! 四、图的连通性问题 1、无向图的连通分量和生成树 生成树的特点: n个顶点的连通子图的生成树是一个极小连通子图,它包含图中所有顶点和n-1条边(但有n-1条边的图不一定是生成树)。 生成树中任意两个顶点间的路径是唯一的。 注: 边数>n-1时,则形成环;边数 五、最小生成树 构造网的一棵最小生成树,即: 在e条带权的边中选取n-1条边(不构成回路),使“权值之和”为最小。 1、普里姆算法: 基本思想: 第一步: 取图中任意一个顶点v作为生成树的根; 第二步: 往生成树上添加新的顶点w。 在添加的顶点w和已经在生成树上的顶点v之间必定存在一条边,并且该边的权值在所有连通顶点v和w之间的边中取值最小; 第三步: 继续往生成树上添加顶点,直至生成树上含有n个顶点为止。 构造的最小生成树不一定唯一,但最小生成树的权值之和一定是相同的。 2、克鲁斯卡尔算法: 考虑问题的出发点: 为使生成树上边的权值之和达到最小,则应使生成树中每一条边的权值尽可能地小。 基本思想: 第一步: 构造一个只含n个顶点的子图SG; 第二步: 从权值最小的边开始,若它的添加不使SG中产生回路,则在SG上加上这条边; 第三步: 如此重复,直至加上n-1条边为止 比较两种算法: ☐普里姆算法: O(n2)、适用于稠密图 ☐克鲁斯卡尔算法: O(eloge)、适用于稀疏图 六、有向无环图及其应用 定义: 一个无环的有向图称作有向无环图 1、拓扑排序检查有向图中是否存在回路的方法之一,是对有向图进行拓扑排序。 ①用顶点表示活动,用弧表示活动间的优先关系的有向图称为顶点表示活动的网(ActivityOnVertexNetwork),简称AOV-网。 在AOV-网中不应该出现有向环。 对给定的AOV-网需首先判断网中是否有环。 ②如何进行拓扑排序? ☐从有向图中选取一个没有前驱的顶点,并输出之; ☐从有向图中删去此顶点以及所有以它为尾的弧; ☐重复上述两步,直至图空,或者图不空但找不到无前驱的顶点为止。 ③在算法中需要用定量的描述替代定性的概念: 没有前驱的顶点入度为零的顶点;删除顶点及以它为尾的弧弧头顶点的入度减1。 ④为避免每次都要搜索入度为零的顶点,在算法中设置一个“栈”,以保存“入度为零”的顶点 2、关键路径 “关键活动”指的是: 该弧上的权值增加将使有向图上的最长路径的长度增加。 3、最短路径 从某顶点出发,沿图的弧到达另一顶点所经过的路径中,各边上权值之和最小的一条路径——最短路径。 注意: 和关键路径区别! 课后作业 P47: 7.3 2.假设图G采用邻接表存储,设计一个算法,输出图G中从顶点u到v的长度为1的所有简单路径。 1.P47: 7.7 (2)P48: 7.10、7.11 第9章查找 本章小结 ⏹查找表是由同一类型的数据元素(或记录)构成的集合。 ⏹对查找表经常进行的操作: 查询检索插入删去 ⏹静态查找表: 顺序表 有序表: 等概率: 折半查找——判定树不等概率: 静态树表的查找——次优二叉查找树 ⏹动态查找表: 二叉排序树和平衡二叉树B-树哈希表 查找的方法取决于查找表的结构 一、静态查找 1、顺序表的查找以顺序表表示静态查找表,称为顺序查找表。 “哨兵”的作用: 免去查找过程中每一步都要检测整个表
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 期末 复习资料