基本数据结构0904数据结构14图A

传智播客数据结构教程（14）,讲师：尹成QQ:77025077博客:,C/C+,算法+实战,传智播客,高薪就业,第2页,上堂课内容回顾,1.二叉排序树,特点：“左小右大”，中序遍历可得从小到大顺序,搜索：同子树根结点比较，同找到，小向左，大向右！,插入：搜索父结点（相应子树空）,小插左，大插右！,删除：无左子树，右子树替代删除结点有左子树，(1)左子树替代删除结点，右子树接到左子树最右下结点。（2）改进：左子树最右下结点t替代删除结点，并将t的左子树挂到其父节点的右子树上。,第3页,2.Huffman树-最优树,(1)哈夫曼树是：WPL最小的树。,(2)Huffman算法的思路：权值大的结点用短路径，权值小的结点用长路径。,(3)构造Huffman树的步骤：对权值的合并、删除与替换,(4)Huffman编码规则：左“0”右“1”，是一种前缀码也称为最小冗余编码、紧致码等，它是数据压缩学的基础。,第4页,哈夫曼树相关算法,1.建立huffman树：结点信息、父结点指针、权值、左右孩子指针。对权值的合并、删除与替换,3.Huffman译码,2.Huffman编码：左“0”右“1”，从叶子结点开始，Huffman编码是一种前缀码也称为最小冗余编码、紧致码，等等，它是数据压缩学的基础。,看实际程序注解和演示！,第5页,建立哈夫曼树,typedefchardatatype;typedefstructnodedatatypename;folatweight;intparent,lchild,rchild;huftree;,整个哈夫曼树的存储结构：2n-1个结点构成的静态链表,第6页,建树主要步骤：,2n-1个结点初始化；结点的合并，形成haffman树注意：无删除与替换操作，原结点保留,第7页,初始状态（上）与最终状态（下）P210,第8页,初始状态（左）与最终状态（右）,第9页,/*数据初始化*m=2*n-1;/总共需要的空间HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/分配空间/for(p=*HT,i=1;i=n;+p,+w)*p=wi-1.elem,wi-1.weight,0,0,0;for(i=1;i=n;+i)/结点、权值和指针初始化HTi.elem=wi-1.elem;HTi.m_weight=wi-1.m_weight;HTi.parent=HTi.lchild=HTi.rchild=0;for(;i=m;+i)/空结点初始化隐含i初值n1HTi.elem=0;HTi.m_weight=HTi.parent=HTi.lchild=HTi.rchild=0;,第10页,/*建立哈夫曼树*for(i=n+1;i=m;+i)Select(*HT,i-1,/两结点权值相加新结点权值,合并,第11页,哈夫曼编码,找到n个结点的父结点从父节点开始到叶子的路径记录下来就是编码，左0右1,注意是逆向编码，自底向上,第12页,静态顺序存储,typedefstructcnodecharbitsleafnum+1;/编码字串，最大深度为叶子结点数目intstart;/记录起始点charch;/字符名称hufcode;,结构简单但浪费空间,第13页,动态链式存储,typedefchar*huffmancode;,HC=(HuffmanCode)malloc(n*sizeof(char*);HCi=(char*)malloc(n-start)*sizeof(char);,结构复杂但节约空间,huffmancodeHC,第14页,/*哈夫曼树编码*(*HC)=(HuffmanCode)malloc(n*sizeof(char*);/分配编码空间数组char*HuffmanCodecd=(char*)malloc(n*sizeof(char);/分配求编码的工作空间cdn-1=0;/编码结束符号for(i=1;i=n;+i)/逐个字符求哈夫曼编码start=n-1;/编码结束符位置for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)/从叶子到根逆向求编码if(HTf.lchild=c)cd-start=0;elsecd-start=1;(*HC)i=(char*)malloc(n-start)*sizeof(char);/为第i个字符分配编码空间strcpy(*HC)i,第15页,c=i;f=HTi.parent;/从叶子到根逆向求编码while(f!=0)if(HTf.lchild=c)cd-start=0;/左0右1elsecd-start=1;c=f;f=HTf.parent;,for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent),第16页,哈夫曼译码,从根结点开始依次根据编码0或1向下搜索到达根结点，提取根结点的字符继续下一个循环,第17页,0011110110101,第18页,例3:设字符集为26个英文字母，其出现频度如下表所示。,注：若圆满实现了此方案，平时成绩奖励5分！,先建哈夫曼树，再利用此树对报文“Thisprogramismyfavorite”进行编码和译码。,要求编程实现：,提示：为了避免在编程调试过程中输入数据过于麻烦，可采用文件存储编码字符及其权重，每次读入即可，或直接用数组存储。,第19页,本章小结（黄色为重点内容）,1、定义和性质,2、存储结构,3、遍历,4、线索化：线索树,先序遍历,中序遍历,二叉排序树,第20页,数据结构课程的内容,多对多（m:n),第21页,7.1基本术语7.2存储结构7.3图的遍历7.4图的其他运算7.5图的应用,第7章图,第22页,7.1图的基本术语,图：记为G(V,E)其中：V是G的顶点集合，是有穷非空集；E是G的边集合，是有穷集。,问：当E(G)为空时，图G存在否？答：还存在！但此时图G只有顶点而没有边。,有向图：无向图：完全图：,图G中的每条边都是有方向的；图G中的每条边都是无方向的；图G任意两个顶点都有一条边相连接；,若n个顶点的无向图有n(n-1)/2条边,称为无向完全图若n个顶点的有向图有n(n-1)条边,称为有向完全图,V=vertexE=edge,第23页,证明：,完全有向图有n(n-1)条边。证明：若是完全有向图，则顶点1必必与所有其他顶点各有2条连线，即有2(n-1)条边，顶点2有2(n-2)条边，顶点n-1有2条边,顶点n有0条边.总边数2(n-1n-210)=2(n-1+0)n/2=n(n-1),完全无向图有n(n-1)/2条边。证明：若是完全无向图，则顶点1必与所有其他顶点各有1条连线，即有n-1条边，顶点2有n-2条边，顶点n-1有1条边,顶点n有0条边.总边数n-1n-210=（n-1+0)n/2=n(n-1)/2,第24页,例：判断下列4种图形各属什么类型？,无向,无向图(树),有向图,有向,n(n-1)/2条边,n(n-1)条边,G1的顶点集合为V(G1)=0,1,2,3边集合为E(G1)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3),完全图,完全图,第25页,稀疏图：边较少的图。通常边数n2,子图：设有两个图G(V,E)和G(V,E)。若VV且EE,则称图G是图G的子图。,稠密图：边很多的图。无向图中，边数接近n(n-1)/2；有向图中，边数接近n(n-1),带权图：即边上带权的图。其中权是指每条边可以标上具有某种含义的数值（即与边相关的数）。,网络：带权图,第26页,简单路径：,路径上各顶点v1,v2,.,vm均不互相重复。,回路：,例：,若路径上第一个顶点v1与最后一个顶点vm重合，则称这样的路径为回路或环。,路径：,在图G(V,E)中,若从顶点vi出发,沿一些边经过一些顶点vp1,vp2,vpm，到达顶点vj。则称顶点序列(vivp1vp2.vpmvj)为从顶点vi到顶点vj的路径。它经过的边(vi,vp1)、(vp1,vp2)、.、(vpm,vj)应当是属于E的边。,路径长度：,非带权图的路径长度是指此路径上边的条数；带权图的路径长度是指路径上各边的权之和。,第27页,路径：1，2，3，5，6，3路径长度：5(路径上结点数-1)简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路：3，5，6，3,路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，5，7，6，5，2，1简单回路：1，2，3，1,第28页,弧头和弧尾：有向边(u,v)称为弧，边的始点u叫弧尾，终点v叫弧头,顶点v的度是与它相关联的边的条数。记作TD(v)。在有向图中,顶点的度等于该顶点的入度与出度之和。顶点v的入度是以v为终点的有向边的条数,记作ID(v);顶点v的出度是以v为始点的有向边的条数,记作OD(v)。,邻接顶点：若(u,v)是E(G)中的一条边，则称u与v互为邻接顶点,度、入度和出度：,问：当有向图中仅1个顶点的入度为0,其余顶点的入度均为1，此时是何形状？,答：是树！而且是一棵有向树！,第29页,生成树：,是一个极小连通子图，它含有图中全部顶点，但只有n-1条边。如果在生成树上添加1条边，必定构成一个环。若图中有n个顶点，却少于n-1条边，必为非连通图。,第30页,连通图：,在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。,在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。,强连通图：,有两类图形不在本章讨论之列：,第31页,ADTGraph数据对象V：v是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R=VR；VR=|v,wV且P(v,w),表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息基本操作P：CreatGraph(初始条件：图G存在，v和图中顶点有相同特征。操作结果：在图G中添加新顶点。（参见P156-257）,图的抽象数据类型,注意：V的大小写含义不同！,第32页,7.2图的存储结构,图的特点：非线性结构（m:n）,邻接表邻接多重表十字链表,设计为邻接矩阵,链式存储结构：,顺序存储结构：,无！,（多个顶点，无序可言）但可用数组描述元素间关系。,可用多重链表,重点介绍：,邻接矩阵(数组)表示法邻接表(链式)表示法,第33页,一、邻接矩阵（数组）表示法,建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间关系）。设图A=(V,E)有n个顶点，则图的邻接矩阵是一个二维数组A.Edgenn，定义为：,例1：,邻接矩阵：,A.Edge=,（v1v2v3v4v5）,v1v2v3v4v5,0000000000000000000000000,分析1：无向图的邻接矩阵是对称的；分析2：顶点i的度第i行(列)中1的个数；特别：完全图的邻接矩阵中，对角元素为0，其余全1。,0101010101010111010101110,0101010101010111010101110,顶点表：,第34页,例2：有向图的邻接矩阵,分析1：有向图的邻接矩阵可能是不对称的。分析2：顶点的出度=第i行元素之和，OD(Vi)=A.Edgeij顶点的入度=第i列元素之和。ID(Vi)=A.Edgeji顶点的度=第i行元素之和+第i列元素之和,即：TD(Vi)=OD(Vi)+ID(Vi),邻接矩阵：,A.Edge=,(v1v2v3v4),v1v2v3v4,0000000000000000,注：在有向图的邻接矩阵中，第i行含义：以结点vi为尾的弧(即出度边）；第i列含义：以结点vi为头的弧(即入度边）。,顶点表：,0110000000011000,0110000000011000,第35页,容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。对稀疏图而言尤其浪费空间。,特别讨论：网（即有权图）的邻接矩阵,定义为：,以有向网为例：,邻接矩阵：,N.Edge=,(v1v2v3v4v5v6),邻接矩阵法优点：,邻接矩阵法缺点：,顶点表：,5748956531,5748956531,第36页,注：用两个数组分别存储顶点表和邻接矩阵#defineINFINITYINT_MAX/最大值#defineMAX_VERTEX_NUM20/假设的最大顶点数TypedefenumDG,DN,AG,ANGraphKind;/有向/无向图，有向/无向网TypedefstructArcCell/弧（边）结点的定义VRTypeadj;/顶点间关系，无权图取1或0；有权图取权值类型InfoType*info;/该弧相关信息的指针ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;,图的邻接矩阵存储表示（参见教材P161）,对于n个顶点的图或网，空间效率=O(n2),第37页,Typedefstruct/图的定义VertexTypevexsMAX_VERTEX_NUM;/顶点表，用一维向量即可AdjMatrixarcs;/邻接矩阵IntVernum,arcnum;/顶点总数，弧（边）总数GraphKindkind;/图的种类标志Mgraph;,第38页,二、邻接表（链式）表示法,对每个顶点vi建立一个单链表，把与vi有关联的边的信息（即度或出度边）链接起来，表中每个结点都设为3个域；,每个单链表还应当附设一个头结点（设为2个域），存vi信息；,表结点,头结点,邻接点域，表示vi一个邻接点的位置,链域，指向vi下一个边或弧的结点,数据域，与边有关信息（如权值）,数据域，存储顶点vi信息,链域，指向单链表的第一个结点,每个单链表的头结点另外用顺序存储结构存储。,第39页,例1：无向图的邻接表,邻接表,例2：有向图的邻接表,邻接表(出边),逆邻接表(入边),注：邻接表不唯一，因各个边结点的链入顺序是任意的。,第40页,例3：已知某网的邻接（出边）表，请画出该网络。,80,64,1,2,5,当邻接表的存储结构形成后，图便唯一确定！,第41页,分析1:对于n个顶点e条边的无向图，邻接表中除了n个头结点外，只有2e个表结点,空间效率为O(n+2e)。若是稀疏图(en2)，则比邻接矩阵表示法O(n2)省空间。,邻接表存储法的特点：,分析2:在有向图中，邻接表中除了n个头结点外，只有e个表结点,空间效率为O(n+e)。若是稀疏图，则比邻接矩阵表示法合适。,它其实是对邻接矩阵法的一种改进,怎样计算无向图顶点的度？,邻接表的缺点：,怎样计算有向图顶点的出度？怎样计算有向图顶点的入度？怎样计算有向图顶点Vi的度：,需遍历全表,邻接表的优点：,TD(Vi)=单链表中链接的结点个数,OD(Vi)单链出边表中链接的结点数ID(Vi)邻接点为Vi的弧个数,TD(Vi)=OD(Vi)+ID(Vi),空间效率高；容易寻找顶点的邻接点；,判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。,第42页,讨论：邻接表与邻接矩阵有什么异同之处？,1.联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。2.区别：对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。(考试怎么办？给定顺序）邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。3.用途：邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)；而邻接表多用于稀疏图的存储（edata;if(!visitedv)DFS2(list,v,p);p=p-link;,第54页,DFS算法效率分析:,（设图中有n个顶点，e条边）如果用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，因此遍历全部顶点所需的时间为O(n2)。如果用邻接表来表示图，虽然有2e个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间，因此遍历图的时间复杂度为O(n+e)。,结论：稠密图适于在邻接矩阵上进行深度遍历；稀疏图适于在邻接表上进行深度遍历。,第55页,二、广度优先搜索(BFS),基本思想：仿树的层次遍历过程。,Breadth_FirstSearch,v1,BFS结果,例1：,例2：,v3,BFS结果,v4v5,起点,遍历步骤,起点,v2v1v6,v9v8v7,第56页,广度遍历：V1V2V3V4V5V6V7V8,广度遍历：V1V2V3V4V5V6V7V8,广度遍历：V1V2V3V4V6V7V8V5,练习：,第57页,广度优先搜索（遍历）步骤：,简单归纳：在访问了起始点v之后，依次访问v的邻接点；然后再依次访问这些顶点中未被访问过的邻接点；直到所有顶点都被访问过为止。,广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。,第58页,讨论1：计算机如何实现BFS？,邻接表,除辅助数组visitedn外，还需再开一辅助队列！,例：,起点,辅助队列,v2已访问过了,BFS遍历结果,入队！,初始f=n-1,r=0,第59页,讨论2：BFS算法如何编程？,BFS1(List,n,v)Visit(v);Visitedv=1;front=n-1;rear=0;qrear=v;while(rear!=front)front=(front+1)%n;v=qfront;p=Listv