devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构实验报告（四）——查找和排序算法_查找算法的设计与实现实验报告

作者：IT小白 | 2024-05-11 23:16:00

赞

踩

查找算法的设计与实现实验报告

实验目的

1. 掌握顺序查找技术和拆半查找技术以及部分排序算法的设计思想；

2. 掌握查找、部分排序算法的实现与执行过程。

实验原理

查找算法

1.顺序查找：从数组第一个元素开始逐个比较，找到后返回相应下标。

2.折半查找：从数组中间开始比较，如果需查找值比中间值大，则在中间值右边继续找，重复上述步骤，直至找到该元素；如果需查找值比中间值小，则在中间值左边继续找，重复上述步骤。

3. 二叉查找树：先利用递归方式构建一棵二叉查找树，使得左子树所有结点都比根节点小，右子树所有结点都比根节点大。查找时，通过与根节点比较大小即可分别对应进入左右子树，依次递归，直至找到该元素。

排序算法

1. 直接插入排序：假设把数组分为两部分，一部分是初始时是R1[1]，另一部分是R2[2……n-1],每次将R2的第一个元素抽出来与R1中的数进行比较，找到合适的位置插入，然后把这个元素加入R1，依次循环直到R2的数组为空。

2. 折半插入排序：与直接插入类似，只不过在寻找插入位置时采用了折半方法。

3. 希尔排序：设置初始增量为n/2（n为数组长度），将数组划分为n/2个小数组,然后对每个小数组进行直接插入排序，一轮结束后，再将增量/2，重复上述步骤，直至增量=0，即排序完成。

4. 冒泡排序：设置双重循环，相邻元素之间比较大小根据大小进行移动。并添加标志，如果剩下的序列中没有元素发生移动，则表明数组元素已排序完成，可以提前退出。

5. 快速排序：初始时，将数组的第一个元素作为标记，然后扫描数组，将比标记小的数移到标记左边，比数组大的数移到标记右边，最后返回标记的位置；所以以标记为中心，数组被划分为了两部分，假设为左右子表，接着对左右子表用递归方式重复上述步骤即可完成排序。

6. 选择排序：设置双重循环，初始时假设第一个元素是最小值，向后扫描找是否有比第一个更小的元素，如果有则记录它的下标，直到找到真正的最小值，然后把最小值和第一个元素交换位置；第二趟排序则设第二个元素是最小值，重复上述步骤，即可完成排序。

7. 堆排序：将数组看作是一棵完全二叉树的顺序存储结构。初始时，需要构建大根堆。由完全二叉树性质可得，序号大于n/2的结点都是叶子结点，叶子结点满足堆，所以只需要对序号小于n/2的这部分结点进行筛选调整。之后再反复重建堆即可完成排序。

8. 归并排序：初始时，设数组分为n个 部分，所以每个部分都是有序的；每一趟排序将两两小数组合并（合并时要比较大小进行排序）；最后合并得到一个数组即为有序数组，完成排序。

实验源码

查找

顺序表查找
  1.  
  2. int SeqSearch(int arr[], int n, int x){//顺序表查找
  3.     cout<<endl;
  4.     cout<<"-----顺序表查找-----"<<endl;
  5.     
  6.     for (int i=1; i <=n; ++i)
  7.     {
  8.         if (arr[i] == x)//找到该元素，返回下标
  9.             return i;//设数组元素位置从1开始
  10.     }
  11.     return -1;//若没找到则返回-1
  12. }
二分查找
  1.  
  2. int BinSearch(int  arr[], int n, int x){//折半查找 
  3.     cout<<endl;
  4.     cout<<"-----折半查找-----"<<endl;
  5.     
  6.     int low = 1, high = n , mid;
  7.     while (low <= high)
  8.     {
  9.         mid = (low + high) / 2;
  10.         if (arr[mid] == x)
  11.             return mid;
  12.         else if (arr[mid] > x)    //如果比中间值小，则在中间值左边查找
  13.             high = mid - 1;        //更新high
  14.         else                    //如果比中间值大，则在中间值右边查找
  15.             low = mid + 1;        //更新low
  16.     }
  17.     return -1;//若没找到则返回-1
  18. }
