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

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

2、t.key，而基準記錄pivot則位于正確的位置(pivotpos)上，它無須參加后續(xù)的排序?？焖伲和ㄟ^遞歸調用快速排序對左、右子區(qū)間Rlow.pivotpos-1和Rpivotpos+1.high快速排序。組合：因為當求解步驟中的兩個遞歸調用結束時，其左、右兩個子區(qū)間已有序。對快速排序而言，組合步驟無須做什么，可看作是空操作。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建成一個大根堆，此堆為初始的無序區(qū) 再將關鍵字最大的記錄R1(即堆頂)和無序區(qū)的最后一個記錄Rn交換，由此得到新的無序區(qū)R1.n-1和有序區(qū)Rn，且滿足R1.n-1.keysRn.key 由于交換后新的根R1可能違反堆性質，故應將當前無序區(qū)R1.n-1調整為堆。然后再次將R1.n-1中關鍵字最大的記錄R1和該區(qū)間的最后一個記錄Rn-1交換，由此得到新的無序區(qū)R1.n-2和有序區(qū)Rn-1.n，且仍滿足關系R1.n-2.keysRn-1.n.keys，同樣要將R1.n-2調

4、整為堆。用小根堆排序與利用大根堆類似，只不過其排序結果是遞減有序的。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)二叉排序樹查找：若根結點的關鍵字值等于查找的關鍵字，成功。 否則，若小于根結點的關鍵字值，遞歸查左子樹。 若大于根結點的關鍵字值，遞歸查右子樹。 若子樹為空，查找不成功。 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í)行查找算法，找出被插結點的父親結點。 判斷被插結點是其父親結點的左、右兒子。將被插結點作為插入。 若二叉樹為空。則首先單獨生成根結點。 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結點為葉子結點，即PL(左子樹)和PR(右子樹)均為空樹。由于刪去葉子結點不破壞整棵樹的結構，則只需修改其雙親結點的指針即可。 若*p結點只有左子樹PL或右子樹PR，此時只要令PL或PR直接成為其雙親結點*f的左子樹（當*p是左子樹）或右子樹（當*p是右子樹）即可，作此修改也不破壞二叉排序樹的特性。 若*p結點的左子樹和右子樹均不空。在刪去*p之后，為保持其它元素之間的相對位置不變，可按中序遍歷保持有序進行調整，可以有兩種做法：其一是令*p的左子樹為*f的左子樹，*s為*f左子樹的最右下的結點，而*p的右子樹為*s的右子

8、樹；其二是令*p的直接前驅（或直接后繼）替代*p，然后再從二叉排序樹中刪去它的直接前驅（或直接后繼）。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、 運行結果（截圖）：1. 快速排序、堆排序2.二叉排序樹查找、插入、生成、刪除3.哈希表5、 調試分析和體會：（1）快速排序、堆排序 交換次數(shù)：快速排序少于堆排序。 比較次數(shù)：快速排序：當數(shù)列有一定的序列的時候，其比較次數(shù)就比較多了， 當數(shù)組是無序的時候，其比較次數(shù)就大大的降低了。 堆排序：比較穩(wěn)定定，并沒有多大的波動，且比較次數(shù)都不是很多。（2）.二叉排序樹查找、插入、生成、刪除輸入時采用邊輸入邊