復(fù)習(xí)課3(0705)數(shù)據(jù)結(jié)構(gòu)公開課一等獎(jiǎng)省優(yōu)質(zhì)課大賽獲獎(jiǎng)?wù)n件

查找、排序

要求：1.掌握查找表各種實(shí)現(xiàn)方法2.掌握幾個(gè)經(jīng)典排序方法：插入排序、交換排序、歸并排序幾個(gè)高效排序方法：希爾排序、快速排序、堆排序第9章查找基礎(chǔ)知識(shí)靜態(tài)查找表和動(dòng)態(tài)查找表關(guān)鍵字基本操作二叉排序樹建立基本算法直接查找算法IntSearch_Seq(SSTableST,KeyTypekey){//從尾部依次比較關(guān)鍵字和數(shù)據(jù)元素關(guān)鍵字，//當(dāng)比到0下標(biāo)才成功則查找不成功，返回0//不然返回下標(biāo)iST.elem[0].key=key;for(i=ST.length;!EQ(ST.elem[i].key,key);--i);returni;}//Search-Seq0下標(biāo)監(jiān)視哨,時(shí)間復(fù)雜度O(n)intSearch_Sq(SSTableST,intkey)//有序表上次序查找,監(jiān)視哨設(shè)在高低標(biāo)端

{

ST.elem[ST.length+1].key=key;

for(i=1;ST.elem[i].key>key;i++);if(i>ST.length||ST.elem[i].key<key)return0;

returni;

}//Search_Sq

9.25假設(shè)次序表按關(guān)鍵字自大到小有序，試改寫9.1.1節(jié)中次序查找算法，將監(jiān)視哨設(shè)在高低標(biāo)端。并求出等概率下查找成功和不成功時(shí)平均查找長度。假設(shè)上題中，次序表是無序，其它要求相同，算法怎樣？for(i=1;ST.elem[i].key<>key;i++);if(i=ST.length+1)return0;

returni;

分析:本算法查找成功情況下平均查找長度為ST.length/2,不成功情況下為ST.length.折半查找：先確定待查統(tǒng)計(jì)范圍，逐步縮小范圍直到找到或找不到。例：在以下數(shù)據(jù)元素中查找關(guān)鍵字為21和85數(shù)據(jù)元素分析：設(shè)置兩個(gè)指針low,high指示待查元素所在范圍上界和下界。mid＝（low+high）/2ST.elem[mid].key=key:查找成功ST.elem[mid].key<key：low=mid+1ST.elem[mid].key>key:high=mid-1low=high:查找不成功513192137566475808893lowhighmidintSearch_Bin(SSTableST,KeyTablekey){//對(duì)有序表查找采取折半查找，逐步縮小//查找范圍，直到找到或找不到，返回值為//找到返回下標(biāo)，找不到返回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)

high=mid–1;elselow=mid+1;}returnOK;}//Search_Bin時(shí)間復(fù)雜度：O(log2n),ASL=log2(n+1)+1(按照滿二叉樹)9.8已知含12個(gè)關(guān)鍵字有序表及其對(duì)應(yīng)權(quán)值以下，畫出對(duì)以下有序表進(jìn)行折半查找判斷樹，并計(jì)算它PH值。關(guān)鍵字ABCDEFGHIJKL權(quán)值8234932671149.9已知以下長度為12表，試按表中元素次序依次插入一棵初始為空二叉排序樹，畫出插入完成后二叉排序樹，并求其在等概率下查找成功平均查找長度。內(nèi)部排序快速排序(又稱交換排序)插入排序選擇排序歸并排序基排序插入排序思想；直接插入、折半插入算法；希爾排序基本思想和排序過程（縮小增量）起泡排序算法快速排序基本思想和排序過程選擇排序基本思想簡(jiǎn)單項(xiàng)選擇擇排序算法堆排序?qū)蓚€(gè)或兩個(gè)以上有序表組合多關(guān)鍵字排序第10章排序直接插入排序算法：voidInsertSort(SqList&L){//對(duì)次序表L作直接插入排序，低位（0位）做監(jiān)視哨for(i=2;i<L.length;++i) if(L.r[i].key<L.r[i-1].key){ L.r[0]=L.r[i]; L.r[i]=L.r[i-1]; for(j=i-2;L[0].key<L[j].key;--j)

L.r[j+1]=L.r[j]; L.r[j+1]=L.r[0]; }}voidInsertSort(SqList&L){//對(duì)次序表L作直接插入排序,以高位(L.length+1)做監(jiān)視哨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]; }}折半插入排序查找過程用折半查找方法。

voidBInsertSort(SqList&L){for(i=2;i<=L.length;++i){ L.r[0]=L.r[i]; low=1;high=i-1; while(low<=high){ m=(low+high)/2; if(L.r[0].key<L.[m].key)high=m-1; elselow=m+1; }//while for(j=i-1;j<=high+1;--j)L.r[j+1]=L.r[j]; L.r[high+1]=L.r[0]; }//for}//BInsertSort49386597761327490冒泡排序算法voidBubbleSort(SqList&L){ for(k=L.length-1;k>=1;k--) for(i=0;i<=k-1;k++) if(L.r[i].key>L.r[i+1].key){交換兩個(gè)統(tǒng)計(jì)}}時(shí)間復(fù)雜度：O(n2)4938659776132749lowhigh273865977613

49lowhigh2738139776

6549lowhigh2738

9776136549lowhigh273813

7697

6549lowhigh一趟快速排序過程10.1以關(guān)鍵字序列(503,087,512,061,908,170,897,275,653,426)為例，手工執(zhí)行以下排序算法，寫出每一趟排序結(jié)束時(shí)關(guān)鍵字狀態(tài)：(1)直接插入