当前位置：文档之家 › 实验六：折半查找

实验六：折半查找

  • 格式：doc
  • 大小：68.50 KB
  • 文档页数：4

《数据结构》实验报告六
实验内容： 折半查找
学号： 20105101132 姓名： 许丽敏
一、上机实验的问题和要求（需求分析）：
[ 题目 ] 设有关键字序列k={ 5 ,14 ,18 ,21 ,23 ,29 ,31 ,35 }。从键盘输入
上述8个整数，存放在数组bub[8]中，并进行遍历，输出其值。用折半查找的
方法分别查找21,25，输出查找结果。
二、程序设计的基本思想，原理和算法描述：
在有序（设为升序）表中，取中间元素作为比较对象，若给定值与中间元素的关
键字相等，则查找成功；若给定值小于中间元素的关键字，则在中间元素的左半
区继续查找；若给定值大于中间元素的关键字，则在中间元素的右半区继续查找。
不断重复上述查找过程，直到查找成功，或所查找的区域无该数据元素，查找失
败。

三、调试和运行程序过程中产生的问题及采取的措施：
1.表中SST.elem[i].key的使用
四、源程序及注释
[ 源程序 ] 程序名：实验六：折半查找.cpp
# include
# include

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

typedef int KeyType;
typedef struct ElemType
{
KeyType key;
}ElemType;
typedef struct SSTable
{
ElemType *elem;//数据元素存储空间基址，建表时按实际长度分配，0号单
元留空
int length;//表长度
}SSTable;
void Create_SSTable(SSTable &ST,int r[],int n)
{//操作结果：由含n个数据元素的数组r构造有序静态顺序查找表ST
int i;
ST.elem=(ElemType *)calloc(n+1,sizeof(ElemType));//动态生成n+1个数
据元素空间（0号单元不用）
if(!ST.elem)
exit(OVERFLOW);
for(i=1;i<=n;i++)
ST.elem[i].key=r[i-1];//将数组r的值依次赋给ST
ST.length=n;
}
void Traverse(SSTable ST)
{
int i;
for(i=1;i<=ST.length;i++)
printf("%4d",ST.elem[i]);
}

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;
}
//**************************以下是主函数**********************************
void main()
{
int N=8;
int i,k,m,bub[8];//键盘上输入的8个数将存放在bub[8]中
KeyType s;
SSTable ST;
printf("初始化数组元素为:\n");
printf("k=");
for(i=0;iscanf("%d",&bub[i]);
Create_SSTable(ST,bub,N);
printf("遍历结果是:\n");
Traverse(ST);
printf("\n");
for(m=0;m<2;m++)
{
printf("请输入要查找的数:\n");
scanf("%d",&s);
printf("操作结果是:\n");
i=Search_Bin(ST,s);
if(i)
printf("%d",i);
else
printf("没找到\n");
printf("\n");
}
}

五、运行结果

合集下载

数据结构-折半查找,哈希查找

数据结构-折半查找,哈希查找

一、实验目的熟练掌握顺序查找，折半查找和哈希表等算法的程序实现。

二、实验内容1、实现折半查找的算法编写一个程序，输出在顺序表（1,2,3,4,,6,7,8,9,10）中采用折半查找方法查找关键字9的过程要求：输出查找过程中的比较对象和被查找元素的位置。

2、实现哈希表的相关运算算法编写程序实现哈希表的构造过程。

要求：建立关键字序列（16,74,60,43,54,90,46,31,29,88,77）对应的哈希表A[0...12]，哈希函数为H（k）=k%p，并采用开放定址法中的线性探测法解决冲突。

输出构造完成后的哈希表。

程序源代码及运行结果（运行结果可以截图，也可以文字描述分析）1#include<stdio.h>#include<stdlib.h>int fun(int a[],int key){int high=9;int low=0;int mid=(high+low)/2;printf("与之相比较的值为:");while(high>=low){if(key==a[mid]){printf("%-2d",a[mid]);printf("\nkey为数组中第%d个元素\n",mid+1);break;}if(key<a[mid]){ printf("%-2d",a[mid]);high=mid-1;mid=(high+low)/2;}if(key>a[mid]){ printf("%-2d",a[mid]);low=mid+1;mid=(high+low)/2;}}}int main(){int a[10]={1,2,3,4,5,6,7,8,9,10};fun(a,9);system("pause");}运行截图：2#include<stdio.h>int main(){int a[11]={16,74,60,43,54,90,46,31,29,88,77};int A[13]={0};int p=11,H;for(int i=0;i<11;i++){H=a[i]%p;while(A[H]!=0){H++;if(H==12){H=0;}}A[H]=a[i];}for(int i=0;i<13;i++){if(A[i]!=0){printf("%d ",A[i]);}}}运行截图三、小结（不少于100字）感觉好像没有真正理解哈希表，折半查找比较好理解，实现起来也比较容易，自己对代码的熟练程度还不够，课后还会多多练习，查找的方式还有很多，课后应该多看书，对每种算法都有一定的了解。

顺序查找和折半查找

顺序查找和折半查找

注：正面实验题目、实验时间、姓名、学号和专业年级均不写实验目的及要求：了解和掌握静态查找表的查找过程；掌握顺序查找算法；掌握折半查找算法要求完成静态查找表的顺序查找和折半查找算法的实现。

实验设备环境及要求：PC机一台，内存要求128M以上，VC++6.0集成开发环境。

实验内容与步骤：1、在VC++6.0环境中新建一个工程和C++文件；2、实现静态查找表的顺序查找和折半查找算法，代码如下：#include <stdio.h>#include <malloc.h>typedef int KeyType;typedef struct{KeyType key;//InfoType data;}ElemType;typedef struct{ElemType *elem;int length;}SSTable;int Search_Sq(SSTable ST,KeyType key){ST.elem[0].key=key;for(int i=ST.length;ST.elem[i].key!=key;--i);return i;}int BinSearch(SSTable ST,KeyType key){int low,high,mid;low=1;high=ST.length;while(low<=high){mid=(low+high)/2;if(ST.elem[mid].key==key) return mid;else if(ST.elem[mid].key>key) high=mid-1;else low=mid+1;}return 0;}void main(){KeyType a[]={0,13,24,35,32,65,19,7,74,20,38};SSTable T;T.elem=(ElemType *)malloc(11*sizeof(ElemType));T.length=10;for(int i=1;i<=10;i++)T.elem[i].key=a[i];printf("要找的元素的位置为%d\n",Search_Sq(T,35));SSTable S;S.elem=(ElemType *)malloc(11*sizeof(ElemType));S.length=10;KeyType b[]={0,2,4,6,8,10,12,14,16,18,20};for(int k=1;k<=10;k++)S.elem[k].key=b[k];printf("要进行折半查找的元素的位置为%d\n",BinSearch(S,14));}实验指导与数据处理：实验结果：要找的元素的位置为3要进行折半查找的元素的位置为7分析讨论：本次实验通过对静态查找表的顺序查找和折半查找算法的实现，加深了对静态查找表查找过程的理解，并且熟悉了VC++6.0集成环境，虽然在调试过程中遇到一些问题，但经分析后达到了预期的结果。

折半查找

折半查找


定义数组a[11]ຫໍສະໝຸດ 找 key = 785 13 19 21 37 56 64 75 80 88 92
Low
Middle
High
key > a[Middle] 令 Low = Middle + 1
折半查找例2
定义数组a[11]
找 key = 78
5 13 19 21 37 56 64 75 80 88 92
折半查找 例1-找到的情况
定义数组a[11]
找 key = 21
在有序的数列中查找
5 13 19 21 37 56 64 75 80 88 92
Low
Middle
High
key < a[Middle]
折半查找例1
定义数组a[11]
找 key = 21
5 13 19 21 37 56 64 75 80 88 92
if (key==a[middle]) { index=middle;
break; } else if (key>a[middle]) low=middle+1; else high=middle-1; }
if (index!=-1) printf("Index: %d",index); else printf("Not found !");
Low Middle HighMiddle
High
key > a[Middle]
折半查找例1
定义数组a[11]
找 key = 21
5 13 19 21 37 56 64 75 80 88 92
Low MidLdolew High Middle
key = a[Middle] 找到
折半查找算法及分析（手工过程）

