软件技术基础11.pptx

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

1、第五章 检索检索的基本方法第1页/共52页检索5.1检索检索是依据元素的关键字，在结构中找寻元素的方法关键字：元素的标志，检索的依据一般情况下，关键字是一个元素的唯一标识第2页/共52页检索检索的方法与数据结构的关系数据结构决定了检索的方法有时为提高检索效率，需要对数据结构采用特殊的实现方式例，按成绩检索学生，检索一个学生成绩递增的表格比杂乱的表格效率高检索效率的一般评价依据：比较次数最多、最少和平均比较次数第3页/共52页检索 顺序检索5.1 顺序检索 顺序查找从头开始逐个检索直到找到需要的结点i=0;while(i length)if(table-ai.key=our_key)break;

2、i=i+1;找到所需的结点if(i length)return i;elseerror(“no such item”);平均查找次数=PiCii=1n=n+12第4页/共52页检索 二分检索5.2 折半（二分）检索方法描述：元素按关键字大小排列，每次查询查找范围内的“中间位置”结点。若该结点不是所需，则缩小查找范围为前半部分或后半部分mm=length/2（要求元素按关键字大小排列）ai.key am.keyai.key am.keyaj.key am.key第5页/共52页检索 二分检索算法框架每次将检索范围缩小一半，直到范围中结点的个数为0whilewhile（L=hL amid.key

3、amid.key )L=m+1L=m+1；else if(amid.key datamid.key=key)if(table-datamid.key=key)break;break;else if(key table-data mid.key)else if(key table-data mid.key)elseelse 检索 二分检索int binary_search(key,table)int binary_search(key,table)L=0;L=0;h=table-length 1;h=table-length 1;while()while()return mid;return m

4、id;L=hL=hh=mid 1;h=mid 1;L=mid+1;L=mid+1;if(L =h)if(L =h)elseelsereturn 1;return 1;L Lh h第8页/共52页平均查找次数检索 二分检索n1(1+2 2+4 3+.+2k (log 2n+1)log2(n+1)-19 97 75 51 11616181810101 1层层2 2层层3 3层层第9页/共52页检索 二分检索无序的线性表必须 才能使用二分检索 数组实现的顺序表 用二分检索单链表 用二分检索排序二叉树 用二分查找排序排序不适合不适合适合适合适合适合9 97 75 51 11616181810101 1

5、层层2 2层层3 3层层第10页/共52页检索顺序检索与二分检索在检索有序线性表时，顺序检索效率较低对于无序线性表，二分检索要求必须对无序线性表先进行排序第11页/共52页检索 分块检索5.3 分块检索将检索对象分块，块内无序，块间有序。块内使用较低效的顺序查找块间通过排序可使用较高效的查找方法可做出块的索引表，进一步针对块索引表进行折半检索306586x=3030 x=6565 x dataindex);p=&(table-dataindex);while(p!=NULL&p-key!=key)while(p!=NULL&p-key!=key)p=p-next;p=p-next;.第16页/

6、共52页检索 哈希检索5.4.4 线性探查法使用数组存储方式存放时，如果hash结果冲突，将新的表项放在下一个空闲的存储单元检索时当发现当前hash地址里存放的不是需要的元素，就从下一个存储单元开始逐个探查。线性探查index=hash(key);index=hash(key);while(table-data index !=empty)while(table-data index !=empty)index+index+；index=hash(key);index=hash(key);while(table-dataindex-key!=key)while(table-dataindex-

7、key!=key)index+;index+;第17页/共52页例 关键字模6的hash运算以关键字分别为6，10，12，18，11，13的顺序存放元素。查找关键字为12，18，13的元素检索 哈希检索0 01 12 23 34 45 5index=hash(key);index=hash(key);while(table-data index !=empty)while(table-data index !=empty)index+index+；index=hash(key);index=hash(key);while(table-dataindex-key!=key)while(table

8、-dataindex-key!=key)index+;index+;6 612121818131310101111第18页/共52页检索 哈希检索5.4.5 开放地址法Hi（k）（H（K）di）mod mi：第i个冲突的元素i 1 to n（1）di 1,2,3,（2）di 12,12,22，22（3）di 伪随机序列目的：使冲突分散线性探测线性探测二次探测二次探测随机再散列随机再散列第19页/共52页排序的基本方法第六章 排序第20页/共52页排序6.1 排序将一组元素按照它们的排序码的大小，递增或递减排列的运算排序码：一般是元素的关键字，但也可以不是关键字，不同元素排序码可以相同排序的方法

