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

第六次试验报告实验题目：排序、二叉树、哈希表实验目的：1.实现快速排序、堆排序2.二叉排序树查找、插入、生成、删除3.哈希表实验内容：一、算法描述（1）快速排序设当前待排序的无序区为R[low..high]，利用分治法可将快速排序的基本思想描述为：分解：R[low..high]中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。快速：通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。组合：因为当求解步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，组合步骤无须做什么，可看作是空操作。voidQuickSort(intu,intv){inti,j,mid;if(uv){i=u;j=v;mid=data[(i+j)/2];while(i=j){while(data[i]mid)i++;while(data[j]mid)j--;if(i=j){swap(data[i],data[j]);i++;j--;}}QuickSort(u,j);QuickSort(i,v);}}堆排序用大根堆排序的基本思想：①先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区②再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。voidHeap_Adjust(inti,intn){intj;j=i*2;while(j=n){if(jn)if(data[j]data[j+1])j++;if(data[i]data[j]){swap(data[i],data[j]);i=j;j=j*2;}elsebreak;}}voidHeap(){inti;for(i=N/2;i=1;i--)Heap_Adjust(i,N);for(i=N;i=1;i--){swap(data[1],data[i]);Heap_Adjust(1,i-1);}for(i=N;i=1;i--)printf(%d,data[i]);printf(\n);}(2)二叉排序树查找：若根结点的关键字值等于查找的关键字，成功。否则，若小于根结点的关键字值，递归查左子树。若大于根结点的关键字值，递归查右子树。若子树为空，查找不成功。BSTNode*BST_Search(BSTNode*T,intkey){if(T!=NULL){if(key==T-key)returnT;elseif(keyT-key)return(BST_Search(T-lchild,key));elsereturn(BST_Search(T-rchild,key));}elsereturnNULL;}插入：首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。voidBST_Insert(BSTNode*&T,intkey){BSTNode*p;p=(BSTNode*)malloc(sizeof(BSTNode));p-key=key;p-lchild=NULL;p-rchild=NULL;if(T==NULL)T=p;else{if(keyT-key)BST_Insert(T-lchild,key);elseif(keyT-key)BST_Insert(T-rchild,key);elsereturn;}}删除：分三种情况：若*p结点为叶子结点，即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可。若*p结点只有左子树PL或右子树PR，此时只要令PL或PR直接成为其双亲结点*f的左子树（当*p是左子树）或右子树（当*p是右子树）即可，作此修改也不破坏二叉排序树的特性。若*p结点的左子树和右子树均不空。在删去*p之后，为保持其它元素之间的相对位置不变，可按中序遍历保持有序进行调整，可以有两种做法：其一是令*p的左子树为*f的左子树，*s为*f左子树的最右下的结点，而*p的右子树为*s的右子树；其二是令*p的直接前驱（或直接后继）替代*p，然后再从二叉排序树中删去它的直接前驱（或直接后继）。voidBST_Delete(intkey){BSTNode*p,*father,*q;father=NULL;p=Root;while(p!=NULL){if(key==p-key)break;else{father=p;if(keyp-key)p=p-lchild;elsep=p-rchild;}}if((p-lchild==NULL)&&(p-rchild==NULL)){free(p);return;}if((p-lchild!=NULL)&&(p-rchild==NULL)){if(father!=NULL)father-lchild=p-lchild;elseRoot=p-lchild;free(p);return;}if((p-lchild==NULL)&&(p-rchild!=NULL)){if(father!=NULL)father-rchild=p-rchild;elseRoot=p-rchild;free(p);return;}if((p-lchild!=NULL)&&(p-rchild!=NULL)){q=p-lchild;father=NULL;while(q-rchild!=NULL){father=q;q=q-rchild;};swap(q-key,p-key);if(father!=NULL)father-rchild=q-lchild;elsep-lchild=q-lchild;free(q);return;}}（3）哈希表voidCreatHashArray(){inti,temp;HashNode*p;for(i=1;i=N;i++){temp=data[i]%N;p=(HashNode*)malloc(sizeof(HashNode));p-key=data[i];p-next=H[temp];H[temp]=p;}}boolHash_Search(intkey){inttemp;HashNode*p;temp=key%N;if(H[temp]==NULL)returnfalse;else{p=H[temp];while(p!=NULL){if(p-key==key)returntrue;p=p-next;}}returnfalse;}voidHash(){inti,key;printf(Howmanynumbersyouwanttoinput?);scanf(%d,&N);printf(Pleaseinputthenumbersequence:\n);for(i=1;i=N;i++)scanf(%d,&data[i]);for(i=0;i=N-1;i++)H[i]=NULL;CreatHashArray();do{printf(Pleaseinputwhichnumberyouwanttosearch(orinput-1toexit):);scanf(%d,&key);if(key==-1)break;if(Hash_Search(key))printf(Yes!\n);elseprintf(No!\n);}while(true);}二、运行结果（截图）：1.快速排序、堆排序2.二叉排序树查找、插入、生成、删除3.哈希表五、调试分析和体会：（1）快速排序、堆排序交换次数：快速排序少于堆排序。比较次数：快速排序：当数列有一定的序列的时候，其比较次数就比较多了，当数组是无序的时候，其比较次数就大大的降低了。堆排序：比较稳定定，并没有多大的波动，且比较次数都不是很多。（2）.二叉排序树查找、插入、生成、删除输入时采用边输入边建立二叉排序树的方法，节约了输入数据所需的空间。二叉排序树的建立和查找实质是完全一样的，查找完全可以看成将所需查找的节点插入已建立好的二叉排序树中，在寻找插入位置时进行比较即可。（3)哈希表哈希表问题，在存储位置和关键字之间建立对应关系f，根据对应关系f找到定值K。若结构中存在关键字和定值K相等的记录，必定在f（K）的存储位置上，由此可以省去比较过程，直接找到所查记录。