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

顺序表的查找和二叉排序树的查找-数据结构类C语言_用c语言实现顺序表的顺序查找和二分查找或建立一个二叉排序树并尽心查找操作实现

作者：酷酷是懒虫 | 2024-08-03 08:21:52

赞

踩

用c语言实现顺序表的顺序查找和二分查找或建立一个二叉排序树并尽心查找操作实现

目录

一、功能函数(func.cpp)

二、主调函数(main.cpp)

三、头文件(before.h)

四、运行截图及功能函数部分展示

        1、顺序表

       （1）顺序表的创建

       （2）顺序查找法

       （3）冒泡排序

       （4）折半查找法

        2、二叉排序树

        （1）二叉排序树的建立

        （2）二叉排序树的插入

        （3）二叉排序树的查找

五、运行环境

一、功能函数(func.cpp)

  1. #include <iostream>
  2. #include "before.h"
  3.  
  4. using namespace std;
  5.  
  6. //*************************************//
  7. //顺序表相关函数定义
  8. status CreateSST(SSTable &ST,int numb)
  9. {
  10.     ST.R = (ElemType *)malloc(sizeof(ElemType)*(numb+1));
  11.     if(!ST.R) return ERROR;                     //空间分配失败
  12.     ST.length = numb;
  13.     cout << "---请输入" << numb << "个元素：" << endl;
  14.     for(int i = 1;i < numb+1;i ++) cin >> ST.R[i].key;
  15.     fflush(stdin);                        //清除缓存
  16.     return OK;                                 //创建成功
  17. }//创建顺序表
  18.  
  19. status Search_Seq(SSTable ST,KeyType key,int &cnt)
  20. {
  21.     ST.R[0].key = key;                             //监视哨
  22.     int i;
  23.     for(i = ST.length;i > 0;i --)                  //末尾开始查找
  24.     {
  25.         if(ST.R[i].key != key)
  26.         {
  27.             cnt ++;
  28.             cout << "经过的元素：" << ST.R[i].key << endl;
  29.         }
  30.         if(ST.R[i].key == key) break;
  31.     }
  32.     cnt ++;
  33.     return i;                                    //返回-1则不存在于顺序表中
  34. }//顺序查找
  35.  
  36. status Search_Bin(SSTable ST,KeyType key,int &cnt)
  37. {
  38.     int low = 1;
  39.     int high = ST.length;
  40.     int mid;
  41.     if(high < 1) return OVERFLOW;                    //表空
  42.     while(low <= high)
  43.     {
  44.         mid = (low+high)/2;
  45.         cout << "经过元素：" << ST.R[mid].key << endl;
  46.         cnt ++;
  47.         if(key == ST.R[mid].key) return mid;        //找到待查元素
  48.         else if(key < ST.R[mid].key) high = mid-1;  //在前一子表进行查找
  49.         else low = mid+1;                           //在后一子表进行查找
  50.     }
  51.     return ERROR;                                   //key不存在于顺序表
  52. }//二分查找
  53.  
  54. status Bubble(SSTable &ST)
  55. {
  56.     int length = ST.length;
  57.     if(length < 1) return OVERFLOW;                 //表为空
  58.     for(int i = length-1;i > 0;i --)                //循环次数
  59.     {
  60.         for(int j = 1;j < i+1;j ++)
  61.         {
  62.             if(ST.R[j].key > ST.R[j+1].key)         //后一个值比前一个值小就交换
  63.             {
  64.                 KeyType temp = ST.R[j].key;
  65.                 ST.R[j].key = ST.R[j+1].key;
  66.                 ST.R[j+1].key = temp;
  67.             }
  68.         }
  69.     }
  70.     return OK;
  71. }//冒泡排序
  72.  
  73. status QuickSort(SSTable &ST,int left,int right)
  74. {
  75.     if(left >= right) return OK;
  76.     int begin = left;
  77.     int end = right;
  78.     int keyi = begin;
  79.     while(left < end)
  80.     {
  81.         while(begin < end && ST.R[end].key >= ST.R[keyi].key) end--;
  82.         while(begin < end && ST.R[begin].key <= ST.R[keyi].key) begin++;
  83.  
  84.         KeyType temp = ST.R[begin].key;
  85.         ST.R[begin].key = ST.R[end].key;
  86.         ST.R[end].key = temp;
  87.     }
  88.     KeyType temp = ST.R[begin].key;
  89.     ST.R[begin].key = ST.R[keyi].key;
  90.     ST.R[keyi].key = temp;
  91.  
  92.     QuickSort(ST,left,begin-1);
  93.     QuickSort(ST,begin+1,right);
  94. }//快速排序
  95.  
  96. void TraverseSST(SSTable ST)
  97. {
  98.     cout << "当前顺序表为：" << endl;
  99.     for(int i = 1;i < ST.length+1;i ++)
  100.     {
  101.         if(i%7 == 0) cout << endl;
  102.         cout << ST.R[i].key << "  ";
  103.     }
  104.     cout << endl;
  105. }//遍历顺序表
  106. //*************************************//
  107.  
  108. //*************************************//
  109. //二叉排序树的函数定义
  110. void CreateBST(BSTree &T)
  111. {
  112.     T = NULL;          //初始化为空树
  113.     ElemType e;
  114.     int numb[1000],i;
  115.     cout << "---请输入一组二叉排序树的整型元素(以-1作为结束标志)：" << endl;
  116.     for(i = 0;numb[i] != -1;i ++)
  117.     {
  118.         cin >> numb[i];
  119.         if(numb[i] == -1) break;
  120.         e.key = numb[i];
  121.         InsertBST(T,e);
  122.     }
  123. }//二叉排序树的创建
  124.  
  125. void InsertBST(BSTree &T,ElemType e)
  126. {
  127.     if(!T)
  128.     {
  129.         BSTNode *s = (BSTNode *)malloc(sizeof(BSTNode));
  130.         s->data.key = e.key;
  131.         s->lchild = s->rchild = NULL;
  132.         T = s;
  133.     }
  134.     else if(e.key < T->data.key) InsertBST(T->lchild,e);    //插入左子树
  135.     else if(e.key > T->data.key) InsertBST(T->rchild,e);    //插入右子树
  136. }//二叉排序树的插入
  137.  
  138. BSTree SearchBST(BSTree T,KeyType key,int &cnt)
  139. {
  140.     cnt ++;
  141.     if((T == NULL) || (T->lchild==NULL&&T->rchild==NULL&&T->data.key!=key) || key==T->data.key)
  142.     {
  143.         return T;//查找结束
  144.     }
  145.     else if(key < T->data.key)
  146.     {
  147.         cout << "经过元素：" << T->data.key << endl;
  148.         return SearchBST(T->lchild,key,cnt); //在左子树中继续查找
  149.     }
  150.     else
  151.     {
  152.         cout << "经过元素：" << T->data.key << endl;
  153.         return SearchBST(T->rchild,key,cnt); //在右子树中继续查找
  154.     }
  155. }//二叉排序树的递归查找
  156.  
  157. status TraverseBST(BSTree T)
  158. {
  159.     if(T == NULL) return OK;
  160.     else
  161.     {
  162.         TraverseBST(T->lchild);
  163.         cout << T->data.key << "  ";
  164.         TraverseBST(T->rchild);
  165.     }
  166. }//二叉排序树的中序遍历
  167.  
  168. //调用菜单
  169. void Menu()
  170. {
  171.     printf("\t\t\t********************此为最后一次数据结构实验的菜单***********************\n");
  172.     printf("\t\t\t\t1、顺序表                        2、 二叉排序树                       \n");
  173.     printf("\t\t\t\t0、退出当前操作系统                                                   \n");
  174.     printf("\t\t\t**********************************************************************\n");
  175. }//调用菜单的打印
  176.  
  177. void Menu_SL()
  178. {
  179.     printf("\t\t\t*************************此为顺序表的菜单*******************************\n");
  180.     printf("\t\t\t\t1、顺序表的创建                          2、顺序查找                   \n");
  181.     printf("\t\t\t\t3、冒泡排序                              4、快速排序                   \n");
  182.     printf("\t\t\t\t5、折半查找法                            6、遍历顺序表                 \n");
  183.     printf("\t\t\t\t0、退出当前操作系统                                                   \n");
  184.     printf("\t\t\t**********************************************************************\n");
  185. }//顺序表菜单的打印
  186.  
  187. void Menu_BST()
  188. {
  189.     printf("\t\t\t***********************此为二叉排序树的菜单*****************************\n");
  190.     printf("\t\t\t\t1、二叉排序树的建立                      2、二叉排序树的查找            \n");
  191.     printf("\t\t\t\t3、二叉排序树的插入                      4、二叉排序树的遍历            \n");
  192.     printf("\t\t\t\t0、退出当前操作系统                                                   \n");
  193.     printf("\t\t\t**********************************************************************\n");
  194. }//二叉排序树菜单的打印
  195.  
  196. //
  197. //Created by somewon on 2022/12/6.
  198. //

