复习课3(0705)数据结构.ppt

《复习课3(0705)数据结构.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、查找、排序要求：1.掌握查找表的各种实现方法2.掌握几种典型的排序方法：插入排序、交换排序、归并排序几种高效的排序方法：希尔排序、快速排序、堆排序第9章查找基础知识静态查找表和动态查找表关键字基本操作二叉排序树的建立基本算法直接查找算法IntSearch_Seq(SSTableST,KeyTypekey){//从尾部依次比较关键字和数据元素的关键字，//当比到0下标才成功则查找不成功，返回0//否则返回下标iST.elem[0].key=key;for(i=ST.length;!EQ(ST.elem[i].key,key);--i);returni;}//Search-S

2、eq0下标监视哨,时间复杂度O(n)intSearch_Sq(SSTableST,intkey)//有序表上顺序查找,监视哨设在高下标端{ST.elem[ST.length+1].key=key; for(i=1;ST.elem[i].key>key;i++);if(i>ST.length

3、

4、ST.elem[i].key

5、求相同，算法如何？for(i=1;ST.elem[i].key<>key;i++);if(i=ST.length+1)return0; returni;分析:本算法查找成功情况下的平均查找长度为ST.length/2,不成功情况下为ST.length.折半查找：先确定待查记录的范围，逐步缩小范围直到找到或找不到。例：在下列数据元素中查找关键字为21和85的数据元素分析：设置两个指针low,high指示待查元素所在范围的上界和下界。mid＝（low+high）/2ST.elem[mid].key=key:查找成功ST.elem[mid].key

6、ST.elem[mid].key>key:high=mid-1low=high:查找不成功513192137566475808893lowhighmidintSearch_Bin(SSTableST,KeyTablekey){//对有序表的查找采用折半查找，逐步缩小//查找范围，直到找到或找不到，返回值为//找到返回下标，找不到返回0low=1;high=ST.length;while(low<=high){mid=(low+high)/2;ifEQ(key,ST.elem[mid].key)returnmid;elseifLT(key,ST.elem[mid].key)

7、high=mid–1;elselow=mid+1;}returnOK;}//Search_Bin时间复杂度：O(log2n),ASL=log2(n+1)+1(按照满二叉树)9.8已知含12个关键字的有序表及其相应权值如下，画出对以下有序表进行折半查找的判断树，并计算它的PH值。关键字ABCDEFGHIJKL权值8234932671149.9已知如下长度为12的表，试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求其在等概率下查找成功的平均查找长度。内部排序快速排序(又称交换排序)插入排序选择排序归并排序基排序插入排序的思想；直接插入、折半

8、插入的算法；希尔排序的基本思想和排序过程（缩小增量）起泡排序的算法快速排序的基本思想和排序过程选择排序的基本思想简单选择排序的算法堆排序将两个或两个以上的有序表组合多关键字的排序第10章排序直接插入排序算法：voidInsertSort(SqList&L){//对顺序表L作直接插入排序，低位（0位）做监视哨for(i=2;i

9、1]=L.r[0];}}voidInsertSort(SqList&L){//对顺序表L作直接插入排序,以高位(L.length+1)做监视哨for(i=L.length-1;i>1;--i)if(L.r[i].key>L.r[i+1].key){L.r[L.length+1]=L.r[i];L.r[i]=L.r[i+1];for(j=i+2;L[L.length+1].key>L[j].key;++j)L.r[j-1]=L.r[j];L.r[j-1]=L.r[L.length+1];}}折半插入排序查找过程用折半查找方法。v