數(shù)據(jù)結(jié)構(gòu)6(4月28日)課件

查找：根據(jù)給定的關(guān)鍵字值，在一組數(shù)據(jù)元素中確定一個(gè)其關(guān)鍵字值等于給定值的數(shù)據(jù)元素的過(guò)程。若存在這樣的數(shù)據(jù)元素，則稱(chēng)查找成功；若不存在這樣的數(shù)據(jù)元素，則稱(chēng)查找失敗。關(guān)鍵字:指數(shù)據(jù)元素中可以標(biāo)識(shí)該數(shù)據(jù)元素的一組數(shù)據(jù)項(xiàng)。例如學(xué)生記錄中的學(xué)號(hào)；公民記錄中的身份證號(hào)碼等。查找表：指一組待查數(shù)據(jù)元素的集合。它具有一定存儲(chǔ)結(jié)構(gòu)，如順序表結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)、樹(shù)形結(jié)構(gòu)等。

2.6查找查找：2.6查找1)查找的方法查找某個(gè)數(shù)據(jù)元素依賴(lài)于查找表中數(shù)據(jù)元素的組織方式。按照數(shù)據(jù)元素的組織方式?jīng)Q定采用某種查找方法；反之,為了提高查找方法的效率，又要求數(shù)據(jù)元素采用某些特殊的組織方式。因此，在研究各種查找方法時(shí)，必須弄清各種查找方法所適用的組織方式。2)查找算法的評(píng)價(jià)衡量一個(gè)算法的標(biāo)準(zhǔn)主要有兩個(gè)：時(shí)間復(fù)雜度和空間復(fù)雜度。而在查找算法中，基本運(yùn)算是給定值與關(guān)鍵字值的比較，即算法的主要時(shí)間是花費(fèi)在“比較”上的，所以，用平均查找長(zhǎng)度作為評(píng)價(jià)查找算法好壞的依據(jù)。對(duì)于含有n個(gè)數(shù)據(jù)元素的查找表，查找成功的平均查找長(zhǎng)度為ASL=其中：Pi為查找第i個(gè)數(shù)據(jù)元素的概率；Ci為查找到第i個(gè)數(shù)據(jù)元素時(shí)，需進(jìn)行的比較次數(shù)。1)查找的方法ASL=其中：Pi為查找第i個(gè)數(shù)據(jù)元**查找方法分類(lèi)線(xiàn)性查找法順序查找法對(duì)半查找法分塊查找法…基于樹(shù)的查找法二叉排序樹(shù)B樹(shù)…計(jì)算式查找法——哈希法順序存儲(chǔ)的查找方法鏈?zhǔn)酱鎯?chǔ)的查找方法散列存儲(chǔ)的查找方法**查找方法分類(lèi)線(xiàn)性查找法順序存儲(chǔ)的查找方法鏈?zhǔn)酱鎯?chǔ)的查找方2.6.1

順序查找法基本思想是：從數(shù)組的第一個(gè)元素開(kāi)始，與查找的關(guān)鍵字逐個(gè)比對(duì)，直到找到關(guān)鍵字所在的位置或遇到數(shù)組的結(jié)尾為止，若找到，則返回關(guān)鍵字在數(shù)組中的位置，否則返回-1(因?yàn)镃#的數(shù)組下標(biāo)不可能為-1)。publicintsearch(intkeyValue){inti=0；while()i++;if()return(i);elsereturn(-1);}假設(shè)每個(gè)元素等概率查找,則平均查找次數(shù)為(n+1)/2i<length&&