9、与数据结构的关系数据结构及其实现方式，将影响排序过程中元素比较时的方便性，和元素位置调整（搬移元素）的方便性如：链表对元素位置调整带来很大方便第21页/共52页排序排序算法一般的评价依据平均的比较次数（完成一次排序所需的元素间排序码的比较次数）元素搬移的次数算法的稳定性：对相同排序码的元素之间相对位置的维持保持相对位置不变稳定算法不一定保持相对位置不稳定算法1212，1010，1111，1010，15151010，1010，1111，1212，15151010，1010，1111，1212，1515第22页/共52页排序 简单插入6.2 线性插入算法 简单插入算法基本思想：从表取一个元素，按照

10、排序关系插入到新的排序表中。若直接在原表中进行：将表分为已排序子表和未排序子表。每次从未排序子表中取出表头元素按排序关系插入到已排序子表中，当未排序子表为空时，排序完成。3 31 14 42 2已排序子表已排序子表未排序子表未排序子表教材及教案中所有的排序算法都是按递教材及教案中所有的排序算法都是按递增顺序排序增顺序排序注注意意第23页/共52页排序 简单插入算法分析算法框架逐个从未排序子表中取出元素，插入排序子表的算法框架。即未排序子表不断减小，已排序子表不断增加的算法框架。tailtail1 13 36 67 7171745452 2whilewhile（tail length)tail

11、length)核心算法：将核心算法：将tailtail所指的元素按序插入到前面已排序的子表中所指的元素按序插入到前面已排序的子表中 tail+;tail+;tail=1;tail=1;tailtail是两个子表的分界线是两个子表的分界线第24页/共52页排序 简单插入核心算法按序插入的算法从已排序子表的后部逐个向前比对，如果插入元素大于表中元素，就将表中元素后移一格，否则在表中元素后放入while(j -1)while(j -1)if(temp.key dataj.key)if(temp.key dataj.key)table-dataj+1=table-dataj;table-dataj+1

12、=table-dataj;elseelsetable-dataj+1=temp;table-dataj+1=temp;break;break;j-;j-;1 12 26 67 710106 61717temptemp第25页/共52页void insert_sort(table)void insert_sort(table)tail=1;tail=1;while(tail length)while(tail length)tail=tail+1;tail=tail+1;temp=table-datatail;temp=table-datatail;j=tail-1;j=tail-1;while

13、(j -1)while(j -1)if(temp.key table-dataj.key)if(temp.key table-dataj.key)table-dataj+1=table-dataj;table-dataj+1=table-dataj;elseelsetable-dataj+1=temp;table-dataj+1=temp;break;break;j-;j-;接近接近n(n+1)/4n(n+1)/4次搬移元素次搬移元素排序 简单插入第26页/共52页排序 简单选择6.3 选择插入排序算法 简单选择算法基本思想：从无序表中依次选择出最小的元素，插入在新的排序表尾若直接在原有的表中

14、进行排序！将表分为已排序子表和未排序子表。每次从未排序子表中选出最小的元素，与未排序子表的表首元素交换，同时未排序子表表首成为排序子表表尾，当未排序子表为空时，排序完成。3 31 14 42 2已排序子表已排序子表未排序子表未排序子表第27页/共52页排序 简单选择算法分析算法框架未排序子表不断减小，已排序子表不断增大的算法框架whilewhile（head length)head length)核心算法：每次从未排序子表选出最小的元素，与核心算法：每次从未排序子表选出最小的元素，与headhead指向的元素指向的元素交交换换。head+;head+;head=0;head=0;headhea

15、d是两个子表的分界线是两个子表的分界线3 31 14 42 2headhead课堂练习：请参照前面的算法写出算法框架课堂练习：请参照前面的算法写出算法框架第28页/共52页排序 简单选择核心算法从未排序子表中选出最小的元素（逐个比较）最小的元素和未排序子表首元素交换3 31 14 42 2headheadj=head;j=head;whilewhile（j length)j length)j+;j+;min=j;min=j;if(table-data j.key datamin.key)if(table-data j.key datamin.key)min=j;min=j;table-data

16、headtable-dataheadtable-datamin;table-datamin;课堂练习：请写出选择最小元素的算法课堂练习：请写出选择最小元素的算法课堂练习：请写出元素交换的算法课堂练习：请写出元素交换的算法第29页/共52页void select_sort(table)void select_sort(table)head=0;head=0;while(head length)while(head length)head=head+1;head=head+1;j=head,min=j;j=head,min=j;while(j length)while(j length)if(ta

17、ble-data j.keydatamin.key)if(table-data j.keydatamin.key)min=j;min=j;j+;j+;temp=table-datahead;temp=table-datahead;table-datahead=table-datamin;table-datahead=table-datamin;table-datamin=temp;table-datamin=temp;table-dataheadtable-dataheadtable-datamin;table-datamin;排序 简单选择n(n+1)/2n(n+1)/2次比较次比较n n次

