cpp综合查找66.cpp

是学语言的课程设计,好象是查找或是迷宫

#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<windows.h>
#define OVERFLLOW 1
#define init_size 10
#define increasesize 10
#define LIST_INIT_SIZE 10 
#define LISTINCREMENT 10  
#define OK 1
typedef int Status; 
typedef int ElemType; 
#define OK 1
#define OVERFLOW -2 
typedef struct TreeNode
{
int key;
struct TreeNode *left;
struct TreeNode *right;

}treeNode;

class BiSortTree
{
public:
    BiSortTree(void);
void desplayTree(void);//显示这个树
void insertTree(int key);//在树中插入一个值
  deleteTree(int key);//在树中删除一个值
    treeNode* searchTree(int key);//在树中查找一个值
    
~BiSortTree();
treeNode*  buildTree(treeNode* head,int number);//建立一个树
treeNode*  search(treeNode* head ,int key);//查找
treeNode* BiSortTree::searchParent(treeNode* head,treeNode* p);//查找出p的父亲节点的指针
treeNode* BiSortTree::searchMinRight(treeNode* head);//找到右子树中最小的节点

void showTree(treeNode* head);//显示
    void destroyTree(treeNode* head);//删除

treeNode *Head;
};

/**************以下是建立一个二叉排序树****************/
BiSortTree::BiSortTree()
{
   cout<<"建立一棵二叉排序树,请输入你要建树的所有数(以-1 作为结束标志!): "<<endl;
   Head=NULL;
   int number;
   cin>>number;
   while(number!=-1)
   {
   Head=buildTree(Head,number);
       cin>>number;  
   
   }

}
treeNode* BiSortTree::buildTree(treeNode* head,int number)
{

treeNode *p;    
p=new treeNode;
    p->key=number;
p->left =p->right=NULL;

if(head==NULL)
{

     
      return p;
}
else
{
  
       if(p->key <head->key)
head->left=buildTree(head->left,number);
   else
  head->right=buildTree(head->right,number);
  
       return head;
}





}
/*****************以下是在一棵二叉排序树插入一个数***********************************/
void BiSortTree::insertTree(int key)
{

Head=buildTree(Head,key);

}
/*****************以下是在一个二叉排序树查找一个数是否存在*************************/
treeNode*  BiSortTree::searchTree(int key)
{
return search(Head,key);
}
treeNode* BiSortTree::search(treeNode* head ,int key)
{  
if(head==NULL)
return NULL;
if(head->key==key)
return head;
else 
{
if(key<head->key )
return search( head->left,key);

    else
return search(head->right,key);


}

}

/************以下是在一个二叉排序树删除一个给定的值*********************************/
BiSortTree::deleteTree(int key)
{

treeNode *p;
p=NULL;
    p=search(Head,key);
if(p==NULL)
{
cout<<"Don't find the key";

}
    if(p==Head)
{
Head=NULL;

}
else
{ 
treeNode* parent;
parent=searchParent(Head,p);
if(p->left==NULL&&p->right==NULL)//叶子节点
{
    if(parent->left==p)
{
parent->left=NULL;
}
    else
{
parent->right=NULL;

}
}
        else//非叶子节点
{
           if(p->right==NULL)//该节点没有右孩子
   {
   if(parent->left==p)
   {
     parent->left=p->left ;
   }
       else
   {
   parent->right=p->left;

   }
   }

   else//该点有左右孩子
   {
   treeNode * rightMinSon,* secondParent;//secondParent为右子树中的最小节点的父亲
   rightMinSon=searchMinRight(p->right);
   secondParent=searchParent(p->right ,rightMinSon);
           
               secondParent->left=rightMinSon->right;
  
                               
           if(p->right==rightMinSon)//右子树中的最小节点的父亲为p
   {
      
        p->right=rightMinSon->right ;
  
   }
      
   p->key=rightMinSon->key ;

      
      
   } 
}
}
}

treeNode* BiSortTree::searchParent(treeNode* head,treeNode* p)
{


if(head->left==p||head->right==p||head==p||head==NULL)
return head;
    else
{
if(p->key<head->key)
return searchParent(head->left ,p);
else
return searchParent(head->right ,p);


}


}

treeNode* BiSortTree::searchMinRight(treeNode* head)//找到右子树中最小的节点
{


if(head->left ==NULL||head==NULL)
{
return head;

}
else
{
return searchMinRight(head->left);

}



}

/*****************以下是显示一个二叉排序树****************************************/
void BiSortTree::desplayTree(void)
{

showTree(Head);
cout<<endl;
}
void BiSortTree::showTree(treeNode* Head)
{

if(Head!=NULL)
{
showTree(Head->left ) ;

    cout<<Head->key<<' ' ;

showTree(Head->right) ;

}


}





/*****************以下是删除一棵整二叉排序树************************************/
BiSortTree::~BiSortTree()
{
cout<<"已经消除了一棵树!!!!"<<endl;
destroyTree(Head);
}
void BiSortTree::destroyTree(treeNode* head )
{

if(head!=NULL)
{
destroyTree(head->left );
destroyTree(head->right );
delete head;

}

}

