期末复习讲义

第1章绪论复习关键点：1.数据结构基本概念2.数据元素、数据项、逻辑结构、物理结构3.时间复杂度、空间复杂度、语句频度等计算@DCSofSUSE第1页基本概念(1)数据：全部能被计算机识别、存放和处理符号集合（包含数字、字符、声音、图像等信息）。(2)数据元素:是数据基本单位，含有完整确定实际意义。在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。(3)数据项:组成数据元素项目。它是数据不可分割最小单位。(4)数据类型：指一个类型和定义在这个类型上操作集合。例：C语言（基本类型：整型、浮点型、字符型等结构类型：数组、结构、联合、指针、枚举等）(5)抽象数据元素：抽象定义、没有实际含义数据元素。(6)抽象数据类型：用户自己定义数据类型。@DCSofSUSE第2页数据结构@DCSofSUSE第3页集合结构：

仅同属一个集合线性结构:一对一（1:1)

树结构:一对多（1:n)

图结构:多对多(m:n)线性逻辑结构可细分为4类：数据逻辑结构指数据元素之间逻辑关系。即从逻辑关系上描述数据，它与数据存放无关，是独立于计算机。@DCSofSUSE第4页（1）R=(D,S)D={a,b,c,d,e,f}S={<a,e>,<b,c>,<c,a>,<e,f>,<f,d>}解：上述表示式可用图形表示为：bcaefd此结构为线性。

例：用图形表示以下数据结构，并指出它们是属于线性结构还是非线性结构。@DCSofSUSE第5页物理结构亦称存放结构，是数据逻辑结构在计算机存放器内表示（或映像）。它依赖于计算机。存放结构可分为4大类：例：复数3.0－2.3i两种存放方式：次序、链式、索引、散列－2.303023.00300041503023.003000415－2.3法1：地址内容法2：地址内容2字节数据物理结构@DCSofSUSE第6页时间复杂度和空间复杂度怎样表示？@DCSofSUSE第7页尤其说明：假如不论算法规模怎样改变，其执行时间为一常数，则该算法时间复杂度为O(1).@DCSofSUSE第8页@DCSofSUSE第9页第2章线性表复习关键点：1.基本概念线性结构、线性表、位序、长度、空表等2.线性表基本操作主要掌握插入、删除等运算及特征3.次序存放、链式存放特点，组织方式次序表、单链表、双链表查找、插入和删除等操作@DCSofSUSE第10页

一、线性表（linear_list）线性表是n个数据元素有限序列，记为：L=（a1,a2,…,an）

数据元素之间关系是：

ai-1领先于ai，ai领先于ai+1。称ai-1是ai直接前驱元素；ai+1是ai直接后继元素。除a1外，每个元素有且仅有一个直接前驱元素，除an外，每个元素有且仅有一个直接后继元素。线性表中数据元素个数n(n>=0)称为线性表长度，当n=0时，称为空表。@DCSofSUSE第11页线性表次序存放结构一、次序存放结构

用一组地址连续存放单元依次存放线性表元素。设线性表每个元素占用k个存放单元，则第i个元素ai存放位置为：Loc(ai)=Loc(a1)+(i-1)*k其中，Loc(ai)为线性表起址。a1a2aian

bb+kb+(i-1)kb+(n-1)k

特点：存放单元地址连续（需要一段连续空间）逻辑上相邻数据元素其物理位置也相邻存放密度大（100%）随机存取元素序号与存放位置存在以下关系：Loc(ai)=Loc(a1)+(i-1)*d(1≤i≤n)线性表次序存放指用一组地址连续存放单元依次存放线性表数据元素。这称为次序表。@DCSofSUSE第12页二.插入和删除操作1.插入运算INSERT（L,i,b）插入前：L=（a1,...,ai-1,ai,...,an）插入后：L=（a1,...,ai-1,b,ai,...,an）算法思想：

