数据结构课程设计—排序与查找.doc

[数 据 结 构 课 程 设 计] 排序与查找  [数 据 结 构 课 程 设 计] 实验目的 - 2 - 实验内容 - 2 - 排序 - 2 - 查找 - 2 - 需求分析 - 2 - 总体设计 - 3 - 总流程图： - 3 - 详细设计 - 4 - 排序 - 4 - 排序的函数模块分析 - 5 - 直接插入排序函数 - 5 - 希尔排序函数 - 6 - 冒泡排序函数 - 6 - 直接选择排序函数 - 7 - 查找 - 8 - 查找的函数模块分析 - 9 - 函数执行流程图 - 9 - 函数分析 - 12 - 测试结果 - 16 - 排序 - 16 - 查找 - 17 - 心得体会 - 19 - 源程序代码 - 19 - 参考文献 - 27 - 1、实验目的 1.1、掌握各种排序算法（直接插入排序、冒泡排序、希尔排序、选择排序）的思路核心，比较他们之间的优劣； 1.2、掌握各种查找算法（顺序查找、二分查找、数表的查找、散列表的查找）的思路核心，比较他们之间的优劣； 1.3、全面提高学生的程序设计、开发能力。 2、实验内容 2.1、排序，是数据处理中经常要使用的一种重要运算。所谓排序就是需要整理文件的记录，使得他按照关键字值递增（或递减）的次序排列起来，也就是说，若给定文件含有n个记录R1，R2，…，Rn，他们的关键字分别为K1，K2，…，Kn，我们要把n个记录重新排列为Ri1，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin（或Ki1≥Ki2≥…≥Kin）。 2.1、查找，又称为检索，也是数据处理中常用的一种重要运算。所谓的查找就是给定一个值K，在含有n个结点的表（或文件）中找出关键字等于给定值K的结点，若找到，则查找成功，输出该结点在表中的位置；否则查找失败，输出查找失败的信息。 我们通过程序的模块分析来进行说明排序与查找的相关联系以及它们的重要性，我们对每个模块的执行效果和空间、时间的复杂度进行详细的分析和说明，并表示排序的稳定性，排序、查找在不同情况下的不同使用效果。 3、需求分析 3.1、本演示程序中，输入值的类型为一组数值型数组，且定义了待排序数组的最大长度不得超过100； 3.2、输出值的类型是一组已经经过排序，最后生成的一组数值型数组； 3.3、改程序所要实现的功能，是能对一组长度为10的数值型数组按照个人选定的一个或多个排序算法进行排序，并将最后排序后的结果显示出来，从而达到方便用户了解各类排序算法的目的； 3.4、软件环境：Windows 7 Visual C++ 6.0简体中文版和Win-Tc简体中文版； 3.5、测试数据：1、82、63、4、65、69、37、98、39、46。 4、总体设计 排序问题是要把若干个无序数据元素序列排成一个有序序列。因此，排序问题的数据元素集合是线性结构的。在这个数据元素集合上也允许存取任意位置的数据元素，所以，排序问题的数据结构是线性表。 线性表的典型的存取结构主要是数组的顺序表和使用指针的链表。因为数组具有随机存取的特性，而链表不具有随机存取特性，所以，排序算法基本是基于顺序设计的。 分别实现顺序查找、二分查找、二叉排序树查找和哈希表查找，哈希表查找只需要选择其中的一种，二叉排序树必须实现构建、查找、插入和删除四个基本操作，输出各种排序的结果并进行比较。在运行结果中，可以选择查找方法，输 入数据后能完成查找并输出结果。 4.1、总流程图： 5、详细设计 5.1、排序 直接插入排序的基本思想是：顺序的把待排序的数据元素按其关键字值的大小顺序插入到已排序数据元素子集合的适当位置。子集合的数据元素个数从只有一个数据元素开始逐次增大，当子集合的大小最终等于集合大小相同时排序完毕。 希尔排序算法思想简单描述：在直接插入排序算法中，每次插入一个数，是有序序列增加1个节点，并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。D.L.Shell于1959年在以他的名字命名的排序算法中实现了这一思想。算法现将要排序的一组数据按某个增量d分成若干组，每组中记录的下标相差d对每组中的全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。 冒泡排序算法思想简单描述：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序要求相反时，就将它们互换。 选择排序算法思想简单描述：在要排序的一组数中，选出最小的一个数与第一个位置的数交换，然后在剩下的数当中再找最小的数与第二个位置的数交换，如此循环到倒数