数据结构课设报告

精品文档 1欢迎下载 南京师范大学南京师范大学 数据结构 课程设计报告 姓名 学号 院系 计算机学院软件工程 班级 指导教师 精品文档 2欢迎下载 目录目录 数据结构数据结构 课程设计报告课程设计报告 1 1 一 必做题一 必做题 3 3 设计内容和要求 设计内容和要求 3 3 算法思想 算法思想 3 3 程序结构 程序结构 4 4 使用说明 使用说明 5 5 测试结果 测试结果 7 7 问题以及解决方案 问题以及解决方案 8 8 收获与体会 收获与体会 8 8 参考文献 参考文献 9 9 二 选做题二 选做题 9 9 设计内容和要求 设计内容和要求 9 9 算法思想 算法思想 9 9 程序结构 程序结构 1010 测试结果 测试结果 1212 精品文档 3欢迎下载 收获与体会 收获与体会 1515 一 必做题一 必做题 设计内容和要求 设计内容和要求 设计内容 四种排序算法的实现以及性能比较 要求 编程实现希尔 快速 堆排序 归并排序算法 要求随机产生 10000 个 数据存入磁盘文件 然后读入数据文件 分别采用不同的排序方法进行排序 并将结果存入文件中 算法思想 算法思想 在本课题中 我们根据要求对大量的随机数分别使用希尔排序 快速排序 堆排序 归并排序进行排序 并根据随机数数量的增加观察四种排序运行所耗 时间 进而分析出四种排序方法在不同情况下的性能好坏 1 希尔排序 希尔排序是对直接插入排序的一种改进 它的基本思想是 先将整个待排序记录序列划分为若干个小序列 在这些小序列中分别进行 直接插入排序 逐步扩大小序列的长度 减少小序列的个数 这样使待排序序 列逐渐处于更有序的状态 最后对全体序列进行一次直接插入排序 从而完成 整个排序过程 2 快速排序 精品文档 4欢迎下载 快速排序是一个递归的过程 其基本思想是 从待排序记录中选区一个记录 通常选取第一个记录 为枢轴 其关键字 为 k 将关键字值小于 k 的记录移到前面 而将关键字值大于 k 的移到后面 结果将待排序记录序列分成两个子表 最后将关键字值为 k 的记录插到分界线 处 我们将这个过程成为 划分 对划分后的子表继续按上述原则进行划分 直到所有子表不超过 1 为止 此时待排序记录序列就编程了一个有序序列 3 堆排序 堆排序是选择排序的一种改进 其基本思想是 首先用待排序的记录序列构造成一个堆 此时选出堆中所有记录的最大者 即堆顶记录 然后将它从堆中移走 通常将堆顶记录和堆中最后一个记录交换 并将剩余的记录再调整成堆 这样又找出了次大的记录 依此类推 直到堆中 只有一个记录为止 4 归并排序 归并排序是通过 归并 进行排序的一种方法 归并就是将两个或两个以上的 有序序列合并成一个有序序列的过程 其基本思想是 将若干有序序列逐步归并 最终归并为一个有序序列 5 计时函数 计时函数使用了高精度时间函数 QueryPerformanceFrequency 和 QueryPerformanceCounter 来实现毫秒级的计时功能 该函数接受一个指向函 数的指针参数 用于在两次查询机器内部计时器的位置插入所需要被计时的代 码 再将两次查询之差除以 CPU 时钟频率即可得到事件执行的精确时间 程序结构 程序结构 本程序由 Sort cpp Sort h 和 Sorts h 三部分组成 Sort h 头文件中实现 精品文档 5欢迎下载 了希尔排序 快速排序 堆排序以及归并排序这四种排序 Sorts h 头文件中 实现了产生随机待排数据 将数据写入文件 从文件读数据 计算排序所消耗 时间 以及输出执行时间的功能 Sort cpp 主函数负责提示操作以及调用头文 件里的函数 使用说明 使用说明 首先 运行程序 出现如下界面 提示用户按照步骤操作 从 1 到 4 依次逐步 执行 精品文档 6欢迎下载 精品文档 7欢迎下载 精品文档 8欢迎下载 测试结果 测试结果 未完成排序的待排数据已经存入名为 a 的文本文档中 精品文档 9欢迎下载 已完成排序的待排数据已经存入名为 b 的文本文档中 精品文档 10欢迎下载 问题以及解决方案 问题以及解决方案 本题的难点在于文件的读写和时间的计算 所以 我首先通过书籍和网络复习 和查阅这两个方面的相关资料 结合自己已经学过的或者编写过的程序来完成 这个题目 收获与体会 收获与体会 通过这次的课程设计 让我对希尔排序 快速排序 堆排序以及归并排序 有写代码的过程中 遇到了一些头疼的问题 比如将数据结构课程设计实验报 告 产生的待排序数据存入磁盘文件以及从磁盘文件中读取数据这些文件操作 需要通过翻阅书籍 查找资料才能解决 也意味着基本功还是有欠缺的 程序 的优化不仅仅看程序运行的正误 我们需要考虑的还有程序的健壮性 运算效 精品文档 11欢迎下载 率等各方面 虽然这个程序最后还是较为顺利的完成了 但是编程之路还有很 远 需要加强的地方还有很多 参考文献 参考文献 吉根林 陈波 王琼等 数据结构教程 C 版 电子工业出版社 二 选做题二 选做题 hashhash 设计内容和要求 设计内容和要求 设计内容设计内容 分别利用 Hash 技术和二分查找技术统计某个 C 源程序中的关键字出 现的频度 要求要求 用 Hash 表存储源程序中出现的关键字 利用 Hash 查找技术统计该程 序中关键字出现的频度 用线性探测法解决 Hash 冲突 用顺序表存储源程序中出现的关键字 利用二分查找统计该程序中关键字出 现的频度 算法思想 算法思想 1 建立 Hash 表用除留余数法 首先确定 32 个关键字 根据 Hash 函数申请一个长度为 41 的类数组 其中有一 个 string 型用来存储所查找的关键字和一个 int 型用来存储关键字的频度 并 初始化为 0 2 解决 Hash 表冲突用线性探测法 首先将整个数组看成一个循环数组 当发生冲突时 从冲突发生的下一个位置 精品文档 12欢迎下载 起 依次寻找空的 Hash 地址 直至找到空位将数据存入 或者无法解决冲突 回到原位 3 建立顺序表用冒泡排序法 因为二分查找的顺序表必须是有序的 所以通过冒泡排序建立有序顺序表 4 文件读取 考虑关键字的识别 还要考虑其他字符会不会被误识别 程序结构 程序结构 程序中的变量 程序中的变量 KeyHash KeysHashList 41 存放关键字的Hash表 用于Hash查找 int HashCount 0 记录 Hash 查找的比较次数 KeyBin KeysBinList 32 存放关键字的顺序表 用于二分查找 int BinCount 0 记录二分查找的次数 class KeyHash Hash存储关键字的类 public KeyHash freq 0 初始化此关键字出现的频率为0 string kw 记录此关键字 int freq 记录此关键字出现的频率 精品文档 13欢迎下载 class KeyBin 顺序存储关键字的类 public KeyBin freq 0 初始化此关键字出现的频率为0 string kw 记录此关键字 int freq 记录此关键字出现的频率 程序中的函数 程序中的函数 1 main cpp文件 main 函数 为主函数 调用其他函数 2 Hash h文件 包含关于hash查找统计的功能 createHash 建立hash表 HashSearch 读入文件 进行hash查找统计 Print HSR 输出Hash查找统计的结果 Hash BackToOrigin 在重新读入文件时 把Hash表状态回到最初状态 精品文档 14欢迎下载 3 Binary h文件 包含关于二分查找统计的功能 createBin 建立顺序表 BinSearch 读入文件 进行二分查找统计 Print BSR 输出二分查找统计的结果 Bin BackToOrigin 在重新读入文件时 把顺序表状态回到最初状态 精品文档 15欢迎下载 测试结果 测试结果 精品文档 16欢迎下载 精品文档 17欢迎下载 精品文档 18欢迎下载 精品文档 19欢迎下载 收获与体会 收获与体会 通过这次课程设计让我对 Hash 查找技术和二分查找技术有了更加深刻的认 识和理解 Hash 技术把关键码通过散列函数计算出 Key 直接得到关键码的存储地址 大大提高了查找效率 但它也并非完美 用 Hash 表存储关键码时容易产生冲突 尽管用线性探测法可以解决 但随之产生了堆积 堆积会大大的降低查找效率 甚至效率