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

第六次试验报告实验主题：排序、二叉树、哈希表实验目的：1.实现快速排序、堆叠排序2 .二叉排序树搜索、插入、生成和删除3 .哈希表实验内容：1 .算法说明(1)快速排序现在排序的无序区设为Rlow.high，迅速排序的基本思想可以说明如下分解：以Rlow.high中的某个记录为基准(Pivot )，将当前无序的划分为左、右两个子划分Rlow.Pivotpos-1和RPivotpos 1.high，左子划分的所有记录的关键字为基准记录(pivot ) 的关键字pivot.key以下的右侧子区间的所有记录的关键字都是pivot.key以上，基准记录的pivot位于正确的位置(pivotpos )，无需参加进一步的排序。快速：通过递归调用快速排序左、右子区间Rlow.pivotpos-1和Rpivotpos 1.high的快速排序。组合：因为当“解决”步骤中的两个递归调用结束时，它们的左右子部分已排序。 在快速排序中，“组合”步骤可以视为空操作。void QuickSort(int u，int v )装模作样int i、j、mid；if (umid) j-；if (i=j) )swap(datai、dataj )I； j-；以下称为以下称为快速排序(u，j )快速排序(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，同样用小根的积累进行排序，与用大根的积累进行排序相似，但排序结果按降序有序。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- )printf(%d”，datai )printf(n )；以下称为(2)二叉树搜索：如果根节点的关键字值等于搜索到的关键字，则成功。否则，如果小于根节点的关键字值，则递归地检查左子树。如果大于根节点的关键字值，则递归地检查右侧子树。如果子树为空，则搜索失败。BST节点* BST _搜索(BST节点* t，int密钥)装模作样if (T！=NULL )装模作样if (key=T-key) return T；else if (密钥)返回(BST _ search (t-lchild，密钥)；else return(BST_Search(T-rchild，key ) )以下称为else return NULL；以下称为插入：首先执行搜索算法以查找插入节点的父节点。判断为被插入节点是其父节点左右的儿子。 将插入节点作为叶节点插入。如果二叉树是空的。 首先分别生成根节点。void BST _ insert (BST节点* t，int密钥)装模作样BSTNode *p；p=(BST node * ) malloc (sizeof (BST node ) )p-key=key； p-lchild=NULL； p-rchild=NULL；if (T=NULL) T=p；else装模作样if (键盘密钥) BST _ insert (t-lchild，键盘密钥)else if (密钥) BST _ insert (t-rcild，密钥)else return；以下称为以下称为删除：分为三个案例：*p节点为叶节点时，PL (左子树)和PR (右子树)为空树。 因为删除叶节点不会损坏整个树的结构，所以修改其父节点的指针即可。如果*p节点只是左侧子树PL或者右侧子树PR，那么PL或者PR可以被直接决定为父节点*f的左侧子树(当前*p是左侧子树)或者右侧子树(当前*p是右侧子树)，即使修改了这一点，也不会破坏二叉树的特性。*如果p节点的左子树和右子树不可用。 *删除p后，可依次循环并维持秩序进行调整，以保持其他要素之间的相对位置不变。 一种是将*p的左子树作为*f的左子树，*s作为*f的左子树的最右下的节点，将*p的右子树作为*s的右子树，其二是将*p的直接前体(或直接后体)代替*p而从二叉排序树中删除其直接前体(或直接后体)。void BST_Delete(int key )装模作样BSTNode *p、*father、*q；法瑟=null p=Root；while (p！=NULL )装模作样if (key=p-key) break；else装模作样法瑟=p；if (键p -键) p=p-lchild； else p=p-rchild；以下称为以下称为if (p-lchild=null ) (p-rcild=null ) ) free (p )； return； 以下称为if (p-lchild！=NULL) (p-rchild=NULL ) )装模作样if (父)=NULL) father-lchild=p-lchild； else Root=p-lchild；free(p) return；以下称为if (p-lchild=NULL) (p-rchild！=NULL ) )装模作样if (父)=null)fate-rcild=p-rcild； else Root=p-rchild；free(p) return；以下称为if (p-lchild！=NULL) (p-rchild！=NULL ) )装模作样q=p-lchild； 法瑟=nullwhile (q-rchild！=NULL )装模作样法瑟=q；q=q-rchild；swap(q-key，p-key )if (父)=null)fate-rcild=q-lchild； else p-lchild=q-lchild；free(q )return；以下称为以下称为(3)散列表void CreatHashArray ()装模作样int i，temp；HashNode *p；for (i=1； i=N； I )装模作样temp=datai % N；p=(hash node * ) malloc (sizeof (hash node ) )p-key=datai；p-next=Htemp； Htemp=p；以下称为以下称为bool Hash_Search(int key )装模作样int temp；HashNode *p；temp=key % N；if (Htemp=NULL) return false；else装模作样p=Htemp；while (p！=NULL )装模作样if (p-key=key) return true；p=p-next；以下称为以下称为return false；以下称为void Hash ()装模作样int i，key；printf ( howmanynumbersyouwanttoinput？ )；scanf(%d”，n )；printf ( pleaseinputthenumbersequence :n )for (i=1； i=N； I)scanf(%d”，datai )for (i=0； i=N-1； i ) Hi=NULL；CreatHashArray ()；do装模作样printf ( pleaseinplentionwhichnumberyouwanttosearch (or input-1至exit ) : )scanf(%d”，key )；if (key=-1) break；if (hash _ search (key ) ) printf (是！ n )； else printf (否！ n )； while (真)以下称为2 .执行结果(屏幕截图):1 .快速排序、堆积排序2 .二叉排序树搜索、插入、生成和删除3 .哈希表5 .调试分析和体会：(1)快速排序堆栈排序更换次数：快速排序少于堆叠顺序。比较次数：快速排序：数列有一定的数组时，比较次数变多当序列无序时，其比较次数大幅减少。沉积顺序：相对稳定，变动不大，比较次数也不多。(2) .二叉排序树检索、插入、生