数据结构：实验七：数据查找_(1)编写程序,利用顺序查找,从控制台给定的十个数据中查找一个数据是否存在。

一、    实验目的

（1）领会各种查找算法的过程和算法设计。

（2）掌握查找算法解决实际问题。

二、  实验要求

（1）编写一个程序exp8-1.cpp, 按提示输入10个任意的整形数据（无序），再输入一个待查找的数据，采用顺序查找方法，如果查找成功，返回该数据所在的位置（逻辑序号）。 如果查找不成功，给出一定的提示。

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

三、实验环境

Windows+DEV C++( 或者其他编译工具)

四、实验步骤及结果 

1.类型声明

（1）

顺序查找（无序）：

typedef int KeyType;//定义关键字类型为int
 
typedef char InfoType[10];
 
typedef struct {
 
   KeyType Key;//关键字项
 
   InfoType data;//其他数据项，类型为InfoType
 
} NodeType; //查找元素类型
 
typedef NodeType SeqList[MAXSIZE];

（2）

折半查找（递归）：

typedef int KeyType;//定义关键字类型为int
 
typedef char InfoType[10];
 
typedef struct {
 
   KeyType key;//关键字项
 
   InfoType data;//其他数据项，类型为InfoType
 
} NodeType; //查找元素类型
 
typedef NodeType SeqList[MAXL];//顺序表类型

2.各类查找算法的实现

（1）

顺序查找（无序）：

int Search(SeqList R,int n,KeyType k) {
 
   int i=0;
 
   while(i<n&&R[i].Key!=k) {
 
       i++;
 
   }
 
   if(i>=n)
 
       return -1;
 
   else
 
      
 
   return i;
 
}

（2）

折半查找（递归）：

int  BinSearch(SeqList R,KeyType k,int low,int high,int count)//折半查找算法(递归)
 
{
 
   int mid;
 
   if(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;
 
       else if(R[mid].key>k) //继续在R[low...mid-1]中查找
 
       BinSearch(R,k,low,mid-1,count);
 
       else
 
       BinSearch(R,k,mid+1,high,count);//继续在R[mid+1...high]中查找
 
   }
 
   else return -1;
 
}

3.主程序设计及完成实验要求中的功能

（1）

顺序查找（无序）：

int main() {
 
   SeqList R;
 
   int n=10;
 
   KeyType k = 9;
 
   printf("输入序列内容(十个不同整型数字):");
 
   int i;
 
   for(i=0;i<10;i++)
 
   {
 
       scanf("%d",&R[i].Key);
 
   }
 
    printf("序列为:");
 
    for(i=0;i<n;i++)
 
    {
 
        printf("%d,",R[i].Key);
 
    }
 
    printf("\n请输入需要查找的数字为:");
 
    scanf("%d",&k);
 
   printf("需要搜索的数字为%d",k);
 
   if((i =Search(R,n,k))!=-1)
 
       printf("\n%d在序列的第%d位置",k,i);
 
   else
 
       printf("\n元素%d不在序列中\n",k);
 
   printf("\n");
 
}

（2）

折半查找（递归）：

int main()
 
{
 
   SeqList R;
 
   int i;
 
   int n=10;
 
   KeyType k = 9;
 
   int a[]={1,2,3,4,5,6,7,8,9,10};
 
   for(i=0;i<n;i++)//建立顺序表
 
   R[i].key=a[i];
 
   printf("用递归方法:\n");
 
   if((i =BinSearch(R,k,0,9,0))!=-1)
 
       printf("元素%d的位置是%d\n",k,i);
 
   else
 
       printf("元素%d不在表中\n",k);
 
}

exp8-1:

#include <stdio.h>
#define MAXSIZE 100
typedef int KeyType;//定义关键字类型为int
typedef char InfoType[10];
typedef struct {
	KeyType Key;//关键字项
	InfoType data;//其他数据项，类型为InfoType
} NodeType; //查找元素类型
typedef NodeType SeqList[MAXSIZE];
int Search(SeqList R,int n,KeyType k) {
	int i=0;
	while(i<n&&R[i].Key!=k) {
		i++;
	}
	if(i>=n)
		return -1;
	else
		
	return i;
}
int main() {
	SeqList R;
	int n=10;
	KeyType k = 9;
	printf("输入序列内容(十个不同整型数字):");
	int i;
	for(i=0;i<10;i++)
   {
       scanf("%d",&R[i].Key);
   }
    printf("序列为:");
    for(i=0;i<n;i++)
    {
        printf("%d,",R[i].Key);
    }
    printf("\n请输入需要查找的数字为:");
    scanf("%d",&k);
   printf("需要搜索的数字为%d",k);
	if((i =Search(R,n,k))!=-1)
		printf("\n%d在序列的第%d位置",k,i);
	else
		printf("\n元素%d不在序列中\n",k);
	printf("\n");
}

exp8-2:

#include <stdio.h>
#define MAXL 100
typedef int KeyType;//定义关键字类型为int 
typedef char InfoType[10];
typedef struct {
	KeyType key;//关键字项
	InfoType data;//其他数据项，类型为InfoType
} NodeType; //查找元素类型
typedef NodeType SeqList[MAXL];//顺序表类型 
int  BinSearch(SeqList R,KeyType k,int low,int high,int count)//折半查找算法(递归)
{
	int mid; 
	if(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;
		else if(R[mid].key>k) //继续在R[low...mid-1]中查找
		BinSearch(R,k,low,mid-1,count); 
		else
		BinSearch(R,k,mid+1,high,count);//继续在R[mid+1...high]中查找
	}
	else return -1;
}
int main()
{
	SeqList R;
	int i;
	int n=10;
	KeyType k = 9;
	int a[]={1,2,3,4,5,6,7,8,9,10};
	for(i=0;i<n;i++)//建立顺序表
	R[i].key=a[i];
	printf("用递归方法:\n"); 
	if((i =BinSearch(R,k,0,9,0))!=-1)
		printf("元素%d的位置是%d\n",k,i);
	else
		printf("元素%d不在表中\n",k);
}

4.实验结果截图

（1）

顺序查找（无序）：

（2）

折半查找（递归）：

如需源文件，请私信作者，无偿