3A_算法与数据结构KANG

算法与数据结构,康金辉网络信息中心电气工程系QQ:158690747Kinghui,一、什么是算法？,计算机解决问题的步骤：,1.问题分析：解决什么问题？2.算法设计：重点算法的设计和数据结构的设计。3.程序设计：编程。4.程序测试和维护：排除错误，修正。,1.什么是算法（algorithm）？解决某一特定问题的具体步骤的描述，是指令的有限序列。,2.算法的评价衡量算法优劣的标准正确性(correctness)可读性(readability)健壮性(robustness)效率与低存储量算法效率用依据该算法编制的程序在计算机上执行所消耗的时间来度量,事后统计根据算法运行后的状态统计分析而得必须先运行依据算法编制的程序所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣,了解,事前分析估计一个高级语言程序在计算机上运行所消耗的时间取决于：依据的算法选用何种策略问题的规模程序语言编译程序产生机器代码质量机器执行指令速度同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，以使用绝对时间单位衡量算法效率不合适,了解,3.算法表示,流程图：略伪代码：略：,4.算法的复杂度,A.时间复杂度：基本操作重复执行的次数的阶数；不好理解？）时间频度：一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)；n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=(f(n),称(f(n)为算法的渐进时间复杂度，简称时间复杂度。常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),.，k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低,例：两个N*N矩阵相乘的算法for(I=1;I=n;+I)for(j=1;j=n;+j)cIj=0;for(k=1;k=n;+k)cIj+=aIk*bkj;问题规模：n原操作：cIj+=aIk*bkj;基本操作重复执行的次数：f(n)=n3该算法时间度量记作T(n)=O(f(n)=O(n3)时间复杂度：O(n3),空间复杂度：指算法所需存储空间。,百钱买百鸡问题,100元钱买100只鸡，母鸡每只5元，公鸡每只3元，小鸡3只1元，问共可以买多少只母鸡、多少只公鸡、多少只小鸡？求解：设母鸡、公鸡、小鸡各为x,y,z只。则有：x+y+z=1005x+3y+z/3=100只需要解出本方程就可以得到答案。,少一个条件,方法1：用三重循环：for(I=0;I=100;I+)for(j=0;j=100;j+)for(k=0;k=100;k+)if(k%3=0,循环100万次,方法2：用两重循环：因总共买100只鸡，所以小鸡的数目可以由母鸡数和公鸡数得到。For(I=0;I100;I+)for(j=0;j100;j+)k=100ij;if(k%3=0,循环1万次,方法3：用两重循环：钱共100元，而母鸡5元1只，所以母鸡数不可能超过20只，同样，公鸡数也不超过33只。For(I=0;I=20;I+)for(j=0;j33;j+)k=100ij;if(k%3=0,循环20*34=680次,有方法4：用一重循环由x+y+z=100和5*x+3*y+z/3=100可以合并为一个方程：14*x+8*y=200,进一步简化为:7*x+4*y=100从上面方程可见，x不超过14（否则14*x超过200），并可以进一步判断x必为4的倍数14x=4*(50-2*y)，于是：For(I=0;Ilink=p-link;p-link=s;returnOK;,(1)单链表的插入运算,s-link=p-link;把原来P指向b节点的指针送到s节点；,p-link=sS节点成为p的后继节点；,voidlink_del(JD*p)/*删除P结点的直接后继结点*/JD*q;if(p-link!=NULL)q=p-link;/*p的指针域暂存；*/p-link=q-link;/*将q原来指向ai+1的指针给p*/free(q);/*将q释放*/,(2)单链表的删除运算,线性链表的查找操作设无表头结点的线性链表的头指针为h,沿着链表的开始往后找结点x，若找到，则返回该结点在链表中的位置，否则返回空地址.JD*link_search(JD*h,intx)JD*p;p=h;/*p先指向第一个结点*/while(p!=NULL,四.树与二叉树,树（tree）是一种简单的非线性结构。,1.树及其基本概念,树型结构是一种应用十分广泛的非线性数据结构，它很类似自然界中的树，直观地讲，树型结构是以分支关系定义的层次结构。树(Tree)是n(n0)个结点的有限集合。当n=0时称为空树，否则在任一非空树中;,树型结构,如图所示的树中，A为根结点，其余的结点分为三个互不相交的有限集合：T1=B，E，F，T2=C，G，J，T3=D，H，I。T1、T2和T3都是A的子树，而它们本身也是一棵树。例如，T1是一棵以B为根的树，其余结点分为互不相交的两个集合E和F，而E和F本身又是仅有一个根结点的树。,基本术语:结点的度：一个结点拥有的子树数目。如A结点的度为3，它有三个子树T1、T2和T3。E、F结点的度为0，它们没有子树。叶子：度为零的结点称叶子或终端结点。树的度：一棵树上所有结点的度的最大值就是这棵树的度。,结点的层次：根结点的层数为1，其它任何结点的层数等于它的父结点的层数加1。树的深度：一棵树中，结点的最大层次值就是树的深度。图3中树的深度为4。森林：森林是m(m0)棵互不相交的树的集合。孩子(child)：某结点子树的根称为该结点的孩子结点。,2.二叉树,定义:一个二叉树是一个有限结点的集合，该集合或者为空，或由一个根结点和两棵互不相交的被称为该根的左子树和右子树的二叉树组成。,(1)每个结点最多只能有两个孩子，即二叉树中不存在度大于2的结点。(2)二叉树的子树有左、右之分，其次序不能任意颠倒。二叉树可以有五种基本形态,二叉树的特点,图二叉树的五种基本形态,二叉树的5种形态,二叉树的性质:性质1：在二叉树中，第i层的结点数最多有2i-1(i1)个。,性质2：在深度为k的二叉树中结点总数最多有2k1个。由性质1可见，深度为k的二叉树的最大结点数为：,=2k1,图3-9两棵二叉树,满二叉树：除最后一层外，每一层上的所有结点都有两个子结点,完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。,缺少右边节点,二叉树的存储结构对于二叉树，可采用顺序存储，又可采用链式存储。A.顺序存储结构顺序存储就是将一棵二叉树的所有结点按照一定的次序顺序存放到一组连续的存储单元中，为此，必须把二叉树中所有结点构成一个适当的线性序列。,图3-10二叉树的顺序存储结构,左1,右1,左1左,左1右,右1左,B链式存储结构因为树型结构是非线性的结构，所以在存储器里表示树型结构的最自然的方法是链式存储。根据二叉树的特性，任何一个结点最多有左、右两棵子树，所以每个结点至少设有三个域：数据域和左、右指针域。其结点结构为：,图3-11二叉树及其链表存储结构,3.二叉树的遍历,遍历二叉树就是按一定的次序，系统地访问树中的所有结点，使每个结点恰好被访问一次。所谓访问结点，其含义是很广的，可以理解为对结点的增、删、修改等各种运算的抽象。,二叉树的三种遍历方式：先序遍历：若二叉树为空，则空操作；否则访问根结点；先序遍历左子树；先序遍历右子树。,(2)中序遍历：中序遍历左子树；访问根结点；中序遍历右子树。(3)后序遍历：后序遍历左子树；后序遍历右子树。访问根结点；,4.树森林与二叉树的转换,由于二叉树和树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。也就是说，给定一棵树，可以找到惟一的一棵二叉树与之对应，,图3-15树与二叉树的对应关系,一般树转换为二叉树步骤：(1)加线：亲兄弟之间加一虚连线。(2)抹线：抹掉(除最左一个孩子外)该结点到其余孩子之间的连线。(3)旋转：新加上去的虚线改实线且均向右斜(rchild)，原有的连线均向左斜(lchild)。,图3-16一般树转换为二叉树的操作过程(a)一般树；(b)加线后；(c)抹线后；(d)旋转后,图3-17森林转换成对应的二叉树的过程(a)森林；(b)各棵树对应的二叉树；(c)转换成的二叉树,5.霍夫曼树及其应用,霍夫曼树(HuffmanTree)，又称最优树，是一类带权路径长度最短的树，有着广泛的应用。结点间的路径长度：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数称为这两个结点之间的路径长度。,1951年，霍夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试。导师RobertM.Fano给他们的学期报告的题目是，寻找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，霍夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。由于这个算法，学生终于青出于蓝，超过了他那曾经和信息论创立者克劳德香农共同研究过类似编码的导师。霍夫曼使用自底向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端自顶向下构建树。,树的路径长度：从树根到树中每一个结点的路径长度之和称为树的路径长度，一般记作PL。如图所示的两棵二叉树，其路径长度分别计算如下：(a)PL=0+1+1+2+2+2+2+3=13(b)PL=0+1+1+2+2+2+3=11,1,1,13,11,易知道，对于有n个结点的所有二叉树而言，满二叉树或者完全二叉树具有最小的路径长度。把路径长度的概念推广到带权的路径长度(WeightedPathLength)。所谓带权是给树的每个终端结点赋以权值，则树的带权路径长度为,WPL=,终端节点有权值,从根节点开始到终端节点的路径长度,根节点的权值,在图中的三棵二叉树，都有四个终端结点，其权值分别为8、6、4、2，则它们的带权路径长度分别为：(a)WPL=2*2+4*2+6*2+8*2=40(b)WPL=4*2+6*3+8*3+2*1=52(c)WPL=8*1+6*2+4*3+2*3=38,霍夫曼树和霍夫曼编码一般地，假设有一组权值W1，W2，Wn，如何构造有n个叶子结点的二叉树，使各个叶子结点的权值分别为Wi(i=1，2，3，n)，且其带权路径长度WPL为最小。这是一个很有实际意义的问题。霍夫曼在1952年首先提出了一个带有一般规律的算法，很好地解决了这个问题，因此人们把这种具有最小带权路径长度的二叉树称为霍夫曼树或者最优二叉树，相应的算法称为霍夫曼算法。该算法思想是：,(1)设给定的一组权值为W1，W2，Wn，据此生成森林F=T1，T2，Tn，F中的每棵二叉树Ti只有一个带权为Wi的根结点(i=1，2，n)。(2)在F中选取两棵根结点的权值最小和次小的二叉树作为左、右子树构造一棵新的二叉树，新二叉树根结点的权值为其左、右子树根结点的权值之和。(3)在F中删除这两棵权值最小和次小的二叉树，同时将新生成的二叉树并入森林F中。(4)重复(2)和(3)，直到F中只有一棵二叉树为止。例如，给定一组权值2，7，4，8，图给出了构造相应霍夫曼树的过程。,最小,次小,从2,7,4,8集合中选7,再选8,构造二叉树,霍夫曼树的应用很广，在不同的应用中叶子结点的权值可以有不同的解释。霍夫曼树应用到信息编码中，如果能让使用频率较高的字符的编码尽可能短，这样就可以缩短整个信息通信过程中所需传送的二进制编码序列的长度，从而达到节省通信资源的目的,构造huffman树：,例如，给出下面一个文本：CASTCATSSATATATASA则有：D=C，A，S，T、W=2，7，4，5，构成的霍夫曼树如图所示。由此得到每个字符的二进制前缀编码为C：110S：111A：0T：10,C,S,T,A,原来数据有：18char*8bit=144bit现在数据有：2个*(110)（位数）+7*(1)+4*(111)+5*(10)=35位,五、图论,18世纪初在普鲁士柯尼斯堡镇(今俄罗斯加里宁格勒)流传一个问题。城内布雷格尔(Pregal)河绕过克奈霍福(Kneiphof)岛后一分为二,有七座桥横跨在河流上。问若从四个地区中的某地区出发,是否可通过每座桥恰好一次,又回到原来的出发地?欧拉在1736年圆满地解决了这一问题,证明这种方法并不存在。他在圣彼得堡科学院发表了图论史上第一篇重要文献。欧拉把实际的问题抽象简化为平面上的点与线组合,每一座桥视为一条线,桥所连接的地区视为点。这样若从某点出发后最后再回到这点,则这一点的线数必须是偶数。,1.图的定义和术语,图的定义,图是由顶点集合以及顶点间的关系的集合组成的一种关系的数学表示G=（V，E）其中：顶点是由有穷非空集合顶点之间的关系（边）是有穷集合Path(x,y)表示从x到y的一条单向通路，它是有方向的,有向图有向图G是由两个集合V(G)和E(G)组成。其中：V(G)是顶点的非空有限集E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对；,图G1中：V(G1)=1,2,3,4,5,6E(G1)=,顶点集,弧集,图G2中：V(G2)=1,2,3,4,5,6,7E(G2)=(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7),无向图无向图G是由两个集合V(G)和E(G)组成V(G)是顶点的非空有限集E(G)是边的有限集合,有向完全图n个顶点的有向图最大边数是n(n-1)无向完全图n个顶点的无向图最大边数是n(n-1)/2顶点的度：无向图中，顶点的度为与每个顶点相连的边数；有向图中，顶点的度分成入度与出度。入度：以该顶点为头的弧的数目；出度：以该顶点为尾的弧的数目；路径路径是顶点的序列V=vi0,vi1,vin，满足(vij-1,vij)E或E,(1jn)。第一个顶点和最后一个顶点相同的路径称为回路或环。序列顶点不重复出现的路径称为简单路径。,2.图的存储结构,邻接矩阵表示顶点间相联关系的矩阵定义：设G=(V,E)是有n1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵,无向图的邻接矩阵是对称的有向图的邻接矩阵往往是不对称的,邻接表(AdjacencyList),同一个顶点发出的边链接在同一个边链表中，每一个链结点代表一条边，结点中另一个顶点的下表dest和指针link,3.图的遍历,图的遍历,深度优先遍历DFS(DepthFirstSearch)广度优先遍历BFS(BreadthFirstSearch),深度优先遍历(DFS)方法：从图的某一顶点Vi出发，访问此顶点；然后依次从Vi的未被访问的邻接点出发，深度优先遍历图，直至图中所有和Vi相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止,深度遍历：V1V2V4V8V5V3V6V7,广度优先遍历(BFS)方法：从图的某一顶点Vi出发，访问此顶点后，依次访问Vi的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止,广度遍历：V1V2V3V4V5V6V7V8,4.最小生成树,最小生成树：,定义：1.必须使用且仅使用该网络中的n-1条边来连接网络中的n个顶点(树的定义)2.不能使用产生回路的边3.各边上的权值的总和达到最小注意：最小生成树不唯一(why?),克鲁斯卡尔(Kruskal)算法：,步骤：1.先按权值进行排序；2.顺序加入各个边，若形成回路，则去掉，否则，保留；3.直至加入所有边；,应用Kruskal构造MST的过程,10,5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,12,5,0,4,6,1,3,2,5,0,4,6,1,3,2,原图(a)(b),10,12,5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,12,5,0,4,6,1,3,2,5,0,4,6,1,3,2,10,14,12,原图(c)(d),5,0,4,6,1,3,2,10,14,16,12,(e)(f)(g),5,0,4,6,1,3,2,10,14,22,16,12,5,0,4,6,1,2,10,25,14,22,16,12,3,普里姆(Prim)：,第1步：所有的点都在集合B中，A集合为空。第2步：任意以一个点为开始，把这个初始点加入集合A中，从集合B中减去这个点，寻找与它相邻的点中路径最短的点，如后把这个点也加入集合A中,从集合B中减去这个点。第3步：集合A中已经有了多个点，这时两个集合A和B，只要找到A集合中的点到B集合中的点的最短边，可以是A集合中的与B集合中的点的任意组合，把这条最短边有两个顶点，把在集合B中的顶点加入到集合A中。第4步：重复上述过程。一直到所有的点都在A集合中结束。,六、查找,查找表由同一类型的数据构成的集合。查找也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素关键字是数据元素中某个数据项的值，它可以标识一个数据元素。（主关键字，次关键字）查找方法评价：查找速度占用存储空间多少算法本身复杂程度平均查找长度ASL(AverageSearchLength)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的平均查找长度。,1.顺序表的查找,查找方法：从表的一端开始逐个进行记录的关键字和给定值的比较,例,01234567891011,513192137566475808892,找64,监视哨,2.折半查找,查找区间在左侧,low,high,mid,若khigh时，查找失败,查找过程：每次将待查记录所在区间缩小一半适用条件：采用顺序存储结构的有序表,intSearch_Bin(SSTableST,KeyTypekey)intlow,high,mid;low=1;high=ST.length;while(lowST.elementmid.key)low=mid+1;elsehigh=mid-1;return(0);,算法描述,3.索引顺序表的查找,索引顺序表的查找(分块查找)将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找适用条件：分块有序表算法实现:用数组存放待查记录,每个数据元素至少含有一个关键字域建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针,123456789101112131415161718,2212138920334244382448605874578653,索引表,查38,例：索引表以升序方式排序，即子表间关键字以升序排列，而子表内关键字无序。,在第二表中找,第二表,4.哈希查找,基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法哈希函数在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象哈希函数可写成：addr(ai)=H(ki)ai是表中的一个数据元素addr(ai)是ai的存储地址ki是ai的关键字,以编号作关键字，构造哈希函数：H(key)=keyH(1)=1H(2)=2,以地区别作关键字，取地区名称第一个拼音字母的序号作哈希函数：H(Beijing)=2H(Shanghai)=19H(Shenyang)=19,哈希表应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫哈希表。哈希查找又叫散列查找，利用哈希函数进行查找的过程叫哈希查找。,从例子可见：哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可冲突：key1key2，但H(key1)=H(key2)的现象叫冲突。同义词：具有相同函数值的两个关键字，叫该哈希函数的同义词。哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽量减少；同时，冲突发生后，应该有处理冲突的方法。,哈希函数的构造方法,直接定址法构造：取关键字或关键字的某个线性函数作哈希地址，即H(key)=key或H(key)=akey+b特点：直接定址法所得地址集合与关键字集合大小相等，不会发生冲突；实际中能用这种哈希函数的情况很少,数字分析法构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况,例有80个记录，关键字为8位十进制数，哈希地址为2位十进制数,分析：只取8只取1只取3、4只取2、7、5数字分布近乎随机所以：取任意两位或两位与另两位的叠加作哈希地址,平方取中法构造：取关键字平方后中间几位作哈希地址适于不知道全部关键字情况折叠法构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址种类移位叠加：将分割后的几部分低位对齐相加间界叠加：从一端沿分割界来回折送，然后对齐相加适于关键字位数很多，且每一位上数字分布大致均匀情况,例关键字为：0442205864，哈希地址位数为4,除留余数法构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=keyMODp，pm特点简单、常用，可与上述几种方法结合使用p的选取很重要；p选的不好，容易产生同义词随机数法构造：取关键字的随机函数值作哈希地址，即H(key)=random(key)适于关键字长度不等的情况选取哈希函数，考虑以下因素：计算哈希函数所需时间关键字长度哈希表长度（哈希地址范围）关键字分布情况记录的查找频率,哈希查找过程及分析：,哈希查找分：哈希查找过程仍是一个给定值与关键字进行比较的过程,七、排序,1.排序概述,排序将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。,2.直接插入排序,直接插入排序：排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序,voidinsert(int*arr,inta,intn)/*0到n-1都已排好序*/inti;intkey=a;for(i=0;i=i;j-)arrj+1=arrj;arri=key;return;arrn=key;return;,3.希尔排序(缩小增量法),基本思想:先把整个待排记录分割成若干子序列分别进行插入排序,待整个序列“基本有序”时再对全体记录进行一次直接插入排序。排序过程：先取一个正整数d1n，把所有相隔d1的记录放一组，组内进行直接插入排序；然后取d2=1;d-)for(i=0;i+dai+d)b=ai;ai=ai+d;ai+d=b;,Shell排序程序,每隔d个进行排序,希尔排序特点：子序列的构成不是简单的“逐段分割”，而是将相隔某个增量的记录组成一个子序列希尔排序可提高排序速度，因为分组后n值减小，n更小，而T(n)=O(n),所以T(n)从总体上看是减小了关键字较小的记录跳跃式前移，在进行最后