数据结构-考研课程总结

1、2020/6/16,数据结构,1,数据结构,主讲刘铁铭单位工院一系二教Tel:31946,2020/6/16,数据结构,2,讲课安排：串讲全书内容典型习题分析前年、去年考题分析,2020/6/16,数据结构,3,第一章概论,2020/6/16,数据结构,4,2020/6/16,数据结构,5,2020/6/16,数据结构,6,逻辑结构：(有时直接称为数据结构）线性结构：线性表、栈、队列、串(最多只有一个直接前趋和一个直接后继)非线性结构：树、图、多维数组、广义表说明：1、逻辑结构与数据元素本身的形式、内容无关2、逻辑结构与数据元素的相对位置无关3、逻辑结构与所含结点个数无关,2020/6/16,

2、数据结构,7,存储结构：顺序存储方法：数据元素在内存中按序连续存储，结点间的逻辑关系由存储单元的邻接关系来体现链接存储方法：用指针指出其直接后继结点的存储位置，结点间的逻辑关系由存储单元的邻接关系来体现索引存储方法：数据元素连续存放，再设一个索引表（有序），索引表由索引项组成，每个索引项由关键字和地址构成分为稠密索引和稀疏索引散列存储方法：确定散列函数后，根据结点的关键字直接计算出该结点的存储地址。,2020/6/16,数据结构,8,关系：逻辑结构是从逻辑关系上描述数据，与存储无关，是独立于计算机的。逻辑结构是从具体问题抽象出来的数学模型存储结构是逻辑结构用计算机语言的实现（亦称映象）数据的运

3、算是定义在数据的逻辑结构上的一个运算的集合运算的实现与存储结构密切相关逻辑结构与存储结构是多对多的关系,2020/6/16,数据结构,9,例：一个学生成绩表：是一个数据结构每行是一个结点（或记录），由学号、姓名、各科成绩及平均成绩等数据项组成。逻辑关系：线性结构存储结构：表的运算：,2020/6/16,数据结构,10,2020/6/16,数据结构,11,2020/6/16,数据结构,12,2020/6/16,数据结构,13,2020/6/16,数据结构,14,第一章概论,三、（渐进）时间复杂度(O(f(n)当问题的规模n趋向无穷大时，时间复杂度T(n)的数量级（阶）称为算法的渐近时间复杂度，简

4、称时间复杂度四、最坏时间复杂度依据数据集中可能出现的最坏情况估算出的时间复杂度称为最坏时间复杂度。五、平均时间复杂度在假设数据集的分布是等概率的条件下，估算出的时间复杂度称为平均时间复杂度。例：顺序查找,2020/6/16,数据结构,15,五、空间复杂度S(n)：算法所耗费的存储空间，仍是问题规模n的函数。,第一章概论,2020/6/16,数据结构,16,第一章概论,2020/6/16,数据结构,17,第二章线性表,本章要学习的主要内容1、线性表的逻辑结构及基本运算2、线性表的顺序存储结构3、线性表的链式存储结构：单链表、循环链表、双链表、静态链表4、顺序表和链表的比较,2020/6/16,数

5、据结构,18,2020/6/16,数据结构,19,2020/6/16,数据结构,20,2020/6/16,数据结构,21,2020/6/16,数据结构,22,2020/6/16,数据结构,23,2020/6/16,数据结构,24,2020/6/16,数据结构,25,2020/6/16,数据结构,26,2020/6/16,数据结构,27,2020/6/16,数据结构,28,2020/6/16,数据结构,29,2020/6/16,数据结构,30,2020/6/16,数据结构,31,2020/6/16,数据结构,32,2.3.2单链表上的基本运算（实现）,Linklist*CREATLISTR1()

6、charch;linklist*head,*s,*r;head=malloc(sizeof(linklist);r=head;ch=getchar();while(ch!=“$”)s=malloc(sizeof(linklist);s-data=ch;r-next=s;r=s;ch=getchar();r-next=NULL;returnhead;,2020/6/16,数据结构,33,2020/6/16,数据结构,34,按值查找即在链表中查找是否有值等于给定值key的结点。若有则返回首次找到的其值为key的结点的指针，否则返回NULL。,算法描述如下：linklist*locate(head,

7、key)linklist*head;datatyekey;linklist*p;p=headnext;,在等概率的情况下，该算法的平均时间复杂度亦为O(n),（2）按值查找LOCATE（head，key）,2.3.2单链表上的基本运算（实现）,while(p!=NULL)if(pdata!=key)p=pnext;elsebreak;returnp;,2020/6/16,数据结构,35,3.插入运算,（1）后插操作:在指针p所指结点之后插入,（2）前插操作:在指针p所指结点之前插入,时间复杂度度O(1),平均时间复杂度O(n),先从头指针起,顺链找到*p的前趋结点*q.,2020/6/16,数

8、据结构,36,x,3.插入运算:,将前插操作转变为后插操作,a,2020/6/16,数据结构,37,4.删除运算,时间复杂度O(1),删除指定结点的直接后继,r=p-next;p-next=r-next;free(r);,删除指定结点,时间复杂度O(n),链表的优点:在链表上实现插入、删除运算无须移动结点，仅须修改指针,2020/6/16,数据结构,38,2020/6/16,数据结构,39,2020/6/16,数据结构,40,DELETENODE（p）/*删除双链表结点*p*/dlinklist*p;p-prior-next=p-next;p-next-prior=p-prior;free(p

9、);,2020/6/16,数据结构,41,2020/6/16,数据结构,42,2.3.5静态链表,静态链表与动态链表的区别,2020/6/16,数据结构,43,2、静态链表存储结构描述如下：definemaxsize1024typedefintdatatype;typedefintcursor;typedefstructdatatypedata;数据域cursornext;游标node;nodenodepoolmaxsize;存储池cursorav;游标变量,2020/6/16,数据结构,44,2020/6/16,数据结构,45,2020/6/16,数据结构,46,4、节点的分配与回收,GET

10、NODE():将表av上的第一个结点取出，并把该结点的位置付给pCursorGETNODE()cursorp;if(av=NULL)p=NULL;elsep=av;av=nodepoolav.next;returnp;,FREENODE(p)将p所指的结点插入到表av的头上。FREENODE(p)nodepoolp.next=av;av=p,2020/6/16,数据结构,47,2020/6/16,数据结构,48,2020/6/16,数据结构,49,2020/6/16,数据结构,50,2020/6/16,数据结构,51,2020/6/16,数据结构,52,2020/6/16,数据结构,53,20

11、20/6/16,数据结构,54,2020/6/16,数据结构,55,2020/6/16,数据结构,56,4链栈上基本运算的实现：1）进栈PUSHLSTACK(top,x),2020/6/16,数据结构,57,2）退栈*POPLSTACK(top,datap),2020/6/16,数据结构,58,3.2栈的应用举例,1.文字编辑器2.函数的递归调用（p47),2020/6/16,数据结构,59,2020/6/16,数据结构,60,3队列的基本运算：（1）SETNULL（Q）置队空（2）EMPTY（Q）判队空（3）FRONT（Q）取队头元素,队中元素保持不变（4）ENQUEUE（Q,x)将元素x入

12、队（5）DEQUEUE（Q）出队,函数返回原队头元素,2020/6/16,数据结构,61,2020/6/16,数据结构,62,2020/6/16,数据结构,63,2020/6/16,数据结构,64,解决“假上溢”的方法有两种：,2020/6/16,数据结构,65,采用循环队列后，进行入队和出队运算时，头、尾指针加1操作应如下进行：出队：sqfront=(sqfront+1)%maxsize;入队：sqrear=(sqrear+1)%maxsize;,循环队列如何判断队空和队满?,方法一：引入标志flag若(sqfront=sqrear)structlinknode*next;linkstrin

13、g;linkstring*s;,如果结点大小不为1，则此处应说明一个字符数组。,链串存储结构描述如下：,2020/6/16,数据结构,78,2020/6/16,数据结构,79,2020/6/16,数据结构,80,2020/6/16,数据结构,81,1.朴素的匹配算法,基本思想：初始时，从S的第一个字符开始将T的第一个字符与其进行比较，若相等，则继续逐个比较后续字符，如匹配成功，则返回子串在S中的位置，否则，将T向右移动一个字符位置，从T的第一个字符开始与S中第二个字符进行比较，并在相等的情况下逐个比较后续字符，进行第二趟匹配，成功则返回子串在S中的位置，否则，T再向右移动一个字符位置，进行第三

14、趟匹配，如此反复，或匹配成功，或当T右移到无法与S继续进行比较时，匹配失败。,2020/6/16,数据结构,82,设S=“ababcabcacbab”T=“abcac”,i指针回溯的位置为：i=i-j+1（i的值为1）,1.朴素的匹配算法,2020/6/16,数据结构,83,设S=“ababcabcacbab”T=“abcac”,i指针回溯的位置为：i=i-j+1（i的值为2）,2020/6/16,数据结构,84,设S=“ababcabcacbab”T=“abcac”,i指针回溯的位置为：i=i-j+1（i的值为3）,2020/6/16,数据结构,85,设S=“ababcabcacbab”T=

15、“abcac”,i指针回溯的位置为：i=i-j+1（i的值为4）,2020/6/16,数据结构,86,设S=“ababcabcacbab”T=“abcac”,i指针回溯的位置为：i=i-j+1（i的值为5）,2020/6/16,数据结构,87,设S=“ababcabcacbab”T=“abcac”,返回子串的位置为：i-j+1=6（串的起始位置从1开始算起）,2020/6/16,数据结构,88,intindex(s,t)seqstring*s,*t;inti=0,j=0;while(i=j则k=i*(i+1)/2+jb:若i=0)个结点的有限集，它或者是空集(n=0)或者由一个根结点和两棵互不

16、相交的，分别称为根的左子树和右子树的二叉树组成。可以看出，二叉树的定义和树的定义一样，均为递归定义。,2020/6/16,数据结构,124,2020/6/16,数据结构,125,6.2.2二叉树的性质,性质1：二叉树第i层上的结点数目最多为2i-1(i=1)性质2：深度为k的二叉树至多有2k-1个结点(k=1)性质3：任意二叉树中，若叶结点的个数为n0,度为2的结点数为n2，则n0=n2+1。,2020/6/16,数据结构,126,2020/6/16,数据结构,127,两种特殊形态的二叉树：满二叉树和完全二叉树深度为k且有2k-1个结点的二叉树称为满二叉树。,对满二叉树的结点进行编号，约定编号

17、从根结点起，自上而下，自左至右。,深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应，则称之为完全二叉树。,2020/6/16,数据结构,128,2020/6/16,数据结构,129,2020/6/16,数据结构,130,2020/6/16,数据结构,131,2020/6/16,数据结构,132,2020/6/16,数据结构,133,2020/6/16,数据结构,134,2020/6/16,数据结构,135,2020/6/16,数据结构,136,2020/6/16,数据结构,137,2020/6/16,数据结构,138,2020/6/16,数

18、据结构,139,算法描述：preorder(t)bitree*t;if(t)printf(“t%c”,tdata);preorder(tlchild);preorder(trchild);,2020/6/16,数据结构,140,三种遍历算法的：1）printf()在算法中的位置不同2）执行时所“走”的路线是一样的。每个结点经过三次。3）访问结点的时机不同得到不同的遍历次序。递归算法看似简单，但执行过程相当复杂。P97,2020/6/16,数据结构,141,2020/6/16,数据结构,142,第一次经过的结点:,第二次经过的结点:,第三次经过的结点:,a,b,d,e,c,f,d,b,a,c,e

19、,f,d,b,e,c,f,a,2020/6/16,数据结构,143,typedefbitree*datatype;typedefstructnodedatatypedata;structnode*next;linkstack;inorder(t)bitree*t;linkstack*top;top=NIL;dowhile(t!=NIL)top=pushlstack(top,t);t=tlchild;if(top!=NIL)top=poplstack(top,算法描述如下：,2020/6/16,数据结构,145,lorder(t)bitree*t;sequeue*sq;/*sq为循环队列指针*/

20、bitree*xsetnull(sq);if(t!=NULL)enqueue(sq,t);while(!empty(sq)x=dequeue(sq);printf(%dt,xdata);if(xlchild!=NIL)enqueue(sq,xlchild);if(xrchild!=NIL)enqueue(sq,xrchild);,2020/6/16,数据结构,147,6.4线索二叉树,问题单单依靠二叉树并不能直接得到结点在任一序列中的前趋和后继,这种信息只有在动态遍历中才能得到.所以某次遍历得到的信息,下次再用时,仍要重新遍历.,一、如何保存在遍历过程中得到的信息?,2020/6/16,数据结

21、构,148,利用已有的指针域存放:,利用二叉链表上的n1个空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针，由此得到的二叉链表称为线索链表，相应地采用这种存储结构的二叉树称为线索二叉树。,线索链表中结点的结构：,typedefstructnodeintltag,rtag;datatypedata;structnode*lchild,*rchild;bithptr;bithptr*p;,2020/6/16,数据结构,149,线索化(建立某次序线索二叉树的步骤2，步骤1类似于二叉链表的建立过程）:将二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。具体地体现在将二叉链表变为线索链

22、表。,2020/6/16,数据结构,150,2020/6/16,数据结构,151,2020/6/16,数据结构,152,2020/6/16,数据结构,153,2020/6/16,数据结构,154,2020/6/16,数据结构,155,2020/6/16,数据结构,156,2020/6/16,数据结构,157,2020/6/16,数据结构,158,2、遍历线索二叉树,遍历二叉树：指按某种路径对树中结点访问且仅访问一次。,遍历线索二叉树：从某次序下的开始结点出发，反复找到该结点在该次序下的后继，直至终端结点。,算法要点：,（1）如果线索二叉树非空，则做（2），否则结束。（2）找到某次序下的开始结点

23、。（3）访问该结点。（4）找到该结点在该次序下的后继。（5）不是空则转（3），否则结束,2020/6/16,数据结构,159,总结：1）遍历线索二叉树对中序和前序线索树，很容易实现。但后序不好实现。因为后序后继不能直接找到。2)比二叉树遍历算法简单易理解，且无需设栈。3）若一棵二叉树要经常进行遍历运算，或经常查找结点在某种指定次序下的前趋和后继，则选用线索二叉树。,2020/6/16,数据结构,160,3、线索二叉树的插入,线索二叉树的优点：查找和遍历优于非线索树。,线索二叉树的缺点：插入和删除不仅要修改指针，还要修改线索。,线索二叉树的插入和删除也分为前序，中序和后序，,2020/6/16,

24、数据结构,161,2020/6/16,数据结构,162,2020/6/16,数据结构,163,2020/6/16,数据结构,164,2020/6/16,数据结构,165,2020/6/16,数据结构,166,2020/6/16,数据结构,167,2020/6/16,数据结构,168,3.孩子兄弟链表表示法,在存储结点信息的同时,附加两个分别指向该结点最左孩子和右邻兄弟的指针域。该方法实际上是用二叉链表实现树的储存。,2020/6/16,数据结构,169,2020/6/16,数据结构,170,2020/6/16,数据结构,171,2020/6/16,数据结构,172,特点：1)前序遍历森林得到的

25、序列与前序遍历对应二叉树得到的序列相同。2)后序遍历森林得到的序列与中序遍历对应二叉树得到的序列相同。,2020/6/16,数据结构,173,2020/6/16,数据结构,174,2、哈夫曼算法已知w1,w2,wn这n个权值后，如何构造哈夫曼树？,1）哈夫曼算法思想(1)根据给定的n个权值w1,w2,wn构造n棵只有根结点的树(2)从中选两棵根结点权值最小的树进行合并，增加一个新结点作为新树的根，树的数目减少一棵。(3)重复(2),直到F只含一棵二叉树为止，这棵二叉树便是哈夫曼树。,(10,9,5,6),2020/6/16,数据结构,177,哈夫曼树的特点哈夫曼树中只有0度和2度结点，不可能有

26、1度结点。具有n个叶结点的哈夫曼树所含结点数必为2n-1。具有n个叶结点的哈夫曼树的最大高度为n。哈夫曼树的形式不是唯一的，但wpl值是唯一的。哈夫曼树不一定是朝一个方向的。,2020/6/16,数据结构,178,2020/6/16,数据结构,179,构造最优(平均码长最短的)前缀码的方法如下：,（1）以字符集中每个字符出现的概率为权值，构造哈夫曼树。（2）在哈夫曼树中每个分支结点的左分支上标上0，右分支上标上1。（3）把从根到每个叶结点的路径上的所有0或1标号连接起来作为叶结点所代表的字符的编码。,2020/6/16,数据结构,180,图是一种复杂的非线性结构。线性结构、树形结构中对结点而言

27、，存在前趋和后继的概念，图中的结点（通常称为顶点）是否也有前趋和后继呢？不能一概而论。,图G由两个集合V和E组成，记为G=(V,E),其中V为顶点的有穷非空集合，E为V中顶点偶对(即边)的集合。图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空集，若E(G)为空，则图G只有顶点而没有边。,第七章图,有向图:图G中的每一条边都是有方向的，。无向图:图中的每一条边都是无方向的。(vi,vj),2020/6/16,数据结构,181,简单图:以下我们讨论的图是满足下列两条件的简单图：,（1）不含顶点到自身的边，即若（Vi，Vj）或Vi，VjE（G）则ViVj（2）不允许一条边在图中重复出现

28、具有上述要求的图，其顶点数n和边数e满足下列关系:若G为无向图0en（n-1）/2若G为有向图0en（n-1）,2020/6/16,数据结构,182,恰好有n(n-1)/2条边的无向图称为无向完全图；恰好有n(n-1)边的有向图称为有向完全图。,若(vi,vj)是一条无向边，则称顶点vi和vj互为邻结点(Adjacent)，(vi,vj)与顶点vi和vj相关联(Incident)。若是一条有向边，则称顶点vi邻接到vj,顶点vj邻接于vi,与顶点vi和vj相关联。,度、入度和出度的概念：无向图中顶点v的度为关联于该顶点的边的数目，记为D(v)有向图中把以顶点v为终点的边的数目称为v的入度，记为

29、ID(v)把以顶点v为始点的边的数目称为v的出度,记为OD(v)顶点的度定义为入度与出度之和，即D(v)=ID(v)+OD(v)。,2020/6/16,数据结构,184,子图的概念:设G=(V,E)是一个图，若V是V的子集，E是E的子集且E中的边所关联的顶点均在V中，则G=(V,E)也是一个图，并称其为G的子图。,V=v0,v1,E=(v0,v2),G=(V,E)不是图,也不可能是子图。,第七章图,2020/6/16,数据结构,185,2020/6/16,数据结构,189,2、邻接矩阵存储结构描述：#definen./*图中顶点个数*/#definee./*图中边(弧)条数*/typedefc

30、harvextype;/*顶点数据类型*/typedeffloatadjtype;/*权值类型*/typedefstructvextypevexsn;/*数组vexs用于存储顶点数据*/adjtypearcsnn;/*arcs为邻接矩阵*/graph;若图中顶点信息仅为编号,则仅需存储一个邻接矩阵即可表示图。采用邻接矩阵表示法实现图的存储，空间复杂度为O(n2)。,2020/6/16,数据结构,192,2020/6/16,数据结构,193,typedefstrcutvextypevertex;edgenode*link;vexnode;/*顶点表结点结构*/vexnodegan;,2、邻接表存

31、储结构描述：typedefstructnodeintadjvex;structnode*nextedgenode;/*边表结点结构*/,2020/6/16,数据结构,194,2020/6/16,数据结构,195,2020/6/16,数据结构,197,7)总结,第七章图,2020/6/16,数据结构,198,定义图的遍历是指从图的某个顶点出发，沿着某条搜索路径对图中所有顶点访问且仅访问一次。,7.3图的遍历,一.图遍历运算的基本概念,2020/6/16,数据结构,199,特点：遍历过程中尽可能地先对纵深方向进行搜索,2020/6/16,数据结构,200,DFSL(i)inti;intj;edge

32、node*p;printf(“node:%cn,gli.vertex);visitedi=TRUE;p=gli.link;/*取vi的边表头指针*/while(p!=NULL)/*依次搜索vi的邻接点*/if(!visitedp-adjvex)/*从vi的未曾访问过的邻接点出发进行深度优先搜索*/DFSL(p-adjvex);p=p-next;/*找vi的下一邻接点*/,以邻接表为存储结构的深度优先算法:,2020/6/16,数据结构,201,7.3图的遍历,DFS序列不唯一,它与遍历算法，图的存储结构以及初始出发点有关。,3.算法分析,对于具有n个顶点、e条边的连通图：,对图进行深度优先搜索

33、得到的顶点序列称为深度优先搜索序列，简称为DFS序列。,注意,2020/6/16,数据结构,202,7.3图的遍历,三.连通图的广度优先搜索遍历(BreadthFirstSearch),1.BFS基本思想从图G中任一顶点vi开始，首先访问顶点vi，接着依次访问vi的所有邻接点w0,w1,wt，然后再依次访问w0,w1,wt邻接的所有未被访问过的顶点，依次类推，直到图中所有和vi有路径相通的顶点都被访问过为止。,特点：尽可能地先对横向进行搜索。,BFS算法,符合先进先出性质。在算法实现过程中，引入队列作为辅助存储结构，存储已被访问的顶点。,2.算法实现:,2020/6/16,数据结构,203,B

34、FSL(intk)inti;edgenode*p;setnull(q);printf(%cn,glk.vertex);visitedk=true;enqueue(q,k);while(!empty(q)i=dequeue(q);p=gli.link;while(p!=null)if(!visitedpadjvex)printf(%cn,glpadjvex.vertex);visitedpadjvex=true;enqueue(q,padjvex);p=pnext;,/*从vk出发广度优先搜索图,图G用邻接表表示*/,/*初始将队列q置空*/,/*访问出发点vk并置访问标志*/,/*已访问的顶点

35、序号入队*/,/*队头元素序号出队列*/,/*取vi邻接表的头指针*/,/*访问vi未访问的邻接点*/,/*已访问的顶点序号入队*/,/*找vi的下一个邻接点*/,2020/6/16,数据结构,204,7.3图的遍历,对图进行广度优先搜索得到的顶点序列称为广度优先搜索序列，简称为BFS序列。,两种遍历方法比较：,BFS序列不唯一,BFS序列与遍历算法，图的存储结构以及初始出发点有关。,3.算法分析,对于具有n个顶点、e条边的连通图：,二者对顶点的搜索次序不同,两种遍历方法实现的手段不同,注意,2020/6/16,数据结构,205,7.3图的遍历,四.非连通图的遍历,非连通图具有两个或两个以上的

36、连通分量,当从某个顶点vi开始对其进行深度或广度优先搜索只能遍历包含顶点vi的连通分量。,非连通图的遍历须多次调用深度或广度优先搜索算法。,2020/6/16,数据结构,206,7.3图的遍历,非连通图遍历算法描述：TRAVER()inti;for(i=0;in;i+)visitedi=false;for(i=0;in;i+)if(!visitedi)DFS(i);,遍历各个连通分量,初始访问标志,深度优先搜索遍历非连通图算法,BFSL(i);,广度优先搜索遍历非连通图算法,如果图是连通的,则算法TRAVER只调用一次DFS(或BFS)；,如果图包含n个连通分量,则算法TRAVER调用n次DF

37、S(或BFS)；,7.4生成树和最小生成树,1）定义：具有n个顶点的无向连通图G，其生成树为包含有n个顶点和n-1条边的无向连通子图，或生成树是连通图G的一个极小连通子图。,1。无向连通图的生成树的定义,2）特点：a.无向连通图的生成树通常是不唯一的b.生成树满足连通性且边数最小,3）无向非连通图没有生成树，但其各个连通分量有生成树，各个连通分量的生成树形成一个森林，称为无向非连通图的生成森林。,第七章图,2020/6/16,数据结构,209,2020/6/16,数据结构,210,2020/6/16,数据结构,211,Prim算法思想：假设G=(V,E)为无向连通网，生成的最小生成树T=(U,

38、TE)。求T（实际上求TE）的步骤为：1）初始化U=u0，TE=2）在所有uU，vV-U的边(u,v)中找一条权值最小的边(u0,v0)并入集合TE，同时v0并入U。3）若U=V，算法结束。否则重复2）,5。如何求无向连通网的最小生成树。,prim算法的时间复杂度为O(n2),与无向连通网中顶点数n有关，与边无关，因此该算法适合稠密连通网。,2020/6/16,数据结构,212,Kruskal算法的初略描述：G=(V,E),T=(V,);while(T中所含边数dk+,则将dk+的值赋给dj,否则，dj的值不变。,2）Djkstra算法的粗略描述：S=v;初始化V-S中各顶点的距离值；whil

39、e(S中的顶点数n)从V-S中选取距离值最小的顶点vj;S=S+vj;调整V-S中各顶点的距离值；,2020/6/16,数据结构,217,2020/6/16,数据结构,218,定义一个nn的方阵序列：A(-1)，A(0)，A(1)，A(k)，A(n-1)其中:A(-1)ij=cijA(k)ij=MinA(k-1)ij,A(k-1)ik+A(k-1)kj0=k=n-1由上述公式可知，A(0)ij是从顶点vi到vj的中间顶点序号不大于0的最短路径；A(k)ij是从顶点vi到vj的中间顶点序号不大于k的最短路径；A(n-1)ij就是从顶点vi到vj的最短路径。,2）实现原理：定义一个nn的方阵序列：

40、,2020/6/16,数据结构,219,3）具体实现a)Floyd算法在具体实现时仅使用一个nn的方阵A，初始时A=cij,通过在A上进行n次迭代求得A(n-1)。由于是在同一个矩阵A中迭代，所以A(k)ijA(k-1)ik+A(k-1)kj是由AijAik+Akj实现的。因此要使迭代正确，必须保证：AikA(k-1)ik，AkjA(k-1)kj，即保证Aik和Akj在该次迭代中不发生变化。,2020/6/16,数据结构,220,4）Floyd算法的具体描述：intpathnn;floyd(a,c)floatan,cn;inti,j,k,next;intmax=160;,for(i=0;i=1

41、;i-)SIFT(R,i,n),2020/6/16,数据结构,264,3、堆排序算法1）首先初始建堆2）然后进行n-1趟堆排序，每一趟排序要做的工作是i）将当前堆顶和堆尾互换ii）去掉该堆尾后的序列重新建堆,2020/6/16,数据结构,265,HEAPSORT（R）rectypeR;inti;rectypetemp;for(i=n/2;i=1;i-)SIFT(R,i,n);for(i=n;i1;i-)temp=R1;R1=Ri;Ri=temp;SIFT(R,1,i-1);,/*初始建堆*/,/*进行n-1趟堆排序*/,2020/6/16,数据结构,266,2020/6/16,数据结构,267

42、,2020/6/16,数据结构,268,8.5归并排序,2020/6/16,数据结构,269,2020/6/16,数据结构,271,2020/6/16,数据结构,272,2020/6/16,数据结构,273,2020/6/16,数据结构,274,8.6分配排序,2020/6/16,数据结构,275,2020/6/16,数据结构,276,2020/6/16,数据结构,277,2020/6/16,数据结构,278,2020/6/16,数据结构,279,平均查找长度ASL(AverageSearchLength)定义为：,pi为查找第i个结点的概率,假定结点的查找是等概率的,则pi=1/n。,ci为

43、查找第i个结点需进行比较的次数。,说明：查找是对已存入计算机的数据所进行的操作，采用什么查找方法首先取决于所采用的数据结构，即表中的结点是按什么方式组织的。为了提高查找速度。我们常用某些特殊的数据结构来组织。所以，在选择查找方法时首先要弄清楚这些方法所需的数据结构，尤其是存储结构。,2020/6/16,数据结构,280,2020/6/16,数据结构,281,2020/6/16,数据结构,282,2.二分查找,要求：线性表是有序表并且用向量作为存储结构,基本步骤(设表为升序）：i)确定查找的起始空间low-highii)求区间内中间结点的下标mid=(high+mid)/2,k与Rmid比较。若

44、，查找成功若，low=mid+1，high不变iii)判断查找区间是否还存在（lownext!=s)q=p;p=p-next;q-next=s;free(p);,2020/6/16,数据结构,316,例2：(p412.11)设有一个双循环链表，每个结点中除有prior、data和next三个域外，还有一个访问频度域freq，在链表被启用之前，其值均初始化为零。每当在链表进行一次LOCATE(L,x)运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度递减的顺序排列，以便使频繁访问的结点总是靠近表头。试编写实现符合上述要求的LOCATE运算的算法。typedefstru