二叉树查找
  1.  
  2. //定义二叉树的结构 
  3. typedef char ElemType;
  4. typedef struct BiTNode{
  5.     ElemType data;        //数据域 
  6.     struct BiTNode* lchild, * rchild;    //左右子树 
  7. } BiTNode, *BiTree;    //结点、整颗树 
  8.  
  9. //在二叉查找树中插入新结点
  10. bool InsertBST(BiTree& bt, char ch){
  11.     if (bt == NULL)    {                //创建新结点
  12.         bt = new BiTNode;
  13.         bt->data = ch;
  14.         bt->lchild = bt->rchild = NULL;
  15.         return true;
  16.     }
  17.     else if (bt->data == ch){
  18.         cout << "已存在该元素，请重新输入!" << endl;
  19.         return false;
  20.     }
  21.     else if (ch < bt->data)
  22.         return InsertBST(bt->lchild, ch);
  23.     else
  24.         return InsertBST(bt->rchild, ch);
  25. }
  26. //创建二叉树
  27. BiTree CreateBST(BiTree& bt){
  28.     bt = NULL;
  29.     char ch;
  30.     for (int i = 0; i < 10; ++i){
  31.         cout << "请输入第" << i + 1 << "个字母:  ";
  32.         cin >> ch;
  33.         if (!InsertBST(bt, ch))//如果输入的数据重复，--i使得可以重新输出第i个字母；不重复则正常插入
  34.             --i;
  35.     }
  36.     cout << endl;
  37.     return bt;
  38. }
  39. //二叉排序树的查找
  40. BiTree SearchBST(BiTree bt, char ch){
  41.     if (bt == NULL || bt->data == ch){
  42.         cout<<"查找成功"<<endl;
  43.         return bt;
  44.     }
  45.         
  46.     if (ch < bt->data)                    //ch比根节点值小
  47.         return SearchBST(bt->lchild, ch);
  48.     else                            //ch比根节点大
  49.         return SearchBST(bt->rchild, ch);
  50. }

排序

直接插入排序
  1.  
  2. int process=1; 
  3. void InsertSort(int arr[], int n){      //直接插入排序
  4.     cout<<endl;
  5.     cout<<"------直接插入排序------"<<endl;
  6.     
  7.     int i, j;
  8.     process = 1;      //趟数 
  9.     for (i = 2; i <=n; ++i){
  10.         if (arr[i] < arr[i - 1]){
  11.             arr[0] = arr[i];           //将待插入的记录暂存到监视哨a[0]中
  12.             arr[i] = arr[i - 1];       //arr[i-1]后移
  13.             for (j = i - 2; arr[0] < arr[j]; --j) { //从后向前寻找插入位置，逐个后移，空出插入位置
  14.                 arr[j + 1] = arr[j];
  15.             }
  16.             arr[j + 1] = arr[0];      //插入
  17.         }
  18.         cout << "第" << process++ << "次排序： ";
  19.         printArr(arr,n);            //输出序列 
  20.         cout << endl;
  21.     }
  22. }
折半排序
  1.  
  2. void BInsertSort(int arr[],int n){      //折半插入排序
  3.     cout<<endl;
  4.     cout<<"-----折半插入排序-----"<<endl;
  5.     int i, j, low, high, m;
  6.     process = 1;                //趟数
  7.     for (i = 2; i <=n; ++i){
  8.         if (arr[i] < arr[i - 1]){
  9.             arr[0] = arr[i];                              //将待插入的记录暂存到监视哨中
  10.             low = 1; high = i;                            //置查找区间初值
  11.             while (low <= high){                        //在arr[low..high]中折半查找插入的位置
  12.                 m = (low + high) / 2;                     //折半
  13.                 if (arr[0] < arr[m])                    //插入点在前一子表
  14.                     high = m - 1;
  15.                 else                                    //插入点在后一子表
  16.                     low = m + 1;
  17.             }
  18.             for (j = i - 1; j >= high + 1; --j){        //后移
  19.                 arr[j + 1] = arr[j];
  20.             }
  21.             arr[high + 1] = arr[0];                        //将arr[0]即原arr[i]，插入到正确位置
  22.         }
  23.         cout << "第" << process++ << "次排序： ";
  24.         printArr(arr,n);                                    //输出数组元素
  25.         cout << endl;
  26.     }
  27. }
希尔排序
  1.  
  2. void ShellSort(int arr[], int n){       //希尔排序
  3.     cout<<endl;
  4.     cout<<"-----希尔排序-----"<<endl; 
  5.     int i, j, d;
  6.     d = n / 2;                  //增量初始值
  7.     process = 1;                //趟数
  8.     while (d > 0){                //当增量d=0时，则排序结束 
  9.         for (i = d+1; i <= n; ++i){                     //对所有组进行直接插入排序
  10.             if (arr[i] < arr[i - d]){
  11.                 arr[0] = arr[i];                            //将待插入的记录暂存到监视哨中
  12.                 for (j=i-d; (arr[0] < arr[j]) && (j>0) ; j = j - d){     //从后向前寻找插入位置，逐个后移，空出插入位置
  13.                     arr[j + d] = arr[j];
  14.                 }
  15.                 arr[j + d] = arr[0];                        //插入正确位置
  16.             }
  17.  
  18.         }
  19.         d = d / 2;                                  //减小增量
  20.         cout << "第" << process++ << "次排序： ";
  21.         printArr(arr,n);                              //输出序列 
  22.         cout << endl;
  23.     } 
  24. }