二、主调函数(main.cpp)

  1. #include <iostream>
  2. #include "before.h"
  3.  
  4. using namespace std;
  5.  
  6. int main()
  7. {
  8.     int CH;
  9.     do {
  10.         Menu();
  11.         cout << "---请输入进入的菜单：";
  12.         cin >> CH;
  13.         if(CH == 1)         //顺序表调用函数
  14.         {
  15.             int ch;
  16.             int numb;
  17.             int fine,cnt;
  18.             KeyType find;
  19.             SSTable ST;
  20.             do {
  21.                 Menu_SL();
  22.                 cout << "---请输入你的选择：";
  23.                 cin >> ch;
  24.                 switch(ch)
  25.                 {
  26.                     case 1:
  27.                         cout << "---请输入顺序表元素的个数：";
  28.                         cin >> numb;
  29.                         fine = CreateSST(ST,numb);
  30.                         if(fine == ERROR) cout << "当前顺序表空间分配失败！请再次进行操作！" << endl;
  31.                         else TraverseSST(ST);
  32.                         break;
  33.                     case 2:
  34.                         cout << "---请输入需要查找的元素：";
  35.                         cin >> find;
  36.                         cnt = 0;                     //查找次数
  37.                         fine = Search_Seq(ST,find,cnt);
  38.                         if(fine == 0)
  39.                         {
  40.                             cout << "该元素不在顺序表中！" << endl;
  41.                             cout << "查找次数为：" << cnt << endl;        //末尾开始查找
  42.                         }
  43.                         else
  44.                         {
  45.                             cout << "所查找的元素" << find << "的位置为：" << fine << endl;
  46.                             cout << "查找次数为：" << cnt << endl;        //末尾开始查找
  47.                         }
  48.                         break;
  49.                     case 3:
  50.                         fine = Bubble(ST);
  51.                         if(fine == OVERFLOW) cout << "当前顺序表为空！" << endl;
  52.                         else if(fine == OK)
  53.                         {
  54.                             cout << "冒泡排序成功！" << endl;
  55.                             TraverseSST(ST);
  56.                         }
  57.                         break;
  58.                     case 4:
  59.                         fine = QuickSort(ST,1,ST.length);
  60.                         if(fine == OK)
  61.                         {
  62.                             cout << "快速排序成功！" << endl;
  63.                             TraverseSST(ST);
  64.                         }
  65.                         break;
  66.                     case 5:
  67.                         cout << "---请输入需要查找的元素：";
  68.                         cin >> find;
  69.                         cnt = 0;
  70.                         fine = Search_Bin(ST,find,cnt);
  71.                         if(fine == ERROR)
  72.                         {
  73.                             cout << "该元素不在顺序表中！" << endl;
  74.                             cout << "查找的次数为：" << cnt << endl;
  75.                         }
  76.                         else if(fine == OVERFLOW) cout << "该表为空！" << endl;
  77.                         else
  78.                         {
  79.                             cout << "所查找的元素" << find << "的位置为：" << fine << endl;
  80.                             cout << "查找的次数为：" << cnt << endl;
  81.                         }
  82.                         break;
  83.                     case 6:
  84.                         TraverseSST(ST);
  85.                         break;
  86.                     case 0:
  87.                         goto END;
  88.                 }
  89.             }while(ch);
  90.         }
  91.         else if(CH == 2)    //二叉排序树调用函数
  92.         {
  93.             int ch;
  94.             BSTree T,s;
  95.             int cnt;
  96.             KeyType find;
  97.             ElemType e;
  98.             do {
  99.                 Menu_BST();
  100.                 cout << "---请输入你的选择：";
  101.                 cin >> ch;
  102.                 switch(ch)
  103.                 {
  104.                     case 1:
  105.                         CreateBST(T);
  106.                         cout << "二叉排序树建立完成！" << endl;
  107.                         TraverseBST(T);
  108.                         cout << endl;
  109.                         break;
  110.                     case 2:
  111.                         cout << "---请输入需要查询的整型数据：";
  112.                         cin >> find;
  113.                         cnt = 0;
  114.                         s = NULL;
  115.                         s = SearchBST(T,find,cnt);
  116.                         if(s == NULL || s->data.key!=find)
  117.                         {
  118.                             cout << "该元素不存在于二叉排序树中！" << endl;
  119.                             cout << "查找次数为：" << cnt << endl;
  120.                         }
  121.                         else
  122.                         {
  123.                             cout << "查找的元素" << find <<"存在于二叉排序树中！" << endl;
  124.                             cout << "查找次数为：" << cnt << endl;
  125.                         }
  126.                         break;
  127.                     case 3:
  128.                         cout << "---请输入需要插入的元素：";
  129.                         cin >> e.key;
  130.                         InsertBST(T,e);
  131.                         cout << "插入成功！" << endl;
  132.                         cout << "当前排序二叉树为：" << endl;
  133.                         TraverseBST(T);
  134.                         cout << endl;
  135.                         break;
  136.                     case 4:
  137.                         cout << "当前排序二叉树为：" << endl;
  138.                         TraverseBST(T);
  139.                         cout << endl;
  140.                         break;
  141.                     case 0:
  142.                         goto END;
  143.                 }
  144.             }while(ch);
  145.         }
  146.         else if(CH == 0) goto ENDD;
  147.         else cout << "无该选择！" << endl;
  148.         END:
  149.         cout << "已退出当前菜单！" << endl;
  150.     }while(CH);
  151.     ENDD:
  152.     cout << "已退出当前程序！" << endl;
  153.     return 0;
  154. }
  155. //
  156. //Created by somewon on 2022/12/6.
  157. //

