查找排序实验报告.doc

实验十： 查找、排序 计算机学院 12级2班 121102013 李龙 实验目的： 掌握折半查找算法的思想。 实现折半查找的算法。 掌握常见的排序算法（插入排序、交换排序、选择排序等）的思想、特点及其适用条件。 能够分析各种算法的效率。 熟练的掌常见的排序算法的程序步骤。 实验内容： 1．建立一静态有序表。 2．用一个函数实现折半查找算法。 3．在主函数中输入一组数据，测试算法的正确性。 4. 按照快速排序思想实现快速排序算法。 5. 在主函数中输入一段数据，测试算法的正确性。 设计思路： 开始的时候提示输入一组数据。并存入一维数组中，接下来调用一系列查找算法对其进行处理。顺序查找只是从头到尾进行遍历。二分查找则是先对数据进行排序，然后利用三个标志，分别指向最大，中间和最小数据，接下来根据待查找数据和中间数据的比较不断移动标志，直至找到。二叉排序树则是先构造，构造部分花费最多的精力，比根节点数据大的结点放入根节点的右子树，比根节点数据小的放入根节点的左子树，其实完全可以利用递归实现，这里使用的循环来实现的，感觉这里可以尝试用递归。当二叉树建好后，中序遍历序列即为由小到大的有序序列，查找次数不会超过二叉树的深度。这里还使用了广义表输出二叉树，以使得更直观。哈希表则是利用给定的函数式建立索引，方便查找 总体设计： 静态表的存储结构 typedef struct { int *elem; int length; }sstable; void CreateData(int data[],int length);//为一个数组赋值 //此函数是折半查找函数。其中data是所查寻的数组，length是数组的长度。x是所要查找的数，返回的值是数据x在数组中的位置 int Bisearch(int data[],int x,int begin,int last);//折半查找函数，使用过程中只需要给出数组名字，要查找的数值x，数组的起始位置begin及末位置即可。 void PrintData(int data[],int length);//输出一个数组的所有元素。 定义void quickSort(int *arr,int l,int r)函数 实验结果： 输入查找数字：7 如上图 查找--得出结果 排序--得出结果 实验总结： 本次实验程序结构比较简单，无需复杂的函数调用。但是由于本人编程基础不够扎实，在面对需要很多数组声明和调用的时候，经常弄错，在编译的过程中出现了很多次内存调用出错的情况。后来发现是二维数组的定义上没有做好，引入了动态定义的方法解决了这一问题。 通过本次实验，加深了我对查找表的认识。但是，实验中也出现了问题，程序循环不能良好退出。希望经过以后的学习我能解决这些问题。 代码：查找代码---见附表1 排序代码—见附表2