概要设计
题目1：
顺序查找和折半查找
typedef struct
{
int key;
int data;
}Node;
题目2：
typedef struct Node
{
int data;
struct Node *lchild,*rchild;
}Node,*BiTree;
详细设计
题目1：
bool cha_zao1(Node ELEM[],int n,int e)
else q->lchild=s->lchild;
free(s);
}
}
void DeleteBST(BiTree &T,int e)
{
if(T)
{
if(e==T->data) Delete(T);
else if(e>T->data) DeleteBST(T->rchild,e);
else DeleteBST(T->lchild,e);
{//a中有n个元素，按键值key由小到大排序,查找e是否存在
int low,mid,high;
low=0;
high=n-1;
while(low<high)
{
mid=(low+high)/2;
if(ELEM[mid].key==e)return true;
else if(e>ELEM[mid].key)low=mid+1;
q=p;
p=p->lchild;
free(p);
}
else if(!p->lchild)
{
q=p;
p=p->rchild;
free(q);
}
else
{
q=p;
s=p->lchild;
while(s->lchild){q=s;s=s->lchild;}
p->data=s->data;
if(q!=p)q->rchild=s->lchild;
}
}
调试分析
问题分析
1.对折半查找端点处元素的处理不太熟悉
2.在删除二叉排序树中的元素的时候代码经常出错，问题出在指针的使用上。
总结：
顺序查找是非常简单的算法，但是元素很多的时候效率非常低。折半查找克服了一部分缺点，但是要求必须是关键字序列是有序的。
测试结果
题目2：二叉排序树的建立查找插入及删除运算
在采用二叉链表存储结构的基础上，实现二叉排序树的以下运算：
（1）实现在二叉排序树上查找指定关键字的运算；
（2）实现在二叉排序树上插入一个关键字的运算；
（3）实现在二叉排序树上删除指定关键字的运算；
（4）实现二叉排序树的中序遍历运算，输出中序遍历序列；
（5）从空的二叉排序树开始，根据一个关键字序列，调用实现插入运算的函数，建立二叉排序树。
}
int main()
{
int i,n,k;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&ELEM[i].key);
printf("输入待查找元素:\n");
scanf("%d",&k);
if(cha_zao1(ELEM,n,k))printf("YES\n");
if(T->rchild)InTraverse(T->rchild,Visit);
}
return;
}
void Insert(BiTree &T,int e)
{//插入函数
BiTree p,s;
if(!Search(T,e,NULL,p))//查找不成功
{
s=(BiTree)malloc(sizeof(Node));
{
scanf("%d",&e);
Insert(T,e);
}
printf("中序遍历序列为:\n");
InTraverse(T,Visit);//遍历运算
printf("\n输入待查找元素:\n");
scanf("%d",&m);
if(Search(T,m,f,p))printf("YES\n");
else printf("NO\n");
程序设计上机实验报告
姓名
学号
时间
环境
VC++
题目及要求
题目1：顺序查找，折半查找
用顺序存储结构表示查找表，实现以下运算要求：
（1）建立一个整数数据文件datafile;
（2）从文件datafile读取数据，并导入一维数组中;
（3）用顺序查找方法查找指定元素（由键盘输入），并显示查找结果；
（4）先对数组中的元素进行排序，分别用递归和非递归两种方式实现折半查找方法
}
void Visit(int e)
{//访问函数
printf(" %d ",e);
}
void InTraverse(BiTree T,void(*Visit)(int e))
{//中序遍历函数
if(T)
{
if(T->lchild)InTraverse(T->lchild,Visit);
Visit(T->data);
else high=mid-1;
}
return false;
}
bool cha_zao2(Node ELEM[],int n,int e)
{
int i;
for(i=0;i<n;i++)
if(ELEM[i].key>e)break;
if(ELEM[i].key==e)return true;
return false;
s->data=e;
s->lchild=NULL;
s->rchild=NULL;
if(!p)T=s;
else if(e<(p->data))p->lchild=s;
else p->rchild=s;
}
}
void Deleteree q,s;
if(!p->rchild)
{
{//查找函数
if(!T){p=f; return false;}
else if(e==T->data){p=T;return true;}//查找成功
else if(e<(T->data))return Search(T->lchild,e,T,p);
else return Search(T->rchild,e,T,p);
else printf("NO\n");
return 0;
}
题目2：
int main()
{
int e,m,n,i;
BiTree T,p,f;
T=NULL;
p=NULL;
f=NULL;
printf("请输入元素个数:\n");
scanf("%d",&n);
printf("输入元:\n");
for(i=0;i<n;++i)
printf("输入待删除元素:\n");
scanf("%d",&m);
DeleteBST(T,m);
printf("删除后的中序遍历序列:\n");
InTraverse(T,Visit);//遍历运算
return 0;
}
bool Search(BiTree T,int e,BiTree f,BiTree &p)