/*********************/
void print()
{

    cout<<endl<<endl<<"以下是对二叉排序树的基本操作:"<<endl
<<"1.显示树"<<endl
    <<"2.插入一个节点"<<endl
<<"3.寻找一个节点"<<endl
<<"4.删除一个节点"<<endl;
}
void print1()
{
	cout<<endl<<endl<<"一下是本程序所要执行几个查找操作:"<<endl
		<<"1.二差排序树"<<endl
		<<"2.二分查找"<<endl
		<<"3.哈希查找"<<endl
		<<"4.顺序查找"<<endl;
}
//二分查找
typedef struct{
int *elem;
int length;
int size;
} SSTable;
int init(SSTable &s){
s.elem=(int *)malloc(init_size*sizeof(int));
if(!s.elem) exit(OVERFLLOW);
s.length=0;
s.size=init_size;
return OK;
}

int Search(SSTable s,int e)
{
int low=0,high=s.length-1,mid;
while(low<=high){
mid=(low+high)/2;
if(s.elem[mid]==e) return mid;
else if(e<s.elem[mid])high=mid-1;
else low=mid+1;
}
return -1;
}
//顺序查找
typedef struct {     
        ElemType *elem;     
        int length;     
        int listsize; 
}SqList;  

Status InitList_Sq(SqList *L,int n){   
    (*L).elem=(ElemType *)malloc(n*sizeof(ElemType));    
    if(!((*L).elem)) return OVERFLOW;
    (*L).length=0;   
    (*L).listsize=n;    
    return OK; 
}/*InitList_Sq*/  

Status ListInsert_Sq(SqList *L,int i,ElemType e){ 
    ElemType *newbase, *p , *q;  
    if(i<1||i>L->length+1) return ERROR;    
    if(L->length>=L->listsize){    
    newbase=(ElemType *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType)); 
    if(!(*newbase)) exit(OVERFLOW);    
    L->elem=newbase;    
    L->listsize+=LISTINCREMENT;  
    }  
    q=&(L->elem[i-1]);  
    for(p=&(L->elem[L->length-1]);p>=q;--p)     
    *(p+1)=*p;    
    *q=e;     
    ++L->length;     
    return OK; 
}/*ListInsert_Sq*/ 

Status ListDelete_Sq(SqList *L,int i,ElemType e){ 
    ElemType *p , *q;     
    if(i<1||(i>L->length)) return ERROR;    
    p=&(L->elem[i-1]);    
    e=*p;    
    q=L->elem+L->length-1;    
    for(++p;p<=q;++p)*(p-1)=*p;    
    --L->length;    
    return OK; 
}/*ListDelete_Sq*/ 

//定义compare函数.
Status compare(ElemType x,ElemType y){
       if(x==y)
         return OK;
       else
         return 0;
}
Status LocateElem_Sq(SqList L,ElemType e){
   ElemType i,*p;
   i=1;
   p=L.elem;
   while(i<=L.length&&!(*compare)(*p++,e))
   ++i;
   if(i<=L.length)
   return i;
   else return 0;
}/*LocateElem_Sq*/ 
//链式存储结构
struct hashnode
{
	int data;//结点信息
	hashnode *next;//指向下一结点的指针
};

//输入序列，建立哈希表
void creathash(hashnode *t[])
{   
    int n,i;
    hashnode *p,*p1;
	cout<<"请输入哈希表元素的个数："<<endl;
    cin>>n;
	cout<<"请输入哈希表元素：" <<endl;
	for(int j=0;j<n;j++)
	{
		p=(hashnode *)malloc(sizeof(hashnode));
		cin>>p->data;
		i=p->data%12;
		p1=t[i];
		if(!p1)
		{
			t[i]=p;p->next=0;	 
		}
		else
		{
			while(p1->next!=0)
			p1=p1->next;
			p1->next=p;
			p->next=0;
		}
	}
}//creathash

//输出哈希表结点
void printhash(hashnode *t[])
{
	hashnode *p;
    for(int i=0;i<12;i++)
    {
		p=t[i];
		while(p!=0)
		{
			cout<<p->data<<" ";
			p=p->next;
		}
	}
}//printhash

//查找结点
void locatehash(hashnode *t[])
{
	int a,k;bool flag=0;
    cout<<"请输入要查找的元素："<<endl;
	cin>>a;
	k=a%12;
	while(t[k]!=0)
	{
		if(t[k]->data==a) 
		{
			cout<<"找到该元素！"<<endl; 
			flag=1;
			break;
		}
		t[k]=t[k]->next;
	};
    if(!flag) 
		cout<<"不存在该元素！"<<endl;
}//locatehash