三、头文件(before.h)

  1. #ifndef _BEFORE_H
  2. #define _BEFORE_H
  3.  
  4. #define OK 1
  5. #define ERROR 0
  6. #define OVERFLOW (-1)
  7.  
  8. typedef int status;
  9. typedef int KeyType;
  10. typedef int InfoType;
  11. typedef struct
  12. {
  13.     KeyType key;
  14.     InfoType otherinfo;
  15. }ElemType;
  16.  
  17. //顺序表相关函数声明
  18. typedef struct
  19. {
  20.     ElemType *R;
  21.     int length;
  22. }SSTable;
  23.  
  24. status CreateSST(SSTable &ST,int numb);           //创建顺序表
  25. status Search_Seq(SSTable ST,KeyType key,int &cnt);//顺序查找
  26. status Search_Bin(SSTable ST,KeyType key,int &cnt);//二分查找
  27. status Bubble(SSTable &ST);                       //冒泡排序
  28. status QuickSort(SSTable &ST,int left,int right); //快速排序
  29. void TraverseSST(SSTable ST);                     //遍历顺序表
  30.  
  31. //排序二叉树相关函数声明
  32. typedef struct BSTNode
  33. {
  34.     ElemType data;
  35.     struct BSTNode *lchild,*rchild;
  36. }BSTNode,*BSTree;
  37.  
  38. void CreateBST(BSTree &T);                        //二叉排序树的创建
  39. void InsertBST(BSTree &T,ElemType e);             //二叉排序树的插入
  40. BSTree SearchBST(BSTree T,KeyType key,int &cnt);  //二叉排序树的递归查找
  41. status TraverseBST(BSTree T);                     //二叉排序树的遍历
  42.  
  43. //相关菜单的函数声明
  44. void Menu();                                    //大菜单
  45. void Menu_SL();                                 //顺序表的菜单
  46. void Menu_BST();                                //二叉排序树的菜单
  47.  
  48. #endif
  49. //
  50. //Created by somewon on 2022/12/6.
  51. //

