数据结构--查找的设计实现.doc

查找 实验日志 指导教师 刘锐 实验时间：2010 年 12月 06 日 学院 数理 专业 数学与应用数学 班级 学号 姓名 实验室 S 331-A 实验题目： 查找 实验目的：掌握顺序查找、折半查找及二叉排序树上查找的基本思想和算法实现，了解怎样对各种查找方法进行时间性能（平均查找长度）分析。 实验要求： 分析、理解程序 设计一组有序数据和一组随机数据输入，分别对线性表进行折半查找和顺序查找，比较它们的查找速度。 将（45，24，55，12，37，53，60，28，40，70）中关键字依次插入初态为空的二叉排序树中，给出树的先序序列。 实验主要步骤： 一 理解各种查找的基本思想 顺序查找的基本思想：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值K相比较，若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。 折半查找（二分查找）的基本思想：在有序的线性表中，从初始的查找区间R[1..n]开始，每经过一次与当前查找区间的中点位置上的结点关键字的比较，就可确定查找是否成功，不成功则当前查找区间就缩小一半。重复这一过程直到找到关键字为K 的结点，或者直至当前查找区间为空（即查找失败）时为止。 二叉排序树上的查找（BinSearch . c） 二叉排序树的定义：或者是一棵空树；或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于根结点的值； 它的左、右子树也分别为二叉排序树。 基本思想：当二叉排序树不空时，首先将给定值K和根结点的关键字比较，若相等，则查找成功，否则将依据给定值和根结点的关键字之间的大小关系，分别在左子树或右子树上继续进行查找。 二 在VC6.0的打开窗口中输入各种查找的程序代码，调试，编译，连接，运行。 1，顺序查找时输入一组随机的7个数字8，10，5，14，25，16，34，需要查找的数字为25，执行结果为下图（1）。 2，折半查找时输入一组有序数的7个数字1，3，5，7，9，11，13，需要查找的数为11，执行结果为下图（2） 3，二叉排序树上查找时，将（45，24，55，12，37，53，60，28，40，70）中关键字依次插入初态为空的二叉排序树中，需要查找的数为55，执行结果为下图（3） 所得到的二叉排序树为： 该二叉排序树的先序序列为45，24，12，37，28，40，55，53，60，70 实验结果： 图（1） 图（2） 图（3） 心得体会：通过这次实验，我基本理解了顺序查找、折半查找及二叉排序树上查找的基本思想和算法实现。我认为在某种时间性能上折半查找的查找速度要快于顺序查找。但折半查找只针对有序序列。二叉排序树上的查找也是一种比较好的查找方法。总之，不同的序列，应该选用最合适的查找方法，这样可以使平均查找的长度更短。从而节省查找的时间。 附加：各种查找的程序代码 顺序查找和折半查找 #includestdio.h #includestdlib.h #define Max 100 //假设文件长度 typedef int KeyType; //自定义数据类型 typedef struct{ //定义记录类型 KeyType key; //关键字项 }RecType; typedef RecType SeqList[Max+1]; //SeqList为顺序表，表中第0个元素作为哨兵 int n; //实际顺序表的长度 int SeqSearch(SeqList R,KeyType K) { int i; R[0].key=K; //设置哨兵 for(i=n;R[i].key!=K;i--); //从表后往前找 return i; //若i为0，表示查找失败；否则R[i]是要找的结点 } int BinSearch(SeqList R,KeyType K) { int low=1,high=n,mid; //置当前查找区间上、下界的初值 while(low=high){ //当前查找区间R[low..high]不空 mid=(low+high)/2; if(R[mid].key==K) return mid; //查找成功返回