二分查找.txt

数据结构二分查找。。。。。。原代码数据结构课程

#include<iostream>
using namespace std;

#define OK 1
#define ERROR -1
 #define N 11 /* 数据元素个数 */
 #define EQ(a,b) ((a)==(b))
 #define LT(a,b) ((a)<(b))
 #define LQ(a,b) ((a)<=(b))
 typedef int KeyType; /* 设关键字域为整型 */
 typedef int Status;
 typedef struct /* 数据元素类型 */
 {
   KeyType key; /* 关键字域 */
   int others; /* 其它部分 */
 }ElemType;
 ElemType r[N]={{5,1},{13,2},{19,3},{21,4},{37,5},{56,6},{64,7},{75,8},
		{80,9},{88,10},{92,11}}; /* 数据元素(以教科书P.219的数据为例),全局变量 */

 typedef struct
 {
   ElemType *elem; /* 数据元素存储空间基址，建表时按实际长度分配，0号单元留空 */
   int length; /* 表长度 */
 }SSTable;


 void print(ElemType c) /* Traverse()调用的函数 */
 {
   printf("(%d %d) ",c.key,c.others);
 }

 Status Creat_Seq(SSTable *ST,int n)
 { /* 操作结果: 构造一个含n个数据元素的静态顺序查找表ST(数据来自全局数组r) */
   int i;
   (*ST).elem=(ElemType *)calloc(n+1,sizeof(ElemType)); /* 动态生成n个数据元素空间(0号单元不用) */
   if(!(*ST).elem)
     return ERROR;
   for(i=1;i<=n;i++)
     *((*ST).elem+i)=r[i-1]; /* 将全局数组r的值依次赋给ST */
   (*ST).length=n;
   return OK;
 }




 int Search_Bin(SSTable ST,KeyType key)
 { /* 在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为 */
   /* 该元素在表中的位置，否则为0*/
   int low,high,mid;
   low=1; /* 置区间初值 */
   high=ST.length;
   while(low<=high)
   {
     mid=(low+high)/2;
     if EQ(key,ST.elem[mid].key)  /* 找到待查元素 */
       return mid;
     else if LT(key,ST.elem[mid].key)
       high=mid-1; /* 继续在前半区间进行查找 */
     else
       low=mid+1; /* 继续在后半区间进行查找 */
   }
   return 0; /* 顺序表中不存在待查元素 */
 }

 Status Traverse(SSTable ST,void(*Visit)(ElemType))
 { /* 初始条件: 静态查找表ST存在，Visit()是对元素操作的应用函数 */
   /* 操作结果: 按顺序对ST的每个元素调用函数Visit()一次且仅一次。 */
   /* 一旦Visit()失败，则操作失败 */
   ElemType *p;
   int i;
   p=++ST.elem; /* p指向第一个元素 */
   for(i=1;i<=ST.length;i++)
     Visit(*p++);
   return OK;
 }

Status Destroy(SSTable *ST)
 { /* 初始条件: 静态查找表ST存在。操作结果: 销毁表ST */
   free((*ST).elem);
   (*ST).elem=NULL;
   (*ST).length=0;
   return OK;
 }

 void main()
 {
   SSTable st;
   int i;
   KeyType s;
   Creat_Seq(&st,N); /* 由全局数组产生非降序静态查找表st */
   Traverse(st,print); /* 顺序输出非降序静态查找表st */
   printf("\n");
   printf("请输入待查找值的关键字: ");
   scanf("%d",&s);
   i=Search_Bin(st,s); /* 折半查找有序表 */
   if(i)
     printf("(%d %d) %d是第%d个记录的关键字\n",st.elem[i].key,st.elem[i].others,s,i);
   else
     printf("没找到\n");
   Destroy(&st);
 }