四、运行截图及功能函数部分展示

        1、顺序表

       （1）顺序表的创建

  1. status CreateSST(SSTable &ST,int numb)
  2. {
  3.     ST.R = (ElemType *)malloc(sizeof(ElemType)*(numb+1));
  4.     if(!ST.R) return ERROR;                     //空间分配失败
  5.     ST.length = numb;
  6.     cout << "---请输入" << numb << "个元素：" << endl;
  7.     for(int i = 1;i < numb+1;i ++) cin >> ST.R[i].key;
  8.     fflush(stdin);                        //清除缓存
  9.     return OK;                                 //创建成功
  10. }//创建顺序表

         （2）顺序查找法

  1. status Search_Seq(SSTable ST,KeyType key,int &cnt)
  2. {
  3.     ST.R[0].key = key;                             //监视哨
  4.     int i;
  5.     for(i = ST.length;i > 0;i --)                  //末尾开始查找
  6.     {
  7.         if(ST.R[i].key != key)
  8.         {
  9.             cnt ++;
  10.             cout << "经过的元素：" << ST.R[i].key << endl;
  11.         }
  12.         if(ST.R[i].key == key) break;
  13.     }
  14.     cnt ++;
  15.     return i;                                    //返回-1则不存在于顺序表中
  16. }//顺序查找

 

        （3）冒泡排序

  1. status Bubble(SSTable &ST)
  2. {
  3.     int length = ST.length;
  4.     if(length < 1) return OVERFLOW;                 //表为空
  5.     for(int i = length-1;i > 0;i --)                //循环次数
  6.     {
  7.         for(int j = 1;j < i+1;j ++)
  8.         {
  9.             if(ST.R[j].key > ST.R[j+1].key)         //后一个值比前一个值小就交换
  10.             {
  11.                 KeyType temp = ST.R[j].key;
  12.                 ST.R[j].key = ST.R[j+1].key;
  13.                 ST.R[j+1].key = temp;
  14.             }
  15.         }
  16.     }
  17.     return OK;
  18. }//冒泡排序

         （4）折半查找法

  1. status Search_Bin(SSTable ST,KeyType key,int &cnt)
  2. {
  3.     int low = 1;
  4.     int high = ST.length;
  5.     int mid;
  6.     if(high < 1) return OVERFLOW;                    //表空
  7.     while(low <= high)
  8.     {
  9.         mid = (low+high)/2;
  10.         cout << "经过元素：" << ST.R[mid].key << endl;
  11.         cnt ++;
  12.         if(key == ST.R[mid].key) return mid;        //找到待查元素
  13.         else if(key < ST.R[mid].key) high = mid-1;  //在前一子表进行查找
  14.         else low = mid+1;                           //在后一子表进行查找
  15.     }
  16.     return ERROR;                                   //key不存在于顺序表
  17. }//二分查找

        2、二叉排序树

        （1）二叉排序树的建立

  1. void CreateBST(BSTree &T)
  2. {
  3.     T = NULL;          //初始化为空树
  4.     ElemType e;
  5.     int numb[1000],i;
  6.     cout << "---请输入一组二叉排序树的整型元素(以-1作为结束标志)：" << endl;
  7.     for(i = 0;numb[i] != -1;i ++)
  8.     {
  9.         cin >> numb[i];
  10.         if(numb[i] == -1) break;
  11.         e.key = numb[i];
  12.         InsertBST(T,e);
  13.     }
  14. }//二叉排序树的创建

         （2）二叉排序树的插入

  1. void InsertBST(BSTree &T,ElemType e)
  2. {
  3.     if(!T)
  4.     {
  5.         BSTNode *s = (BSTNode *)malloc(sizeof(BSTNode));
  6.         s->data.key = e.key;
  7.         s->lchild = s->rchild = NULL;
  8.         T = s;
  9.     }
  10.     else if(e.key < T->data.key) InsertBST(T->lchild,e);    //插入左子树
  11.     else if(e.key > T->data.key) InsertBST(T->rchild,e);    //插入右子树
  12. }//二叉排序树的插入

 

         （3）二叉排序树的查找

  1. BSTree SearchBST(BSTree T,KeyType key,int &cnt)
  2. {
  3.     cnt ++;
  4.     if((T == NULL) || (T->lchild==NULL&&T->rchild==NULL&&T->data.key!=key) || key==T->data.key)
  5.     {
  6.         return T;//查找结束
  7.     }
  8.     else if(key < T->data.key)
  9.     {
  10.         cout << "经过元素：" << T->data.key << endl;
  11.         return SearchBST(T->lchild,key,cnt); //在左子树中继续查找
  12.     }
  13.     else
  14.     {
  15.         cout << "经过元素：" << T->data.key << endl;
  16.         return SearchBST(T->rchild,key,cnt); //在右子树中继续查找
  17.     }
  18. }//二叉排序树的递归查找

         

五、运行环境

        CLion、Dev（注：Dev中运行可能需要加上一些头文件，如：#include <stdlib.h>）

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

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

  

闽ICP备14008679号