二叉排序树查找、插入、生成、删除----实现快速排序、堆排序--哈希表实验报告

1、精选优质文档-倾情为你奉上第六次试验报告实验题目：排序、二叉树、哈希表实验目的：1.实现快速排序、堆排序 2.二叉排序树查找、插入、生成、删除 3.哈希表实验内容：1、 算法描述（1）快速排序设当前待排序的无序区为Rlow.high，利用分治法可将快速排序的基本思想描述为：分解：Rlow.high中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间Rlow.pivotpos-1)和Rpivotpos+1.high，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivo

2、t.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。快速：通过递归调用快速排序对左、右子区间Rlow.pivotpos-1和Rpivotpos+1.high快速排序。组合：因为当求解步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，组合步骤无须做什么，可看作是空操作。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建成一个大根堆，此堆为初始的无序区 再将关键字最大的记录R1(即堆顶)和无序区的最后一个记录Rn交换，由此得到新的无序区R1.n-1和有序区Rn，且满足R1.n-1.keysRn.key 由于交换后新的根R1可能违反堆性质，故应将当前无序区R1.n-1调整为堆。然后再次将R1.n-1中关键字最大的记录R1和该区间的最后一个记录Rn-1交换，由此得到新的无序区R1.n-2和有序区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、：首先执行查找算法，找出被插结点的父亲结点。 判断被插结点是其父亲结点的左、右儿子。将被插结点作为插入。 若二叉树为空。则首先单独生成根结点。 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）快速排序、堆排序 交换次数：快速排序少于堆排序。 比较次数：快速排序：当数列有一定的序列的时候，其比较次数就比较多了， 当数组是无序的时候，其比较次数就大大的降低了。 堆排序：比较稳定定，并没有多大的波动，且比较次数都不是很多。（2）.二叉排序树查找、插入、生成、删除输入时采用边输入边