发布时间 : 星期三 文章查找 二叉树更新完毕开始阅读75a27f85fe4733687f21aa8d
查找算法-二叉树(设计性) 实验目的
1、掌握查找的特点。
2、掌握折半查找的基本思想及其算法。
3、熟悉二叉排序树的特点,掌握二叉排序树的插入、删除操作。
实验要求
1.认真阅读和掌握本实验的算法。 2.上机将本算法实现。
3.保存程序的运行结果,并结合程序进行分析。
4.上机过程中,能够熟练运用高级语言的程序调试器DEBUG调试程序。 5.上机后,认真整理源程序及其注释,完成实验报告(包括源程序、实验结果、算法分析、心得体会等)。
实验内容
1、设有关键字序列k={ 5 ,14 ,18 ,21 ,23 ,29 ,31 ,35 },查找key=21和key=25的数据元素。
2、根据关键字序列{45、24、53、12、37、93}构造二叉排序树,并完成删除关键字53和24的操作。
3、可以完成作业布置的内容。题目:对输入的n个整数进行折半查找
实验步骤
1、折半查找
(1)从键盘输入上述8个整数5 ,14 ,18 ,21 ,23 ,29 ,31 ,35,存放在数组bub[8]中,并输出其值。
(2)从键盘输入21,查找是否存在该数据元素,若存在,则输出该数据元素在表中的位置,否则给出查找失败的信息。
(3)从键盘输入25,查找是否存在该数据元素,若存在,则输出该数据元素在表中位置,否则给出查找失败的信息。
程序清单
#include
typedef char KeyType; typedef int OtherType;
typedef struct {
KeyType key;
OtherType other_data;
}RecordType;
typedef struct {
RecordType r[LIST_SIZE+1]; int length;
}RecordList;
void createlist(RecordList *l) {
int i; int len; int ch;
printf(\请输入线性表的长度:\scanf(\l->length = len;
}
for(i=1; i<=len; i++) { }
printf(\请输入线性表的第%d个元素:\fflush(stdin); scanf(\l->r[i].key = ch;
int BinSrch(RecordList l, KeyType k) {
int low,high,mid; }
low=1;
high=l.length;/*置区间初值*/ while( low <= high) { } return (0);
mid=(low+high) / 2; if (k==l.r[mid]. key)
return (mid);/*找到待查元素*/
else
if (k high=mid-1;/*未找到,则继续在前半区间进行查找*/ else low=mid+1;/*继续在后半区间进行查找*/ void main() { } RecordList l; int locate; KeyType k; createlist(&l); printf(\请输入要查找的元素:\fflush(stdin); scanf(\locate = BinSrch(l,k); if(locate == 0) else printf(\该元素在表中的位置为%d\\n\printf(\未找到!\\n\ 运行结果 实验心得 自己对折半查找的基本思想和算法设计思路还不是很清晰,在实验时遇到很 多问题都不能及时解决,