18、交换次交换第30页/共52页排序简单插入与简单选择算法的比较排序效率简单插入算法搬移元素的次数较多简单选择算法比较元素的次数较多，但搬移次数少对于一个基本有序的表，倾向使用 算法对于一个顺序混乱的表，倾向使用 算法简单插入简单插入简单选择简单选择例：例：1 2 3 4 5 7 61 2 3 4 5 7 6第31页/共52页排序简单插入与简单选择算法的比较稳定性：简单插入算法是？简单选择算法是？稳定的稳定的不稳定的不稳定的算法的稳定性：算法的稳定性：对相同排序码的元素之间相对位置的维持对相同排序码的元素之间相对位置的维持保持相对位置不变稳定算法保持相对位置不变稳定算法不一定保持相对位置不稳定算法

19、不一定保持相对位置不稳定算法1 14 42 23 33 3例：例：第32页/共52页排序 冒泡排序6.4 冒泡排序基本思想：逐个交换次序不当的相邻表项，多趟扫描后得到排序表3 319192 24 413131010交换交换19192 2交换交换19194 4交换交换1313191910101919交换交换第33页/共52页排序 冒泡排序冒泡！最大的元素在第一趟算法中排到了（冒）表尾次大的元素在第二趟算法中将冒到倒数第二逐趟冒泡，我们就获得排序表3 319192 24 41313101019192 219194 413131919191910101313131310102 23 3第34页/共5

20、2页排序 冒泡排序算法分析（1）多趟扫描的框架每一趟扫描，都将一个最大的元素排到表尾。每一趟扫描，未排序子表减少一格for(turn=0;turn length-2;turn+)for(turn=0;turn length-2;turn+)核心算法：从前向后，每两个元素根据大小交换位置。核心算法：从前向后，每两个元素根据大小交换位置。for(turn=table-length-1;turn 1;turn-)for(turn=table-length-1;turn 1;turn-)核心算法：核心算法：turn:turn:未排序子表结束位置未排序子表结束位置法法一一法法二二第35页/共52页排序

21、冒泡排序（2）核心算法，从前向后逐个比较相邻元素的排序码，并根据大小关系交换元素位置for(i=0;i data i.key table-data i+1.key)temp=table-data i;table-data i =table-data i+1;table-data i+1 =temp;table-data i table-data i table-data i+1 table-data i+1 第36页/共52页排序 冒泡排序改进不一定要进行table-length-1趟，当发现有一趟算法中没有发生交换事件，说明表中的元素已经排好序了。void bubble_sort(table

22、)void bubble_sort(table)for(turn=table-length-1;turn 1;turn-)for(turn=table-length-1;turn 1;turn-)for(i=0;i trun-1;i+)for(i=0;i data i.key table-datai+1.key)if(table-data i.key table-datai+1.key)table-data i table-datai+1;table-data i table-datai+1;课堂练习：将改进加入算法中课堂练习：将改进加入算法中第37页/共52页排序 冒泡排序改进：加一个标志位

23、void bubble_sort(table)void bubble_sort(table)for(turn=table-length-1;turn 1;turn-)for(turn=table-length-1;turn 1;turn-)flag=0;flag=0;for(i=0;i trun-1;i+)for(i=0;i data i.key table-datai+1.key)if(table-data i.key table-datai+1.key)table-data i table-datai+1;table-data i table-datai+1;flag=1flag=1;if

24、(flag=0)if(flag=0)breakbreak;第38页/共52页排序 冒泡排序冒泡排序法的效率同时兼顾了比较和搬移元素的开销对于基本有序的序列，效率较高。是稳定的算法第39页/共52页排序 快速排序6.5 快速排序法基本思想：从表中任意选取一个元素，把它放于它在排序表中应该放置的位置k kki kk kjk k两端的子表不一定有序两端的子表不一定有序第40页/共52页排序 快速排序(1)选取表首元素(2)将该元素放在表中这样的位置：在它之前的元素都比它小，在它之后的元素都比它大。(3)以该元素为界限，两端的子表不一定有序(4)将快速算法分别作用于两端的子表，不断进行下去，直到最小的

25、子表是一个元素的子表。ki kk kjk k实际上，就是逐个定位的思想实际上，就是逐个定位的思想第41页/共52页排序 快速排序算法分析递归的算法框架：将表按照（1）（2）的步骤逐步化小。最小的单元素子表是排序表由此回溯上去，形成排序表if(low high)if(low high)核心算法：核心算法：将将tablelowtablelow放在排序表中，它应该在的位置放在排序表中，它应该在的位置 调用调用quick_sort quick_sort 对左半无序子表进行排序对左半无序子表进行排序调用调用quick_sort quick_sort 对右半无序子表进行排序对右半无序子表进行排序对于对于l

