16
2019
12

顺序和二分法查找 (C C++)

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
int cnt=0;//定于总共有多少个成员 
typedef int KeyType;	//关键字类型为int型 
typedef struct{
	KeyType key;	//存放关键字,KeyType为关键字类型 
}SearchL;

void get_num(SearchL i[])//获取数组成员数 
{
	int point=1;
	while(i[point++].key!=0)
	cnt++;
}

int SeqSearch(SearchL i[])
{
	printf("请输入要查找的数:");
	scanf("%d",&i[0].key);
	int point=0,count=1;//定义指针
	while(i[point++].key!=0)
	{
		if(i[point].key==i[0].key){
		printf("数字的位置为%d,查找的次数为%d\n",point,count);
		return 0;
		}
		count++;
	 } 
	 printf("元素不存在!");
	 return 0;
}

int Bin_Search(SearchL i[])
{
	printf("请输入要查找的数:");
	scanf("%d",&i[0].key);
	int first = 1,last = cnt-1,mid;
	int counter = 0;
	while(first <= last)
	{
		counter ++;
		mid = (first + last) / 2;//确定中间元素	
		if(i[mid].key > i[0].key)
		{
			last = mid-1; //mid已经交换过了,last往前移一位
		}
		else if(i[mid].key < i[0].key)
		{
			first = mid+1;//mid已经交换过了,first往后移一位
		}	
		else //判断是否相等
		{
			printf("数字的位置为%d,查找的次数为%d\n",mid,counter);
			return 1;
		}
	}
	printf("数字的位置为%d,查找的次数为%d\n",mid,counter);
	return 0;
}

/*
(2)对结构体数组元素进行初始化为值为{2,4,6,8,10,12,14,16,18,20};
(3)编写设置监视哨的顺序查找算法,在数组中查找值为8的元素,输出该元素的位置和查找次数;
(4)编写设置监视哨的顺序查找算法,在数组中查找值为7的元素,如果不存在,给出结论"元素不存在";
(5)编写二分查找算法,在数组中查找值为12的元素,输出其位置,并输出每次查找的过程(例如:第一次查找到的元素是?,第二次查找到的元素是?,……)。
注:输出元素位置时,假设数组中第一个元素的位置输出为1
*/

void SearchMenu()
{
	    printf("         查找子系统");
		printf("\n==========================");
		printf("\n|     1--顺序查找         |");
		printf("\n|     2--二分查找         |");
		printf("\n|     0--返回             |");
		printf("\n==========================");	
		printf("\n请输入菜单号(0-2):");
}

main(){
	char choice;
	/*初始化数组*/ 
	SearchL r[MAXSIZE]={0};//初始化数组,并令所有元素为0 
	int a[]={2,4,6,8,10,12,14,16,18,20};int i=0,n=10;
	for(i=0; i<n; i++)	{
		r[i+1].key = a[i];
	}
	get_num(r);
	/*<-END初始化数组*/             
	while(1){
		SearchMenu();
		scanf("%c",&choice);
		getchar();
		switch(choice){
			case '1':
				SeqSearch(r);
				break;
				
			case '2':
				Bin_Search(r) ;
				break;
				
			case '0':
				exit(1);
			default:
				printf("输入有误,请重新输入!\n");
		}
		if(choice != '0'){
			printf("按回车继续,按任意键返回主菜单!\n");
			if(getchar() != '\xA'){
				getchar();
				exit(1);
			}
		}

	}
}
#include<iostream>
#include<stdlib.h>
#define MAXSIZE 100
using namespace std;
int cnt=0;//定于总共有多少个成员 
typedef int KeyType;	//关键字类型为int型 
typedef struct{
	KeyType key;	//存放关键字,KeyType为关键字类型 
}SearchL;

void get_num(SearchL i[])//获取数组成员数 
{
	int point=1;
	while(i[point++].key!=0)
	cnt++;
}

int SeqSearch(SearchL i[])
{
	cout<<"请输入要查找的数:";
	cin>>i[0].key;
	int point=0,count=1;//定义指针
	while(i[point++].key!=0)
	{
		if(i[point].key==i[0].key){
		cout<<"数字的位置为"<<point<<",查找的次数为"<<count<<"\n";
		return 0;
		}
		count++;
	 } 
	 cout<<"元素不存在!\n";
	 return 0;
}

int Bin_Search(SearchL i[])
{
	cout<<"请输入要查找的数:";
	cin>>i[0].key;
	int first = 1,last = cnt-1,mid;
	int counter = 0;
	while(first <= last)
	{
		counter ++;
		mid = (first + last) / 2;//确定中间元素	
		if(i[mid].key > i[0].key)
		{
			last = mid-1; //mid已经交换过了,last往前移一位
		}
		else if(i[mid].key < i[0].key)
		{
			first = mid+1;//mid已经交换过了,first往后移一位
		}	
		else //判断是否相等
		{
			cout<<"数字的位置为"<<mid<<",查找的次数为"<<counter<<"\n";
			return 1;
		}
	}
	cout<<"数字的位置为"<<mid<<",查找的次数为"<<counter<<"\n";
	return 0;
}

/*
(2)对结构体数组元素进行初始化为值为{2,4,6,8,10,12,14,16,18,20};
(3)编写设置监视哨的顺序查找算法,在数组中查找值为8的元素,输出该元素的位置和查找次数;
(4)编写设置监视哨的顺序查找算法,在数组中查找值为7的元素,如果不存在,给出结论"元素不存在";
(5)编写二分查找算法,在数组中查找值为12的元素,输出其位置,并输出每次查找的过程(例如:第一次查找到的元素是?,第二次查找到的元素是?,……)。
注:输出元素位置时,假设数组中第一个元素的位置输出为1
*/

void SearchMenu()
{
	    cout<<"         查找子系统";
		cout<<"\n==========================";
		cout<<"\n|     1--顺序查找         |";
		cout<<"\n|     2--二分查找         |";
		cout<<"\n|     0--返回             |";
		cout<<"\n==========================";	
		cout<<"\n请输入菜单号(0-2):";
}

main(){
	char choice;
	/*初始化数组*/ 
	SearchL r[MAXSIZE]={0};//初始化数组,并令所有元素为0 
	int a[]={2,4,6,8,10,12,14,16,18,20};int i=0,n=10;
	for(i=0; i<n; i++)	{
		r[i+1].key = a[i];
	}
	get_num(r);
	/*<-END初始化数组*/             
	while(1){
		SearchMenu();
		cin>>choice;
		getchar();
		switch(choice){
			case '1':
				SeqSearch(r);
				break;
				
			case '2':
				Bin_Search(r) ;
				break;
				
			case '0':
				exit(1);
			default:
				cout<<"输入有误,请重新输入!\n";
		}
		if(choice != '0'){
			cout<<"按回车继续,按任意键返回主菜单!\n";
			if(getchar() != '\xA'){
				getchar();
				exit(1);
			}
		}

	}
}


« 上一篇 下一篇 »

返回顶部
请先 登录 再评论,若不是会员请先 注册