二叉排序樹(shù)查找、插入、生成、刪除----實(shí)現(xiàn)快速排序、堆排序--哈希表實(shí)驗(yàn)報(bào)告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第六次試驗(yàn)報(bào)告實(shí)驗(yàn)題目：排序、二叉樹(shù)、哈希表實(shí)驗(yàn)?zāi)康模?.實(shí)現(xiàn)快速排序、堆排序 2.二叉排序樹(shù)查找、插入、生成、刪除 3.哈希表實(shí)驗(yàn)內(nèi)容：1、 算法描述（1）快速排序設(shè)當(dāng)前待排序的無(wú)序區(qū)為Rlow.high，利用分治法可將快速排序的基本思想描述為：分解：Rlow.high中任選一個(gè)記錄作為基準(zhǔn)(Pivot)，以此基準(zhǔn)將當(dāng)前無(wú)序區(qū)劃分為左、右兩個(gè)較小的子區(qū)間Rlow.pivotpos-1)和Rpivotpos+1.high，并使左邊子區(qū)間中所有記錄的關(guān)鍵字均小于等于基準(zhǔn)記錄(不妨記為pivot)的關(guān)鍵字pivot.key，右邊的子區(qū)間中所有記錄的關(guān)鍵字均大于等于pivo

2、t.key，而基準(zhǔn)記錄pivot則位于正確的位置(pivotpos)上，它無(wú)須參加后續(xù)的排序?？焖伲和ㄟ^(guò)遞歸調(diào)用快速排序?qū)ψ蟆⒂易訁^(qū)間Rlow.pivotpos-1和Rpivotpos+1.high快速排序。組合：因?yàn)楫?dāng)求解步驟中的兩個(gè)遞歸調(diào)用結(jié)束時(shí)，其左、右兩個(gè)子區(qū)間已有序。對(duì)快速排序而言，組合步驟無(wú)須做什么，可看作是空操作。void QuickSort(int u,int v)int i,j,mid;if (uv)i = u;j = v; mid = data(i+j)/2;while (i=j)while (dataimid) j-;if (i=j) swap(datai,dataj);

3、i+; j-;QuickSort(u,j);QuickSort(i,v);堆排序用大根堆排序的基本思想： 先將初始文件R1.n建成一個(gè)大根堆，此堆為初始的無(wú)序區(qū) 再將關(guān)鍵字最大的記錄R1(即堆頂)和無(wú)序區(qū)的最后一個(gè)記錄Rn交換，由此得到新的無(wú)序區(qū)R1.n-1和有序區(qū)Rn，且滿足R1.n-1.keysRn.key 由于交換后新的根R1可能違反堆性質(zhì)，故應(yīng)將當(dāng)前無(wú)序區(qū)R1.n-1調(diào)整為堆。然后再次將R1.n-1中關(guān)鍵字最大的記錄R1和該區(qū)間的最后一個(gè)記錄Rn-1交換，由此得到新的無(wú)序區(qū)R1.n-2和有序區(qū)Rn-1.n，且仍滿足關(guān)系R1.n-2.keysRn-1.n.keys，同樣要將R1.n-2調(diào)

4、整為堆。用小根堆排序與利用大根堆類似，只不過(guò)其排序結(jié)果是遞減有序的。void Heap_Adjust(int i, int n)int j;j = i * 2;while (j=n)if (jdataj+1) j+;if (dataidataj)swap(datai, dataj);i = j; j = j * 2;else break;void Heap()int i;for (i=N/2;i=1;i-) Heap_Adjust(i, N);for (i=N;i=1;i-)swap(data1, datai);Heap_Adjust(1, i-1);for (i=N;i=1;i-)print