冒泡排序
  1.  
  2. void BubbleSort(int arr[],int n){     //冒泡排序
  3.     cout<<endl;
  4.     cout<<"-----冒泡排序-----"<<endl;   
  5.    
  6.     int j,m, flag;
  7.     m = n - 1;
  8.     flag = 1;                      //flag用来标记某一趟排序是否发生交换
  9.     process = 1;                //趟数 
  10.     while(m && flag){
  11.         flag = 0;                           //flag置为0，如果本趟排序没有发生交换，则不会执行下一趟排序
  12.         for (j = 1; j <= m; ++j){
  13.             if (arr[j] > arr[j + 1]){
  14.                 flag = 1;                    //flag置为1，表示本趟排序发生了交换
  15.                 arr[0] = arr[j];
  16.                 arr[j] = arr[j + 1];
  17.                 arr[j + 1] = arr[0];        //交换前后两个记录
  18.             }
  19.         }
  20.         --m;
  21.         if (flag == 0) return;    //没有排序，说明排完了，直接跳出 
  22.         else{
  23.             cout << "第" << process++ << "次排序： ";
  24.             printArr(arr,n);
  25.             cout << endl;
  26.         }
  27.     }  
  28. }
快速排序
  1.  
  2. int Partition(int arr[], int low, int high){    //划分
  3.     //对arr中的子表arr[low..high]进行一趟排序，返回枢轴位置
  4.     arr[0] = arr[low];                        //用子表的第一个记录做标记
  5.     while (low < high){                        //从序列的两端交替地向中间扫描
  6.         while (low < high && arr[high] >= arr[0]){
  7.             --high;
  8.         }
  9.         arr[low] = arr[high];                    //将比标记记录小的记录移到左边
  10.         while (low < high && arr[low] <= arr[0]){
  11.             ++low;
  12.         }
  13.         arr[high] = arr[low];                    //将比标记记录大的记录移到右边
  14.     }
  15.     arr[low] = arr[0];                        //标记记录到位
  16.     cout << "第" << process++ << "次排序： ";
  17.     printArr(arr,10);
  18.     cout << endl;
  19.     return  low;                            //返回标记位置
  20. }
  21. void QuickSort(int arr[], int low, int high){        //快速排序
  22.     int i;
  23.     if (low < high){
  24.         i = Partition(arr, low, high);         //将arr[low..high]一分为二，i是标记位置
  25.         QuickSort(arr, low, i - 1);                //对左子表递归排序
  26.         QuickSort(arr, i + 1, high);            //对右子表递归排序
  27.     }
  28. }
简单选择排序
  1.  
  2. void SelectSort(int arr[],int n){       //简单选择排序
  3.     cout<<endl;
  4.     cout<<"-----选择排序-----"<<endl;
  5.  
  6.     int i, j, temp;               //假设arr[temp]为最小
  7.     process = 1;                //趟数
  8.     for (i = 1; i <n-1; ++i){      //在arr[] 中选择关键字最小的记录
  9.         temp = i;
  10.         for (j = i + 1; j <=n; ++j){
  11.             if (arr[j] < arr[temp])
  12.                 temp = j;            //temp指向此趟排序中关键字最小的记录
  13.         }
  14.         if (temp != i){     //交换r[i]与r[k] 
  15.             arr[0] = arr[i]; 
  16.             arr[i] = arr[temp]; 
  17.             arr[temp] = arr[0]; 
  18.         } 
  19.         cout << "第" << process++ << "次排序： ";
  20.         printArr(arr,n);
  21.         cout << endl;
  22.     }
  23. }
  24. vo
堆排序
  1.  
  2. void sift(int arr[], int low, int high){             //筛选
  3.     int i = low, j = 2 * i;         //根据完全二叉树性质，i的孩子为2*i和2*i+1
  4.     arr[0] = arr[i];
  5.     while (j <= high){
  6.         if (j < high && arr[j] < arr[j + 1])         //若右孩子大 
  7.             ++j;
  8.         if (arr[0] < arr[j]){         //将arr[j]调整到双亲结点位置上
  9.             arr[i] = arr[j];
  10.             i = j;                   //修改i和j，以便向下筛选
  11.             j = 2 * i;
  12.         }else{
  13.             break;
  14.         }
  15.     }
  16.     arr[i] = arr[0];          //被筛选结点放入最终位置上
  17. }
  18. void HeapSort(int arr[], int n){             //堆排序
  19.     cout<<endl;
  20.     cout<<"-----堆排序-----"<<endl;
  21.     
  22.     int i;
  23.     process = 1;                        //趟数
  24.     for (i = n / 2; i >= 1; --i)       //建立初始堆，调用sift算法（n/2）（向下取整）次
  25.         sift(arr, i, n);
  26.     for (i = n; i >= 2; i--){
  27.         //a[0]为哨兵位 
  28.         arr[0] = arr[i];                //将堆顶元素a[1]和当前未经排序子序列arr[1...i]的最后一个元素交换 
  29.         arr[i] = arr[1];
  30.         arr[1] = arr[0];
  31.         sift(arr, 1, i - 1);            //重新调整arr[1...i-1]为根堆 
  32.         cout << "第" << process++ << "次排序： ";
  33.         printArr(arr,n);
  34.         cout << endl;
  35.     }
  36. }
