查找.cpp

数据结构查找子系统 通过查找试验理解查找的基本方法

#include<string.h>
#define SEARCHMAX 100
#define N 10
void SeqSearch()
{
	int a[N],x,y;
	char ch;
	printf("\n\t\t 建立一个整数的顺序表(以回车为间隔，以-1结束): \n");
	for(i=0;i<SEARCHMAX;i++)
	{
		printf("\t\t");
		scanf("%d",&a[i]);
		getchar();
		if(a[i]==-1)
		{ y=i;break; }
	}
    printf("\n\t\t 需要查找请输入Y，否则输入N：");
    scanf("%c",&ch);
    while(ch=='y'||ch=='y')
	{
	printf("\n\t\t 请输入要查找的数据：");
    scanf("%d",&x);getchar();
    i=y-1;
    while(i>0&&a[i]!=x)
        i--;
    if(i==-1)
        printf("\n\t\t 抱歉！你没有要查找的数据。");
    else
        printf("\n\t\t 你要查找的数据在第%d个位置上。\n",i+1);
        printf("\n\t\t 继续查找请输入Y，否则输入N：");
        scanf("%c",&ch);
	}
}
void BinSearch()
{
	int R[SEARCHMAX],i,k,low,mid,high,m,nn;
	char ch;
    printf("\n\t\t 建立递增有序的查找顺序表(以回车为间隔，以-1结束): \n");
    for(i=0;i<SEARCHMAX,i++)
	{
		printf("\t\t");
		scanf("%d",&R[i]);
		getchar();
		if(R[i]==-1)
		{nn=i;break;}
	}
    printf("\n\t\t 查找请输入Y，否则输入N：");
    scanf("%c",&ch);
	getchar();
    while(ch=='y'||ch=='y')
	{
		printf("\n\t\t 请输入要查找的数据：");
        scanf("%d",&k);
        getchar();
        low=0;
        high=nn-1;
        m=0;
        while(low<=high)
		{
	        mid=(low+high)\2;
	        m++;
	        if(R[mid]>k)
		        high=mid-1;
	        else
		        if(R[mid]>k)
			        low=mid+1;
		        else
			        break;
		}
        if(low>high)
		{
	        printf("\n\t\t 抱歉！没有你要查找的数据.\n);
            printf("\n\t\t 共进行 %d次比较.\n",m);
	        if(R[mid]<k)
		       mid++;
		    printf("\n\t\t 可将此数插入到第 %d 个位置上.\n",mid+1);
		}
        else
		{
		    printf("\n\t\t 要找的数据 %d 在第 %d 个位置上。\n",k,mid+1);
		    printf("\n\t\t 共进行 %d 次比较。\n",m);
		}
	        printf("\n\t\t 继续查找输入Y,否则输入N: ");
	        scanf("%c",&ch);getchar();
	}
} 
typedef int KeyType;
typedef struct node
{
	keytype key;
	struct node *lchild,*rchild;
}BSTNode;
typedef BSTNode *BSTree;
BSTree CreateBST(void);
void SearvhBST(BSTree T,KeyType Key);
void InsBST(BSTree *Tptr,KeyType Key);
void DelBSTNode(BSTree *Tptr,Keytype Key);
void InorderBST(BSTree T);
void BTSearch()
{
	BSTree T;
	char ch1,ch2;
	Keytype Key;
	printf("\n\t\t 建立一棵二叉数的二叉链表存储\n");
	T=CreateBST();
	ch1='y';           ////////////////////////gai
	getchar();
while (ch1=='y' ||ch1=='y')
{
	printf ("\n");
	printf ("\n\t\t         二叉排序表        ");
	printf ("\n\t\t* * * * * * * * * * * * * * * * * * * * * * * * * * * *");
	printf ("\n\t\t*                 1-------更新二叉排序树              *");
	printf ("\n\t\t*                 2-------查  找  结  点              *");
	printf ("\n\t\t*                 3-------插  入  结  点              *");
	printf ("\n\t\t*                 4-------删  除  结  点              *");
	printf ("\n\t\t*                 5-------中序输出排序树              *");
	printf ("\n\t\t*                 0-------返          回              *");
    printf ("\n\t\t* * * * * * * * * * * * * * * * * * * * * * * * * * * *");
    rintf ("\n\t\t 请选择菜单号 (0--5): ");
	scanf ("c%"，&ch2);
	getchar();
	switch (ch2)
	{
	case '1':t=createBST();break;
	case '2':printf("\n\t\t 请输入你要查找的数据 ");
	   scanf("%d,&key);
	   getchar();
	   SearchBST(t,key);
	   printf ("\n\t\t 查找完毕.\n");break
    case '3':printf("\n\t\t 请输入你要插入的数据：");
	   scanf("%d,&key);	getchar();
	   Insbet(&t,key);
   	   printf ("\n\t\t 插入完毕". \n");break;
    case '3':printf("\n\t\t 请输入你要删除数据 ");
	   scanf("%d,&key); getchar();
	   delBSTnode(&t,key);
	   printf ("\n\t\t 删除完毕". \n");break;
	   case '5':printf("\n\t\t");
	   inorderBST(t);
	   printf ("\n\t\t 二叉排序树输入完毕.\n ");break;
	   case '0' :ch1='n';
		   return;
	   default:printf("\n\t\t输入错误! 请重新输入.\n ");
	}
}
}
BSTree creatBST(void)
{
	BSTree t;
	keytype key;
	t=null;
	 printf ("\n\t\t 请输入一个整数关键字 (输入0时结束输入): ");
	scanf("%d,&key);   
	while(key)                          
	{
	insBST(&t,key);
	printf ("\n\t\t 请输入下一个关键字 (输入0时结束输入): ");
       scanf("%d",&Key);
	 }
	 return T;
}
void SearchBST(BSTree T,KeyType Key)
{
	BSTNode *p=T;
	while(p)
	{
		if(p->key==Key)
		{
		    printf("\n\t\t 已经找到您输入的数据. \n");
			return;
		 }
		 p=(key<q->key)?p->lchild:p->rchild;
	 }
	 printf("\n\t\t 没有找到您输入的数据. \n");
}
void InsBST(BSTree *T,KeyType Key)
{
	BSTNode *f,*p;
	p=(*T);
	while(p)
	{
		if(p->key==key)
		{
			printf("\n\t\t 树中已有 &d, 不需要插入. \n",Key);
			return;
		 }
		 f=p;
		 p=(Key<p->key)?p->lchild:p->rchild;
	 }
	 p=new BSTNode;
	 p->key=Key;
	 P->lchild=p->rchild=NULL;
	 if((*T)==NULL)
		 (*T)=p;
	 else
		 if(Key<f->key)
			 f->lchild=p;
		 else
			 f->rchild=p;
}
void DelBSTNode(BSTree *T,KeyType Key)
{
	BSTNode *parent=NULL,*p,*q,*child;
	p=*T;
	while(p)
	{
		if(p->key==Key) break;
		parent=p;
		p=(Key<p->key)?p->lchild:p->rchild;
	}
	if(!p)
	{
		printf("\n\t\t没有找到您要删除的结点. ");
		return;
	}
	q=p;
	if(q->lchild&&q->rchild)
		for(parent=q,p=q->rchild;p->lchild;parent=p,p=p->lchild);
	child=(p->lchild)?p->lchild:p->rchild;
	if (!parent) *T=child;
	else
	{
		if(p==parent->lchild)
			parent->lchild=child;
		else
			parent->rchild=child;
		if(p!=q)
			q->key=p->key;
	}
	delete(p);
}
void InordweBST(BSTree T)
{
	if(T!=NULL)
	{
		InordweBST(T->lchild);
		printf("\t%d",T->key);
		InorderBST(T->rchild);
	}
}
void main()
{
	int choice;
	char ch;
	ch='y';
	while(ch=='y'||ch=='Y')
	{
		printf("\n");
		printf("\n\t\t          查找子系统           ");
		printf("\n\t\t*******************************");
		printf("\n\t\t*       1-----顺序查找         ");
		printf("\n\t\t*       2------二分查找        ");
		printf("\n\t\t*       3-----二叉排序树       ");
		printf("\n\t\t*       0-----返    回         ");
		printf("\n\t\t*******************************");
		printf("\n\t\t 请选择菜单号(0--3): ");
		scanf("%d",&choice);
		switch (choice)
		{
			case 1:SeqSearch();break;
			case 2:BinSearch();break;
			case 3:BTSearch();break;
			case 0:ch='n';break;
			default:printf("\n\t\t 菜单选择错误!请重输. ");

		}

	}
}