软件技术基础课件-第3章 算法与数据结构(五)

软件技术基础电子教案第3章算法与数据结构2/49第3章内容摘要3.1数据结构概述3.2算法的描述和分析3.3线性表3.4树和二叉树3.5图3.6查找与排序《软件技术基础》电子教案3/493.6查找与排序•查找与排序是计算机最频繁的操作，特别是大量数据的数据处理领域。•排序和查找是两个密切相关、很基本的技术。•查找和排序一般数据结构比较简单，主要是算法问题。在早期计算机内存紧张，速度慢时，对程序员尤其重要。如今CPU快速、内存大，相对重要性降低。但是作为学习编程，“想得到它就写得出算法来”还是非常有意义的，还可以开阔思路。它包含了许多编程技巧的精髓。《软件技术基础》电子教案4/49•查找基本概念查找表:由同一类数据构成的用于查找的集合被称作查找表。查找表是具有一定存储结构的数据集合，比如顺序表结构、链式结构、树形结构等。查找往往根据数据元素的某个属性进行。例如根据学号查找某个学生记录。这种被用于查找的元素属性一般称为关键字，它往往可以唯一标识一个元素。3.6.1查找《软件技术基础》电子教案5/49静态查找表:查找表一旦建立，在以后的查找过程中就不会改变。它所对应的查找算法属于静态查找技术。动态查找表：查找表建立后，在后来的查找过程中仍会改变查找表的内容。它所对应的查找算法属于动态查找技术。动态查找的例子——词汇统计问题。就是统计一篇文章中使用了多少词汇以及每个词汇的使用次数。解决方法是先建立一个空的查找表，以后每读到一个词就在查找表中查询一下，如果该词汇存在则将其使用次数加一，否则将新词插入到查找表中并设使用次数为一次。显然，这个查找表是不断扩张的。6/49平均查找长度：为了确定数据元素在查找表中的位置，需要将给定值和表中的数据元素的关键字进行比较的次数的期望值。平均查找长度ASL的计算方法为：niiiCPASL1n为表长；Pi为查找第i个元素的概率。Ci为找到该记录时，曾和给定值比较过的数据元素的个数。在等概率条件下(Pi=1/n)这时平均查找长度为：11niiP其中：niiCnASL11《软件技术基础》电子教案7/49查找表定义#definemaxsize100/*查找表最大长度*/typedefintKeyType；/*整型*/涉及的数据记录至少含有一个关键字段（域）：typedefstruct{KeyTypekey；………}DataType；typedefstruct{DataTyper[maxsize]；/*数据元素存储空间*/intlength；/*表的长度*/}Sqlist；《软件技术基础》电子教案8/49线性表的查找•常见的线性表查找算法顺序查找折半查找分块查找《软件技术基础》电子教案9/49顺序查找顺序查找改进算法：intSeqSearch(Sqlists,KeyTypek){/*在表s中顺序查找关键字k，若查找成功，则函数值为该元素在表中的位置，若查找失败，返回-1。*/inti；for(i=0；is.length；i++)if(s.r[i].key==k)return(i)；/*查找成功*/return(-1)；/*查找失败*/}思考:此算法的效率能提高吗?10/49顺序查找顺序查找改进算法：intSeqSearch_gai(Sqlists,KeyTypek){inti；i=s.length-1；s.r[-1].key=k；/*设置前哨站*/while(s.r[i].key!=k)/*从表尾开始向前扫描*/i--；return(i)；}请比较这两个算法,由于改进后的算法不需要判断当前下标是否出界,时间效率几乎提高了一倍.顺序查找的平均查找长度为2/)1n(in1cpASLn1in1iii11/49i例-1012345678910513192137566475808892找6464监视哨iiii比较次数=5比较次数：查找第n个元素：1查找第n-1个元素：2……….查找第1个元素：n查找第i个元素：n+1-i查找失败：n+1《软件技术基础》电子教案12/49有序表的查找前提：表中的结点按关键字递增有序首先将待查值k和表中间位置上的结点关键字进行比较，若两者相等，则查找成功；否则，若k值小，则在表的前半部分中继续利用折半查找法查找，若k值大，则在表的后半部分中继续利用折半查找法查找这样，经过一次关键字比较缩小一半的查找区间，如此进行下去，直到查找到该关键字或查找失败。《软件技术基础》电子教案13/49折半查找算法intBinSearch(Sqlists,KeyTypek){/*在表s中用折半查找法查找关键字k，若查找成功，则函数值为该元素在表中的位置，若查找失败，返回-1。*/intlow,mid,high；low=0；high=s.length-1；while(low=high){mid=(low+high)/2；/*取区间中点*/if(s.r[mid].key==k)return(i)；/*查找成功*/elseif(s.r[mid].keyk)high=mid-1；/*在左区间中查找*/elselow=mid+1；/*在右区间中查找*/}return(-1)；/*查找失败*/}14/49算法描述lowhighmid例1234567891011513192137566475808892找211234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid《软件技术基础》电子教案15/49例1234567891011513192137566475808892lowhighmid找701234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid16/491234567891011513192137566475808892lowhigh1185210741936判定树：1234567891011513192137566475808892ASL=(1*1+2*2+4*3+4*4)/11=317/49折半查找•查找过程可用二叉树来描述(如图所示)•折半查找的ASL近似37671583422302914931081)1n(logASL2《软件技术基础》电子教案18/49哈希表查找（杂凑法）•哈希(Hash)表与哈希方法基本思想在记录的存储地址和它的关键码之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法定义哈希函数——在记录的关键码与记录的存储地址之间建立的一种对应关系，哈希函数可写成：addr(ai)=H(ki)。按照存储的方法去查找:你是如何存储的你就如何去查找,回忆一下:你是如何找存折?如何找钱包?《软件技术基础》电子教案19/49哈希表与哈希方法•哈希表——应用哈希函数，由记录的关键码确定记录在表中的地址，并将记录放入此地址。•哈希查找——又叫散列查找，利用哈希函数进行查找的过程。关键码集合存储地址集合HASH《软件技术基础》电子教案20/49哈希表与哈希方法•哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键码的哈希函数值都落在表长允许的范围之内即可•冲突：key1key2，但H(key1)=H(key2)的现象•同义词：具有相同函数值的两个关键码哈希函数冲突不可避免，只能尽量减少。所以，哈希方法解决两个问题：构造好的哈希函数；制定解决冲突的方法《软件技术基础》电子教案21/49常用的哈希函数构造方法•直接定址法构造：取关键码或关键码的某个线性函数作哈希地址，即H(key)=key或H(key)=a·key+b例如：取学号作为关键字，哈希函数H(k)=k+(-230000)查找学号230009记录，只需查230009-230000=9项即可特点–直接定址法所得地址集合与关键字集合大小相等，不会发生冲突–实际中能用这种哈希函数的情况很少《软件技术基础》电子教案22/49常用的哈希函数构造方法•数字分析法构造：对关键码进行分析，取关键码的若干位或其组合作哈希地址适于关键码位数比哈希地址位数大，且可能出现的关键码事先知道的情况《软件技术基础》电子教案23/49常用的哈希函数构造方法•平方取中法构造：取关键码平方后中间几位作哈希地址适于不知道全部关键码情况•除余法（亦称除留余数法）构造：取关键码被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=keyMODp，pm•特点–简单、常用，可与上述几种方法结合使用–p的选取很重要；p选的不好，容易产生同义词，一般取不大于m的最大素数。《软件技术基础》电子教案24/49常用的哈希函数构造方法•折叠法构造：将关键码分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址种类–移位叠加：将分割后的几部分低位对齐相加–间界叠加：从一端沿分割界来回折送，然后对齐相加适于关键码位数很多，且每一位上数字分布大致均匀情况《软件技术基础》电子教案25/49常用的哈希函数构造方法•选取哈希函数，考虑以下因素：计算哈希函数所需时间关键码长度哈希表长度（哈希地址范围）关键码分布情况记录的查找频率《软件技术基础》电子教案26/49哈希表的操作哈希表的类型定义为#definemaxsize100#definenullkey-1/*设定空记录标记*/typedefstruct{DataTypeelem[maxsize]；intlength；}HashTable；《软件技术基础》电子教案27/49哈希表的查找算法intHashSearch(HashTable*ht,KeyTypekey)/*查找成功，返回所在的下标，不成功返回-1*/{intd,i；d=Hash(key)；/*计算哈希地址，哈希函数为H(key)*/for(i=0；iht-length；i++){if(ht-elem[d].key==k)return(d)；/*检索成功，返回哈希地址*/if(ht-elem[d].Key==nullkey)return(-1)；/*检索失败*/d=(d+1)%ht-length；/*用解决冲突的方法求下一个哈希地址*/}return(-1)；}《软件技术基础》电子教案28/49•排序基本概念排序是计算机内经常进行的一种操作，其目的是将一组同类型的记录序列调整为按照元素关键字有序的记录序列。例如将学生记录按学号排序，将课程记录按课程编码排序。排序的形式化定义为：假设含n个记录的序列为{R1,R2,…，Rn}，其相应的关键字序列为{K1,K2,…，Kn}。这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系Kp1≤Kp2≤…≤Kpn，按此固有关系将最初的记录序列重新排列为{Rp1,Rp2,…，Rpn}的操作称作排序。3.6.2排序《软件技术基础》电子教案29/49排序分为内部排序和外部排序。若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。本节只讨论内部排序的若干方法《软件技术基础》电子教案30/49内部排序方法有很多类型。•按方法实现特点可分为插入排序、选择排序、交换排序、归并排序等等；•按方法效率可分为简单的排序法、先进的排序法等等。简单的排序法包括插入排序、选择排序、冒泡排序等，它们的时间复杂度为O(n2)。而先进的排序法包括快速排序、归并排序等，它们的时间复杂度大约为O(nlog2n)。《软件技术基础》电子教案31/49•默认的排序数据结构：#defineMAXSIZE100typedefintKeyType；/*假定关键字类型为整数类型*/typedefstruct{KeyTy