归并排序
  1.  
  2. void Merge(int arr[], int temp[], int low,int mid, int high){       //合并
  3.    int i = low,j=mid+1,k=low;
  4.    while (i <= mid && j <= high)        //将arr中的记录从小到达放入temp中
  5.    {
  6.        if (arr[i] <= arr[j]){
  7.            temp[k++] = arr[i++];
  8.        }
  9.        else{
  10.            temp[k++] = arr[j++];        
  11.        }
  12.    }
  13.    while (i <= mid)                     //若arr[j……high]已遍历完，则将arr[i,mid]复制到temp中
  14.    {
  15.        temp[k++] = arr[i++];
  16.    }
  17.    while (j <= high)                    //若arr[i,mid]已遍历完，则将arr[j……high]复制到temp中
  18.    {
  19.        temp[k++] = arr[j++];
  20.    }
  21. }
  22. void MergeSort(int arr[], int temp[], int low, int high){        //二分归并排序
  23.     int s[20];
  24.     if (low == high)
  25.         temp[low] = arr[low];
  26.     else{
  27.         int mid = (low + high) / 2;             //将当前序列一分为二
  28.         MergeSort(arr, s, low, mid);            //对分裂点的左边序列递归归并排序，结果放入S[low……mid]
  29.         MergeSort(arr, s, mid + 1, high);       //对分裂点的右边序列递归归并排序，结果放入S[mid+1……high]
  30.         Merge(s, temp, low, mid, high);         //合并S[low……mid]和S[mid+1……high]
  31.         cout << "第" << process++ << "次排序的中间过程： ";
  32.         printArr(temp,20);
  33.         cout << endl;
  34.     }
  35. }

main

  1.  
  2. int main(){
  3.  
  4. //    cout<<"初始序列: ";
  5. //    for(int i=1;i<=10;i++){
  6. //        cin>>arr[i];
  7. //    }
  8.  
  9.     //排序
  10. //    InsertSort(arr,10);
  11. //    BInsertSort(arr,10);
  12. //    ShellSort(arr,10); 
  13. //    BubbleSort(arr,10);
  14. //    cout<<endl;
  15. //    QuickSort(arr,0,10); 
  16. //    SelectSort(arr,10);
  17. //    HeapSort(arr,10);
  18.  
  19.     //查找
  20. //    int x;
  21. //    cin>>x;
  22. //    cout<<SeqSearch(arr,10,x);
  23. //    cout<<BinSearch(arr,10,x);
  24.  
  25. //    BiTree Tree=NULL;
  26. //    CreateBST(Tree);
  27. //    cout<<"输入要查的值：";
  28. //    char x;
  29. //    cin>>x;
  30. //    SearchBST(Tree,x);
  31.  
  32.     return 0;
  33. }

实验结果

查找

排序

等等等等（篇幅有限）

实验心得

  1. 对于序列，一般从索引1开始存放数据，索引0留着，可作为哨兵位，因此一些for循环中的结束条件是i<n还是i<=n要考虑清除。实验中设置长度为11的数组，首位放0。实际排序是后面10个数字。

2.查找过程中，二分查找针对有序序列，因此要先对序列排序，再二分查找，一开始疏忽了这个点，出了小错误，自己手画一遍查找流程才恍然大悟。

3.直接插入排序、冒泡排序、简单选择排序相对比较慢，但是代码比较简单；快速排序、堆排序、归并排序比较快，但代码相对复杂。

今日创作在听《龙卷风》

其他博文：

数据结构实验报告（一）——线性表、堆栈和队列的操作与实现_队列的基本操作实验报告-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/luohaojia123/article/details/128689896?spm=1001.2014.3001.5501数据结构实验报告（二）——二叉树基本操作_数据结构实验报告二叉树的基本操作-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/luohaojia123/article/details/127905639?spm=1001.2014.3001.5502数据结构实验报告（三）——图的操作和实现_图的基本操作数据结构实验总结与体会(问题及解决方案、收获与感想等,不低于500字)-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/luohaojia123/article/details/128690098?spm=1001.2014.3001.5501

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/556632
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号