cpp009.cpp

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

/* c1.h (程序名) */
 #include<string.h>
 #include<ctype.h>
 #include<malloc.h> /* malloc()等 */
 #include<limits.h> /* INT_MAX等 */
 #include<stdio.h> /* EOF(=^Z或F6),NULL */
 #include<stdlib.h> /* atoi() */
 #include<io.h> /* eof() */
 #include<math.h> /* floor(),ceil(),abs() */
 #include<process.h> /* exit() */
 /* 函数结果状态代码 */
 #define TRUE 1
 #define FALSE 0
 #define OK 1
 #define ERROR 0
 #define INFEASIBLE -1
 /* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 */
 typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
 typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
 
typedef struct node { int key ;
struct node *lchild,*rchild ;}BTnode;
BTnode *f=NULL;
BTnode *BSTSearch(BTnode *r,int k)
{
	f=r;
	while ( r!=NULL)
	{ if (r->key==k)
	return r;
	else {f=r; r=k<r->key ?r->lchild :r->rchild;}
}
return r;}
BTnode *BSTInsert(BTnode *r,int x)
{ BTnode *p,*q,*s;
if(r==NULL)
{
	r=(BTnode *)malloc ( sizeof(BTnode));
	r->key=x;
	r->rchild=r->lchild =NULL;}
else
{
	p=r;
	while(p!=NULL&&p->key!=x)
	{
		q=p;
		p=x<p->key?p->lchild:p->rchild;}
	if(x==p->key)
		printf("find %d node!",p->key);
	else
	{
		s=(BTnode *) malloc(sizeof(BTnode));
		s->key=x;
		s->rchild=s->lchild=NULL;
		if(x<q->key) q->lchild=s;
		else q->rchild=s;}
}
return r;}
BTnode *BSTdel(BTnode *r,BTnode *p,BTnode *f)
{
	BTnode *q,*s;
	if(p->lchild ==NULL)
	{ if(p==r) r=r->rchild;
	else if(p==f->rchild) f->rchild=p->rchild;
	else f->lchild=p->rchild;}
	{ if(p->rchild==NULL) { if(p==r) r=r->lchild;
	else if ( p==f->rchild) f->rchild=p->lchild;
	else f->lchild=p->lchild;}
	else
	{
		q=p;
		s=q->lchild;
		while(s->rchild!=NULL)
		{
			q=s;
			s=s->rchild;}
		s->rchild=p->rchild;
		if(p!=q)
		{ q->rchild =s->lchild;
		s->lchild=p->lchild;}
		if(p==r) r=s;
		else if (p==f->rchild )f->rchild =s;
		else f->lchild = s;
	}
	}
	free(p);
	return r;
}
 void Inorder(BTnode *r)
 { if(r!=NULL)
 { Inorder(r->lchild);
 printf("%d,",r->key);
 Inorder(r->rchild);}
 }
 main ()
 { BTnode *r=NULL,*p;
 int k;
 scanf("%d",&k);
 while(k!=-1)
 { r=BSTInsert( r,k);
 scanf("%d",&k);}//jianli erchashu
 Inorder(r);
 printf("search k=");
 p=BSTSearch(r,k);//
 if(p)
 { printf("find k=%d!",p->key);
 if(p==r)
	 printf(" no parents");
 else
	 printf(",parent=%d",f->key);
 r=BSTdel ( r,p,f);
 printf("after deleted ;");
 Inorder(r);}
 else printf("no find!");
 }
 typedef  struct {                                                               
     ElemType  *elem;       // 数据元素存储空间基址，建表时                                                                                                按实际长度分配，0号单元留空
     int       length;    // 表的长度
} SSTable;
int Search_Seq(SSTable ST, KeyType key) {
   // 在顺序表ST中顺序查找其关键字等于 key的数据   元素。若找到，则函数值为该元素在表中的位置，否则为0。
   ST.elem[0].key = key;      // “哨兵”
   for (i=ST.length; ST.elem[i].key!=key;  --i);  
                              // 从后往前找
   return i;            // 找不到时，i为0
} // Search_Seq顺序查找
int Search_Bin ( SSTable ST, KeyType key ) {
   int low ; int high ;                                                                                    
low = 1;  high = ST.length;     // 置区间初值
   while (low <= high) {
      mid = (low + high) / 2;
      if (key==ST.elem[mid].key )
        return  mid;        // 找到待查元素
     else if (key<ST.elem[mid].key))
        high = mid - 1;       // 继续在前半区间进行查找
      else  low = mid + 1; // 继续在后半区间进行查找
   }
   return 0;                 // 顺序表中不存在待查元素
} // Search_Bin二分查找
typedef struct {                                                  
	ElemType * elem;
	int count;
	int sizeindex;
}HashTable;
# define SUCCESS 1;
# define UNSUCCESS 0;
# define DUPLICATE -1;
Status SearchHash ( HashTable H,KeyType K,int &p,int &c) {
	p=Hash (k);
	while ( H.elem[p].key !=NULLKEY && !EQ( K,H.elem[p].key))
	collision(p,++c);
   	if EQ(K,H.elem[p].key)
		return SUCCESS;
	else return UNSUCCESS;
}//SearchHash
Status InsertHash ( HashTable &H,Elemtype e){
   	c=0;
	if(SearchHash( H,e.key,p,c))
		return DUPLICATE;
	else if ( c<hashsize[H.sizeindex]/2){
		H.elem[p]=e;++H.count ;return OK;
	}
	else { RecreateHashTable(H);return UNSUCCESS;}
}//InsertHash

//程序使用说明
	int number;  char kk,ch[10];
	List L1;
	 cout<<"\t\t\t\t综合查找"<<endl;
	printf("\t\t说明:【使用前必需先录入数据,否则功能无法实现!】\n");
//	getch();
	while(true)
	{    
printf(" \n\t* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\n");
printf(" \t*\t    *             综合查找            *           *\n");
printf(" \t*\t    * * * * * * * * * * * * * * * * * * * * *           *\n");
printf("  \t*\t          * * * * * * * * * * * * * * *                 *\n");
printf("  \t*\t         *                             *                *\n");
printf("  \t*\t        *        1.二叉排序树           *               *\n");
printf("  \t*\t       *                                 *              *\n");
printf("  \t*\t      *        2. 顺序查找          *             *\n");
printf("  \t*\t     *                                     *            *\n");
printf("  \t*\t    *        3.二分查找           *           *\n");
printf("  \t*\t   *                                         *          *\n");
printf("  \t*\t    *        4.哈希查找           *           *\n");
printf("  \t*\t     *                                     *            *\n");
printf("  \t*\t      *       5.退出系统              *             *\n");
printf("  \t*\t       *                                 *              *\n");
printf("  \t*\t        *                 *               *\n");
printf("  \t*\t         *                             *                *\n");
printf("  \t*\t          * * * * * * * * * * * * * * *                 *\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;  }
			break;
		}
	case 1: 
		{
			while(1) 
			{
			
		}//case 1
	case 2:   break;
	case 4:  break;
	case 3: break;
	case 5: break;
	default : cout<<" error\n";
	}//switch
	//	cout<<"按任意键继续"<<endl;

	}//while
bb:;
}
/*

*/