①进行正当性检验，1<=i<=n+1；②判断线性表是否已满；③将第n个至第i个元素逐一后移一个单元；④在第i个位置处插入新元素；⑤将表长度加1。@DCSofSUSE第13页线性表上基本运算插入运算 含义： 将元素e插入到线性表：(a1,a2,…,ai-1,ai,…,an)中，组成新线性表(a1,a2,…,ai-1,e,ai,…,an)，满足ai-1≤e≤ai,(其中≤为比较关系),即不破坏原线性关系。表长度为n+1将元素e插入到元素ai-1之后，ai-1直接后继和ai直接前驱就改变了，需要在次序表存放结构上反应出来。@DCSofSUSE第14页2.删除运算DELETE（L,i）删除前：L=（a1,...,ai-1,ai,ai+1,...,an）删除后：L=（a1,...,ai-1,ai+1,...,an）算法思想：①进行正当性检验，i是否满足1<=i<=n；②判线性表是否已空，L.length==0；③将第i+1至第n个元素逐一向前移一个位置；④将表长度减1。思索：假如要删除指定位置开始m个元素，怎样实现？@DCSofSUSE第15页线性表次序存放结构特点(1).逻辑上相邻元素，其物理位置也相邻；(2).可随机存取表中任一元素；(3).必须按最大可能长度预分存放空间，存放空间利用率低，表容量难以扩充，是一个静态存放结构；(4).插入删除时，需移动大量元素，平均移动元素为n/2。次序表基本运算复杂度插入T(n)=O(n)，S(n)=O(1)删除T(n)=O(n)，S(n)=O(1)@DCSofSUSE第16页线性表链式表示和实现链表---线性表链式存放内涵：线性表链式存放指用任意存放单元存放线性表中元素，每个元素与其直接前驱和（或）直接后继之间关系用指针来存放。这称为链表。术语结点：数据元素及与其有直接关系元素地址组成存放单位。数据域指针域datanext（a）链表结点结构示意图datapriornextdata（b）（c）nextdata（d）prior@DCSofSUSE第17页单链表表示和实现单链表上查找运算在单链表中，必须从头指针出发进行查找：查找第i个元素查找指定元素是否在表中...若找到，则返回该元素值，不然返回ERROR。

在单链表上查找第i个元素示意图pk=1a1

a2

…ai

an^…Head

pk=i单链表查找示意图a1

a2

…ai

an^…Head

找到，返回P指向结点数据。问题：i<0或i>n呢？尤其说明：指针移动，不会删除结点。@DCSofSUSE第18页单链表上插入运算(第i个位置上插入新结点)逻辑运算(a1,a2,…,ai-1,ai,ai+1,…,an)(a1,a2,…,ai-1,e,ai,ai+1,…,an)在元素ai之前插入一个新元素e单链表上实现示意图……a1

ai

an^L

ai-1

ai+1

基本步骤：①找到第i-1个元素所在结点；②申请一个新结点s并填入e值；③

修改s指针域指向p下一结点；p①es②③④思索：第③④步是否可交换？@DCSofSUSE第19页链表优缺点优点：插入、删除时无须移动元素，只需修改指针依据需要申请存放空间，且不要求连续存放空间缺点：对表中元素只能进行次序访问用指针指示元素之间逻辑关系（直接前驱、后继），存放空间利用率低@DCSofSUSE第20页head∧ai-1ai+1anai…∧…a1双向链表双向链表上插入操作(将元素e插入到链表第i个结点前)基本步骤：(1)定位指针p指向结点ai-1;pe

s(2)建立新结点s并赋e;(3)修改snext指针域指向p下一结点：s->next=p->next;(5)修改pnext指针域指向s结点：p->next=s;(6)修改s下一结点prior指针域指向s：s->next->prior=s;(4)修改sprior指针域指向p结点：s->prior=p;问题：①修改指针步骤是否可随意？②不带头结点？@DCSofSUSE第21页双向链表上删除操作(删除第i个结点)head

