软件技术基础 算法与数据结构五.pptx

《软件技术基础 算法与数据结构五.pptx》由会员分享，可在线阅读，更多相关《软件技术基础 算法与数据结构五.pptx（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1/49第3章 内容摘要3.1 数据结构概述 3.2 算法的描述和分析3.3 线性表 3.4 树和二叉树3.5 图3.6 3.6 查找与排序查找与排序软件技术基础电子教案第1页/共49页2/493.6 查找与排序 查找与排序是计算机最频繁的操作，特别是大量数据的数据处理领域。排序和查找是两个密切相关、很基本的技术。查找和排序一般数据结构比较简单，主要是算法问题。在早期计算机内存紧张，速度慢时，对程序员尤其重要。如今CPU快速、内存大，相对重要性降低。但是作为学习编程，“想得到它就写得出算法来”还是非常有意义的，还可以开阔思路。它包含了许多编程技巧的精髓。软件技术基础电子教案第2页/共49页3/

2、49查找基本概念 查找表:由同一类数据构成的用于查找的集合被称作查找表。查找表是具有一定存储结构的数据集合，比如顺序表结构、链式结构、树形结构等。查找往往根据数据元素的某个属性进行。例如根据学号查找某个学生记录。这种被用于查找的元素属性一般称为关键字，它往往可以唯一标识一个元素。3.6.1 查找查找软件技术基础电子教案第3页/共49页4/49 静态查找表:查找表一旦建立，在以后的查找过程中就不会改变。它所对应的查找算法属于静态查找技术。动态查找表：查找表建立后，在后来的查找过程中仍会改变查找表的内容。它所对应的查找算法属于动态查找技术。动态查找的例子词汇统计问题。就是统计一篇文章中使用了多少词

3、汇以及每个词汇的使用次数。解决方法是先建立一个空的查找表，以后每读到一个词就在查找表中查询一下，如果该词汇存在则将其使用次数加一，否则将新词插入到查找表中并设使用次数为一次。显然，这个查找表是不断扩张的。第4页/共49页5/49平均查找长度平均查找长度：为了确定数据元素在查找表中的位置，需要将给定值为了确定数据元素在查找表中的位置，需要将给定值和表中的数据元素的关键字进行比较的次数的期望值。和表中的数据元素的关键字进行比较的次数的期望值。平均查找长度平均查找长度ASLASL的计算方法为：的计算方法为：n n 为表长；为表长；P Pi i为查找第为查找第i i个元素的概率。个元素的概率。C Ci

4、 i为找到该为找到该记录时，曾和给定值比较过的数据元素的个数。记录时，曾和给定值比较过的数据元素的个数。在等概率条件下在等概率条件下(P(Pi i=1/n)=1/n)这时平均查找长度为：这时平均查找长度为：其中其中：软件技术基础电子教案第5页/共49页6/49查找表定义#define maxsize 100 /*查找表最大长度*/typedef int KeyType；/*整型*/涉及的数据记录至少含有一个关键字段（域）：typedef struct KeyType key；DataType；typedef struct DataType rmaxsize；/*数据元素存储空间*/int le

5、ngth；/*表的长度*/Sqlist；软件技术基础电子教案第6页/共49页7/49线性表的查找常见的线性表查找算法顺序查找顺序查找 折半查找折半查找 分块查找分块查找 软件技术基础电子教案第7页/共49页8/49顺序查找顺序查找改进算法：int SeqSearch(Sqlist s,KeyType k)/*在表在表s中顺序查找关键字中顺序查找关键字k，若查找成功，则函数值为该元素在表中的位置，若，若查找成功，则函数值为该元素在表中的位置，若查找失败，返回查找失败，返回-1。*/int i；for(i=0；is.length；i+)if(s.ri.key=k)return(i)；/*查找成功查

6、找成功*/return(-1)；/*查找失败查找失败*/思考:此算法的效率能提高吗?第8页/共49页9/49顺序查找顺序查找改进算法：顺序查找改进算法：int SeqSearch_gai(Sqlist s,KeyType k)int i；i=s.length-1；s.r-1.key=k；/*设置前哨站设置前哨站*/while(s.ri.key!=k)/*从表尾开始向前扫描从表尾开始向前扫描*/i-；return(i)；请请比比较较这这两两个个算算法法,由由于于改改进进后后的的算算法法不不需需要要判判断断当当前前下下标标是是否否出出界界,时时间间效效率率几几乎乎提提高了一倍高了一倍.顺序查找的平