data[i]!=keyValuei<length2.6.1順序查找法假設(shè)每個(gè)元素等概率查找,則平均查找次數(shù)2.6.2對(duì)半查找法以順序方式存放的有序表的查找可采用對(duì)半查找。將被查關(guān)鍵字k與線(xiàn)性表中間位置mid上的數(shù)據(jù)元素的關(guān)鍵字進(jìn)行比較：(假設(shè)表按由小到大順序排列）（1）若k==a[mid]，則查找成功，過(guò)程結(jié)束。（2）若k>a[mid],則取表的后半部分作為新表再去查找。（3）若k<a[mid],則取表的前半部分作為新表再進(jìn)行查找。這個(gè)過(guò)程一直進(jìn)行到查找成功或子表的長(zhǎng)度為0為止。對(duì)半查找是基于關(guān)鍵字比較的最優(yōu)方法。2.6.2對(duì)半查找法對(duì)半查找是基于關(guān)鍵字比較的最優(yōu)方法。publicintbinSearch(intkeyValue){intlow,high,mid;low=0;high=length-1;while(){mid=(low+high)/2;if(data[mid]==keyValue);elseif(data[mid]<keyValue);else;}return(-1);}low<=highreturn(mid)low=mid+1high=mid-1對(duì)半查找成功時(shí)比較次數(shù)最多為log2n+1publicintbinSearch(intkeyVa**分塊查找(索引順序查找）“分塊有序”表特點(diǎn)：(1)表中數(shù)據(jù)分塊(2)塊中數(shù)據(jù)不必有序(3)塊間有序“分塊有序”表的結(jié)構(gòu)有兩部分：(1)順序存儲(chǔ)結(jié)構(gòu)的線(xiàn)性表(2)索引表（由每塊的最大元素組成）分塊查找過(guò)程：(1)用對(duì)半查找法查找索引表，確定待查項(xiàng)x所在的塊。(2)在相應(yīng)的塊中用順序查找法查找待查項(xiàng)x。**分塊查找(索引順序查找）2.6.3二叉排序樹(shù)及查找若線(xiàn)性表中的結(jié)點(diǎn)經(jīng)常插入和刪除，就應(yīng)設(shè)計(jì)成把鏈表和二分法結(jié)合的查找方法。二叉排序樹(shù)是將線(xiàn)形表中的元素組織成二叉樹(shù)的形式，以達(dá)到與對(duì)半查找相同的查找效率。1、二叉排序樹(shù)定義：（1）若它的左子樹(shù)不空，則左子樹(shù)上所有的關(guān)鍵字均小于它 的根結(jié)點(diǎn)的關(guān)鍵字；（2）若它的右子樹(shù)不空，則右子樹(shù)上所有的關(guān)鍵字均大于或 等于它的根結(jié)點(diǎn)的關(guān)鍵字；（3）它的左、右子樹(shù)也是二叉排序樹(shù)。

如果按中序遍歷二叉排序樹(shù)，可得到一個(gè)遞增排列的序列。2.6.3二叉排序樹(shù)及查找526481937中序遍歷序列：1、2、3、4、5、6、7、8、9二叉排序樹(shù)示例：526481937中序遍歷序列：1、2、3、4、5、6、7、//TreeNode類(lèi)publicclassTreeNode{publicchardata;publicTreeNodeleftChild;publicTreeNoderightChild;publicTreeNode(charc){data=c;leftChild=null;rightChild=null;}}//BiTree類(lèi)publicclassBiTree{privateTreeNoderoot;publicBiTree(){root=null;}publicvoidinsBTree(chark){//二叉排序樹(shù)創(chuàng)建}

publicTreeNodebanSearch(chark){//二叉排序查找方法}}二叉排序樹(shù)代碼表示：//TreeNode類(lèi)//BiTree類(lèi)二叉排序樹(shù)代碼表示：2、查找算法及實(shí)現(xiàn)在給定的二叉排序樹(shù)t中查找給定待查關(guān)鍵字k：從根結(jié)點(diǎn)出發(fā)（1）如果樹(shù)t為空，那么查找失敗。算法結(jié)束；否則，轉(zhuǎn)（2）（2）如果t.data等于k，則查找成功。算法結(jié)束。否則轉(zhuǎn)（3）（3）如果k<t.data，則t=t.leftchild(到左子樹(shù)查找)， 轉(zhuǎn)(1);否則t=t.rightchild（到右子樹(shù)查找），轉(zhuǎn)（1）。2、查找算法及實(shí)現(xiàn)publicTreeNodebanSearch(chark){TreeNodep=root;while(){if(p.data>k);else;}return(p);}(p!=null)&&(p.data!=k)p=p.leftChildp=p.rightChildpublicTreeNodebanSearch(cha

假設(shè)一組數(shù)據(jù)元素的關(guān)鍵字序列如下：{45，24，53，12，37，93，30，40，80}分析查找元素40

如何創(chuàng)建二叉排序樹(shù)？假設(shè)一組數(shù)據(jù)元素的關(guān)鍵字序列如下：如3、創(chuàng)建二叉排序樹(shù)

通過(guò)在初始為空的樹(shù)中不斷插入數(shù)k來(lái)建立二叉排序樹(shù)，步驟：（1）若二叉排序樹(shù)為空，則插入結(jié)點(diǎn)應(yīng)為根結(jié)點(diǎn)（2）若二叉排序樹(shù)非空，根據(jù)關(guān)鍵字比較的結(jié)果確定是在左 子樹(shù)還是在右子樹(shù)中繼續(xù)查找插入位置，直至某個(gè)結(jié)點(diǎn)的 左子樹(shù)或右子樹(shù)空為止，則插入結(jié)點(diǎn)應(yīng)為該結(jié)點(diǎn)的左孩子 或右孩子。3、創(chuàng)建二叉排序樹(shù)

假定由整數(shù)序列{10，6，19，22，8，2}生成一棵二叉排序樹(shù)，可以采用逐個(gè)元素插入的方法實(shí)現(xiàn)。

(1)首先將10作為根結(jié)點(diǎn)

(2)然后插入6時(shí)，通過(guò)比較知6<10，所以將6作為10的 左孩子插入；

(3)同理將19作為10的右孩子插入；

(4)整數(shù)22通過(guò)和10、19比較后，作為19的右孩子插入。

(5)依次插入剩余的其他元素

假定由整數(shù)序列{10，6，19，22，8，2}生成一棵publicvoidinsBTree(chark)//將k插入到二叉排序樹(shù){TreeNodep,q;q=newTreeNode(k);if(root==null)//樹(shù)為空，該節(jié)點(diǎn)即根節(jié)點(diǎn)

{root=q;return;}p=root;//從根開(kāi)始開(kāi)始找位置

while((p.leftChild!=q)&&(p.rightChild!=q))//尚未插入新節(jié)點(diǎn)

{if(k<p.data){if(p.leftChild!=null);else;}else{if()p=p.rightChild;elsep.rightChild=q;}}}p=p.leftChildp.leftChild=qp.rightChild!=nullpublicvoidinsBTree(chark)4.二叉排序樹(shù)的構(gòu)造如果給定一個(gè)數(shù)據(jù)元素的集合，則數(shù)據(jù)元素的讀入順序不同，其構(gòu)造出的二叉排序樹(shù)的形態(tài)也不同。例序列(53,61,12,37,90,100,3,78,45)， (61,37,90,45,100,78,12,3,53), (3,12,37,45,53,61,78,90,100)構(gòu)造的二叉排序樹(shù)分別為圖1，圖2和圖3。531261337904578100613790124535378100圖1圖2312374553617890100圖34.二叉排序樹(shù)的構(gòu)造53126133790457810065.二叉排序樹(shù)的平衡化處理二叉排序樹(shù)的查找效率與構(gòu)成的二叉排序樹(shù)的形態(tài)有關(guān)。為了提高查找效率，還需在構(gòu)造二叉排序樹(shù)的過(guò)程中進(jìn)行“平衡化”處理，使之成為平衡的二叉排序樹(shù)。這樣，平衡二叉排序樹(shù)的查找就與折半查找一樣高效。平衡二叉樹(shù)的遞歸定義如下：平衡二叉樹(shù)或是一棵空樹(shù)，或是一棵具有下列性質(zhì)的二叉樹(shù)：(1)左子樹(shù)與右子樹(shù)的深度之差的絕對(duì)值不超過(guò)1；(2)左、右子樹(shù)也是平衡二叉樹(shù)。5.二叉排序樹(shù)的平衡化處理2.7排序排序是將一個(gè)數(shù)據(jù)元素的無(wú)序序列，按其關(guān)鍵字的大小重新排列，變成一個(gè)有序序列。分為內(nèi)部排序和外部排序.內(nèi)部排序:排序操作都在內(nèi)存中進(jìn)行.以比較次數(shù)衡量算法效率.外部排序:排序操作還需訪(fǎng)問(wèn)外存.以訪(fǎng)問(wèn)外存的次數(shù)衡量算法效率排序算法的穩(wěn)定性:對(duì)于關(guān)鍵字相同的元素,排序中不改變其相對(duì)次序,稱(chēng)為穩(wěn)定的排序算法;反之稱(chēng)為不穩(wěn)定的排序算法.按算法效率分簡(jiǎn)單的排序和先進(jìn)的排序。前者包括選擇法排序、冒泡法排序、插入法排序；后者則包括快速排序法和歸并排序。2.7排序2.7.1選擇排序第1步：在N個(gè)元素的排序表中選擇最小元素第2步：將最小元素與表頭元素交換第3步：N=N-1第4步：若N>1，則執(zhí)行第1步，否則結(jié)束排序

初始狀態(tài)4521341952603424第1趟（i=1）[19]21344552603424第2趟（i=2）[19

21]344552603424第3趟（i=3）[19

2124]4552603434第4趟（i=4）[19

212434]52604534第5趟（i=5）[19

21243434]604552第6趟（i=6）[19

2124343445]6052第7趟（i=7）[19

212434344552]60可見(jiàn)，選擇排序是一種不穩(wěn)定的排序。2.7.1選擇排序第1步：在N個(gè)元素的排序表中選擇最小元素具體算法描述如下:

publicvoidselectSort(){inti,j,k;for(i=0;i<length-1;i++){; for(j=i+1;j<n;j++)if()

k=j;//記錄最小元素的位置

if(){intx=data[i];data[i]=data[k];data[k]=x;}}}k=idata[j]<data[k]k!=i具體算法描述如下:k=idata[j]<data[k2.6.2交換排序1、冒泡排序?qū)⒋判蛭募械挠涗泝蓛杀容^，若為逆序，則進(jìn)行交換。按此方法將文件從頭到尾處理一遍稱(chēng)作一趟起泡。一趟起泡的結(jié)果是將關(guān)鍵字最大的記錄交換到了表尾。對(duì)余下n-1個(gè)記錄，重復(fù)此過(guò)程，直至文件排好序?yàn)橹埂Ｈ裟骋惶似鹋葸^(guò)程中沒(méi)有任何交換發(fā)生，則表明此時(shí)文件已經(jīng)排好序了，不必再繼續(xù)重復(fù)起泡過(guò)程。初始狀態(tài)[4521341952603424]第一趟21341945523424[60]第二趟211934453424[5260]第三趟1921343424[455260]第四趟19213424[34455260]第五趟192124[3434455260]第六趟1921243434455260可見(jiàn)，冒泡算法是穩(wěn)定的。2.6.2交換排序可見(jiàn)，冒泡算法是穩(wěn)定的。publicvoidbubSort(){boolneedChange=true;

intj=length-1;while(){needChange=false;//先假定不需要交換

for(inti=0;i<j;i++)if(data[i]>data[i+1]){;

inttemp=data[i];data[i]=data[i+1];data[i+1]=temp;}j--;}}needChange的作用是當(dāng)前內(nèi)循環(huán)無(wú)交換時(shí)，即終止程序的運(yùn)算。needChange&&j>0needChange=truepublicvoidbubSort()needChan**直接插入排序基本思想：將n個(gè)待排序元素看成為一個(gè)有序表和一個(gè)無(wú)序表。開(kāi)始有序表只有一個(gè)元素，無(wú)序表中則有n-1個(gè)元素。排序過(guò)程中每次從無(wú)序表中取出第一個(gè)元素，將其關(guān)鍵字與有序表的關(guān)鍵字比較，將其插入到適當(dāng)位置，使之成為新的有序表。插入步驟：（1）將無(wú)序表中的第一個(gè)元素存入輔助變量temp中。（2）將temp和有序表中從最后一個(gè)元素開(kāi)始進(jìn)行比較，若小于有序表中的元素，則有序表中該元素后移一位，同時(shí)繼續(xù)和前一元素比較。否則插入到該元素的后面。**直接插入排序基本思想：初始狀態(tài)[45]21341952603424

第一趟[2145]341952603424

第二趟[213445]1952603424

第三趟[19213445]52603424

第四趟[1921344552]603424

第五趟[192134455260]3424

第六趟[19213434455260]24

第七趟[1921243434455260]

有序文件1921243434455260插入排序是穩(wěn)定的排序初始狀態(tài)[45]21341952publicvoidinsertSort(){ inti,j,temp; for(i=1;i<length;i++) {;//將待插入元素保存 j=i-1;//有序表最后一個(gè)元素的下標(biāo) while(j>=0&&temp<data[j]) { ; j--; } ; }}data[j+1]=data[j]data[j+1]=temptemp=data[i]publicvoidinsertSort()data[j2.6.4快速排序基本思想：在待排序的n個(gè)元素中任取一個(gè)元素R，以該元素排序碼k為準(zhǔn)，將所有剩下的n-1個(gè)元素分割為兩個(gè)子序列：第一個(gè)子序列中每個(gè)元素的排序碼均小于或等于k；第二個(gè)子序列中每個(gè)元素的排序碼均大于或等于k。然后將k所對(duì)應(yīng)的元素放在兩個(gè)子序列之間。完成第一趟排序，使得待排序序列成為

<子序列1>R<子序列2>分別對(duì)子序列1和子序列2重復(fù)上述劃分，直到每個(gè)子序列中只有一個(gè)元素時(shí)為止。2.6.4快速排序線(xiàn)性表分割步驟:（1）設(shè)置兩個(gè)指示器i和j，其初始狀態(tài)分別指向區(qū)間內(nèi)第一個(gè)記錄和最后一個(gè)記錄。（2）將第一個(gè)記錄移向輔助變量x中（3）從j所指位置起向前搜索第一個(gè)小于x的記錄，找到后，將a[j]移至a[i]的位置；（4）從i所指向的位置向后搜索第一個(gè)關(guān)鍵字大于x的記錄，找到后，將a[i]移至a[j]的位置；（5）重復(fù)3、4兩步，直至i==j，最后將x送至a[i]中去。至此一趟排序完成，文件劃分為兩個(gè)子序列。重復(fù)以上步驟直到每個(gè)子序列中只有一個(gè)元素時(shí)為止。數(shù)據(jù)結(jié)構(gòu)6(4月28日)課件初始狀態(tài)4521341952603424ij一次交換24213419526034

24

i→j二次交換2421341952603452i←j三次交換242134193460

3452i→j[2421341934]45[6052]ij(a)一趟排序初始狀態(tài)[4521341952603424]第一趟[2421341934]45[6052]第二趟[1921]24[3434]第三趟1921第四趟3434第五趟5260有序文件1921243434455260(b)全部快速排序初始狀態(tài)452134195260

privatevoidqkOne(intstart,intend,outintmid){intx,i,j;i=start;j=end;x=data[i];//將第一個(gè)值保存在x中

while(){while(i<j&&data[j]>=x)//自右向左掃描

;

if(i<j){;i++;}while(i<j&&data[i]<=x)//自左向右掃描

;

if(i<j){data[j]=data[i];j--;}};mid=i;}i!=jj--data[i]=data[j]i++data[i]=x一趟分割的代碼privatevoidqkOne(intstart,快速排序是不穩(wěn)定的排序，但是內(nèi)排序中速度最快的。publicvoidqkSort(){intstart=0,end=length-1,mid;ArrayStackas=newArrayStack(100);//建立一個(gè)堆棧as.push(start);as.push(end);while(!as.isEmpty()){end=as.pop();//與壓棧的次序相反，彈出位置start=as.pop();while(start<end){qkone(start,end,outmid);as.push(mid+1);//將分割后的第二個(gè)序列壓棧

as.push(end);end=mid-1;//調(diào)節(jié)位置準(zhǔn)備對(duì)第一個(gè)序列再分割，位置從start到mid-1}}}快速排序快速排序是不穩(wěn)定的排序，但是內(nèi)排序中速度最快的。public2.7.3歸并排序采用二路歸并技術(shù)，即每次將數(shù)組a中兩個(gè)相鄰的有序序列歸并為一個(gè)有序序列。排序步驟：（1）假設(shè)待排序文件含有n個(gè)記錄，則可看成是n個(gè)有序的子序列，每個(gè)子序列的長(zhǎng)度為1（2）兩兩歸并，得到[n/2]個(gè)長(zhǎng)度為2或1的有序子序列（3）再兩兩歸并，直到得到一個(gè)長(zhǎng)度為n的有序文件為止。2.7.3歸并排序初始狀態(tài)[45][21][34][19][52][60][34][24]┕━━┙┕━━┙┕━━┙┕━━┙第一趟[2145][1934][5260][2434]┕━━┙┕━━┙第二趟[19213445][24345260]┕━━━━━━┙第三趟1921243434455260二路歸并排序過(guò)程示例

二路歸并排序是穩(wěn)定的排序初始狀態(tài)[45][21][34][19][52]有序文件a[s..m]和a[m+1...t]歸并為b[s..t]的算法:twoSort(inta[],ints,intm,intt,intb[]){inti,j,k;i=s;//i是a[s..m]的指示器j=m+1;//j是a[m+1..t]的指示器k=s-1;//k是b[s..t]的指示器while(){k++;if(a[i]<=a[j]){;i++;}else{;j++;}}

b[k]=a[i]b[k]=a[j]i<=m&&j<=t有序文件a[s..m]和a[m+1...t]歸并為b[s..if(i>m)for(;;j++){k++;b[k]=a[j];}elsefor(;;i++){k++;b[k]=a[i];}}j<=ti<=mif(i>m)j<=ti<=m

假設(shè)文件長(zhǎng)度為n,每個(gè)子文件的長(zhǎng)度為k，歸并結(jié)果存放在數(shù)組b中，則一趟歸并描述如下:voidmerge(inta[],intk,intn,intb[]){inti=0;while(n-i>=2*k){twosort(a,i,i+k-1,i+2*k-1,b);i=i+2*k;}if(n-i>k)twosort(a,i,i+k-1,n-1,b);elsefor(;i<n;i++)b[i]=a[i];}

假設(shè)文件長(zhǎng)度為n,每個(gè)子文件的長(zhǎng)度為k，歸并結(jié)果存放一趟歸并后，有序子文件長(zhǎng)度為2，二趟歸并后，有序子文件長(zhǎng)度為4，因歸并的結(jié)果在b中,故每次歸并完將其復(fù)制到a中。重復(fù)此過(guò)程，直到有序子文件為n，具體算法描述如下voidmergeSort(inta[],intn){intk=1,b[N];//N為已定義的符號(hào)常量,代表線(xiàn)性表的長(zhǎng)度while(k<n){merge(a,k,n,b);k=2*k;for(inti=0;i<N;i++)a[i]=b[i];}

}一趟歸并后，有序子文件長(zhǎng)度為2，二趟歸并后，有序子文件長(zhǎng)度為各種排序方法的比較各種排序方法的比較（學(xué)號(hào)-6-1）將如下一組數(shù)據(jù)插入到一棵二叉排序樹(shù)中，并將該二叉排序樹(shù)的中序遍歷結(jié)果輸出。{45，24，53，12，37，93，30，40，80}作業(yè)（學(xué)號(hào)-6-1）將如下一組數(shù)據(jù)插入到一棵二叉排序樹(shù)中，并將該查找：根據(jù)給定的關(guān)鍵字值，在一組數(shù)據(jù)元素中確定一個(gè)其關(guān)鍵字值等于給定值的數(shù)據(jù)元素的過(guò)程。若存在這樣的數(shù)據(jù)元素，則稱(chēng)查找成功；若不存在這樣的數(shù)據(jù)元素，則稱(chēng)查找失敗。關(guān)鍵字:指數(shù)據(jù)元素中可以標(biāo)識(shí)該數(shù)據(jù)元素的一組數(shù)據(jù)項(xiàng)。例如學(xué)生記錄中的學(xué)號(hào)；公民記錄中的身份證號(hào)碼等。查找表：指一組待查數(shù)據(jù)元素的集合。它具有一定存儲(chǔ)結(jié)構(gòu)，如順序表結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)、樹(shù)形結(jié)構(gòu)等。

2.6查找查找：2.6查找1)查找的方法查找某個(gè)數(shù)據(jù)元素依賴(lài)于查找表中數(shù)據(jù)元素的組織方式。按照數(shù)據(jù)元素的組織方式?jīng)Q定采用某種查找方法；反之,為了提高查找方法的效率，又要求數(shù)據(jù)元素采用某些特殊的組織方式。因此，在研究各種查找方法時(shí)，必須弄清各種查找方法所適用的組織方式。2)查找算法的評(píng)價(jià)衡量一個(gè)算法的標(biāo)準(zhǔn)主要有兩個(gè)：時(shí)間復(fù)雜度和空間復(fù)雜度。而在查找算法中，基本運(yùn)算是給定值與關(guān)鍵字值的比較，即算法的主要時(shí)間是花費(fèi)在“比較”上的，所以，用平均查找長(zhǎng)度作為評(píng)價(jià)查找算法好壞的依據(jù)。對(duì)于含有n個(gè)數(shù)據(jù)元素的查找表，查找成功的平均查找長(zhǎng)度為ASL=其中：Pi為查找第i個(gè)數(shù)據(jù)元素的概率；Ci為查找到第i個(gè)數(shù)據(jù)元素時(shí)，需進(jìn)行的比較次數(shù)。1)查找的方法ASL=其中：Pi為查找第i個(gè)數(shù)據(jù)元**查找方法分類(lèi)線(xiàn)性查找法順序查找法對(duì)半查找法分塊查找法…基于樹(shù)的查找法二叉排序樹(shù)B樹(shù)…計(jì)算式查找法——哈希法順序存儲(chǔ)的查找方法鏈?zhǔn)酱鎯?chǔ)的查找方法散列存儲(chǔ)的查找方法**查找方法分類(lèi)線(xiàn)性查找法順序存儲(chǔ)的查找方法鏈?zhǔn)酱鎯?chǔ)的查找方2.6.1