45、ctdnodedatatypedata;intfreq;structdnode*prior,*next;dlklist;,2020/6/16,数据结构,317,voidlocate(dlklist*L,datatypex)dlklist*p,*q;p=L-next;while(p!=L）,插q后,2020/6/16,数据结构,318,3、假设分别以两个元素递增有序的单链表A、B表示两个集合（即同一单链表中的元素各不相同），现要求构造一个新的单链表C。C表示集合A、B的交，且C中元素也递增有序。编写实现上述运算的算法。,2020/6/16,数据结构,319,Voidinsert(A,B,C)li

46、nklist*A,*B,*C;linklist*p,*q,*r,*s;p=A-next;q=B-next;C=malloc(sizeof(linklist);r=C;while(p!=NULL),2020/6/16,数据结构,320,4、（Josephus环)任给正整数n、k，按下述方法可得一个排列1，2，n环形排列（下图），按顺时针方向从1开始计数；计满k时输出该位置上的数字（并从环中删去该数字），然后从下一个数字开始继续计数，直到所有数字均被输出为止。例如当n=10,k=3时，输出的置换是3,6,9,2,7,1,8,5,10,4。试写一算法，对输入的任意正整数n,k，输出相应的置换。,20

47、20/6/16,数据结构,321,voidreplace(head,n,k)linklist*head;intn,k;linklist*p,*q,;inti,j;i=n;p=head;/*i用于计数*/while(i0)j=0;/*j=0对应于头结点*/while(jnext!=head)j+;q=p;p=p-next;q-next=p-next;printf(“%d”,p-data);free(p);i-;p=q;,p,q,p,2020/6/16,数据结构,322,5、停车场管理：设停车场只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出，汽车在停车场内按车辆到达时的先后顺序，依次

48、由北向南排到（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，由于停车场是狭长的通道，在它之后开入车场的车辆必须先退出车场为它让路，待该辆车开出大门外后，为它让路的车辆再按原次序进入车场。在这里假设汽车不能从便道上开走。试设计一个停车场管理程序。,场栈,临时栈,便道,北,南,n辆车,分析:1)初始化两个栈及队列2）接受命令（到达或离开）和车号。i)若有车到达，先判断场栈是否满。若不满，则入场栈，否则入便道队列等待。ii)若有车离开。将场栈中的若干辆车

