main.cpp

数据结构中的人、二分查早问题

//File : main.cpp
//Designer : Ma Zhejiang  (from the class KT323-1)
//Data :  3/11/2005
//Subject:二分查找方法

#include "iostream.h"

template <class Type>
int Find(Type * pDatas,int nCount,Type & Data)
//Find a item Data from a group datas pointed by the pointer pDatas.
//从一组被指针 pDatas 指向的数据中查找某个数据
//The group datas must be ordinal from small to big.
//这组数据必须是有序的
//The nCount means how many items exist in the group datas.
//nCount 是这组数据的个数
//If the group datas exit the item, return the number of its order,
//or give a integer zero
//如果这组数据中存在数据data，函数就返回这个数的序数，
//否则就返回零值
{
   int small=0,big=nCount-1;
   int mid=(big+small)/2;
   while(big>=small)
   {   
	  if(*(pDatas+mid)==Data)
		 return mid+1;
	  else if(*(pDatas+mid)<Data)
		  small=mid+1;
	  else
		  big=mid-1;
	  mid=(big+small)/2;
   }
   return 0;
}

void main()
{
	int number[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
	int count=20;
	int findData,findPosition;
	char choose;
	cout<<"A group of ordinal datas are the following numbers."<<endl;
	cout<<"一组有序的数据如下："<<endl;
	for(int i=0;i<count;i++)
	   cout<<number[i]<<" ";
	cout<<endl;
	while(1)
	{
	   cout<<"Please input the data that you want to find. "<<endl;
       cout<<"请输入你想要查找的数据：";
	   cin>>findData;
	   if(findPosition=Find(number,count,findData))
	   {
		   cout<<"The data "<<findData<<" is found . The number is the "<<findPosition<<"th."<<endl;
           cout<<"数据"<<findData<<"被找到。序数是第"<<findPosition<<"个。"<<endl; 	   
	   }
	   else
	   {
	      cout<<"The data "<<findData<<" isn't found in the group datas."<<endl;
	       cout<<"在这组数据中找不到数据"<<findData<<"。"<<endl;  
	   }
	   cout<<"Do you want to continue to test?Yes/No (Y/N) :"<<endl;
	   cout<<"你想继续测试吗？是/否（Y/N）：";
	   cin>>choose;
	   if(!(choose=='y'||choose=='Y'))
	       break;
	}
}