void main()
{
	//程序使用说明
	int number;  char kk,ch[10];int i;
    cout<<"\t\t\t\t欢迎使用综合查找系统"<<endl;
	printf("\t\t说明:【使用前必需先录入数据,否则功能无法实现!】\n");
//	getch();
	while(1)
	{
		    
printf(" \n\t* * * * * * * * * * * * *  * * * * * * * * * *\n");
printf("  \t*                 综合查找                   *\n");
printf("  \t*  *  * * * * * * * * * * * * * * * * * * * **\n");
printf("  \t*              1.二叉排序树查找              *\n");
printf("  \t*              2.二分查找                    *\n");
printf("  \t*              3.顺序查找                    *\n");
printf("  \t*              4.哈希查找                    *\n");
printf("  \t*              5退出系统                     *\n");
printf("  \t* * * * * * * * * * * * * * * * * * * * * * ** \n");
printf("  \t                                                  【制作人:黄海燕】\n");
printf("\t\t\t\t请输入选择1--5/?");
 scanf("%d",&number);
switch(number)
	{
	case 5: 
			cout<<" 是否确认要退出？Yes\\No"<<endl;
			scanf("%s",ch); kk=ch[0];
			if(kk=='y'||kk=='Y') { cout<<"\t\t\t\t谢谢使用本系统"<<endl; goto bb;  }
			system("cls");
			break;			
 	case 1:			    
			int number;
			int choiceNumber;
			char flag;
			while(1)
			{
			 BiSortTree tree;
			 print() ; 
			 cout<<"请选择你要进行的操作(1~4)"<<endl;
             cin>>choiceNumber;
			switch(choiceNumber)
			 {
			case 1:   
					tree.desplayTree();break;
			case 2:
			    	cout<<"请插入一个数: "<<endl;
                   cin>>number;
					tree.insertTree(number);
                   tree.desplayTree();break;              
			case 3:
					cout<<"请插入你要找数: "<<endl;
					 cin>>number;   
					 if(tree.searchTree(number)==NULL)
					 {
						 cout<<"没有发现"<<endl;
						}
				     else
					 {   
                    cout<<"发现"<<endl;   
					}
					 break;
            case 4:
				 cout<<"请输入你要删除的数: "<<endl;  
					cin>>number;
					 tree.deleteTree(number);
                  tree.desplayTree();
				  break;
			 default: printf("请输入一个1-4的数据!");
			}
      cout<<"你是否要继续(Y/N)?";
      cin>>flag;
  if(flag=='N'||flag=='n')
     break;
}
	system("cls");
break;		
case 2:
SSTable s;
int n,e;
init(s);
printf("注意以下是二分查找输入的表的元素必须按递增顺序排列！\n");
printf("请输入表的长度：\n");
scanf("%d",&n);
while(n>s.size){
s.elem=(int *)realloc(s.elem,increasesize*sizeof(int));
s.size+=increasesize;
}
printf("请输入表的元素:\n");
for(i=0;i<n;i++)
 scanf("%d",&s.elem[i]);
s.length=n;
printf("请输入要查找的元素：\n");
scanf("%d",&e);
if(Search(s,e)!=-1)
    printf("存在该元素。\n");
	else
	printf("不存在该元素。\n");
	system("pause");
	system("cls");
break;	
case 3: 
	int place;
    SqList L; 
	printf("请输入表的长度：\n");
    scanf("%d",&n);
    int select;      
    if(InitList_Sq(&L,n)==OVERFLOW) printf("ERROR"); 
    else     
    {  printf("请输入线性表的元素:");
       for( i=0;i<L.listsize;i++)
            {scanf("%d",&L.elem[i]);L.length++;}
            printf("插入前的线性表:\n"); 
       for (i = 0; i< L.listsize; i++)                
            printf("%d ",L.elem[i]);  
            printf("\n");
       do{     
          printf("\n0:增加一个元素\n");
          printf("1:删除一个元素\n"); 
          printf("2:查找一个元素\n");
          printf("3:结束\n");     
          scanf("%d",&select); 
       switch(select){     
             case 0:printf("请输入插入元素的位置及被插入的元素:");            
                    scanf("%d%d",&i,&e);
                    ListInsert_Sq(&L,i,e);
					printf("The Add Position Is:%d\nTo Add A Elem Is%d\n",i,e);
                    printf("插入后的线性表:\n");            
                    for(i=0;i<L.length;i++)
                       printf("%4d",L.elem[i]);break; 
             case 1:printf("请输入删除元素的位置:");            
                    scanf("%d",&i);
                    ListDelete_Sq(&L,i,e);
                    printf("The Delete Position Is:%d\n",i);
                    printf("删除后的线性表:\n");            
                    for(i=0;i<(L.length);i++)               
                       printf("%4d",L.elem[i]);break;  
             case 2:printf("请输入要查找的元素.");
                    scanf("%d",&e); 
					place=LocateElem_Sq(L,e);
					if(place)
                       printf("你查找的元素位置是:%d",place);
					else
						printf("查无此元素！");					
					break;
             case 3:printf("OVER");   
                    printf("\n");break;
             default:printf("请输入一个0-3的数据!"); 
                    printf("\n");
       }
      }while(select!=3);
    }

break;
case 4:
	hashnode *t[12]={0};	
	creathash(&t[0]);
	printhash(&t[0]);
    printf("\n");
	locatehash(&t[0]);
    system("pause");     
	break;	
}
}
bb:;
}