顺序表查找和折半查找

2024-05-28 14:32

文章标签 查找顺序折半

本文主要是介绍顺序表查找和折半查找，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <memory.h>  //包含memsetd的函数//对两个数值型关键字的比较约定如下：
#define EQ(a,b)   ((a) == (b))
#define LT(a,b)   ((a) < (b)) 
#define LQ(a,b)   ((a) <= (b))#define OK 1;
#define KeyType int
//#define ElemType inttypedef struct KeyTable
{KeyType key;  //关键字字域
}ElemType;struct SSTable
{ElemType *elem; //数据元素存储空间基址，建表时按实际长度分配，0号单元留空int length;   int cnt; //有效元素的个数
};void Init_arr(SSTable *ST,ElemType *arr,int n);
void Creat_Seq(SSTable *ST,ElemType *arr,int n);  //给数组赋值
void Ascend(SSTable *ST);  //重建静态查找表，排序 升序
void Creat_Ord(SSTable *ST, ElemType *arr,int n);
int Destroy(SSTable *ST);
int Search_Seq(SSTable *ST,KeyType key);
int Search_Bin(SSTable *ST,KeyType key); //折半查找
void Traverse(SSTable *ST);int main(void)
{int seq,bin;struct SSTable pSSTable;ElemType r[6] = {4,2,1,3,6,5};Init_arr(&pSSTable,r,6);Creat_Seq(&pSSTable,r,6);Traverse(&pSSTable);Ascend(&pSSTable);printf("排序后的元素为：\n");Traverse(&pSSTable);seq = Search_Seq(&pSSTable,3);printf("顺序查找元素的下标为：%d\n",seq);bin = Search_Bin(&pSSTable,8);printf("折半查找元素的小标为：%d\n",bin);return 0;
}void Init_arr(SSTable *ST,ElemType *arr,int n)
{ST->elem = (ElemType *)calloc(n+1,sizeof(ElemType));if(NULL == ST->elem){printf("动态内存分配失败!\n");exit(-1);}else{memset(ST->elem,0,n+1);//初始化分配的内存区域，初始化为0ST->length = n+1; //整个数组的长度ST->cnt = 0;/*  for(int i=0 ; i<n ; i++)*  {*      ST->elem[i+1] = arr[i];*      (ST->cnt)++;*  } */}
}void Creat_Seq(SSTable *ST,ElemType *arr,int n)  //给数组赋值
{int i;for(i=0 ,ST->cnt = 0 ; i<n ; i++){ST->elem[i+1] = arr[i];(ST->cnt)++;}   
}void Ascend(SSTable *ST)
{int i,j;for(i=1 ; i<ST->cnt ; i++){ST->elem[0] = ST->elem[i];  //待比较值存[0]单元for(j=i+1 ; j<=ST->cnt ; j++){if(ST->elem[i].key > ST->elem[j].key){ST->elem[0] = ST->elem[j];ST->elem[j] = ST->elem[i];ST->elem[i] = ST->elem[0];}}}
}int Destroy(SSTable *ST)
{free(ST->elem);ST->elem = NULL;ST->length = 0;ST->cnt = 0;return OK;
}int Search_Seq(SSTable *ST,KeyType key)
{int i;ST->elem[0].key = key; //哨兵for(i=ST->cnt ; key != (ST->elem[i].key) ; --i); //从前往后找return i; //找不到i=0
}int Search_Bin(SSTable *ST,KeyType key) //折半查找
{int low,high,mid;low = 1;high = ST->cnt;while(low <= high){mid = (low + high)/2;if(key == ST->elem[mid].key)return mid;  //返回查找元素的下标else if(key < (ST->elem[mid].key))high = mid -1;elselow = mid + 1;}return 0; //查找失败返回0
}void Traverse(SSTable *ST)
{int i;ElemType *p = ST->elem;for(i = 1;i <= ST->cnt ;i++)printf("  %d",p[i].key);printf("\n");
}