数据结构复习要点.docx
- 文档编号:9321614
- 上传时间:2023-05-18
- 格式:DOCX
- 页数:21
- 大小:41.20KB
数据结构复习要点.docx
《数据结构复习要点.docx》由会员分享,可在线阅读,更多相关《数据结构复习要点.docx(21页珍藏版)》请在冰点文库上搜索。
数据结构复习要点
数据结构总复习一、基本要求掌握的知识点如下:
⑴线性表、顺序表和链表。
要求掌握线性表的概念,两种存储结构的实现、优缺点及两种存储结构上的基本操作。
⑵栈与队列。
要求掌握栈和队列的概念,顺序栈、链栈的操作,栈的应用,循环队列、循环链队列的操作。
⑶串的基本运算和模式匹配。
掌握串的基本运算的含义,了解模式匹配算法和时间复杂度。
⑷多维数组和广义表。
掌握多维数组及特殊矩阵的地址公式,广义表的运算和存储。
⑸树和二叉树。
树、二叉树的定义、术语,二叉树的性质、存储、遍历、应用,线索二叉树的概念,树与二叉树的关系。
⑹图的存储及其操作。
掌握图的定义、术语,图的存储,图的遍历、图的操作(最小生成树、拓扑排序、关键路径、最短路径)概念。
⑺表和树的查找。
掌握表和树查找的概念、平均比较次数,二叉排序树和平衡二叉树的插入、删除,了解B-树的定义。
⑻Hash技术。
掌握哈希表构造、解决冲突的方法及哈希表的查找。
⑼排序算法。
掌握直接插入排序、冒泡排序、简单选择排序、快速排序、堆排序、归并排序和希尔排序算法和时间复杂度,了解基数排序、外排序的概念和算法。
二、基本内容第一章数据结构与算法概念数据结构:
数据结构DS=(A,R),其中A是数据元素的非空有限集合,R是定义在A上关系的非空有限集合。
结构就是元素之间的关系。
算法:
算法就是解决问题的方法和步骤。
算法的时间复杂度:
算法中语句重复执行次数(或称语句频度)或算法中基本操作次数,一般用数量级符号○来描述。
抽象数据类型:
抽象数据类型ADT=(A,R,P),其中A是数据元素的非空有限集合,R是定义在A上关系的非空有限集合,P是(A,R)上非空的基本操作集合。
【例1-1】求表2-1中程序段的各语句的语句频度和时间复杂度。
表2-1语句频度和时间复杂度计算语句语句频度说明for(i=0;i
a[i][j]=x++;时间复杂度T(n)为所有语句频度之和,即T(n)=n+1+2=当n→∞时,所以时间复杂度T(n)=○(n2)第二章线性表线性表的定义:
线性表是n(n≥0)个元素的有限序列,当n=0,则称为空表;当n>0时,线性表通常表示为(a1,a2,...,an),其中a1无前驱,an无后继,其余结点有且只有一个前驱和一个后继。
线性表的存储:
线性表有顺序存储和链式存储两种存储结构。
l线性表的操作:
主要操作有初始化表、判表空、求表长、查找、插入和删除元素等。
线性表的存储结构不同,具体的操作实现就不同,如表2-2所示。
表2-2线性表的两种存储结构的基本操作特点顺序存储结构链式存储结构静态数组动态数组类型定义#defineArSize10typedefstruct{ElemTypeelem[ArSize];intlength;}SqList;typedefstruct{Elemtype*elem;intlength,ArSize;}sqList;typedefstructnode{ElemTypedata;structnode*next;}LNode;初始化表voidinitList(SqList*L){L->length=0;}voidinitList(sqList*L,intn){L->elem=(ElemType*)malloc(n*sizeof(ElemType));L->ArSize=n;L->length=0;}LNode*initLK(){LNode*head;head=NULL;returnhead;}查找由于第i个元素ai的存储位置LOC(ai)=LOC(a1)+(i-1)×d,所以能随机查找任一个元素,时间复杂度为O
(1)只能进行顺序查找,查找一个元素平均比较次数为(n+1)/2插入删除插入、删除时大量结点要移动,在等概率下插入、删除一个元素平均移动结点的次数分别是n/2和(n-1)/2。
插入、删除时只要修改相关的指针即可,时间复杂度都为O
(1)【例2-1】在非空的双链表中删除指针p所指向的结点。
双链表的结点形式如图2-1(a)所示,删除p的操作步骤如图2-1(b)所示。
图2-1中
(1)为p->front->next=p->next;
(2)为p->next->front=p->front。
【例2-2】在非空的双链表中指针p所指向的结点前插入一个新结点q。
插入q的操作步骤如图2-2所示。
图2-2中
(1)为q->next=p;
(2)q->front=p->front;(3)p->front->next=q;(4)p->front=q注意:
步骤(3)与(4)的顺序不能颠倒。
第三章栈和队列3.1栈l栈的定义:
栈是一种只能在表的某一端(首端)进行操作的线性数据结构。
栈的操作主要有进栈和出栈,因为只能在某一端进栈出栈,所以必定是先进后出的(FILO或LIFO)。
l栈的存储结构:
有顺序栈(静态数组或动态数组)和链栈。
l栈的操作:
初始化栈、进栈、出栈,通过栈顶指针(top)来操作如表2-3所示。
表2-3顺序栈和链栈的操作静态数组栈动态数组栈链栈类型定义#defineSSize10typedefstruct{ElemTypeelem[SSize];inttop;}SqSNode;Typedefstruct{ElemType*elem,*top;intSSize;}DSNode;typedefstructnode{ElemTypedata;structnode*next;}LSNode;进栈SqSNodes;s.elem[s.top++]=e;DSNodes;*s.top++=e;LSNode*top,*p;p=newLSNode;p->data=e;p->next=top;top=p;出栈e=s.elem[--s.top];e=*--s.top;p=top;e=p->data;top=top->next;delete(p)栈空s.top==0s.top==s.elemtop==NULL栈满s.top==SSizes.top==s.elem+s.SSize空间分配失败p==NULLl栈的应用举例:
表达式求值和递归的实现。
【例3-1】算术表达式a+b*c/(d-e)-f的逆波兰式为abc*de-/+f-;【例3-2】已知下列算法voidp(intn){if(n>1&&n%2==1)p(n-1);printf(“%2d”,n);if(n>1&&n%2==0)p(n-1);}用p(5)调用的结果是:
42135分析:
当遇到调用语句时将参数、返回地址进栈;当遇到函数结束时退栈返回。
3.2队列l队列的定义:
队列是一种只能在表的尾端进行插入操作,在首端进行删除操作的线性数据结构。
它是先进先出(FIFO)的线性表。
l队列的存储结构:
有顺序队列—循环队列,设有首指针和尾指针;链队列—一般在单循环链表上实现,只设尾指针,不设首指针称循环链队列。
队列的操作:
初始化队列、进队、出队,通过队列的首指针front和尾指针rear实现操作如表2-4所示。
表2-4循环队列和循环链队列的操作循环队列循环链队列类型定义#defineQSize10typedefstruct{ElemTypeelem[QSize];intfront,rear;}SqQNode;typedefstructnode{ElemTypedata;structnode*next;}LQNode;进队SqQNodeQ;Q.rear=(Q.rear+1)%QSize;Q.elem[Q.rear]=e;LQNode*rear,*p;p=newLQNode;p->data=e;p->next=rear->next;rear->next=p;rear=p;出队Q.front=(Q.front+1)%QSize;e=Q.elem[Q.front];p=rear->next;e=p->data;(无头链表)rear->next=p->next;delete(p);队空Q.front==Q.rearrear==NULL队满Q.front==(Q.rear+1)%QSize空间分配失败p==NULL【例3-3】设循环队列Q,则当前循环队列中的元素个数是:
(Q.rear-Q.front+QSize)%QSize.第四章串l串、子串的定义:
串是有限个字符组成的序列。
子串是串中任意长度的连续字符构成的序列。
l串的运算:
两个串的联接、比较,串的赋值,求串长,插入子串,删除子串和模式匹配。
串的模式匹配算法有朴素的模式匹配算法和KMP算法等,设主串s、长度为m,子串t、长度为n,匹配算法如表2-5所示。
表2-5模式匹配算法朴素的模式匹配KMP算法若s[i]==t[j],则i++;j++;若s[i]==t[j],则i++;j++;若s[i]!
=t[j],则i=i-j+2;j=1;若s[i]!
=t[j],则j=next[j];i不动时间复杂度T(m,n)=○(mn)时间复杂度T(m,n)=○(m+n)其中【例4-1】已知主串s=”ABBABA”,子串t=”ABA”,求用朴素的模式匹配算法查找子串t的比较次数。
解:
用朴素的模式匹配算法需要进行8次比较,子串位置是4。
【例4-2】求子串t=”ABCABCACAB”的next值。
解:
j:
12345678910t[j]:
ABCABCACABf[j]:
0001234012next[j]:
0111234512第五章数组和广义表l数组的定义:
n维数组Ab1b2…bn,A中的每个元素A[j1,j2,…,jn]其中1≤ji≤bi,1为每一维的下界,bi为第i维的上界。
l数组的存储l【例5-1】已知三维数组Amnp,将A以行序为主序存储在首地址为loc(A[1,1,1])的内存空间中,每个元素占L个单元,则数组A中任意一个元素的地址为loc(A[i,j,k])=loc(A[1,1,1])+((i-1)*n*p+(j-1)*p+k-1)*L若以列序为主序,则loc(A[i,j,k])=loc(A[1,1,1])+((k-1)*m*n+(j-1)*m+i-1)*L【例5-2】已知对称阵Ann,以行序为主序存储A的下三角阵部分,内存首地址为loc(A[1,1]),每个元素占L个单元,则下三角阵中任意一个元素的地址为loc(A[i,j])=【例5-3】已知上三角矩阵Ann以行序为主序存储在内存首地址为loc(A[1,1]),每个元素占L个单元,则上三角阵中任意一个元素的地址为loc(A[i,j])=loc(A[1,1])+((2n-i+2)*(i-1)/2+(j-i))*L当1≤i≤j时【例5-4】已知广义表LS=((a,(b)),(c)),LS深度为3(括号的重数),求头Head(LS)=(a,(b)),求尾Tail(LS)=((c)).【例5-5】已知四行七列的稀疏矩阵M=,其三元组表为((1,3,6),(2,2,3),(2,6,8),(4,1,5),(4,6,7))。
【例5-6】已知广义表LS=((a),(b,c)),广义表的结点结构如图2-3所示,LS的链式存储结构如图2-4所示。
第六章树和二叉树6.1二叉树l二叉树的定义:
二叉树是由一个特定的结点(无前驱)称为根和两个互不相交的左子树、右子树组成,其中左子树,右子树本身是二叉树。
ll线索二叉树:
二叉树用二叉链表存储时,当二叉树有n个结点时,则有n+1个指针域为空,可以利用这些空指针域存放某种遍历次序下的前趋和后继结点的指针,这种二叉树就称为线索二叉树。
在线索二叉树中用得较多的是中序线索二叉树,即树中任意结点p,若p左指针域空,则其左指针域指向p的中序前趋;若p右指针域空,则其右指针域指向p的中序后继。
l哈夫曼树(Huffman):
哈夫曼树又称最优二叉树。
它是n个带权叶子结点构成的所有二叉树中带权路径长度WPL最小的二叉树。
其中:
其中n表示叶子结点的数目,Wi和li分别表示叶子结点ki的权值和根到ki之间的路径长度。
6.2树和森林l树的定义:
树是由一个特定的结点(无前驱)称为根和m(m>0)个互不相交的树(称为子树)组成,其中当m=0时称为空树。
lll树转换为二叉树:
树用孩子兄弟表示法表示后即为二叉树了。
l【例6-1】图2-5所示树与二叉树的区别,二叉树的子树有左右之分。
【例6-2】图2-6所示满二叉树和完全二叉树。
【例6-3】完全二叉树的顺序存储如图2-7所示。
【例6-4】n个结点的二叉树用二叉链表存储,那么有n+1个空指针,因为n个结点共有2n个指针空间,其中n-1个指向孩子结点。
【例6-5】对于图2-8所示的二叉树,它的前序遍历序列为:
ABEDHCFG中序遍历序列为:
EDBHACGF后序遍历序列为:
DEHBGFCA层次遍历序列为:
ABCEHFDG【例6-6】对于图2-9所示的二叉树,其中序线索二叉树如图2-10所示。
【例6-7】假设通信的电文仅有a,b,c,d,e五个字母组成,字母在电文中出现的次数分别是8,2,5,4,5。
用哈夫曼算法构造的哈夫曼树过程如图2-11所示。
哈夫曼树中从根到每个叶子结点都有一条唯一的路径,对路径上的各分支约定左分支表示‘0’码,右分支表示‘1’码,则从根结点到叶子结点的路径上分支的码组成的字符串作为该叶子结点的编码,这就是哈夫曼编码。
为上述五个字母设计的哈夫曼编码如图2-12所示。
【例6-8】对于图2-13的树T,它的孩子兄弟表示法如图2-14所示,即将树T转换为二叉树了。
【例6-9】图2-13中树T的前序遍历序列为:
ABEFCDG,后序遍历序列为:
EFBCGDA。
而图2-14中的二叉树的前序遍历序列为:
ABEFCDG,中序遍历序列为:
EFBCGDA。
这个例子验证了树和树转换为二叉树的前序遍历序列相同;树的后序与二叉树的中序相同。
第七章图7.1图的定义:
图G=(V,E),其中V是顶点(结点)的有穷非空集合,E是V中顶点的序偶组成的有穷集,这些序偶称为边。
7.2基本术语l邻接点:
,若存在一条边,则在无向图中称vi和vj互为邻接点,在有向图中称vj是vi的邻接点。
l完全图:
图G中任意两点都邻接,称该图为完全图。
无向完全图有n(n-1)/2条边,有向完全图有n(n-1)条边。
l度、入度和出度:
无向图中顶点v依附(关联)的边数称为v的度。
对于有向图,顶点V的度分为入度和出度,v的入度是边的箭头指向v的入边数目;v的出度是箭头离开v的出边数目。
有关度的结论有图中所有结点度数之和等于图的边数的两倍。
l连通和连通图:
在无向图G中.若从顶点vi到vj有路径,则称vi和vj是连通的。
若图G中任意两个顶点都是连通的,则称G连通图。
l连通分量:
无向图G中的极大连通子图称为图G的连通分量。
l强连通图和强连通分量:
在有向图G中,若任意两个顶点vi和vj都连通,即从vi到vj存在路径,从vj到vi也存在路径,则称该图是强连通图。
有向图G中的极大强连通子图称为G的强连通分量。
l网:
在一个图中,每条边可以标上具有某种含义的数值,该数值称为该边的权。
边带权的图称为带权图,也称为网。
l生成树:
连通图G有n个顶点,取G中n个顶点,取连接n个顶点的n-1条边所得的子图称为G的生成树。
满足此定义的生成树可能有多棵,即生成树不唯一。
7.3图的存储结构l邻接矩阵:
邻接矩阵是表示顶点之间相邻关系的矩阵。
设图G=(V,E)有n个顶点,则G的邻接矩阵是一个n阶方阵:
A[i][j]=若图是带权(w)图,则:
A[i][j]=l邻接表:
邻接表就是对图中的每个顶点ki建立一个单链表,把与ki相邻接的顶点放在一个链表中。
7.4图的遍历l深度优先搜索遍历(DFS):
首先访问指定的起始顶点v,然后选取与v邻接的未被访问的任意一个顶点w,访问之,再选取与w邻接的未被访问的任一顶点,访问之。
重复进行如上的访问,当到达一个所有邻接顶点都被访问过时,则依次退回到最近被访问过的顶点,若它还有邻接顶点未被访问过,从这些未被访问过的顶点中取其中的一个顶点开始重复上述的访问过程,直到所有的顶点都被访问过为止。
l广度优先搜索遍历(BFS):
首先访问指定的起始顶点v,然后选取与v邻接的全部顶点w1,w2,...,wt,再依次访问与w1,w2,...,wt邻接的全部顶点(已被访问的顶点除外),再从这些被访问的顶点出发,逐次访问与它们邻接的全部顶点(已被访问的顶点除外)。
依次类推,直到所有顶点都被访问过为止。
l深度优先生成树和广度优先生成树:
在对具有n个顶点的连通图进行遍历时,要访问图中的所有顶点,在访问n个顶点过程中一定经过n-1条边,由深度优先遍历和广度优先遍历所经过的n-1条边是不同的,通常把由深度优先遍历所经过的n-1条边和n个顶点组成的图形就称为深度优先生成树。
而由广度优先遍历所经过的n-1条边和n个顶点组成的图形就称为广度优先生成树。
7.5最小生成树l定义:
生成树中边权之和定义为树权,在图的所有生成树中树权最小的那棵生成树就是最小生成树。
l最小生成树的算法:
普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法,Prim算法的时间复杂度为O(n2),它适用于稠密图,而Kruskal算法的时间复杂度为O(elog2e),它适用于稀疏图。
7.6拓扑排序l拓扑排序就是对一个有向无环图(AOV网)中的各顶点排成一个具有前后次序的线性序列。
l拓扑排序的方法:
在图中始终找无前趋(入度为零)的顶点,找到无前趋的顶点输出并将其每个后继顶点的前趋数(入度数)减1,重复上述过程直至所有顶点都输出或无顶点可输出。
只要图是无环的,一定能输出所有的顶点,否则说明有向图存在环。
算法的时间复杂度为O(n+e)。
7.7关键路径l带权有向图(AOE网)中从源点(表示工程开始)到汇点(表示工程结束)的路径长度最长的路径称为关键路径。
关键路径上的所有活动都是关键活动,只要提高关键路径上的活动的速度就能缩短整个工程的工期。
7.8最短路径l最短路径是图中两个顶点之间的最短距离或最便宜的交通费用或途中所需的时间最少的问题。
要找出最短路径方法很多。
常用经典算法Dijkstra算法来求从一个源点到其他顶点的最短路径。
l【例7-1】已知图G如图2-15所示从v0出发深度优先遍历序列是v0v1v2v3v7v4v5v6或v0v3v2v7v1v4v5v6等,从v0出发广度优先遍历序列:
v0v1v3v4v2v5v6v7或v0v4v3v1v6v5v2v7等。
【例7-2】对于图2-15所示无向图,从v0出发深度优先遍历生成树和广度优先遍历生成树如图2-16所示。
【例7-3】用Prim算法构造的最小生成树的过程如图2-17所示。
【例7-4】用Kruskal算法构造的最小生成树的过程如图2-18所示。
【例7-5】假设某专业中的六门课程的前修后继之间的关系如图2-19所示,课程的教学安排次序为:
c1、c3、c2、c5、c4、c6。
或c1、c2、c3、c5、c4、c6。
这就是拓扑排序序列,方法是将图中的无前驱的结点输出,若有多个无前驱的结点,则用栈或队列暂存无前驱的结点,然后依次输出并将后件的前驱数减一。
【例7-6】已知AOE网如图2-20(a)所示,其中顶点表示事件,弧表示活动,弧上的数值表示活动需要的时间,关键路径如图2-20(b)所示。
2-22有向图的邻接矩阵【例7-7】有向图G如图2-21所示,G的邻接矩阵如图2-22所示:
从源点v0到各终点的最短路径值、路径和Dijkstra算法的动态执行过程如图2-23所示:
输出结果为:
v0到v2:
v0→v2距离10v0到v4:
v0→v4距离30v0到v3:
v0→v4→v3距离50v0到v5:
v0→v4→v3→v5距离60v0到v1:
无路径距离∞第九章查找9.1查找概念9.2静态查找表上的查找方法:
9.3动态查找表的查找1.二叉搜索(排序)树l定义:
非空的二叉排序树中的任意结点K,若k有左子树,则左子树中的每个结点的值都小于k的值;若k有右子树,则右子树中的每个结点的值都大于等于k的值。
(注意:
k是指树中的每个结点)l查找:
将待查元素与二叉排序树的根比较,若相等,则查找成功;若待查元素小于根,则在左子树中找;若待查元素大于根,则在右子树中找;重复这样的查找过程直至找到(查找成功)或子树空(查找不成功)止。
l插入:
先查找插入位置,然后新结点挂在从根到插入位置这条路径的末端。
l删除:
先查找到被删元素,①若被删元素是叶子,则直接删除;②若被删结点是单支(被删结点只有左子树或只有右子树)结点,则将单支的子树挂到被删结点的父结点上即从树上断开了被删结点;③若被删结点是双支(被删结点有左子树又有右子树)结点,则将左子树挂到被删结点的中序后继的左边或将右子树挂到被删结点的中序前驱的右边,这样变成删单支结点如情况②所述操作。
2.平衡二叉树(AVL树)l定义:
对于非空的平衡二叉树中的任意结点K,K的左子树和右子树的深度之差的绝对值不超过1。
注意:
k是指树中的每个结点。
l插入:
在平衡二叉排序树中插入结点,然后检查是否因插入结点而破坏平衡,若是,则找出其中最小的不平衡二叉树,按如图2-24所示情况进行调整。
图2-24中结点的值为该结点的平衡值,阴影结点的平衡值为1或0或-1。
3.B_树lB_树定义:
一棵m阶B_树,或是空树,或是满足下列特性的m叉树:
①树中每个结点最多有m棵子树;②若根不是叶结点,则至少有两棵子树;③除根外的每个非终端结点至少有棵子树;④所有非终端结点中都包含下列数据信息:
(n,A0,K1,A1,K2,A2,…,Kn,An)其中Ki(i=1,2,…,n)为关键字且由小到大有序排列,Ai(i=0,1,…,n)为指向子树根的指针,且指针Ai-1所指子树中的所有结点的关键字均小于Ki,An所指结点的关键字均大于Kn,n为结点中的关键字数目()。
⑤所有的叶子结点都出现在同一层次上,并且不带信息(看作外部结点或查找失败结点)。
一棵3阶B_树如图2-25所示。
3阶B_树也称2-3树。
lB_树的查找:
类似二叉排序树的查找,首先在根结点包含的关键字中查找,若找到则成功返回;否则根据待查的关键字在相应的子树中继续查找,直至查找成功或查找失败。
lB_树的插入:
B_树的结点插入只在底层进行,先查找插入位置,在底层某个位置中插入结点,若该结点中的关键字个数不超过m-1,则插入完成;否则进行结点的“分裂”处理。
“分裂”就是把结点中处于中间位置上的关键字取出插到父结点中,并以该结点为分界线,把原结点分成两个结点,对父结点再进行关键字个数判断,“分裂”过程可能一直持续到树根。
lB_树的删除:
先找到被删结点,若被删结点不在底层,则用底层的后继(或前驱)替代,然后再删后继(或前驱),若被删结点关键字数目小于则进行“合并”,否则删除完成。
4.哈希表及其查找l哈希表:
设哈希函数H(Key),结点的存储方法为:
H(关键字)=存储位置,即关键字作为函数的自变量,函数值解释为存储位置,按这种方法得到的存储结构图称为哈希表。
l解决冲突的方法:
当哈希函数H(Key)不是一对一函数时则产生冲突,冲突即两个不同结点占同一存储空间。
常见的处理冲突的方法有:
①开放地址法:
Hi=(H(Key)+di)%Mi=1,2,…,M-1其中H(Key)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 复习 要点