∧ai-1ai+1anai…∧…a1∧基本步骤：(1)定位指针p指向结点ai;p(2)修改p前一结点next指针域指向p下一结点：p->prior->next=p->next;(3)修改p下一结点prior指针域指向p前一结点：p->next->prior=p->prior;(4)释放结点p。@DCSofSUSE第22页第3章栈和队列

一、栈概念

栈（stack）是插入和删除操作限定在表尾进行线性表。栈逻辑表示为：S=（a1,a2,…,an）表尾元素an称为栈顶(top)表头元素a1称为栈底(bottom)不含元素空表称为空栈栈运算特征是后进先出(LastInFirstOut--LIFO)或先进后出(FirstInLastOut--FILO)@DCSofSUSE第23页二、队列概念队列（Queue）是限定仅在一端插入,另一端删除线性表。允许插入一端叫队尾(rear),允许删除一端叫队头(front),不含元素空表称为空队列队列运算特征是先进先出(FirstInFirstOut--FIFO)出队列入队列a1a2…...an队头队尾@DCSofSUSE第24页插入、删除操作栈：Push(&S,x)Pop(&S,&e)GetTop(S,&e)

StackEmpty(S)队列：QueueEmpty(Q)EnQueue(&Q，e)DeQueue(&Q,&e)GetHead(Q,&e)@DCSofSUSE第25页第4章串关键点：基本概念和朴素模式匹配算法模式匹配算法朴素串匹配算法intIndex(sstringS,sstringT,intpos){//返回子串T在主串S中从第pos个字符开始位置//要求T非空，1≤pos≤Strlength(S)i=pos;j=1;while(i<=Strlength(S)&&j<=Strlength(T)){if(S[i]==T[j]){++i;++j;}else{i=i-j+2;j=1;}}if(j>Strlength(T))return(i–Strlength(T));return0;}//Index算法时间复杂度?O(n*m)，其中n、m分别为主串和子串长度@DCSofSUSE第26页第5章数组和广义表关键点：数组基本概念和特殊矩阵压缩存贮LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*d对称矩阵数组Bai,jan,na1,1a2,1a2,2a3,11234km下标a1,1a1,2…a1,na2,1a2,2…a2,n……ai,j…an,1an,2…an,na1,1a2,1a2,2…ai,j…an,1an,2…an,n……

k=?m=?@DCSofSUSE第27页第6章树与二叉树关键点：（1）二叉树性质、推论及应用性质1、性质2、性质3、性质4、性质5（2）完全二叉树概念及特点（3）二叉树遍历（4）线索二叉树基本概念和数据结构（5）树、森林与二叉树转换，及相关特点（6）Huffman树及Huffman编码@DCSofSUSE第28页树基本术语1.树结点:包含一个DE和指向其子树全部分支;2.结点度:一个结点拥有子树个数,度为零结点称为叶结点;3.树度:树中全部结点度最大值Max(D(I))含义:树中最大分支数为树度;4.结点层次及树深度:根为第一层,根孩子为第二层,若某结点为第k层,则其孩子为k+1层.树中结点最大层次称为树深度或高度5.森林:是m(m>=0)棵互不相树集合森林与树概念相近,相互很轻易转换.结论：一棵树各结点度之和，等于该树分支数目。@DCSofSUSE第29页二叉树性质(扩展要求掌握各性质推论)性质1.

在二叉树第i层上至多有2i-1个结点(i≥1)。性质2.深度为k二叉树至多有2k-1个结点(k≥1)。（深度一定，二叉树最大结点数也确定）性质3.二叉树中,终端结点数n0与度为2结点数n2有以下关系:n0=n2+1性质4.结点数为n完全二叉树，其深度为└log2n┘+1@DCSofSUSE第30页性质5.在按层序编号n个结点完全二叉树中，任意一结点i(1≤i≤n)有：⑴i=1时，结点i是树根；不然(i>1)，结点i双亲为结点└i/2┘。⑵2i＞n时，结点i无左孩子，为叶结点；不然，结点i左孩子为结点2i。⑶2i+1＞n时，结点i无右孩子；不然，结点i右孩子为结点2i+1。性质6.含有n个结点二叉链表中，有n+1个空链域。重点说明：对于前4个性质，要求能推广到多叉树。@DCSofSUSE第31页二叉树遍历遍历次序：DLR，LDR，LRD，层序遍历DLR根结点根左子树根右子树@DCSofSUSE第32页线索二叉树：⑴结点结构在二叉链表中增加ltag和rtag两个标志域lchildltagdatartagrchild

若结点有左子树，则左链域lchild指示其左孩子（ltag=0）；不然，令左链域指示其前驱（ltag=1）；若结点有右子树，则右链域rchild指示其右孩子（rtag=0）；不然，令右链域指示其后继（rtag=1）；@DCSofSUSE第33页树与二叉树转换借助于“孩子弟兄表示法”实现树与二叉树之间转化ACBD

A

B

C

D=>I

I

J

K

L=>JKL@DCSofSUSE第34页森林转化为二叉树ICBHGFEDKLMBDFCKLMEGHI结论：从根开始，沿右指针前进，结点个数对应原森林中树数目。@DCSofSUSE第35页赫夫曼编码已知某系统在通信联络中只可能出现8种字符，其概率以下表所表示:abcdefgh0.050.290.070.080.140.230.030.11agcdhefb最优二叉树01000000111111a:0010b:11c:1010d:1011e:100f:01g:0011h:000abcdefgh@DCSofSUSE第36页第7章图关键点：（1）图邻接矩阵和邻接表表示特点及关系（2）最小生成树及算法（3）完全图基本概念、拓扑排序基本概念和特点、@DCSofSUSE第37页一、数组表示法（邻接矩阵）设图G=（V，{E}）有n个顶点，则G邻接矩阵定义为n阶方阵A。其中：A[i，j]=1若（vi，vj）或<vi，vj>∈E，i≠j

0其它比如：G1邻接矩阵┌0110┐A1＝│0000││0001│1000①②G2③④⑤

┌01010┐A2＝│10101││01011│10100

01100无向图邻接矩阵为对称矩阵①②③④G1@DCSofSUSE第38页特点：判定两个顶点Vi与Vj是否关联,只需判A[i,j]是否为1顶点度轻易求得:

有向图中：

TD(Vi)=OD(Vi)+ID(Vi)

nn=∑A[i,j]+∑A[j,i]

j=1j=1

nn

无向图中：TD(Vi)=∑A[i,j]=∑A[j,i]

j=1j=1

即顶点Vi度等于邻接矩阵中第i行（或第i列）元素之和（非0元素个数之和）。即顶点Vi出度为邻接矩阵中第i行元素之和顶点Vi入度为邻接矩阵中第i列元素之和@DCSofSUSE第39页二、邻接表（adjacencylist）如图G2邻接表为：2534154353341221212345特点：设无向图中顶点数为n，边数为e，则它邻接表需要n个头结点和2e个表结点。顶点Vi度TD（Vi）=链表i中表结点数。①②G2③④⑤

@DCSofSUSE第40页二、邻接表（adjacencylist）2.有向图邻接表与无向图邻接表结构一样。只是在第i条链表上结点是以Vi为弧尾各个弧头顶点234143121234特点：1.n个顶点，e条弧有向图，需n个表头结点，e个表结点2.第i条链表上结点数，为Vi出度（求顶点出度易，求入度难）如图G1邻接表为：①②G1③④@DCSofSUSE第41页图遍历一、深度优先搜索（depth-first-search)如图G4：深到底回退深到底V1V2V4V8V5（V2V8均已访问）深到底V3V6V7回退访问V1V2V3V4V5V6V7V8二、广度优先搜索（breadth-first-search)首先访问指定顶点v0，将v0作为当前顶点;访问当前顶点全部未访问过邻接点，并依次将访问这些邻接点作为当前顶点;重复2，直到全部顶点被访问为止。@DCSofSUSE第42页最小生成树概念1.设无向连通图G=（V，{E}），其子图G’=（V，{T}）满足：①V(G’)=V(G)n个顶点②G’是连通③G’中无回路则G’是G生成树@DCSofSUSE第43页普里姆（Prim）最小生成树算法1.TE=Ф,U={u0}2.当U≠V，重复以下步骤：(1)选取（u0,v0)=min{cost(u,v)|u∈U,v∈V-U}，确保不形成回路(2)TE=TE+（u0,v0),边（u0,v0)并入TE(3)U=U+{V0}，顶点V0并入U初始化：①②①④⑤

