數(shù)據(jù)結(jié)構(gòu)中查找和排序算法實驗報告.doc

《數(shù)據(jù)結(jié)構(gòu)中查找和排序算法實驗報告.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、鄭州輕工業(yè)軟件學(xué)院試驗報告姓名張文豪班級測試技術(shù)15-01試驗名稱數(shù)據(jù)結(jié)構(gòu)中查找和排序算法三．實驗分析與步驟：1.折半查找分析：有序表表示靜態(tài)查找表時，Search函數(shù)可用折半查找來實現(xiàn)。先確定待查記錄所在的范圍（區(qū)間），然后逐步縮小范圍直到找到或找不到該記錄為止。2.順序查找分析：查找操作的性能分析：查找算法中的基本操作是將記錄的關(guān)鍵字和給定值進行比較，，通常以“其關(guān)鍵字和給定值進行過比較的記錄個數(shù)的平均值”作為衡量依據(jù)。平均查找長度：為確定記錄在查找表中的位置，需用和給定值進行比較的關(guān)鍵字個數(shù)的期望值稱為查找算法在查找成功時的平均查找長度。其中：Pi為查找表中第i

2、個記錄的概率，且；Ci為找到表中其關(guān)鍵字與給定值相等的第i個記錄時，和給定值已進行過比較的關(guān)鍵字個數(shù)。等概率條件下有：假設(shè)查找成功與不成功的概率相同：3.歸并排序分析：將兩個或兩個以上的有序表組合成一個新的有序表的方法叫歸并。第頁，共頁假設(shè)初始序列含有n個記錄，則可看成是n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到n/2個長度為2或1的有序子序列；再兩兩歸并，如此重復(fù)。4.堆排序分析:只需要一個記錄大小的輔助空間，每個待排序的記錄僅占有一個存儲空間。什么是堆？n個元素的序列{k1,k2,...,kn}當(dāng)且僅當(dāng)滿足下列關(guān)系時，稱之為堆。關(guān)系一：ki<=k2

3、i關(guān)系二：ki<=k2i+1（i=1,2,...,n/2)堆排序要解決兩個問題：1、如何由一個無序序列建成一個堆？2、如何在輸出堆頂元素之后，調(diào)整剩余元素成為一個新的堆？問題2的解決方法：四．實驗數(shù)據(jù)與清單：1.折半查找算法描述如下：intSearch_Bin(SSTableST,KeyTypekey)low=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;els

4、elow=mid+1;}return0;第頁，共頁}//Search_Bin;2.順序查找算法描述如下：靜態(tài)查找表的順序存儲結(jié)構(gòu)：typedefstruct{ElemType*elem;intlength;}SSTable;順序查找：從表中最后一個記錄開始，逐個進行記錄的關(guān)鍵字和給定值的比較，若某個記錄的關(guān)鍵字和給定值比較相等，則查找成功，找到所查記錄；反之，查找不成功。intSearch_Seq(SSTableST,KeyTypekey){ST.elme[0].key=key;for(i=ST.length;!EQ(ST.elem[i].key,key);--i);

5、returni;}3.歸并排序算法描述如下：merge(ListTyper,intl,intm,intn,ListType&r2){i=l;j=m+1;k=l-1;while(i<=m)and(j

6、;else{mergesort(r,r2,s,s+t/2);mergesort(r,r2,s+t/2+1,t);merge(r2,s,s+t/2,t,r1);}}4.堆排序算法描述如下：sift(ListType&r,intk,intm){i=k;j=2*i;x=r[k].key;finished=FALSE;t=r[k];while((j<=m)&&(!finished)){第頁，共頁if((jr[j+1].key))j++;if(x<=r[j].key)finished:=TRUE;else{r[i]=r[j];i=j;j=2*i;}

7、}r[i]=t;}HeapSort(ListType&r){for(i=n/2;i>0;i--)sift(r,i,n);for(i=n;i>1;i--){r[1]<->r[i];sift(r,i,i-1)}}五．實驗體會：通過本次實驗，我了發(fā)現(xiàn)書本上的知識和老師的講解都能慢慢理解。但是做實驗的時候，需要我把理論變?yōu)樯蠙C調(diào)試，這無疑是最難的部分，有時候我想不到合適的算法去解決問題，就請教同學(xué)，上網(wǎng)搜索，逐漸糾正了自己的錯誤。這次的程序設(shè)計對我的編程設(shè)計思維有很大的提高，以前我很不懂這門課，覺得它很難，但是現(xiàn)在明白了一些代碼的應(yīng)用，明白了每個程序都有相似