7、均查找长度顺序查找的平均查找长度为 第9页/共49页10/49i例-1012345678910513192137566475808892找6464监视哨iiii比较次数=5比较次数：比较次数：查找第查找第n个元素：个元素：1查找第查找第n-1个元素：个元素：2.查找第查找第1个元素：个元素：n查找第查找第i个元素：个元素：n+1-i查找失败查找失败：n+1软件技术基础电子教案第10页/共49页11/49有序表的查找 前提：表中的结点按关键字递增有序首先将待查值k和表中间位置上的结点关键字进行比较，若两者相等，则查找成功；否则，若k值小，则在表的前半部分中继续利用折半查找法查找，若k值大，则在表

8、的后半部分中继续利用折半查找法查找这样，经过一次关键字比较缩小一半的查找区间，如此进行下去，直到查找到该关键字或查找失败。软件技术基础电子教案第11页/共49页12/49折半查找算法int BinSearch(Sqlist s,KeyType k)/*在在表表s中中用用折折半半查查找找法法查查找找关关键键字字k，若若查查找找成成功功，则则函函数数值值为为该该元元素素在在表表中中的的位置，若查找失败，返回位置，若查找失败，返回-1。*/int low,mid,high；low=0；high=s.length-1；while(lowk)high=mid-1；/*在左区间中查找在左区间中查找*/el

9、se low=mid+1；/*在右区间中查找在右区间中查找*/return(-1)；/*查找失败查找失败*/第12页/共49页13/49算法描述lowhighmid例 1234567891011513192137566475808892找211234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid软件技术基础电子教案第13页/共49页14/49例例 1234567891011513192137566475808892lowhighmid找7012345678910115131

10、92137566475808892lowhighmid1234567891011513192137566475808892low highmid1234567891011513192137566475808892lowhighmid第14页/共49页15/491234567891011513192137566475808892lowhigh1185210741936判定树：1234567891011513192137566475808892ASL=(1*1+2*2+4*3+4*4)/11=3第15页/共49页16/49折半查找查找过程可用二叉树来描述(如图所示)折半查找的ASL近似软件技术基础