521③3466556⑥

①1③第1步：6①1③4第2步：④6①1③42第3步：5②④6①1③42第4步：23⑤

②5④6①1③4第5步：特点:以连通为主选代价最小邻接边顶点加入序列：V1，V3，V6，V4，V2，V5顶点逐一加入@DCSofSUSE第44页克鲁斯卡尔（Kruskal）最小生成树算法步骤(v,u)ET②①④⑤

③⑥

②①④⑤

③⑥

1(1,3)0②①④⑤

52③3466556⑥

②①④⑤

5③3466556⑥

213(2,5)2(4,6)②①④⑤

③⑥

②①④⑤

5③466556⑥

②①④⑤

③⑥

②①④⑤

5③3466556⑥

5(1,4)4(3,6)②①④⑤

5③66556⑥

②①④⑤

③66556⑥

②①④⑤

③⑥

②①④⑤

③⑥

6(2,3)②①④⑤

③6656⑥

边数=n-1=5代价=(1+2+3+4+5)=15②①④⑤

③⑥

12345@DCSofSUSE第45页拓扑排序(topologicalsort)拓扑排序是一个对非线性结构有向图进行线性化主要伎俩AOV网可处理以下两个问题：（1）判定工程可行性。显然，有回路，整个工程就无法结束（2）确定各项活动在整个工程执行中先后次序。称这种先后次序为拓扑有序序列。如图有以下拓扑有序序列：a1a2a3a4a6a5a7a8a9