折半查找算法及分析（手工过程）

折半查找算法及分析（⼿⼯过程）折半查找的⼿⼯过程：1.我需要查找的数是10；给定：1 5 8 10 13 14 17 22 25 27 29 31 35 37 40 42 45 47 50 51 58下标：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 h m t h m t h m t h t m h m这个⼿⼯过程到head = tail 时找到了。

我需要查找的数是29；给定：1 5 8 10 13 14 17 22 25 27 29 31 35 37 40 42 45 47 50 51 58下标：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 h m t这个⼿⼯过程数在head < tail时程序停⽌，找到的是下标的那个数。

代码如下：#include<stdio.h>#include<stdlib.h>int binarySearch(int *arr,int count ,int data){int middle;int head = 0;int tail;tail = count;while(arr[middle] != data){middle = (head + tail)/ 2;if(arr[middle] < data){head = middle + 1;}else if(arr[middle] > data){tail = middle - 1;}}return middle;return -1;}int main(){int n = 0;int m ;int a[10]={1,4,8,9,16,17,19,20,25,27};printf("请输⼊需要查找的数: ");scanf("%d",&n);m = binarySearch(a,10,n);printf("%d ",m);return 0;}这是⼀个简单的折半处理，⽤的是⼀个简单的数组需要强调的是： 如果要运⽤折半算法，数必须是有序的（升序或者降序） 很多⼈都认为while（head > tail）这样也是正确的，但是对于middle = data时条件⼀直成⽴就会出现问题的！。