5、f(%d , datai);printf(n); (2)二叉排序樹(shù)查找：若根結(jié)點(diǎn)的關(guān)鍵字值等于查找的關(guān)鍵字，成功。 否則，若小于根結(jié)點(diǎn)的關(guān)鍵字值，遞歸查左子樹(shù)。 若大于根結(jié)點(diǎn)的關(guān)鍵字值，遞歸查右子樹(shù)。 若子樹(shù)為空，查找不成功。 BSTNode *BST_Search(BSTNode *T, int key)if (T!=NULL)if (key = T-key) return T;else if (key key) return(BST_Search(T-lchild, key);else return(BST_Search(T-rchild, key);else return NULL;插入

6、：首先執(zhí)行查找算法，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)。 判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子。將被插結(jié)點(diǎn)作為插入。 若二叉樹(shù)為空。則首先單獨(dú)生成根結(jié)點(diǎn)。 void BST_Insert(BSTNode *&T, int key)BSTNode *p;p = (BSTNode*)malloc(sizeof(BSTNode);p-key = key; p-lchild = NULL; p-rchild = NULL;if (T=NULL) T = p;else if (key key) BST_Insert(T-lchild, key);else if (key T-key) BST_Insert(T-rc

7、hild, key);else return; 刪除：分三種情況： 若*p結(jié)點(diǎn)為葉子結(jié)點(diǎn)，即PL(左子樹(shù))和PR(右子樹(shù))均為空樹(shù)。由于刪去葉子結(jié)點(diǎn)不破壞整棵樹(shù)的結(jié)構(gòu)，則只需修改其雙親結(jié)點(diǎn)的指針即可。 若*p結(jié)點(diǎn)只有左子樹(shù)PL或右子樹(shù)PR，此時(shí)只要令PL或PR直接成為其雙親結(jié)點(diǎn)*f的左子樹(shù)（當(dāng)*p是左子樹(shù)）或右子樹(shù)（當(dāng)*p是右子樹(shù)）即可，作此修改也不破壞二叉排序樹(shù)的特性。 若*p結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)均不空。在刪去*p之后，為保持其它元素之間的相對(duì)位置不變，可按中序遍歷保持有序進(jìn)行調(diào)整，可以有兩種做法：其一是令*p的左子樹(shù)為*f的左子樹(shù)，*s為*f左子樹(shù)的最右下的結(jié)點(diǎn)，而*p的右子樹(shù)為*s的右子

8、樹(shù)；其二是令*p的直接前驅(qū)（或直接后繼）替代*p，然后再?gòu)亩媾判驑?shù)中刪去它的直接前驅(qū)（或直接后繼）。void BST_Delete(int key)BSTNode *p, *father, *q;father = NULL; p = Root;while (p!=NULL)if (key = p-key) break;elsefather = p;if (key key) p = p-lchild; else p = p-rchild;if (p-lchild = NULL) & (p-rchild = NULL) free(p); return; if (p-lchild != NULL)

9、 & (p-rchild = NULL) if (father!=NULL) father-lchild = p-lchild; else Root = p-lchild;free(p); return;if (p-lchild = NULL) & (p-rchild != NULL) if (father!=NULL) father-rchild = p-rchild; else Root = p-rchild;free(p); return;if (p-lchild != NULL) & (p-rchild != NULL) q = p-lchild; father = NULL;whil

10、e (q-rchild!=NULL) father = q;q = q-rchild;swap(q-key, p-key);if (father != NULL) father-rchild = q-lchild; else p-lchild = q-lchild;free(q);return;（3） 哈希表void CreatHashArray()int i,temp;HashNode *p;for (i=1;ikey = datai; p-next = Htemp; Htemp = p;bool Hash_Search(int key)int temp;HashNode *p;temp =

11、 key % N;if (Htemp=NULL) return false;elsep = Htemp;while (p!=NULL)if (p-key = key) return true;p = p-next;return false;void Hash()int i,key;printf(How many numbers you want to input? );scanf(%d, &N);printf(Please input the number sequence:n);for (i=1;i=N;i+) scanf(%d, &datai);for (i=0;i=N-1;i+) Hi

12、= NULL;CreatHashArray();doprintf(Please input which number you want to search(or input -1 to exit): );scanf(%d, &key);if (key = -1) break;if (Hash_Search(key) printf(Yes!n); else printf(No!n);while (true);2、 運(yùn)行結(jié)果（截圖）：1. 快速排序、堆排序2.二叉排序樹(shù)查找、插入、生成、刪除3.哈希表5、 調(diào)試分析和體會(huì)：（1）快速排序、堆排序 交換次數(shù)：快速排序少于堆排序。 比較次數(shù)：快速排序：當(dāng)數(shù)列有一定的序列的時(shí)候，其比較次數(shù)就比較多了， 當(dāng)數(shù)組是無(wú)序的時(shí)候，其比較次數(shù)就大大的降低了。 堆排序：比較穩(wěn)定定，并沒(méi)有多大的波動(dòng)，且比較次數(shù)都不是很多。（2）.二叉排序樹(shù)查找、插入、生成、刪除輸入時(shí)采用邊輸入邊