順序查找法基本思想是：從數(shù)組的第一個(gè)元素開(kāi)始，與查找的關(guān)鍵字逐個(gè)比對(duì)，直到找到關(guān)鍵字所在的位置或遇到數(shù)組的結(jié)尾為止，若找到，則返回關(guān)鍵字在數(shù)組中的位置，否則返回-1(因?yàn)镃#的數(shù)組下標(biāo)不可能為-1)。publicintsearch(intkeyValue){inti=0；while()i++;if()return(i);elsereturn(-1);}假設(shè)每個(gè)元素等概率查找,則平均查找次數(shù)為(n+1)/2i<length&&

data[i]!=keyValuei<length2.6.1順序查找法假設(shè)每個(gè)元素等概率查找,則平均查找次數(shù)2.6.2對(duì)半查找法以順序方式存放的有序表的查找可采用對(duì)半查找。將被查關(guān)鍵字k與線(xiàn)性表中間位置mid上的數(shù)據(jù)元素的關(guān)鍵字進(jìn)行比較：(假設(shè)表按由小到大順序排列）（1）若k==a[mid]，則查找成功，過(guò)程結(jié)束。（2）若k>a[mid],則取表的后半部分作為新表再去查找。（3）若k<a[mid],則取表的前半部分作為新表再進(jìn)行查找。這個(gè)過(guò)程一直進(jìn)行到查找成功或子表的長(zhǎng)度為0為止。對(duì)半查找是基于關(guān)鍵字比較的最優(yōu)方法。2.6.2對(duì)半查找法對(duì)半查找是基于關(guān)鍵字比較的最優(yōu)方法。publicintbinSearch(intkeyValue){intlow,high,mid;low=0;high=length-1;while(){mid=(low+high)/2;if(data[mid]==keyValue);elseif(data[mid]<keyValue);else;}return(-1);}low<=highreturn(mid)low=mid+1high=mid-1對(duì)半查找成功時(shí)比較次數(shù)最多為log2n+1publicintbinSearch(intkeyVa**分塊查找(索引順序查找）“分塊有序”表特點(diǎn)：(1)表中數(shù)據(jù)分塊(2)塊中數(shù)據(jù)不必有序(3)塊間有序“分塊有序”表的結(jié)構(gòu)有兩部分：(1)順序存儲(chǔ)結(jié)構(gòu)的線(xiàn)性表(2)索引表（由每塊的最大元素組成）分塊查找過(guò)程：(1)用對(duì)半查找法查找索引表，確定待查項(xiàng)x所在的塊。(2)在相應(yīng)的塊中用順序查找法查找待查項(xiàng)x。**分塊查找(索引順序查找）2.6.3二叉排序樹(shù)及查找若線(xiàn)性表中的結(jié)點(diǎn)經(jīng)常插入和刪除，就應(yīng)設(shè)計(jì)成把鏈表和二分法結(jié)合的查找方法。二叉排序樹(shù)是將線(xiàn)形表中的元素組織成二叉樹(shù)的形式，以達(dá)到與對(duì)半查找相同的查找效率。1、二叉排序樹(shù)定義：（1）若它的左子樹(shù)不空，則左子樹(shù)上所有的關(guān)鍵字均小于它 的根結(jié)點(diǎn)的關(guān)鍵字；（2）若它的右子樹(shù)不空，則右子樹(shù)上所有的關(guān)鍵字均大于或 等于它的根結(jié)點(diǎn)的關(guān)鍵字；（3）它的左、右子樹(shù)也是二叉排序樹(shù)。

如果按中序遍歷二叉排序樹(shù)，可得到一個(gè)遞增排列的序列。2.6.3二叉排序樹(shù)及查找526481937中序遍歷序列：1、2、3、4、5、6、7、8、9二叉排序樹(shù)示例：526481937中序遍歷序列：1、2、3、4、5、6、7、//TreeNode類(lèi)publicclassTreeNode{publicchardata;publicTreeNodeleftChild;publicTreeNoderightChild;publicTreeNode(charc){data=c;leftChild=null;rightChild=null;}}//BiTree類(lèi)publicclassBiTree{privateTreeNoderoot;publicBiTree(){root=null;}publicvoidinsBTree(chark){//二叉排序樹(shù)創(chuàng)建}

publicTreeNodebanSearch(chark){//二叉排序查找方法}}二叉排序樹(shù)代碼表示：//TreeNode類(lèi)//BiTree類(lèi)二叉排序樹(shù)代碼表示：2、查找算法及實(shí)現(xiàn)在給定的二叉排序樹(shù)t中查找給定待查關(guān)鍵字k：從根結(jié)點(diǎn)出發(fā)（1）如果樹(shù)t為空，那么查找失敗。算法結(jié)束；否則，轉(zhuǎn)（2）（2）如果t.data等于k，則查找成功。算法結(jié)束。否則轉(zhuǎn)（3）（3）如果k<t.data，則t=t.leftchild(到左子樹(shù)查找)， 轉(zhuǎn)(1);否則t=t.rightchild（到右子樹(shù)查找），轉(zhuǎn)（1）。2、查找算法及實(shí)現(xiàn)publicTreeNodebanSearch(chark){TreeNodep=root;while(){if(p.data>k);else;}return(p);}(p!=null)&&(p.data!=k)p=p.leftChildp=p.rightChildpublicTreeNodebanSearch(cha

假設(shè)一組數(shù)據(jù)元素的關(guān)鍵字序列如下：{45，24，53，12，37，93，30，40，80}分析查找元素40

如何創(chuàng)建二叉排序樹(shù)？假設(shè)一組數(shù)據(jù)元素的關(guān)鍵字序列如下：如3、創(chuàng)建二叉排序樹(shù)

通過(guò)在初始為空的樹(shù)中不斷插入數(shù)k來(lái)建立二叉排序樹(shù)，步驟：（1）若二叉排序樹(shù)為空，則插入結(jié)點(diǎn)應(yīng)為根結(jié)點(diǎn)（2）若二叉排序樹(shù)非空，根據(jù)關(guān)鍵字比較的結(jié)果確定是在左 子樹(shù)還是在右子樹(shù)中繼續(xù)查找插入位置，直至某個(gè)結(jié)點(diǎn)的 左子樹(shù)或右子樹(shù)空為止，則插入結(jié)點(diǎn)應(yīng)為該結(jié)點(diǎn)的左孩子 或右孩子。3、創(chuàng)建二叉排序樹(shù)

假定由整數(shù)序列{10，6，19，22，8，2}生成一棵二叉排序樹(shù)，可以采用逐個(gè)元素插入的方法實(shí)現(xiàn)。

(1)首先將10作為根結(jié)點(diǎn)

(2)然后插入6時(shí)，通過(guò)比較知6<10，所以將6作為10的 左孩子插入；

(3)同理將19作為10的右孩子插入；

(4)整數(shù)22通過(guò)和10、19比較后，作為19的右孩子插入。

(5)依次插入剩余的其他元素

假定由整數(shù)序列{10，6，19，22，8，2}生成一棵publicvoidinsBTree(chark)//將k插入到二叉排序樹(shù){TreeNodep,q;q=newTreeNode(k);if(root==null)//樹(shù)為空，該節(jié)點(diǎn)即根節(jié)點(diǎn)

{root=q;return;}p=root;//從根開(kāi)始開(kāi)始找位置

while((p.leftChild!=q)&&(p.rightChild!=q))//尚未插入新節(jié)點(diǎn)

{if(k<p.data){if(p.leftChild!=null);else;}else{if()p=p.rightChild;elsep.rightChild=q;}}}p=p.leftChildp.leftChild=qp.rightChild!=nullpublicvoidinsBTree(chark)4.二叉排序樹(shù)的構(gòu)造如果給定一個(gè)數(shù)據(jù)元素的集合，則數(shù)據(jù)元素的讀入順序不同，其構(gòu)造出的二叉排序樹(shù)的形態(tài)也不同。例序列(53,61,12,37,90,100,3,78,45)， (61,37,90,45,100,78,12,3,53), (3,12,37,45,53,61,78,90,100)構(gòu)造的二叉排序樹(shù)分別為圖1，圖2和圖3。531261337904578100613790124535378100圖1圖2312374553617890100圖34.二叉排序樹(shù)的構(gòu)造53126133790457810065.二叉排序樹(shù)的平衡化處理二叉排序樹(shù)的查找效率與構(gòu)成的二叉排序樹(shù)的形態(tài)有關(guān)。為了提高查找效率，還需在構(gòu)造二叉排序樹(shù)的過(guò)程中進(jìn)行“平衡化”處理，使之成為平衡的二叉排序樹(shù)。這樣，平衡二叉排序樹(shù)的查找就與折半查找一樣高效。平衡二叉樹(shù)的遞歸定義如下：平衡二叉樹(shù)或是一棵空樹(shù)，或是一棵具有下列性質(zhì)的二叉樹(shù)：(1)左子樹(shù)與右子樹(shù)的深度之差的絕對(duì)值不超過(guò)1；(2)左、右子樹(shù)也是平衡二叉樹(shù)。5.二叉排序樹(shù)的平衡化處理2.7排序排序是將一個(gè)數(shù)據(jù)元素的無(wú)序序列，按其關(guān)鍵字的大小重新排列，變成一個(gè)有序序列。分為內(nèi)部排序和外部排序.內(nèi)部排序:排序操作都在內(nèi)存中進(jìn)行.以比較次數(shù)衡量算法效率.外部排序:排序操作還需訪(fǎng)問(wèn)外存.以訪(fǎng)問(wèn)外存的次數(shù)衡量算法效率排序算法的穩(wěn)定性:對(duì)于關(guān)鍵字相同的元素,排序中不改變其相對(duì)次序,稱(chēng)為穩(wěn)定的排序算法;反之稱(chēng)為不穩(wěn)定的排序算法.按算法效率分簡(jiǎn)單的排序和先進(jìn)的排序。前者包括選擇法排序、冒泡法排序、插入法排序；后者則包括快速排序法和歸并排序。2.7排序2.7.1選擇排序第1步：在N個(gè)元素的排序表中選擇最小元素第2步：將最小元素與表頭元素交換第3步：N=N-1第4步：若N>1，則執(zhí)行第1步，否則結(jié)束排序

初始狀態(tài)4521341952603424第1趟（i=1）[19]21344552603424第2趟（i=2）[19

21]344552603424第3趟（i=3）[19

2124]4552603434第4趟（i=4）[19

212434]52604534第5趟（i=5）[19

21243434]604552第6趟（i=6）[19

2124343445]6052第7趟（i=7）[19

212434344552]60可見(jiàn)，選擇排序是一種不穩(wěn)定的排序。2.7.1選擇排序第1步：在N個(gè)元素的排序表中選擇最小元素具體算法描述如下:

publicvoidselectSort(){inti,j,k;for(i=0;i<length-1;i++){; for(j=i+1;j<n;j++)if()

k=j;//記錄最小元素的位置

if(){intx=data[i];data[i]=data[k];data[k]=x;}}}k=idata[j]<data[k]k!=i具體算法描述如下:k=idata[j]<data[k2.6.2交換排序1、冒泡排序?qū)⒋判蛭募械挠涗泝蓛杀容^，若為逆序，則進(jìn)行交換。按此方法將文件從頭到尾處理一遍稱(chēng)作一趟起泡。一趟起泡的結(jié)果是將關(guān)鍵字最大的記錄交換到了表尾。對(duì)余下n-1個(gè)記錄，重復(fù)此過(guò)程，直至文件排好序?yàn)橹?。若某一趟起泡過(guò)程中沒(méi)有任何交換發(fā)生，則表明此時(shí)文件已經(jīng)排好序了，不必再繼續(xù)重復(fù)起泡過(guò)程。初始狀態(tài)[4521341952603424]第一趟21341945523424[60]第二趟211934453424[5260]第三趟1921343424[455260]第四趟19213424[34455260]第五趟192124[3434455260]第六趟1921243434455260可見(jiàn)，冒泡算法是穩(wěn)定的。2.6.2交換排序可見(jiàn)，冒泡算法是穩(wěn)定的。publicvoidbubSort(){boolneedChange=true;

intj=length-1;while(){needChange=false;//先假定不需要交換

for(inti=0;i<j;i++)if(data[i]>data[i+1]){;

inttemp=data[i];data[i]=data[i+1];data[i+1]=temp;}j--;}}needChange的作用是當(dāng)前內(nèi)循環(huán)無(wú)交換時(shí)，即終止程序的運(yùn)算。needChange&&j>0needChange=truepublicvoidbubSort()needChan**直接插入排序基本思想：將n個(gè)待排序元素看成為一個(gè)有序表和一個(gè)無(wú)序表。開(kāi)始有序表只有一個(gè)元素，無(wú)序表中則有n-1個(gè)元素。排序過(guò)程中每次從無(wú)序表中取出第一個(gè)元素，將其關(guān)鍵字與有序表的關(guān)鍵字比較，將其插入到適當(dāng)位置，使之成為新的有序表。插入步驟：（1）將無(wú)序表中的第一個(gè)元素存入輔助變量temp中。（2）將temp和有序表中從最后一個(gè)元素開(kāi)始進(jìn)行比較，若小于有序表中的元素，則有序表中該元素后移一位，同時(shí)繼續(xù)和前一元素比較。否則插入到該元素的后面。**直接插入排序基本思想：初始狀態(tài)[45]21341952603424

第一趟[2145]341952603424

第二趟[213445]1952603424

第三趟[19213445]52603424

第四趟[1921344552]603424

第五趟[192134455260]3424

第六趟[19213434455260]24

第七趟[1921243434455260]

有序文件1921243434455260插入排序是穩(wěn)定的排序初始狀態(tài)[45]21341952publicvoidinsertSort(){ inti,j,temp; for(i=1;i<length;i++) {;//將待插入元素保存 j=i-1;//有序表最后一個(gè)元素的下標(biāo) while(j>=0&&temp<data[j]) { ; j--; } ; }}data[j+1]=data[j]data[j+1]=temptemp=data[i]publicvoidinsertSort()data[j2.6.4快速排序基本思想：在待排序的n個(gè)元素中任取一個(gè)元素R，以該元素排序碼k為準(zhǔn)，將所有剩下的n-1個(gè)元素分割為兩個(gè)子序列：第一個(gè)子序列中每個(gè)元素的排序碼均小于或等于k；第二個(gè)子序列中每個(gè)元素的排序碼均大于或等于k。然后將k所對(duì)應(yīng)的元素放在兩個(gè)子序列之間。完成第一趟排序，使得待排序序列成為

<子序列1>R<子序列2>分別對(duì)子序列1和子序列2重復(fù)上述劃分，直到每個(gè)子序列中只有一個(gè)元素時(shí)為止。2.6.4快速排序線(xiàn)性表分割步驟:（1）設(shè)置兩個(gè)指示器i和j，其初始狀態(tài)分別指向區(qū)間內(nèi)第一個(gè)記錄和最后一個(gè)記錄。（2）將第一個(gè)記錄移向輔助變量x中（3）從j所指位置起向前搜索第一個(gè)小于x的記錄，找到后，將a[j]移至a[i]的位置；（4）從i所指向的位置向后搜索第一個(gè)關(guān)鍵字大于x的記錄，找到后，將a[i]移至a[j]的位置；（5）重復(fù)3、4兩步，直至i==j，最后將x送至a[i]中去。至此一趟排序完成，文件劃分為兩個(gè)子序列。重復(fù)以上步驟直到每個(gè)子序列中只有一個(gè)元素時(shí)為止。數(shù)據(jù)結(jié)構(gòu)6(4月28日)課件初始狀態(tài)4521341952603424ij一次交換24213419526034

24

i→j二次交換2421341952603452i←j三次交換242134193460

3452i→j[2421341934]45[6052]ij(a)一趟排序初始狀態(tài)[4521341952603424]第一趟[2421341934]45[6052]第二趟[1921]24[3434]第三趟1921第四趟3434第五趟5260有序文件1921243434455260(b)全部快速排序初始狀態(tài)452134195260

privatevoidqkOne(intstart,intend,outintmid){intx,i,j;i=start;j=end;x=data[i];//將第一個(gè)值保存在x中

while(){while(i<j&&data[j]>=x)//自右向左掃描

;

if(i<j){;i++;}while(i<j&&data[i]<=x)//自左向右掃描