1、顺序查找
#define MAXL 100
typedef int KeyType;
typedef char InfoType[10];
typedef struct {
KeyType key;
InfoType data;
}NodeType;
typedef NodeType SeqList[MAXL];
int SeqSearch(SeqList R,int n,KeyType k){
int i=0;
while(i<n&&R[i].key!=k){
printf("%d",R[i].key);
i++;
}
if(i>=n){
return -1;
}else{
printf("%d",R[i].key);
return i;
}
}
2、折半查找
int BinSearch(SeqList R,int n,KeyType k){
int low=0,high=n-1,mid,count=0;
while (low<=high) {
mid=(low+high)/2;
printf("%d:在[%d,%d]中查找到元素R[%d]:,%d\n",++count,low,high,mid,R[mid].key);
if(R[mid].key==k){
return mid;
}
if(R[mid].key>k){
high=mid-1;
}else{
low=mid+1;
}
}
return -1;
}
3、分块查找
typedef struct {
KeyType key;
int link;
}IdxType;
typedef IdxType IDX[MAXL];
int IdxSearch(IDX I,int m,SeqList R,int n,KeyType k){
int low=0,high=m-1,mid,i,count1=0,count2=0;
int b=n/m;
printf("二分查找\n");
while(low<=high){
mid=(low+high)/2;
printf("第%d次查找: 在[%d,%d]中查找到元素R[%d]: %d\n",count1+1,low,high,mid,R[mid].key);
if(I[mid].key>=k){
high=mid-1;
}else{
low=mid+1;
}
count1++;
}
if(low<m){
printf("比较%d次,在第%d块中查找元素 %d\n",count1,low,k);
i=I[low].link;
printf("顺序查找 :\n");
while(i<I[low].link+b-1&&R[i].key!=k){
i++;
count2++;
printf("%d ",R[i].key);
}
printf("\n");
printf("比较%d次,在顺序表中查找元素%d\n",count2,k);
if(i<=I[low].link+b-1){
return i;
}else{
return -1;
}
}
return -1;
}
//测试代码
int main (int argc, const char * argv[])
{
SeqList R;
KeyType k=46;
IDX I;
int a[]={8,14,6,9,10,22,34,18,19,31,
40,38,54,66,46,71,78,68,80,85,100,94,88,96,87},i;
for(i=0;i<25;i++){
R[i].key=a[i];
}
I[0].key=14;I[0].link=0;
I[1].key=34;I[1].link=4;
I[2].key=66;I[2].link=10;
I[3].key=85;I[3].link=15;
I[4].key=100;I[4].link=20;
printf("\n");
if((i=IdxSearch(I,5,R,25,k))!=-1){
printf("元素 %d的位置是%d\n",k,i);
}else{
printf("元素%d不在表中\n",k);
}
printf("\n");
return 0;
}
分享到:
相关推荐
实验目的或任务 通过指导学生上机实践,对常用数据结构的基本概念及其不同的实现方法的理论得到 进一步的掌握,并对在不同存储结构上实现不同的运算方式和技巧有所体会。 2. 实验教学基本要求 1.了解实验目的及实验...
数据结构实现顺序查找,折半查找,二叉排序树,哈希表实验原理。
数据结构查找 主要为顺序查找和折半查找的具采用c++语言实现
合肥工业大学数据结构 查找实验 编写算法实现下列问题的求解。 (1) 对下列数据表,分别采用二分查找算法实现查找,给出查找过程依次所比较的元素,并以二分查找的判定树来解释。 (2) 设计出在二叉排序树中插入结点的...
这是我在网上下载的。经过自己的修改得到的。希望对大家有帮助啊
折半查找是数据结构中,查找的其中一种。此资源不但包括折半查找的算法,还包括帮助其运行的其他代码,可直接运行以实现折半查找。注:输入数据时,要将数据从大到小依次输入,方可实现折半查找。
c语言实现数据结构折半查找
学数据结构写的东西--静态查找表的实现,希望对大家有点帮助!
数据结构作业 链表实现 构造 数值 插入 删除 查找 排序 的完美实现 这是可执行的文件 cpp格式 是用c语言编写的
该部分代码实现了数据结构课程查找一章几乎所有的算法,对学习数据结构查找算法的程序实现有很好的帮助
数据结构实验C语言实现散列表-构造-解决冲突-查找.pdf数据结构实验C语言实现散列表-构造-解决冲突-查找.pdf数据结构实验C语言实现散列表-构造-解决冲突-查找.pdf数据结构实验C语言实现散列表-构造-解决冲突-查找.pdf...
3种查找算法,顺序查找 折半查找 索引查找,c语言编写,可直接运行
主要包含冒泡 插入 选择 希尔 快速排序 堆排序 折半查找等常用的数据结构排序算法的实现
数据结构各种查找排序算法的实现 以及有关数据结构的试卷,习题 ,答案等
数据结构中的折半查找程序,C语言描述,数据结构中的折半查找程序,C语言描述
哈希查找数据结构实验报告.pdf
问题描述: 设计哈希表实现电话号码查找系统。 基本要求: (1)设每个记录有下列数据项:电话号码、用户名、地址; (2)从文件中读取各记录,分别以电话号码和用户名为关键字建立不同的哈希表; (3)采用链地址法...
1. 分别利用顺序查找和折半查找方法完成查找。 有序表(3,4,5,7,24,30,42,54,63,72,87,95) 输入示例: 请输入查找元素: 52 输出示例: 顺序查找: 第一次比较元素 95 第二次比较元素 87 …….. 查找成功, i=**/...
实验内容及要求:定义B-树存储结构(要求m3;为方便操作,结点中增加双亲结点指针域,最底层的Fail结点用NULL指针表示并且所有结点均存储于内存)。定义B-树插入关键字函数、删除关键字函数、查找关键字函数以及按...