学步园

 程序名称：Search.cpp
// 程序功能：采用结构化方法设计程序，实现多种查找算法。
// 程序作者：***
// 最后修改日期：2011-3-3
#include"iostream"
#include"stdlib.h"
#include"stdio.h"
#include "malloc.h"
#define MAX 11 
using namespace std;
typedef int ElemType ;
//顺序存储结构
typedef  struct {
  ElemType *elem;   //数据元素存储空间基址，建表时按实际长度分配，号单元留空
  int  length;      //表的长度
} SSTable; 

void Create(SSTable *table, int length);	
void Destroy(SSTable *table);
int Search_Seq(SSTable *table, ElemType key);		
void Traverse(SSTable *table, void (*visit)(ElemType elem));
// 构建顺序表
void Create(SSTable **table, int length)
{
 	SSTable *t = (SSTable*) malloc(sizeof(SSTable));//分配空间
	t->elem=(ElemType*)malloc(sizeof(ElemType)*(length+1));
	t->length=length;
	*table=t;
}
// 无序表的输入
void FillTable(SSTable *table)
{
	ElemType *t=table->elem;
//for循环，输入各个元素
	for(int i=0; i<table->length; i++)
	{
		t++;
		scanf("%d", t);//输入元素
		getchar();
	}
}
// 销毁表
void Destroy(SSTable *table)
{
	free(table->elem);//释放元素空间
	free(table);//释放表的空间
}
// 打印查找表
void PrintTable(SSTable *table)
{
    int i;//定义变量
	ElemType *t=table->elem;
	for(i=0; i<table->length; i++)//进入循环，依次打印表中元素
	{
 		t++;
		printf("%d ", *t);//打印输出
	}
	printf("\n");
}
//哨兵查找算法
int Search_Seq(SSTable *table, ElemType key)
{
	table->elem[0]=key;//设置哨兵
	int result=0;  // 找不到时，返回
	int i;
	for (i=table->length; i>=1;i--)     
	{
        if  (table->elem[i]==key)  
		{
			result=i;
			break;
		}
	}
return result;//返回结果
}

void printSeq()
{
//先设置几个变量
	SSTable *table;
	int r;
	int	n;
	ElemType key;
	printf("请输入元素个数:");
    scanf("%d",&n);//输入元素个数
	Create(&table, n);//建立表
	printf("请输入");cout<<n;printf("个值：");
	FillTable(table);//输入无序表的值
	printf("您输入的%d 个值是：\n",n);
	PrintTable(table);//打印无序表
	printf("请输入关键字的值:");
	scanf("%d",&key);
	printf("\n");
	printf("顺序查找法运行结果如下：\n\n ");
	Search_Seq(table,key);//哨兵查找算法
	r=Search_Seq(table,key);
	if( r>0)
	{
		printf(" 关键字%d 在表中的位置是：%d\n",key, r);//打印关键字在表中的位置
		printf("\n");
	}
	else  //查找失败
	{
		printf ("查找失败，表中无此数据。\n\n");
	}
}

// 排序算法     
void Sort(SSTable *table )
{
	int i, j;
	ElemType temp;
  	for (i=table->length; i>=1 ;i--)    // 从前往后找
	{
        for (j=1; j<i; j++)
		{
			if(table->elem[j]>table->elem[j+1])
			{
				temp=table->elem[j];
				table->elem[j]=table->elem[j+1];
				table->elem[j+1]=temp;
			}
		}
	}
 }

// 二分法查找（非递归）
int Search_Bin(SSTable *table, ElemType key)
{
	 int low=1;
	 int high=table->length;
	 int result=0;  // 找不到时，返回

	 while(low <= high)//low不大于high时
	 {
		int mid=(low+high)/2;
		if(table->elem[mid]==key)//如果找到
		{
			result=mid;
			break;
		}
		else if(key<table->elem[mid])//如果关键字小于mid对应的值
		{
			high=mid-1;
		}
		else  //否则的话
		{
			low=mid+1;
		}
	 }
	 return result;//返回结果
}