49、入临时栈，为该车让路。该车出场栈开走，临时栈中汽车出栈。再看便道队列是否为空。若不空说明有车等候入栈。取队头车辆入场栈。3）重复2），直到退出。（输入车号0）,场栈,临时栈,便道,北,南,n辆车,2020/6/16,数据结构,324,顺序栈、链队类型说明；顺序栈三个基本运算；链队列三个基本运算；main()seqstack*ps,*ts;linkqueue*lq;intout,num,temp;charch;setnull1(ps);setnull1(ts);setnull2(lq);out=0;scanf(“%c”,2020/6/16,数据结构,325,While(num0)switch(c

50、h)caseA:if(ps-top=maxsize-1)ENQUEUE(lq,num);elsePUSH(ps,num);break;caseD:while(!EMPTY1(ps),2020/6/16,数据结构,326,例6：p714.7voidindex(s,t)linkstring*s,*t;linkstring*p,*q,*r,*h;p=s;q=t;r=s;/*r用于指向匹配子串的第一个结点*/while(p!=null),2020/6/16,数据结构,327,7、intEQUAL(s,t)seqstrings,t;inti;if(s.curlen!=t.curlen)return(0)

51、;i=0;while(idata=q-data)q=q-next;p=p-nextif(p=null),2020/6/16,数据结构,328,8、voidmaxsubstr(seqstrings)seqstrings;intindex=0,len=0,i=0,j,k;/*index,len用于记录最长重复子串的下标和长度*/while(ilen)index=i;len=k;elsej+;i+;for(i=0;idatal2.i=x-datal1.i;y-datal2.j=x-datal1.j;y-datal2.v=x-datal1.v;,2020/6/16,数据结构,330,voidadd(a,b,c)spmatrixa,b,*c;intp,q,k;if(a.m!=