#include"stdio.h"
#include"stdlib.h"
#define maxsize 20
//顺序表结构
typedef struct {
int date[maxsize+1];
int length;
}ssTable;
//二叉排序树结构体
typedef struct node{
int date;
node *lchild,*rchild;
}Tree;
int search01(ssTable &s);
int search02(ssTable &s1);
int search03(Tree **head,int n);
int insert01(ssTable &s,int j)//无序顺序表的插入
{
if(s.length>=maxsize)
printf("无法继续插入\n");
else
{
s.date[s.length+1]=j;
s.length++;
}
}
int insert02(ssTable &s1,int j)//有序顺序表的插入
{
int i;
if(s1.length>=maxsize)
printf("无法继续插入\n");
else
{
s1.date[0]=j;
for(i=s1.length;s1.date[i]>s1.date[0];i--)
s1.date[i+1]=s1.date[i];
s1.date[i+1]=s1.date[0];
s1.length++;
}
}
int insert03(Tree **t,int j)//二叉排序树的插入
{
Tree *p;
if(!(*t))
{
p=new Tree;
p->date=j;p->lchild=NULL;p->rchild=NULL;
(*t)=p;
}
else if((*t)->date>j)
insert03(&(*t)->rchild,j);
else
insert03(&(*t)->lchild,j);
}
int init(Tree **t,ssTable &s,ssTable &s1)
{
int n,i,j;
(*t)=NULL;
s.length=s1.length=0;
while(1)
{
printf("请输入有多少个数\n");
scanf("%d",&n);
if(n<=maxsize)
break;
else
printf("输入数的个数大于存储范围,重新输入\n");
}
printf("请输入数\n");
for(i=1;i<=n;i++)
{
scanf("%d",&j);
insert01(s,j);
insert02(s1,j);
insert03(&(*t),j);
}
}
int select(Tree **t,ssTable &s,ssTable &s1)
{
int i,n;
printf("1.设置监视哨的顺序查找\n");
printf("2.二分查找查找\n");
printf("3.二叉排序树查找\n");
printf("4.插入\n");
printf("其他.退出\n");
printf("请输入要执行的步骤\n");
scanf("%d",&i);
switch(i)
{
case 1:search01(s);break;
case 2:search02(s1);break;
case 3:
printf("请输入要查找的数\n");
scanf("%d",&s.date[0]);
search03(&(*t),s.date[0]);break;
case 4:
printf("请输入元素\n");
scanf("%d",&n);
insert01(s,n);insert02(s1,n);insert03(&(*t),n);
break;
default:exit(0);
}
select(&(*t),s,s1);
}
int search01(ssTable &s)//设置哨兵查找
{
int i;
printf("请输入要查找的数\n");
scanf("%d",&s.date[0]);
for(i=1;i<s.length;i++)
{
if(s.date[0]==s.date[i])
printf("(未排序)数%d的位置为%d\n",s.date[0],i);
}
if(i>s.length)
printf("不存在数%d",s.date[0]);
}
int search02(ssTable &s1)//二分查找
{
int high=s1.length,row=1,mid;
printf("请输入要查找的数\n");
scanf("%d",&s1.date[0]);
while(row<=high)
{
mid=(high+row)/2;
if(s1.date[0]==s1.date[mid])
{
printf("(已排序)数%d的位置为%d\n",s1.date[0],mid);
return 0;
}
else if(s1.date[0]>s1.date[mid])
row=mid+1;
else
high=mid-1;
}
if(row>high)
printf("查无此数---%d\n",s1.date[0]);
}
int search03(Tree **head,int n)//排序二叉树查找
{
if(!(*head))
{
printf("查无此数--%d\n",n);
return 0;
}
else if((*head)->date==n)
{
printf("存在数%d",(*head)->date);
return 0;
}
else if(n>(*head)->date)
search03(&(*head)->rchild,n);
else
search03(&(*head)->lchild,n);
}
int main()
{
Tree *t;ssTable s,s1;//s内容不排序,s1内容排序
init(&t,s,s1);
select(&t,s,s1);
}