void printBin()
{
//声明变量
	SSTable *table;
	int r;
	int	n;
	ElemType key;


	printf("请输入元素个数:");
	scanf("%d",&n);
	Create(&table, n);//建立表
	printf("请输入");cout<<n;printf("个值：");
	FillTable(table);//输入无序表的值
	printf("您输入的%d 个值是：\n",n);
	PrintTable(table);//打印无序表
	printf("请输入关键字的值:");
	scanf("%d",&key);
	printf("\n");
	Sort(table);//对无序表进行排序
	printf("数据排序后的顺序如下：\n\n ");
	PrintTable(table);//打印有序表
	printf("\n");
	printf("二分查找法的运行结果如下：\n\n ");
	r=Search_Bin(table,key);//二分（非递归）查找算法
	if( r>0)
		printf("关键字%d 在表中的位置是：%d\n",key, r);
	else 
	{
		printf ("查找失败，表中无此数据。\n\n");
	}
}
//二叉排序树
typedef struct BiTnode //定义二叉树节点
{
	int data; //节点的值
	struct BiTnode *lchild,*rchild;//节点的左孩子，节点的右孩子
}BiTnode,*BiTree;

//查找（根据节点的值查找）返回节点指针
BiTree search_tree(BiTree T,int keyword,BiTree *father)
{
	BiTree p;// 临时指针变量
	*father = NULL;//先设其父亲节点指向空
	p = T;//p赋值为根节点（从根节点开始查找）
	while (p && p->data!=keyword)//如果不是p不指向空且未找到相同值的节点
	{
		*father = p;//先将父亲指向自己（注意：这里传过来的father是二级指针）
		if (keyword < p->data)//如果要找的值小于自己的值
			p = p->lchild;// 就向自己的左孩子开始找
		else
			p = p->rchild;//否则向自己的右孩子开始查找
	}
	return p;//如果找到了则返回节点指针
}
BiTree creat_tree(int count)
{
	BiTree T,p;//设置两个临时变量T,p
	int i = 1;
	while (i <= count)
	{
		if (i == 1)//如果i=1，说明还是空树
		{
			p = (BiTnode *)malloc(sizeof(BiTree));//使p指向新分配的节点
			if (!p)//分配未成功
				return NULL;
			T = p;//分配成功,T=p( 这里实际上T就是根节点)
			scanf("%d",&p->data);//输入p指向节点的值
			p->lchild = p->rchild = NULL;//p的左孩子和右孩子都指向空
			i++;
		}
		else
		{
			int temp;// 如果不是空树
			scanf("%d",&temp);//输入节点的值
			search_tree(T,temp,&p);//查找节点要插入的位置。（T是根节点，插入的节点的值，父亲节点的地址）
			if (temp < p->data)//如果插入的值小于父亲节点的值
			{
				p->lchild = (BiTnode *)malloc(sizeof(BiTnode));//那么就为父亲节点的左孩子分配一个节点空间，并指向这个空间
				if (!p->lchild)
					return NULL;
				p = p->lchild;//分配成功，p指向自己的左孩子
			}
			else// 如果插入的值大于父亲节点的值
			{
				p->rchild = (BiTnode *)malloc(sizeof(BiTnode));
				if (!p->rchild)
					return NULL;//分配不成功，退出
				p = p->rchild;//p指向自己的右孩子
			}
			p -> data = temp;//新分配的节点的值赋值为插入的值
			p -> lchild = p->rchild = NULL;//使其左右节点均为NULL
			i++;
		}
	}
	return T;//返回根节点
}

void InOrder(BiTree T)
{
	if(T)
	{
		InOrder(T->lchild);
		printf("%d ",T->data);
		InOrder(T->rchild);
	}
}

int insert_tree(BiTree *T,int elem)//插入（根节点，插入的值）返回-1和,-1代表插入失败，代表成功
{
	BiTree s,p,father;
	s = (BiTnode *)malloc(sizeof(BiTnode));//s指向新开辟一个节点
	if (!s)//为开辟成功
		return -1;// 返回值-1
	s->data = elem;//新节点的值赋值为插入的值
	s->lchild = s->rchild = NULL;//其左右孩子为空
	p = search_tree(*T,elem,&father);//p赋值为要插入的节点
	if (!p)
		return -1;//未开辟成功，返回-1
	if (father == NULL)//如果父亲节点指向空，说明是空树
		*T = s;//让根节点指向s
	else if (elem < father->data)//否则如果插入的值小于父亲的值
		father->lchild = s;//父亲的左孩子赋值为s
	else
		father->rchild = s;//否则父亲的右孩子赋值为s
	return 0;//返回

}

