本文主要是介绍顺序表查找和折半查找,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
#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");
}
这篇关于顺序表查找和折半查找的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!