查找與內(nèi)排序試驗五

本文格式為Word版，下載可任意編輯——查找與內(nèi)排序試驗五甘肅政法學(xué)院

本科生試驗報告

（五）

姓名:學(xué)院:專業(yè):班級:

試驗課程名稱:數(shù)據(jù)結(jié)構(gòu)試驗日期:2023年12月17日指導(dǎo)教師及職稱:金濤試驗成績:

開課時間：2023-2023學(xué)年第一學(xué)期

甘肅政法學(xué)院試驗管理中心印制

試驗題查找、內(nèi)排序目姓名班級小組合否作學(xué)號一、試驗?zāi)康睦斫獠檎业幕靖拍?包括靜態(tài)查找表和動態(tài)查找表、內(nèi)查找和外查找之間的差異；重點(diǎn)把握線性表上各種查找算法,包括順序查找、二分查找和分塊查找的基本思路、算法實(shí)現(xiàn)和查找效率等；把握各種樹表的查找算法,包括二叉排序樹、AVL樹和B-樹的基本思路、算法實(shí)現(xiàn)和查找效率等；把握哈希表查找技術(shù)以及哈希表與其他表的本質(zhì)區(qū)別。理解內(nèi)排序的基本概念；重點(diǎn)把握插入排序算法,包括直接插入排序和希爾排序的過程和算法實(shí)現(xiàn)；重點(diǎn)把握交換排序算法,包括冒泡排序和快速排序的過程和算法實(shí)現(xiàn)；重點(diǎn)把握選擇排序算法,包括直接選擇排序和堆排序的過程和算法實(shí)現(xiàn)；把握歸并排序的過程和算法實(shí)現(xiàn)；握基數(shù)排序的過程和算法實(shí)現(xiàn)；活運(yùn)用各種排序算法解決一些綜合應(yīng)用問題。二．試驗環(huán)境一臺裝有MicrosoftVisualC++6.0的計算機(jī)。三、試驗內(nèi)容與步驟一、查找：查找是給定一個值k,在含有n個記錄的表中找出關(guān)鍵字等于k的記錄。若找到,則查找成功,返回該記錄的信息或該記錄在表中的位置；否則查找失敗,返回相關(guān)的指示信息。若在查找的同時對表做修改運(yùn)算(如插入和刪除),則相應(yīng)的表稱之為動態(tài)查找表,否則稱之為靜態(tài)查找表。2.①順序查找：它的基本思路是：從表的一端開始,順序掃描線性表,依次將掃描到的關(guān)鍵字和給定值k相比較,若當(dāng)前掃描到的關(guān)鍵字與k相等,則查找成功；若掃描終止后,仍未找到關(guān)鍵字等于k的記錄,則查找失敗。②二分查找：二分查找也稱為折半查找要求線性表中的結(jié)點(diǎn)必需己按關(guān)鍵字值的遞增或遞減順序排列。它首先用要查找的關(guān)鍵字k與中間位置的結(jié)點(diǎn)的關(guān)鍵字相比較,這個中間結(jié)點(diǎn)把線性表分成了兩個子表,若比較結(jié)果相等則查找完成;若不相等,再根據(jù)k與該中間結(jié)點(diǎn)關(guān)鍵字的比較大小確定下一步查找哪個子表,這樣遞歸進(jìn)行下去,直到找到滿足條件的結(jié)點(diǎn)或者該線性表中沒有這樣的結(jié)點(diǎn)。試驗步驟及截圖如下：運(yùn)行結(jié)果如下：③分塊查找：分塊查找又稱索引順序查找,它是一種性能介于順序查找和二分查找之間的查找方法。它要求按如下的索引方式來存儲線性表：將表R[0..n-1]均分為b塊,前b-1塊中記錄個數(shù)為s=?n/b?,最終一塊即第b塊的記錄數(shù)小于等于s；每一塊中的關(guān)鍵字不一定有序,但前一塊中的最大關(guān)鍵字必需小于后一塊中的最小關(guān)鍵字,即要求表是“分塊有序〞的；抽取各塊中的最大關(guān)鍵字及其起始位置構(gòu)成一個索引表IDX[0..b-1],即IDX[i](0≤i≤b-1)中存放著第i塊的最大關(guān)鍵字及該塊在表R中的起始位置。由于表R是分塊有序的,所以索引表是一個遞增有序表。運(yùn)行結(jié)果如下：3.若一棵二叉樹中所有結(jié)點(diǎn)的平衡因子的絕對值小于或等于1,即平衡因子取值為1、0或-1,則該二叉樹稱為平衡二叉樹（AVL）。運(yùn)行結(jié)果如下：二叉排序樹：