//删除树结点的操作
int delete_tree(BiTree *T,int elem)
{
	BiTree s,p,q,father;//声明变量
	p = search_tree(*T,elem,&father);//查找
	if(!p)
		return -1;
	if(!p->lchild)//如果p的左孩子为空
	{
		if (father == NULL)
		{
			*T = p->rchild;//T指向左孩子
			free(p);//释放p
			return 0;
		}
		if (p == father->lchild)//如果p和father的左孩子相等
			father->lchild = p->rchild; //将p的左孩子的值赋给father的左孩子
		else
			father->rchild = p->rchild;//将p的左孩子的值赋给father的右孩子
		free(p);//释放p
		return 0;
	}
	else
		if(!p->rchild)
		{
			if (father == NULL)//如果father为空
			{
				*T = p->lchild;//将p的左孩子赋给T
				free(p);//释放p
				return 0;
			}
			if (p == father->lchild)//如果p等于father的左孩子的值
				father->lchild = p->lchild; //将p的左孩子的值赋给father的左孩子
			else
				father->rchild = p->lchild; //将p的左孩子的值赋给father的右孩子
			free(p);
			return 0;
		}
		else
		{
			q = p;
			s = p->lchild;//将p的左孩子赋给s
			while (s->rchild)
			{
				q = s;
				s = s->rchild;
			}
			p->data = s->data;//将s的值赋给p
			if (q != p)//如果q不等于p
				q->rchild = s->lchild; //将s的左孩子值赋给p的右孩子
			else
				q->lchild = s->lchild; //将s的左孩子值赋给p的右孩子
			free(s);//释放s
			return 0;
		}
}
//定义print1（）以便调用
void print1()
{
	printf("\t**********************\n");
	printf("\t1,输出中序遍历\n");
	printf("\t2,插入一个结点\n");
	printf("\t3,删除一个结点\n");
	printf("\t4,查找一个结点\n");
	printf("\t5,返回主菜单\n");
	printf("\t**********************\n");

}

void printTree()
{
//声明变量
	BiTree T,p;
	T=NULL;
	int	i,n;
	ElemType key;
	printf("请输入结点个数：\n");
	scanf("%d",&n);//输入值
	printf("请输入");cout<<n;printf("个值：");
	T=creat_tree(n);//建立树
	print1();
	scanf("%d",&i);//输入各个值
	while(i!=5)//i不等于5时
	{
		switch(i)
		{
		case 1:
			printf("中序遍历二叉树结果如下：\n");
			InOrder(T);//中序遍历
			break;
		case 2:
			printf("请输入要插入的结点值：");
			scanf("%d",&key);//输入要查找的关键字
			if(insert_tree(&T,key))//如果插入成功
				printf("插入成功！");
			else
				printf("已存在此元素！");
			break;
		case 3:
			printf("请输入要删除的结点值：");
			scanf("%d",&key); //输入要删除的关键字
			if(!(delete_tree(&T,key)))//如果删除成功
				printf("删除成功！");
			else
				printf("不存在此元素！");
			break;
		case 4:
			printf("请输入要查找的结点值：");
			scanf("%d",&key); //输入要查找的关键字
			if(search_tree(T,key,&p))//如果查找成功
				printf("查找成功！");
			else
				printf("不存在此元素！");
			break;
		default:
			printf("按键错误！");
		}
		printf("\n");
		print1();
		scanf("%d",&i);
	}
}
//哈希表
typedef struct 
{ 
	int num; 
} 
Elemtype;//定义查找的结点元素
typedef struct 
{ 
	Elemtype *elem; //数据元素存储基址
	int count; //数据元素个数
	int sizeindex; 
}HashTable;//定义哈希表

int Hash(int num) 
{ 
	int p; 
	p=num%11; 
	return p; 
}//定义哈希函数

//冲突处理函数，采用二次探测再散列法解决冲突
int collision(int p,int &c)
{
 int i,q;
 i=c/2+1;
 while(i<MAX){
  if(c%2==0){
   c++;
   q=(p+i*i)%MAX;
   if(q>=0) return q;
   else i=c/2+1;
  }
  else{
   q=(p-i*i)%MAX;
   c++;
   if(q>=0) return q;
   else i=c/2+1;
  }
 }
  return 0;
}

void InitHash(HashTable *H)//创建哈希表
{ 
	int i; 
    H->elem=(Elemtype *)malloc(MAX*sizeof(Elemtype)); 
	H->count=0; 
	H->sizeindex=MAX; 
	for(i=0;i<MAX;i++) 
		H->elem[i].num=0;//初始化，使SearHash函数能判断到底有没有元素在里面
} 