a2a6a1a3a4a5a7a9a8a1a5a4a6a2a3a8a7a9@DCSofSUSE第46页第9章查找关键点：（1）基本概念（2）有序表查找(二分查找，或折半查找)思想、算法（3）哈希查找基本概念及冲突处理方法(链地址法，公共溢出区法)(4)二叉排序树特点@DCSofSUSE第47页查找:在查找表中确定与给定值相等DE过程.查找结果:

查找成功(table中存在给定值统计)查找不成功(table中不存在给定值统计)查找表分为:

静态查找表

(对查找表中数据元素不进行插入和删除操作)

动态查找表

(对查找表中数据元素可进行插入和删除操作)@DCSofSUSE第48页有序表查找有序表:

查找表中统计按关键字有序排列表.即:ST.elem[i].key<=ST.elem[i+1].keyi=1,2,…,n-1折半查找:

要求:查找表为有序表;查找过程:先确定待查统计范围;然后逐步缩小范围;直到:查找成功或不成功.@DCSofSUSE第49页折半查找算法intSearch_Bin(SSTableST,KeyTypekey);{low=1;high=ST.length;while(low<=high){mid=(low+high)/2;if(EQ(key,ST.elem[mid].key))returnmid;elseif(LT(key,ST.elem[mid].key))high=mid-1;elselow=mid+1;}return0;}//Search_Bin折半查找算法（递归实现）intSearch_Bin(SSTableST,intlow,inthigh,KeyTypekey);{if(low<=high){mid=(low+high)/2;if(EQ(key,ST.elem[mid].key))returnmid;elseif(LT(key,ST.elem[mid].key))returnSearch_Bin(ST,low,mid-1,key);elsereturnSearch_Bin(ST,mid+1,high,key)

;}elsereturn0;}//Search_Bin@DCSofSUSE第50页链地址法将关键字发生冲突统计存放在同一个线性链表中。例：H（key）=keymod13对关键字19，14，23，01，68，20，84，27，55，11，10，79处理结果为：

01234567891011127901146855198420231011∧∧∧∧∧∧27∧∧∧∧∧∧