運(yùn)行結(jié)果如下：4.B-樹又稱為多路平衡查找樹,是一種組織和維護(hù)外存文件系統(tǒng)十分有效的數(shù)據(jù)結(jié)構(gòu)。運(yùn)行結(jié)果如下：5.哈希表(HashTable)又稱散列表,是除順序表存儲結(jié)構(gòu)、鏈接表存儲結(jié)構(gòu)和索引表存儲結(jié)構(gòu)之外的又一種存儲線性表的存儲結(jié)構(gòu)。哈希表存儲的基本思路是：設(shè)要存儲的對象個數(shù)為n,設(shè)置一個長度為m(m≥n)的連續(xù)內(nèi)存單元,以線性表中每個對象的關(guān)鍵字ki(0≤i≤n-1)為自變量,通過一個稱為哈希函數(shù)的函數(shù)h(ki),把ki映射為內(nèi)存單元的地址(或稱下標(biāo))h(ki),并把該對象存儲在這個內(nèi)存單元中。h(ki)也稱為哈希地址(又稱散列地址)。把如此構(gòu)造的線性表存儲結(jié)構(gòu)稱為哈希表。

運(yùn)行結(jié)果如下：5．快速排序基本思想是：在待排序的n個記錄中任取一個記錄(尋常取第一個記錄),把該記錄放入適當(dāng)位置后,數(shù)據(jù)序列被此記錄劃分成兩部分。所有關(guān)鍵字比該記錄關(guān)鍵字小的記錄放置在前一部分,所有比它大的記錄放置在后一部分,并把該記錄排在這兩部分的中間(稱為該記錄歸位),這個過程稱作一趟快速排序。運(yùn)行結(jié)果如下：6.直接選擇排序的基本思想是：第i趟排序開始時,當(dāng)前有序區(qū)和無序區(qū)分別為R[0..i-1]和R[i..n-1](0≤i＜n-1),該趟排序則是從當(dāng)前無序區(qū)中選出關(guān)鍵字最小的記錄R[k],將它與無序區(qū)的第1個記錄R[i]交換,使R[0..i]和R[i+1..n-1]分別變?yōu)樾碌挠行騾^(qū)和新的無序區(qū)。運(yùn)行結(jié)果如下：7.堆排序是一樹形選擇排序,它的特點(diǎn)是,在排序過程中,將R[1..n]看成是一棵完全二叉樹的順序存儲結(jié)構(gòu),利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系,在當(dāng)前無序區(qū)中選擇關(guān)鍵字最大(或最小)的記錄。8.歸并排序是屢屢將兩個或兩個以上的有序表合并成一個新的有序表。最簡單的歸并是直接將兩個有序的子表合并成一個有序的表。

}}2.希爾排序：voidShellSort(RecTypeR[],intn)/*希爾排序算法*/{inti,j,d;RecTypetemp;d=n/2;/*d取初值n/2*/while(d>0){for(i=d;i=0/*R[j]與R[j+d]交換*/R[j]=R[j+d];R[j+d]=temp;j=j-d;}}d=d/2;/*遞減增量d*/}}3.冒泡排序：voidBubbleSort(RecTypeR[],intn){inti,j,exchange;RecTypetemp;for(i=0;ii;j--)/*比較,找出最小關(guān)鍵字的記錄*/if(R[j].keyiif(i=1;i--)/*循環(huán)建立初始堆*/sift(R,i,n);for(i=n;i>=2;i--)/*進(jìn)行n-1次循環(huán),完成推排序*/{temp=R[1];/*將第一個元素同當(dāng)前區(qū)間內(nèi)R[1]對換*/R[1]=R[i];R[i]=temp;sift(R,1,i-1);/*篩選R[1]結(jié)點(diǎn),得到i-1個結(jié)點(diǎn)的堆*/}}7.二路歸并排序算法如下：voidMergeSort(RecTypeR[],intn)/*自底向上的二路歸并算法*/{intlength;for(length=1;length=0;i--)/*從低位到高位做d趟排序*//*123以“321〞存儲*/{for(j=0;jdata[i]-'0';/*找第k個鏈隊*/if(head[k]==NULL)/*進(jìn)行分派,即采用尾插法建立單鏈表*/{head[k]=p;tail[k]=p;}else{tail[k]->next=p;tail[k]=p;}p=p->next;/*取下一個待排序的元素*/}p=NULL;for(j=0;jnext=head[j];t=tail[j];}}t->next=NULL;/*最終一個結(jié)點(diǎn)的next域置NULL*/}}五、試驗總結(jié)本次試驗是有關(guān)查找和內(nèi)排序的試驗，在整個試驗過程中由于操作不熟練和源代碼理解不透徹問題導(dǎo)致了一些錯誤；但通過本次試驗還是或多或少的把握了有關(guān)查找和內(nèi)排序的相關(guān)知識點(diǎn)兒。通過本次查找和排序的練習(xí)，初步把握了其基本概念和操作查找的基本概念查找表:是由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。查找表的操作：查詢某個“特定的〞數(shù)據(jù)元素是否在查找表中；檢索某個“特定的〞數(shù)據(jù)元素的各種屬性；在查找表中插入一個元素；從查找表中刪去某個數(shù)據(jù)元素。排序：將一個數(shù)據(jù)元素的無序序列重新排列成一個按關(guān)鍵字有序的序列。內(nèi)部排序：待排序記錄存放在計算機(jī)隨機(jī)存儲器中進(jìn)行的排序過程；外部排序：待排序記錄的數(shù)量很大，以致內(nèi)存一次不能容納全部記錄，在排序過程中尚需對外存進(jìn)行訪問的排序過程。在以后的試驗和學(xué)習(xí)過程中，我會更加重視理論知識與實(shí)踐相結(jié)合的方法；更好的學(xué)習(xí)該課程。

