折半查找及其改进（算法与数据结构课程设计）

更新时间：2023-09-13 12:30:01 阅读量：教学研究文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

折半查找及其改进

一、问题描述

查找是在一个数据元素集合中查找关键字等于某个给个数据元素关键字的过程，也称为检索。给出一个特定的元素x，在含有n个元素的数列中判断是否存在这个元素，如果存在，返回此元素在数列中的位置，否则返回零。数列查找在实际中的应用十分广泛，因此数列查找算法的好坏直接影响到程序的优劣。本设计要求读取文件中的数据建立查找表,并设计算法实现折半查找及其改进查找。

二、基本要求

1、选择合适的存储结构，读取已知文件数据建立查找表； 2、完成基于递归和非逆归的折半查找算法的设计； 3、完成基于区间约束对折半查找算法的改进算法的设计； 4、完成三分查找算法的设计。

三、测试数据

文件in.txt中100个数据：1,2,3…98,99,100。 1、读取文件in.txt中前50位数，查找元素:58 2、读取文件in.txt中前50位数，查找元素:18 3、读取文件in.txt中前100位数，查找元素：18 4、读取文件in.txt中前100位数，待查元素：58

四、算法思想

1、折半查找的算法思想是以处于区间中间位置记录的关键字和给定值比较，若相等，则查找成功，如不等，则缩小范围，直至新的区间中间位置记录的关键字等于给定值或区间大小小于零时为止。

2、缩小区间查找算法的思想是先求出有序数列中每相邻两个元素之差的最大值的一个上界，设为m．要查找的数值为key，然后在每次循环做折半之前先进行一次筛选工作，即将low右移(key-a[low]/m)位，high值左移(a[high]-key)/m位，从而把尽可能多的不必要的元素过滤掉，缩小查找范围继续查找，直至新的区间中间位置记录的关键字等于给定值或区间大小小于零时为止。

3、三分查找的算法思想是在给出n个已经排好序的数，在n/3和2n/3处各取一个数，跟给定值key比较，确定待查数所在的范围, 直至新的区间中间位置记录的关键字等于给定值或区间大小小于零时为止。

五、模块划分

1、void read_dat(SSTable *ST,int n),读取文件in.dat中的数据并建立一个含文件in.dat中前n个数据的静态查找表ST。

wilyes11收集博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

2、void DestroyList(SSTable *ST) ,销毁表ST。

3、int SearchB1(SSTable ST, KeyType key),利用折半查找的非递归算法，查找关键字等于key的数据元素，若存在，返回该元素在表中的位置，否则为0。

4、SearchB2(SSTable ST,int key,int low,int high),利用折半查找的递归算法，查找关键字等于key的数据元素，若存在，返回该元素在表中的位置，否则为0。

5、SearchB3(SSTable ST, KeyType key),对折半查找算法的一种改进

6、SearchB4(SSTable ST, KeyType key ),利用三分查找法，查找关键字等于key的数据元素，若存在，返回该元素在表中的位置，否则为0。

7、void MainMenue(),主菜单。 8、main(),主函数。

六、数据结构

查找表类型定义如下： typedef int KeyType; typedef struct { KeyType key; /*其它域:略*/ } ElemType; typedef struct { ElemType *elem; int length; } SSTable;

七、源程序

/* 查找 */

#include \#include \

#define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)<(b)) #define LQ(a,b) ((a)<=(b))

/* 查找表类型定义 */ typedef int KeyType; typedef struct { KeyType key; /*其它域:略*/ } ElemType; typedef struct

{ ElemType *elem;

wilyes11收集博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

int length; } SSTable;

/*1.读取文件数据并建立查找表*/ void read_dat(SSTable *ST,int n) { int i; FILE *fp;

ST->elem=(ElemType*)malloc((n+1)*sizeof(ElemType)); ST->length=n;

fp = fopen(\ for (i=0; i<=n; i++)

fscanf(fp, \

printf(\ for(i=1; i<=n; i++)

printf(\ fclose(fp); }

/* 2.销毁查找表 */

void DestroyList(SSTable *ST) { free(ST->elem); }

void Destroy(SSTable *ST) { if (ST->elem)

{ free(ST->elem); ST->length=0;} }

/* 3.折半查找的非递归算法 */

int SearchB1(SSTable ST, KeyType key) { 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; }

/*4.折半查找的递归算法 */

int SearchB2(SSTable ST,int key,int low,int high) { int mid;

if(low>high) return 0; mid=(low+high)/2;

wilyes11收集博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

if (EQ(key,ST.elem[mid].key)) return mid;

else if (LT(key,ST.elem[mid].key))

return SearchB2(ST,key,low,mid-1); else

return SearchB2(ST,key,mid+1,high); }

/*5.对折半查找算法的一种改进*/ int MAX(SSTable ST) { int max,i; max=ST.elem[2].key-ST.elem[1].key;

for(i=2;i

return max;}

int SearchB3(SSTable ST, KeyType key) { int low,high,mid,l=0,h=0,m=MAX(ST); low=1;

high=ST.length;

while(low<=high&&l>=0&&h>=0) { l=(key-ST.elem[low].key)/m; h=(ST.elem[high].key-key)/m; 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; }

/*6.三分查找*/

int SearchB4(SSTable ST, KeyType key ) { int mid1,mid2,low=1,high=ST.length; if(ST.elem[low].key>key||ST.elem[high].key

if(EQ(key,ST.elem[mid1].key)) return mid1; else if(LT(key,ST.elem[mid1].key))

high=mid1-1;

else

{ if(EQ(key,ST.elem[mid2].key)) return mid2;

else if(LT(key,ST.elem[mid2].key)) {low=mid1+1;high=mid2-1;} else low=mid2+1; } }

wilyes11收集博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

return 0;

}

/*7.主菜单*/ void MainMenue() {

printf(\printf(\折半查找的非递归算法 **\\n\printf(\折半查找的递归算法 **\\n\printf(\对折半查找算法的一种改进 **\\n\printf(\三分查找 **\\n\printf(\printf(\}