查找算法的实现（C语言版）

实验五 查找的实现

一、 实验目的

1．通过实验掌握查找的基本概念；

2．掌握顺序查找算法与实现；

3．掌握折半查找算法与实现。

二、 实验要求

1． 认真阅读和掌握本实验的参考程序。

2． 保存程序的运行结果，并结合程序进行分析。

三、 实验内容

1、建立一个线性表，对表中数据元素存放的先后次序没有任何要求。输入待查数据元素的关键字进行查找。为了简化算法，数据元素只含一个整型关键字字段，数据元素的其余数据部分忽略不考虑。建议采用前哨的作用，以提高查找效率。

2、查找表的存储结构为有序表，输入待查数据元素的关键字利用折半查找方法进行查找。此程序中要求对整型量关键字数据的输入按从小到大排序输入。

一、顺序查找

顺序查找代码：

#include"stdio.h"

#include"stdlib.h"

typedef struct node{

int key;

}keynode;

typedef struct Node{

keynode r[50];

int length;

}list,*sqlist;

int Createsqlist(sqlist s)

{

int i;

printf("请输入您要输入的数据的个数:\n");

scanf("%d",&(s->length));

printf("请输入您想输入的%d个数据;\n\n",s->length);

for(i=0;ilength;i++)

scanf("%d",&(s->r[i].key));

printf("\n");

printf("您所输入的数据为:\n\n");

for(i=0;ilength;i++)

printf("%-5d",s->r[i].key);

printf("\n\n");

return 1;

}

int searchsqlist(sqlist s,int k)

{

int i=0;

s->r[s->length].key=k;

while(s->r[i].key!=k)

{

i++;

}

if(i==s->length)

{

printf("该表中没有您要查找的数据！\n");

return -1;

}

else

return i+1;

}

sqlist Initlist(void)

{

sqlist p;

p=(sqlist)malloc(sizeof(list));

if(p)

return p;

else

return NULL;

}

main()

{

int keyplace,keynum;//

sqlist T;//

T=Initlist();

Createsqlist(T);

printf("请输入您想要查找的数据的关键字:\n\n");

scanf("%d",&keynum);

printf("\n");

keyplace=searchsqlist(T,keynum);

printf("您要查找的数据的位置为:\n\n%d\n\n",keyplace);

return 2;

}

顺序查找的运行结果：

二、折半查找

折半查找代码：

#include"stdio.h"

#include"stdlib.h"

typedef struct node{

int key;

}keynode;

typedef struct Node{

keynode r[50];

int length;

}list,*sqlist;

int Createsqlist(sqlist s)

{

int i;

printf("请输入您要输入的数据的个数:\n");

scanf("%d",&(s->length));

printf("请由大到小输入%d个您想输入的个数据;\n\n",s->length);

for(i=0;ilength;i++)

scanf("%d",&(s->r[i].key));

printf("\n");

printf("您所输入的数据为:\n\n");

for(i=0;ilength;i++)

printf("%-5d",s->r[i].key);

printf("\n\n");

return 1;

}

int searchsqlist(sqlist s,int k)

{

int low,mid,high;

low=0;

high=s->length-1;

while(low<=high)

{

mid=(low+high)/2;

if(s->r[mid].key==k)

return mid+1;

else if(s->r[mid].key>k)

high=mid-1;

else

low=mid+1;

}

printf("该表中没有您要查找的数据!\n");

return -1;

}

sqlist Initlist(void)

{

sqlist p;

p=(sqlist)malloc(sizeof(list));

if(p)

return p;

else

return NULL;

}

main()

{

int keyplace,keynum;//

sqlist T;//

T=Initlist();

Createsqlist(T);

printf("请输入您想要查找的数据的关键字:\n\n");

scanf("%d",&keynum);

printf("\n");

keyplace=searchsqlist(T,keynum);

printf("您要查找的数据的位置为:\n\n%d\n\n",keyplace);

return 2;

}

折半查找运行结果：

三、实验总结：

该实验使用了两种查找数据的方法（顺序查找和折半查找），这两种方法的不同之处在于查找方式和过程不同，线性表的创建完全相同，程序较短，结果也一目了然。

本文来源：https://www.2haoxitong.net/k/doc/1da6314af7ec4afe04a1df6c.html