查找算法.docx
- 文档编号:15741399
- 上传时间:2023-07-07
- 格式:DOCX
- 页数:13
- 大小:120.01KB
查找算法.docx
《查找算法.docx》由会员分享,可在线阅读,更多相关《查找算法.docx(13页珍藏版)》请在冰点文库上搜索。
查找算法
课程设计(实习)评审表
姓名
贺泽
学院
计算机与电子信息工程学院
学号
090910047
专业班级
电信0902
题目
各种查找算法的实现
评
审
意
见
评审成绩
指导教师签名
职称
评审时间
年月日
课程设计(实习)作品验收表
题目
各种查找算法的实现
参与人员
姓名
贺泽
班级
电信0902
学号
090910047
设计任务与要求:
首先给定数组长度,按顺序任意输入一组所给定长度的数据组,输入完毕后,执行查找功能,若输入的数据在数组中出现,则显示查找成功,否则,查找失败,并显示结果。
作品完成情况:
在程序编译和调试过程没出现错误报告,但是无法完成相关功能,只能输入数据组,无法完成查找功能,经过反复检查,case语句后的数字写错了,导致无法调用该段程序功能,修改后能正常运行,并实现查找功能。
验收情况:
验收教师签名:
___________
年月日
目录
1设计任务与要求1
1.1设计目的、任务和要求1
1.2设计计划1
2概要设计1
2.1系统功能描述1
3总体设计1
4详细设计2
4.1流程图2
4.2存储结构设计2
4.3主要算法设计3
4.4运行流程说明3
4.5运算结果3
5系统实现与测试4
5.1程序测试4
5.2运行结果4
6收获与体会6
参考文献6
附录7
各种查找算法的实现
1设计任务与要求
1.1设计目的、任务和要求
目的:
通过二周的课程设计,加深对c语言的运用,以及对数据结构的进一步学习,构建理论运用到实践的思维,开发创新能力。
任务和要求:
用程序实现查找功能,对于给定任意长度的数据组,输入指定长度数据组,然后再输入任意一个数值,通过程序的查找功能,实现自动查找功能,并显示该数据是否在该数组中,通过所写程序的给定功能,完成查找的整个过程。
1.2设计计划
时间:
2011年10月
地点:
湖南商学院实验楼
方式:
Windows2000以上操作系统
编译环境:
VisualC++6.0以上编译环境
2概要设计
2.1系统功能描述
我所编写的查找程序主要完成数据的查找并显示,根据二分法的特点编写的,主要包括以下几个模块。
第一个模块是创建数据存储单元list,用来存储输入的一组数据,第二个模块Mid用来进行折半查找,第三个模块是case语句用来实现switch循环语句,用来描述几种可能的情况并进行判断运行,第四个模块是主函数的设计,判断输入是否符合要求,决定运行是否继续。
若输入数据不符合规格或溢出,提示输入错误。
若输入不在查找范围内,则提示无法找到。
3总体设计
查找算法有很多种,我所选的程序是运用的二分查找法,二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。
因此,折半查找方法适用于不经常变动而查找频繁的有序列表。
首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。
重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
对于无序表,采用折半查找之前,需要排序,根据采用排序算法的不同,此时整个折半查找的时间复杂度需要考虑排序的时间,而不仅仅是折半查找的时间复杂度。
二分查找只适用顺序存储结构。
为保持表的有序性,在顺序结构里插入和删除都必须移动大量的结点。
因此,二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。
4详细设计
4.1流程图
图1二分法查找算法流程图
4.2存储结构设计
在该程序的运行调试过程我输入的数据是整型,所需储存的数据是一个输入的一维数组的整数,只要采用一维数组(a[n])来储存就可以了。
而对于查找过程会出现小数的情况,采用数据类型浮点型(float)。
4.3主要算法设计
该程序本身就是一个查找算法,对输入的数据进行查找,用树杈进行堆放存栈,并对节点进行比较,输出查找的结果。
二分查找又称折半查找,它是一种效率较高的查找方法。
二分查找要求:
线性表是有序表,即表中结点按关键字有序,并且要用向量作为表的存储结构。
不妨设有序表是递增有序的。
它的基本思想是,将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 查找 算法