26、owlow到到highhigh之间的子表通过以下调用，成为排序表。之间的子表通过以下调用，成为排序表。quick_sort(low,high)quick_sort(low,high)第42页/共52页核心算法：如何在无序表里面找到一个元素排序后应该在的位置？排序 快速排序13132 29 94 424246 62020lowlowhighhigh1)1)利用利用highhigh向左移找到比向左移找到比1111小的元素，小的元素，2)2)利用利用lowlow向右找到比向右找到比1111大的元素，大的元素，3)3)交换这两个元素的存放位置。交换这两个元素的存放位置。4)4)不断循环不断循环1)2)

27、3)1)2)3)知道知道lowlow与与highhigh相遇相遇:low=high:low=high5)5)表首元素与表首元素与highhigh指向的元素交换位置，指向的元素交换位置，该位置就是表首元素应该在的位置该位置就是表首元素应该在的位置1111第43页/共52页排序 快速排序核心算法whilewhile（lowhigh)lowdatalow.key data f)while(table-datalow.key data f)low+;low+;while(table-datahigh.key table-data f)while(table-datahigh.key table-dat

28、a f)high-;high-;if(low high)if(low datalow table-datalowtablehigh;tablehigh;table-dataftable-dataftable-datahigh;table-datahigh;2)2)利用利用low low 向右移找到比向右移找到比1111大的元素，大的元素，1)1)利用利用highhigh向左找到比向左找到比1111小的元素，小的元素，3)3)交换这两个元素的存放位置。交换这两个元素的存放位置。4)4)不断循环不断循环1)2)3)1)2)3)知道知道lowlow与与highhigh相遇相遇:lowhigh:low

29、high5)5)表首元素与表首元素与highhigh指向的元素交换位置，指向的元素交换位置，该位置就是表首元素应该在的位置该位置就是表首元素应该在的位置第44页/共52页quick_sort(table,low,high)quick_sort(table,low,high)while(low high)while(low datahigh table-dataf while(table-datahigh table-dataf&low high&low datalow dataf while(table-datalow dataf&low high&low high)low+;low+;if(

30、low high)if(low datalow table-datalowtable-datahigh;table-datahigh;table-data f table-data f table-datahigh;table-datahigh;f=lowf=low，lowlowlowlow1 1，last=high;last=high;quick_sort(first,high 1);quick_sort(first,high 1);quick_sort(high+1,last);quick_sort(high+1,last);防止死循环防止死循环防止死循环防止死循环第45页/共52页排序

31、快速排序教材中的核心算法11112 29 94 424242020lowlowhighhighx x：13136 61111第46页/共52页排序 快速排序11112 29 94 424242020lowlowhighhighx x：13136 61111x=table-datalow;x=table-datalow;while(low high)while(low data low =x;table-data low =x;while(table-datahigh.key x&lowdatahigh.key x&lowhigh)high-;high-;if(low datalow+=tabl

32、e-datahigh;if(low datalow+=table-datahigh;while(table-datalow.key x&lowdatalow.key x&lowhigh)low+;low+;if(low datahigh-=table-datalow;if(low datahigh-=table-datalow;第47页/共52页排序 快速排序快速排序算法效率（1）算法趟数少快速具有“二分”处理的特色（2）每一趟算法中交换的结点少，比较的次数为n次(3)排序算法的稳定性？4 43 35 54 41 16 6课堂练习：试举例说明快速排序算法是否稳定课堂练习：试举例说明快速排序算法

33、是否稳定第48页/共52页排序 快速排序注意：教案中介绍的快速排序算法与教材介绍的算法在交换元素问题上有所不同快速排序算法不稳定算法是否稳定应视具体语句而定。如在选择插入算法中，如果将寻找最小元素的语句改为if(table i =tablemin)if(table i =tablemin)min=i;min=i;算法就不稳定了。算法就不稳定了。第49页/共52页排序 归并排序6.6 归并排序“归并”：将两个或以上的有序序列合并为一个有序序列。归并排序：假设n个元素的序列，将它视为n个子序列，然后不断两两归并子序列直到全部归并为一个有序序列。例：教材P69归并算法的基本思想与快速排序正好相反，一个是不断将子表化小，一个是不断合并子表第50页/共52页作业教材73页第26、27、28题第51页/共52页感谢您的观看！第52页/共52页