数据结构：实验七：数据查找

一、 实验目的

（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）

顺序查找（无序）：