线性表的查找算法-C语言

文章目录

一、实验目的
二、实验内容
三、实验工具
四、实验代码
五、实验结果
六、总结与思考

一、实验目的

了解查找的基本概念，理解顺序查找、折半查找和分块查找的思想，掌握折半查找过程的判定树构造方法，实现线性表的查找算法。

二、实验内容

通过编写程序，实现线性表的查找算法。具体步骤如下：

在主函数中输入线性序列和关键字；
创建实现顺序查找和折半查找的子函数；
在主函数中通过switch语句选择调用相关函数实现查找。

三、实验工具

Dev - C++

四、实验代码

//Authors:xiaobei

//线性表的查找方法：顺序查找、二分查找
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 10
#define OK 1;
//定义线性表数据项结构
typedef struct{
 int key;//关键字域
}ElemType;
//定义线性表结构
typedef struct{
 ElemType *R;
 int length;
}SSTable;
//初始化线性表
int InitList_SSTable(SSTable &L){
 L.R=(ElemType*)malloc(sizeof(ElemType)*MAXSIZE);
 if (!L.R){
  printf("初始化错误！");
  return 0;
 }
 L.length=0;
 return OK;
}
//函数赋值线性表
int Insert_SSTable(SSTable &L){
 int i,num;           //空出ST.R[0]的位置
 for(i=1;i<MAXSIZE;i++){
  printf("
【请依次输入关键字的值】
>>>");
  getchar();
  scanf("%d",&num);
  L.R[i].key=num;
  L.length++;
 }
 return OK;
}
//函数顺序查找线性表
int Search_Seq(SSTable ST, int key){
//在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为
//该元素在表中的位置，否则为0
 int i;
    ST.R[0].key = key;                            //“哨兵”
    for(i = ST.length; ST.R[i].key!=key; --i);   //从后往前找
    return i;                                         
}// Search_Seq
//函数折半查找线性表（非递归）
int Search_Bin(SSTable ST,int key){
   // 在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为
   // 该元素在表中的位置，否则为0
   int low=1,high=ST.length;       //置查找区间初值
   int  mid;
   while(low<=high) {
    mid=(low+high) / 2;
      if (key==ST.R[mid].key)
    return mid;              //找到待查元素
      else if(key<ST.R[mid].key)
    high = mid -1;        //继续在前一子表进行查找
      else  
    low =mid +1;                          //继续在后一子表进行查找
   }//while
   return 0;           //表中不存在待查元素
}// Search_Bin
//函数折半查找线性表（递归）
int Search_Bin2(SSTable ST,int key,int low,int high){
 int mid = (low+high) / 2;       //向下去整
 if (key==ST.R[mid].key)
  return mid;              //找到待查元素
      else if(key<ST.R[mid].key)
    Search_Bin2(ST,key,low,mid-1);     //继续在前一子表进行查找
      else
    Search_Bin2(ST,key,mid+1,high);
}
//函数显示顺序表查找结果
void Show_End(int result,int key){
 if(result==0)
  printf("
未找到%d
",key);
 else
  printf("
找到%d,位置为%d
",key,result);
 return;
}
//函数打印菜单
void Menu(){
 printf("
************菜单***********
");
 printf("
1.创建线性表;
");
 printf("
2.顺序查找;
");
 printf("
3.折半查找(非递归);
");
 printf("
4.折半查找(递归);
");
 printf("
0.退出;
");
 printf("
***************************
");
 printf("
【请输入你的选择】
>>>");
}
//主函数
int main(){
 SSTable ST;
 int key,result,user;
 while (true)
 {
  Menu();
  scanf("%d",&user);
  switch(user){
  case 1:{
   if(InitList_SSTable(ST) && Insert_SSTable(ST))
    printf("
【创建成功……】
");
   break;
  }
  case 2:{
   printf("
-----------顺序查找-----------
");
   printf("
【请输入要查找的关键字】
>>>");
   getchar();
   scanf("%d",&key);
   result = Search_Seq(ST,key);
   Show_End(result,key);
   printf("
-------------------------------
");
   break;
  }
  case 3:{
   printf("
-----------折半查找(非递归)-----------
");
   printf("
【请输入要查找的关键字】
>>>");
   getchar();
   scanf("%d",&key);
   result = Search_Bin(ST,key);
   Show_End(result,key);
   printf("
---------------------------------------
");
   break;
  }
  case 4:{
   printf("
-----------折半查找(递归)-----------
");
   printf("
【请输入要查找的关键字】
>>>");
   getchar();
   scanf("%d",&key);
   result = Search_Bin2(ST,key,1,ST.length);
   Show_End(result,key);
   printf("
-------------------------------------
");
   break;
  }
  case 0:exit(0);
  }
 }
 return 0;
}