運(yùn)行結(jié)果如下：9.基數(shù)排序是通過“分派〞和“收集〞過程來實(shí)現(xiàn)排序,是一種借助于多關(guān)鍵字排序的思想對單關(guān)鍵字排序的方法。運(yùn)行結(jié)果如下：四、試驗過程與分析本次試驗是有關(guān)查找與內(nèi)排序的試驗，在整個試驗過程中我們應(yīng)當(dāng)注意一下一些問題：1.由于查找運(yùn)算的主要運(yùn)算是關(guān)鍵字的比較,所以尋常把查找過程中對關(guān)鍵字需要執(zhí)行的平均比較次數(shù)(也稱為平均查找長度)作為衡量一個查找算法效率優(yōu)劣的標(biāo)準(zhǔn)。平均查找長度ASL(AverageSearchLength)定義為：其中,n是查找表中記錄的個數(shù)。pi是查找第i個記錄的概率,一般地,均認(rèn)為每個記錄的查找概率相等,即pi=1/n(1≤i≤n),ci是找到第i個記錄所需進(jìn)行的比較次數(shù)。2.①順序查找：順序查找的算法如下(在順序表R[0..n-1]中查找關(guān)鍵字為k的記錄,成功時返回找到的記錄位置,失敗時返回-1)：intSeqSearch(SeqListR,intn,KeyTypek){inti=0;while(i=n)return-1;elsereturni;}②二分查找：算法如下(在有序表R[0..n-1]中進(jìn)行二分查找,成功時返回記錄的位置,失敗時返回-1)：intBinSearch(SeqListR,intn,KeyTypek){intlow=0,high=n-1,mid;while(lowk)/*繼續(xù)在R[low..mid-1]中查找*/high=mid-1;elselow=mid+1;/*繼續(xù)在R[mid+1..high]中查找*/}return-1;}③分塊查找：采用二分查找索引表的分塊查找算法如下(索引表I的長度為m)：intIdxSearch(IDXI,intm,SeqListR,intn,KeyTypek){intlow=0,high=m-1,mid,i;intb=n/m;/*b為每塊的記錄個數(shù)*/while(low=k)high=mid-1;elselow=mid+1;}if(lowkey==k)/*遞歸終結(jié)條件*/returnbt;if(kkey)returnSearchBST(bt->lchild,k);/*在左子樹中遞歸查找*/elsereturnSearchBST(bt->rchild,k);/*在右子樹中遞歸查找*/}4.在一棵B-樹上順序查找關(guān)鍵字為k的方法為：將k與根結(jié)點(diǎn)中的key[i]進(jìn)行比較：(1)若k=key[i],則查找成功；(2)若k＜key[1],則沿著指針ptr[0]所指的子樹繼續(xù)查找；(3)若key[i]＜k＜key[i+1],則沿著指針ptr[i]所指的子樹繼續(xù)查找；(4)若k＞key[n],則沿著指針ptr[n]