文档介绍：数据结构课程设计报告
搜索算法效率比较的设计
专业
计算机科学与技术
学生姓名
Xxxxx
班级
Xxxx
学号
Xxxx
指导教师
Xxx
完成日期
2016年6月16日
目录
3
3
3
3
3
4
5
5
5
6
7
7
7
7
8
6测试方法 10
11
12
搜索算法效率比较的设计

给定一个已排序的由N个整数组成的数列{0,1,2,3,……,N-1},在该队列中查找指定整数,并观察不同算法的运行时间。考虑两类算法:一个是线性搜索,从某个方向依次扫描数列中各个元素;另一个是二叉搜索法。要完成的任务是:分别用递归和非递归实现线性搜索;分析最坏情况下,两个线性搜索算法和二叉搜索算法的复杂度;测量并比较这三个方法在N=100,500,1000,2000,4000,6000,8000,10000时的性能。

(1)需要同学达到熟练掌握C语言的基本知识和技能;
(2)基本掌握面向对象程序设计的基本思路和方法;
(3)能够利用所学的基本知识和技能,解决简单的程序设计问题;

学生必须仔细阅读数据结构,认真主动完成课设的要求,有问题及时主动通过各种方式与教师联系沟通;要发挥自主学习的能力,充分利用时间,安排好课设的时间计划,并在课设过程中不断检测自己计划完成情况;独立思考,课程设计中各任务的设计和调试哦要求独立完成,遇到问题可以讨论,可以通过同学间相互讨论而解决。

任何程序基本上都是要用特定的算法来实现的。算法性能的好坏,直接决定了所实现程序性能的优劣。此次对有关算法设计的基本知识作了简单的介绍。针对静态查找问题,以搜索算法的不同实现,并对非递归线性搜索算法、递归线性搜索算法和二叉搜索算法这三种方法进行了比较和分析。
算法是为求解一个问题需要遵循的、被清楚地指定的简单指令的集合。解决一个问题,可能存在一种以上的算法,当这些算法都能正确解决问题时,算法需要的资源量将成为衡量算法优良度的重要度量,列如算法所需的时间、空间等。算法是对问题求解过程的一种描述,是为解决一个问题或一类问题给出的一个正确的,有限长的操作序列。
由于查找一个数的过程,无论运用哪种算法对于电脑来说速度都是非常快的,都爱1ms之内,无法用计时函数测试出来。所以为了能够直观准确地表示出各个算法间的差异,此程序用了循环查找的方法,具体的思想是:先随机生成3000个数作为查找的数据源,再随机生成3000个数作为被查找的数,让当前的查找算法运行一趟,这样就相当于运行了3000次。
这样还不具有一定的客观性,用flag标记出刚刚运行完查找后的结果,从数据源中找到目标的数标记为1,没找到的标记为0,并以此存为两个数组,最后我们就可以使用这两个数组再次分别进行循环查找,同时开始计时,如此一来就可以计算出各个算法在查找成功的情况下需要多少时间,反之在没查找到的情况下需多长时间了。

表(List)是用来存放多个相同类型数据的数据结构之一。对表的所有操作都可以通过使用数组来实现。在本题目中,使用数组来存放数列。虽然数组是动态指定的,但是还是需要对表的大小的最大值进行估计。一般需要估计得大一些,从而会浪费一定的空间。本题目中传递数组时,以常数参数const a[]的方式,这样可以防止在搜索是数据被修改。
1
2
3
………………
N-1
两种线性搜索算法的程序结构分别为以下所示。非递归线性搜索从数组的最左边开始,逐个比较,直到找到所搜索的对象或者直到最后搜索失败。递归搜索从最右开始搜索。为什么不从最左边开始?因为从左边开始,每次递归除要传递待处理数列的左边界外,还需要传递运算数组的右边界(即N-1,这在本题目里也是变化的)。从而右边开始,每次只需传递数组的右边界(左边界固定为0)。
所谓时间复杂度:时间复杂度 在刚才提到的时间频度中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此,我们引入时间复杂度概念。一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级