11、电子教案第16页/共49页17/49哈希表查找（杂凑法）哈希(Hash)表与哈希方法基本思想基本思想 在记录的存储地址和它的关键码之间建立一个确在记录的存储地址和它的关键码之间建立一个确定的对应关系；这样，定的对应关系；这样，不经过比较不经过比较，一次存取就，一次存取就能得到所查元素的查找方法能得到所查元素的查找方法定义定义哈希函数哈希函数在记录的关键码与记录的存储地址在记录的关键码与记录的存储地址之间建立的一种对应关系，哈希函数可写成：之间建立的一种对应关系，哈希函数可写成：addraddr(a(ai i)=H(k)=H(ki i)。按照存储的方法去查找按照存储的方法去查找:你是如何存储的你

12、就如你是如何存储的你就如何去查找何去查找,回忆一下回忆一下:你是如何找存折你是如何找存折?如何找钱包如何找钱包?软件技术基础电子教案第17页/共49页18/49哈希表与哈希方法 哈希表哈希表应用应用哈希函数哈希函数，由记录的关键码确定记录在表中的地址，由记录的关键码确定记录在表中的地址，并将记录放入此地址。并将记录放入此地址。哈希查找哈希查找又叫散列查找，利用哈希函数进行查找的过程。又叫散列查找，利用哈希函数进行查找的过程。关键码集合存储地址集合HASH软件技术基础电子教案第18页/共49页19/49哈希表与哈希方法哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键哈希函数只是一种

13、映象，所以哈希函数的设定很灵活，只要使任何关键码的哈希函数值都落码的哈希函数值都落在表长允许的范围之内在表长允许的范围之内即可即可冲突：冲突：key1 key2，但但H(key1)=H(key2)的现象的现象同义词：具有相同函数值的两个关键码哈希函数冲突不可避免，只能尽同义词：具有相同函数值的两个关键码哈希函数冲突不可避免，只能尽量减少。所以，哈希方法解决两个问题：量减少。所以，哈希方法解决两个问题：构造好的哈希函数；制定解决冲突的方法软件技术基础电子教案第19页/共49页20/49常用的哈希函数构造方法直接定址法直接定址法构造：取关键码或关键码的某个线性函数作哈希地址，即H(key)=key

14、 或 H(key)=akey+b例如：取学号作为关键字，哈希函数H(k)=k+(-230000)查找学号230009记录，只需查230009-230000=9 项即可特点直接定址法所得地址集合与关键字集合大小相等，直接定址法所得地址集合与关键字集合大小相等，不会发生冲突不会发生冲突实际中能用这种哈希函数的情况很少实际中能用这种哈希函数的情况很少软件技术基础电子教案第20页/共49页21/49常用的哈希函数构造方法数字分析法数字分析法构造：对关键码进行分析，取关键码的若干位或其组合作哈希地址适于关键码位数比哈希地址位数大，且可能出现的关键码事先知道的情况软件技术基础电子教案第21页/共49页22

15、/49常用的哈希函数构造方法平方取中法平方取中法构造：取关键码平方后中间几位作哈希地址适于不知道全部关键码情况除余法（亦称除留余数法）除余法（亦称除留余数法）构造：取关键码被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=key MOD p，pm特点简单、常用，可与上述几种方法结合使用简单、常用，可与上述几种方法结合使用p p的选取很重要；的选取很重要；p p选的不好，容易产生同义词，一般取不大于选的不好，容易产生同义词，一般取不大于m m的最大素数。的最大素数。软件技术基础电子教案第22页/共49页23/49常用的哈希函数构造方法折叠法折叠法构造：将关键码分割成位数相同的

16、几部分，然后取这几部分的叠加和（舍去进位）做哈希地址种类移位叠加：将分割后的几部分低位对齐相加移位叠加：将分割后的几部分低位对齐相加间界叠加：从一端沿分割界来回折送，然后对齐相加间界叠加：从一端沿分割界来回折送，然后对齐相加适于关键码位数很多，且每一位上数字分布大致均匀情况软件技术基础电子教案第23页/共49页24/49常用的哈希函数构造方法选取哈希函数，考虑以下因素：选取哈希函数，考虑以下因素：计算哈希函数所需时间关键码长度哈希表长度（哈希地址范围）关键码分布情况记录的查找频率软件技术基础电子教案第24页/共49页25/49哈希表的操作哈希表的类型定义为#definemaxsize100#d

17、efinenullkey-1/*设定空记录标记*/typedefstructDataTypeelemmaxsize；intlength；HashTable；软件技术基础电子教案第25页/共49页26/49哈希表的查找算法intHashSearch(HashTable*ht,KeyTypekey)/*查找成功，返回所在的下标，不成功返回-1*/intd,i；d=Hash(key)；/*计算哈希地址，哈希函数为H(key)*/for(i=0；ilength；i+)if(ht-elemd.key=k)return(d)；/*检索成功，返回哈希地址*/if(ht-elemd.Key=nullkey)r

18、eturn(-1)；/*检索失败*/d=(d+1)%ht-length；/*用解决冲突的方法求下一个哈希地址*/return(-1)；软件技术基础电子教案第26页/共49页27/49排序基本概念 排序是计算机内经常进行的一种操作，其目的是将一组同类型的记录序列调整为按照元素关键字有序的记录序列。例如将学生记录按学号排序，将课程记录按课程编码排序。排序的形式化定义为：假设含n个记录的序列为 R1,R2,，Rn，其相应的关键字序列为 K1,K2,，Kn。这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系Kp1Kp2Kpn，按此固有关系将最初的记录序列重新排列为 Rp1,Rp2,，Rpn

19、 的操作称作排序。3.6.2 排序排序软件技术基础电子教案第27页/共49页28/49 排序分为内部排序和外部排序。若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。本节只讨论内部排序的若干方法 软件技术基础电子教案第28页/共49页29/49内部排序方法有很多类型。按方法实现特点可分为插入排序、选择排序、交换排序、归并排序等等；按方法效率可分为简单的排序法、先进的排序法等等。简单的排序法包括插入排序、选择排序、冒泡排序等，它们的时间复杂度为O(n2)。而先进的排序法包括快速排序、

20、归并排序等，它们的时间复杂度大约为O(nlog2n)。软件技术基础电子教案第29页/共49页30/49默认的排序数据结构：#define MAXSIZE 100 typedef int KeyType；/*假定关键字类型为整数类型*/typedef struct KeyType key；/*关键字项*/OtherType other；/*其他项*/DataType；/*数据元素类型*/typedef struct DataType rMAXSIZE+1；/*r0闲置或充当前哨站*/int length；/*顺序表长度 */SqList；/*顺序表类型*/软件技术基础电子教案第30页/共49页3

21、1/491.插入排序基本思想通过构建有序序列，将待排序的数据，在已排好序的序列中从后向前扫描，找到其相应位置并进行插入操作。常见的插入排序算法直接插入排序折半插入排序希尔排序 软件技术基础电子教案第31页/共49页32/491、直接插入排序 直接插入排序方法的基本思想是：将记录分为有序和无序两个序列，假定当插入第k个记录时，前面的R1，R2，Rk-1已经排好序，而后面的Rk，Rk+1，Rn仍然无序。这时用Rk的关键字与Rk-1的关键字进行比较,若Rk小于Rk-1则将Rk-1向后移动一个单元；再用Rk与Rk-2比较，若Rk小于Rk-2则将Rk-2向后移动一个单元，依次比较下去，直到找到插入位置即

22、将Rk插入。初始状态可以认为有序序列为R1。软件技术基础电子教案第32页/共49页33/49初始状态：初始状态：3535353522222222161616161919191922222222第第1 1 1 1趟趟 ：2222222235353535161616161919191922222222第第2 2 2 2趟趟 ：1616161622222222353535351919191922222222第第3 3 3 3趟趟 ：1616161619191919222222223535353522222222第第4 4 4 4趟趟 ：16161616191919192222222222222222

23、35353535直接插入直接插入排序执行过程排序执行过程显示在序列35，22，16，19，22上应用插入排序的过程，为了对序列中相同记录加以区别，使用了下划线。第33页/共49页34/49直接插入排序算法C语言描述：voidStraightInsertSort(SqList*S)/对数据S按升序排序inti，j；for(i=2；ilength；i+)S-r0=S-ri；/*从ri-1起向前进行顺序查找，监视哨设置在r0*/j=i-1;while(S-r0.keyrj.key)S-rj+1=S-rj；j-;/*记录后移*/S-rj+1=S-r0；/*插入到正确位置*/*实现整个序列的排序*/软件

24、技术基础电子教案第34页/共49页35/49直接插入排序分析空间效率：O(1)一个辅助单元r0 时间效率时间效率：实现排序的基本操作有两个实现排序的基本操作有两个“比较比较”序列中两个关键字的大小；序列中两个关键字的大小；“移动移动”记录。记录。对于直接插入排序对于直接插入排序最好的情况（关键字在记录序列中顺序有序）最好的情况（关键字在记录序列中顺序有序）:O(n)软件技术基础电子教案第35页/共49页36/49直接插入排序分析(续)时间效率时间效率：最坏的情况（关键字在记录序列中逆序有序）:O(n2)软件技术基础电子教案一般情况:O(n2)第36页/共49页37/492.交换排序交换排序的思

25、想：通过两两比较待排序记录的关键字，若不满足排序要求，则交换通过两两比较待排序记录的关键字，若不满足排序要求，则交换;不断重复比较和交换过程，直到待排不断重复比较和交换过程，直到待排序记录满足排序要求为止。序记录满足排序要求为止。交换排序算法冒泡排序冒泡排序快速排序快速排序软件技术基础电子教案第37页/共49页38/49冒泡排序算法步骤：待排序记录待排序记录S=r1,r2,rn,假设待排序记录长为假设待排序记录长为n第一趟：第一趟：比较记录比较记录r1与与r2的关键字，若的关键字，若r1.keyr2.key，则将两个记录交换，紧接着依次比较，则将两个记录交换，紧接着依次比较r2和和r3，直至，

26、直至rn-1与与rn为止。这样一趟将关键字值最大的记录移至为止。这样一趟将关键字值最大的记录移至rn位置，位置，第二趟：第二趟：比较比较r1至让至让rn-1，关键字值次大的记录移动，关键字值次大的记录移动到第到第n-1位置，方法同第一趟位置，方法同第一趟依次完成第依次完成第3趟，第趟，第4趟，趟，n-1趟，直到所有记录都趟，直到所有记录都完成排序完成排序软件技术基础电子教案第38页/共49页39/49下图显示了在序列35，22，16，19，22上应用冒泡排序的过程。初始状态：3522161922第1趟：2216192235第2趟：1619222235第3趟：1619222235第4趟：1619

27、222235软件技术基础电子教案第39页/共49页40/49冒泡排序算法描述：void BubbleSort(SqList*s)/*对顺序表对顺序表S作冒泡排序作冒泡排序*/int i,j;for(i=1；ilength-1；i+)/*进行进行n-1趟排序趟排序*/for(j=2;jlength-i;j+)if(S-rj.key rj-1.key)S-r0=S-rj；/*S-rj与与S-rj-1交换交换 */S-rj=S-rj-1;S-rj-1=S-r0;n-1次ni次比较软件技术基础电子教案第40页/共49页41/49冒泡排序算法空间复杂度为算法空间复杂度为O(1)总的比较次数为：总的比较次

28、数为：总的交换次数最多为总的交换次数最多为O(n2)，最少为，最少为0 平均交换次数为平均交换次数为:冒泡排序是稳定的：冒泡排序是稳定的：S-rj.key rj-1.key交换交换改进的冒泡排序软件技术基础电子教案第41页/共49页42/49冒泡排序改进后的冒泡排序算法void BubbleSort(SqList*s)/*对顺序表S作冒泡排序*/int i,j;int flag=0；for(i=1;!flag&ilength-1;i+,flag=0)/*进行n-1趟排序*/for(j=2;jlength-i;j+)if(S-rj.key rj-1.key)flag=1;S-r0=S-rj；/*

29、S-r j与S-r j-1交换 */S-rj=S-rj-1;S-rj-1=S-r0;软件技术基础电子教案第42页/共49页43/493.选择排序基本思想：一趟从待排序列中选取一个关键字最小的记录，一趟从待排序列中选取一个关键字最小的记录，即第一趟从即第一趟从n个记录中选取关键字最小的记录，第个记录中选取关键字最小的记录，第二趟从剩下的二趟从剩下的n-1个记录中选取关键字次小的记录，个记录中选取关键字次小的记录，直到整个序列的记录选完为止。这样根据选取记直到整个序列的记录选完为止。这样根据选取记录的顺序，可得到按关键字有序的序列录的顺序，可得到按关键字有序的序列 常见选择排序算法简单选择排序简单

30、选择排序堆排序堆排序软件技术基础电子教案第43页/共49页44/49简单选择排序算法步骤 第第1趟，从趟，从n个个待排序记录待排序记录中找出中找出关键字最小关键字最小的记录与第一个记录交换；的记录与第一个记录交换；第第2趟，从第二个记录开始的趟，从第二个记录开始的n-1个待排序记录中再选出关键字最小的记个待排序记录中再选出关键字最小的记录与第二个记录交换；录与第二个记录交换；第第i趟，则从第趟，则从第i个记录开始的个记录开始的n-i+1个待排序记录中选出关键字最小的记个待排序记录中选出关键字最小的记录与第录与第i个记录交换，直到整个序列有序。个记录交换，直到整个序列有序。软件技术基础电子教案第

31、44页/共49页45/49 在序列35，22，16，19，22上应用简单选择排序的过程。初始状态：初始状态：3535 222216161919 2222 第第 1 1趟趟 ：1616222235351919 2222 第第2 2趟趟：1616191935352222 2222 第第3 3趟趟：161619192222 3535 2222 第第4 4趟趟：1616 191922222222 3535软件技术基础电子教案第45页/共49页46/49简单选择排序算法描述voidSelectSort(SqList*s)for(i=1；ilength；i+)/*作S-length-1趟选取*/for(j

32、=i+1，t=i；jlength；j+)/*在i开始的length-i+1条待排序记录中选关键字最小的记录*/if(S-rt.keyS-rj.key)t=j；/*t中存放关键字最小的记录下标*/tmp=S-rt;S-rt=S-ri;S-ri=tmp;/*关键字最小的记录与第i条记录交换*/软件技术基础电子教案第46页/共49页47/49简单选择排序算法分析：简单选择排序第简单选择排序第i i趟排序中选出关键字最小的记趟排序中选出关键字最小的记录，需做录，需做n-in-i次比较，因此总的比较次数为：次比较，因此总的比较次数为：辅助空间为辅助空间为O(1)O(1)，简单选择排序是不稳定的。简单选择排序是不稳定的。软件技术基础电子教案第47页/共49页48/49排序小结算法算法最大时间最大时间平均时间平均时间最小时间最小时间辅助空间辅助空间代价代价稳定性稳定性直接插入排序直接插入排序O(O(n n2 2)O(O(n n2 2)O(O(n n)O(1)O(1)稳定稳定*冒泡排序冒泡排序O(O(n n2 2)O(O(n n2 2)O(O(n n2 2)O(1)O(1)稳定稳定简单选择排序简单选择排序O(O(n n2 2)O(O(n n2 2)O(O(n n2 2)O(1)O(1)不稳定不稳定软件技术基础电子教案第48页/共49页49/49感谢您的观看！第49页/共49页