查找算法的数据结构及实现

一、目的

1. 掌握顺序查找算法的实现过程
2. 熟悉折半查找算法的原理及实现

二、内容

1. 实现顺序查找的算法
   编写一个程序exp9-1.cpp，输出在顺序表（3，6，2，10，1，8，5，7，4，9）中采用顺序查找方法查找关键字5的过程。
2. 实现折半查找的算法
   编写一个程序exp9-2.cpp，输出在顺序表（1，2，3，4，5，6，7，8，9，10）中采用折半查找方法查找关键字9的过程。

三、源代码

1. 实现顺序查找的算法

#include<stdio.h>
#define MAXL 100
typedef int KeyType;
typedef char InfoType;
typedef struct
{
	KeyType key;
	InfoType data;
}RecType;
void CreateList(RecType R[],KeyType keys[],int n)
{
	for(int i=0;i<n;i++)
		R[i].key=keys[i];
}
void DispList(RecType R[],int n)
{
	for(int i=0;i<n;i++)
		printf("%d",R[i].key);
	printf("n");
}
int SeqSearch(RecType 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 0;
	else
	{
		printf("%d",R[i].key);
		return i+1;
	}
}
int main()
{
	RecType R[MAXL];
	int n=10,i;
	KeyType k=5;
	int a[]={3,6,2,10,1,8,5,7,4,9};
	CreateList(R,a,n);
	printf("关键字序列：");DispList(R,n);
	printf("查找%d所比较的关键字：nt",k);
	if((i=SeqSearch(R,n,k))!=0)
		printf("n元素%d的位置是%dn",k,i);
	else
		printf("n元素%d不在表中n",k);
	return 1;
}

2. 实现折半查找的算法

#include<stdio.h>
#define MAXL 100
typedef int KeyType;
typedef char InfoType;
typedef struct
{
	KeyType key;
	InfoType data;
}RecType;
void CreateList(RecType R[],KeyType keys[],int n)
{
	for(int i=0;i<n;i++)
		R[i].key=keys[i];
}
void DispList(RecType R[],int n)
{
	for(int i=0;i<n;i++)
		printf("%d",R[i].key);
	printf("n");
}


int BinSearch(RecType 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]:%dn",++count,low,high,mid,R[mid].key);
		if(R[mid].key==k)
			return mid+1;
		if(R[mid].key>k)
			high=mid-1;
		else
			low=mid+1;
	}
	return 0;
}
int main()
{
	RecType R[MAXL];
	KeyType k=9;
	int a[]={1,2,3,4,5,6,7,8,9,10},i,n=10;
	CreateList(R,a,n);
	printf("关键字序列：");DispList(R,n);
	printf("查找%d的比较过程如下：n",k);
	if((i=BinSearch(R,n,k))!=-1)
		printf("元素%d的位置是%dn",k,i);
	else
		printf("元素%d不在表中n",k);
	return 0;
}

备注：
有问题可以评论，看到后我会尽力及时回复的，谢谢！

最后

以上就是昏睡自行车为你收集整理的查找算法的数据结构及实现的全部内容，希望文章能够帮你解决查找算法的数据结构及实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。