滁 州 学 院
课程设计报告
课程名称： 数据结构与算法
设计题目： 综合查找算法
系 别： 计算机科学与技术
专 业： 网络工程
组 别： 第十一组
起止日期: 2009
年
5
月
17
日 ~ 2009
年
6
月
17
日
指导教师: 赵玉艳
1
计算机科学与技术系二○○九年制
课程设计题目 综合查找算法
组长 张阿丽 学号
2007210946
班级 2 班
系别 计算机科学与技术 专业 07 级网络工程
组员 刘洋 黄鑫 朱青青 张阿丽
指导教师 赵玉艳
课程设计目的
（1）熟练掌握 C 语言的基本知识和技能；
（2）基本掌握面向对象程序设计的基本思路和方法；
（3）能够利用所学的基本知识和技能，解决简单的程序
设计问题。
课程设计所需环境
WindowsXP VC6.0
课程设计任务要求
分别实现顺序查找、二分查找、二叉排序树查找和哈希表
查找，哈希表查找只需要选择其中的一种，二叉排序树必
须实现构建、查找、插入和删除四个基本操作，输出各种
排序的结果并进行比较。在运行结果中，可以选择查找方
法，输入数据后能完成查找并输出结果
课程设计工作进度计划
序号 起止日期 工 作 内 容 分工情况
1
2009.5.18—2009.5.21
详细代码 黄鑫---顺序查找 刘洋---折半查找和主
程序 朱青青--二叉排序树 张阿丽--哈
希表和主程序
2
2009.5.23—2009.5.26
调试与操作说明 黄鑫---顺序查找 刘洋---折半查找和主
程序 朱青青--二叉排序树 张阿丽--哈
希表和主程序
3
2009.5.28—2009.5.30
需求分析 黄鑫
4
2009.6.2—2009.6.7
概要设计 朱青青 刘洋 张阿丽
5
2009.6.9—2009.6.11
引言 张阿丽
6
2009.6.13—2009.6.16
总结与体会 黄鑫 刘洋 朱青青 张阿丽
教研室审核意见：
教研室主任签字： 年 月 日
2
课程设计任务书
目 录
1 需求分析.................................................................................................................................................4
1.1 课程设计题目.................................................................................................................................4
1.2 课程设计任务与要求.....................................................................................................................4
1.3 课程设计思想.................................................................................................................................4
1.4 软硬件运行环境及开发工具.........................................................................................................5
2 概要设计.................................................................................................................................................5
2.2 主要的数据结构.............................................................................................................................8
2.3 设计方法及原理.............................................................................................................................9
3 详细设计...............................................................................................................................................10
3.1 主函数代码...................................................................................................................................10
3.2 顺序查找部分代码.......................................................................................................................10
3.3 折半查找部分代码.......................................................................................................................11
4 调试与操作说明...................................................................................................................................13
4.1 主界面...........................................................................................................................................13
4.2 顺序查找.......................................................................................................................................13
4.3 折半查找.......................................................................................................................................14
4.4 二叉树查找...................................................................................................................................14
4.5 哈希表查找...................................................................................................................................15
课程设计总结与体会..............................................................................................................................15
致谢..........................................................................................................................................................16
参考文献..................................................................................................................................................16
3
1 需求分析
1.1 课程设计题目
这一组的课程设计题目是《综合查找算法》，需要实现各种查找，而且可以自由选择
查找算法和输入数据。
1.2 课程设计任务与要求
分别实现顺序查找、二分查找、二叉排序树查找和哈希表查找，哈希表查找只需要选
择其中的一种，二叉排序树必须实现构建、查找、插入和删除四个基本操作，输出各种排
序的结果并进行比较。在运行结果中，可以选择查找方法，输入数据后能完成查找并输出
结果。
1.3 课程设计思想
主函数是运用 C 语言中调用子函数的思想来实现的，如 case 'a': printf("顺序查找：\
n");
system("\"H:\\sh\\tui\\Debug\\tui.exe\""); break;
顺序查找是从输入的顺序表中第一个元素开始，逐个进行记录的关键字和给定值的比
较，如果某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；如果直至最
后一个记录，其关键字和给定值比较都不相等，则表明表中没有所查记录，查找不成功。
运用 Search 函数实现顺序查找。在 Search_seq 中，查找之前先对 ST.elem[0]的关键字赋值
key，目的在于免去查找过程中每一步都要检测整个表是否查找完毕。其中 ST.elem[0]是哨
兵，起到了监视哨的作用。
二分查找要先确定待查记录所在的范围（区间），以处于区间中间位置记录的关键字
和给定值比较，若相等，则查找成功，若不相等，则逐步缩小范围，直到新的区间中间位
置记录的关键字等于给定值或者查找区间的大小小于零（表明查找不成功）时为止。假设
指针 low 和 high 分别指示待查元素所在范围的下界和上界，指针 mid 指示区间的中间位置，
即 mid=[(low+high)/2]。二分查找可以用 Search_Bin 函数实现。
二叉排序树查找的查找过程和次优二叉树类似，当二叉排序树不为空时，首先将给定
值和根节点的关键字比较，若相等，则查找成功，否则将依据给定值和根节点的关键字之
间的大小关系，分别在左子树或右子树上继续进行查找。二叉排序树的结构通常不是一次
生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入，新插
入的结点一定是一个新添的叶子结点，并且是查找不成功时查找路径上访问的最后一个结
点的左孩子或右孩子结点。删除二叉排序树中的一个结点相当于删除有序序列中的一个记
录，若左右子树均为空树，则只需修改其双亲结点的指针；若只有左子树或只有右子树，
只要把左子树或右子树直接成为其双亲结点的左子树；若左右子树均不为空，可以把删除
结点的左右子树分别作为其双亲结点的左右子树，或者让删除结点的直接前驱或直接后继
代替删除结点，再从二叉排序树中删除它的直接前驱或直接后继。
哈希表查找，给定 K 值，根据造表时设定的哈希函数求得哈希表地址，若表中此位置
上没有记录，则查找不成功；否则比较关键字，若和给定值相等，则查找成功；否则根据
造表时设定的处理冲突的方法找“下一个地址”，直到哈希表中某个位置为“空”或者表中所填
记录的关键字等于给定值时为止。
4
1.4 软硬件运行环境及开发工具
软件环境：Windows XP visual C++ 6.0
硬件环境：处理器 双核
Interl(R) Pentiun(R)Dual CPU E2160@ 1.80GHz
Interl(R) Pentiun(R)Dual CPU E2160@ 1.80GHz
内存 2G
硬盘 160G
2 概要设计
2.1 流程图
主流程图
5
- 1
- 2
- 3
- 4
- 5
前往页