int SearHash(HashTable H,int key,int *p)//查找函数
{ 
	*p=Hash(key); 
	while(H.elem[*p].num!=key&&H.elem[*p].num!=0) 
		*p=*p+1; 
	if(H.elem[*p].num==key) 
		return 1; 
	else 
		return 0; 
} 

void InsertHash(HashTable *H,Elemtype e) 
{//如果查找不到就插入元素
	int p; 
	SearHash(*H,e.num,&p); //查找
	H->elem[p]=e; 
	++H->count; 
} 

void printHash()//调用哈希表
{ 
	HashTable H; 
	int p,key,i,n; 
	Elemtype e; 
	InitHash(&H);
	printf("输入数据个数(<11 ):");
	scanf("%d",&n);
	printf("请输入各个值：");
	for(i=0;i<n;i++) 
	{//输入n个元素
		scanf("%d",&e.num);//输入数字
		if(!SearHash(H,e.num ,&p)) 
		{ 
			InsertHash(&H,e );//插入元素
		} 
		else 
			printf("已经存在\n");//否则就表示元素的数字已经存在
	} 
	printf("输入查找的数字:"); 
	scanf("%d",&key);//输入要查找的数字
	if(SearHash(H,key,&p))//能查找成功
	{ 
		printf("查找成功！");//输出位置
	} 
	else 
		printf(" 不存在此元素！"); 
} 

void print()
{
	printf("\t**********************\n");
	printf("\t1,顺序查找\n");
	printf("\t2,二分查找\n");
	printf("\t3,二叉排序树\n");
	printf("\t4,哈希查找\n");
	printf("\t5,退出程序\n");
	printf("\t**********************\n");
}


// 主函数
int main(int argc, char* argv[])
{
	int i;//定义变量

	print();
	scanf("%d",&i);//输入要数字选择要使用的查找方法
	while(i!=5)//i不等于5时
	{
		switch(i)
	    {
	        case 1://i=1时
				printf("顺序查找法：\n");
				printSeq();//顺序查找法
				break;//跳出循环}
			case 2:
				printf("二分查找法：\n");
				printBin();//二分查找法
				break; //跳出循环
			case 3:
				printf("二叉排序树：\n");
				printTree();//二叉排序树
				break; //跳出循环
			case 4:
				printf("哈希查找法：\n");
				printHash();//哈希查找法
				break; //跳出循环
			default:
				printf("按键错误！");
		}
		printf("\n");
		print();//调用函数print()
		scanf("%d",&i);
	}
	return 0;//返回0
}
（1）首主菜单：首先出现主菜单，通过选择相应数字进行相应功能的实现，如图所示：
 
图4.2.1 主菜单
（2）通过主菜单按键选择1进入顺序查找功能，输入元素个数，然后输入这几个元素的值，用户再输入需要查询的数字即可得出查找结果，如果查找成功则显示出关键字所在的位置，否则显示“查找失败，表中无此数据”，图4.2.2示：
 
图4.2.2 顺序查找

（3）通过主菜单按键选择2进入二分查找功能，根据提示输入元素个数，再输入这几个值，然后输入要查找的关键字，系统排序后会显示该关键字在顺序表中的位置，否则显示“查找失败，表中无此数据”，如图4.2.3所示：
 

图4.2.3 查询功能
（4）a．通过主菜单按键选择3进入二叉排序树功能，首先输入结点个数及结点的值建立二叉排序树，然后便进入一个菜单提示选择二叉排序树的某个功能如图4.2.4a所示：
 
图4.2.4a 二叉排序树功能菜单
b.中序遍历二叉排序树，如图4.2.4b所示：
 
图4.2.4b 中序遍历二叉排序树
c.插入一个结点，如图4.2.4c所示：
 
图4.2.4c二叉排序树插入一个结点
d．删除一个结点，如图4.2.4d所示：
 
图4.2.4d 二叉排序树删除一个结点
e．查找一个结点，如图4.2.4e所示：
 
图4.2.4e 二叉排序树查找一个结点
（5）通过主菜单按键选择4进入哈希查找功能，根据提示输入元素个数，再输入这几个值，然后输入要查找的关键字，找到则显示“查找成功！”，否则显示“不存在此元素”，如图4.2.5所示：
 
图4.2.5 哈希查找法