数据结构课程设计报告搜索算法效率比较的设计专业计算机科学与技术学生姓名Xxxxx班级Xxxx学号Xxxx指导教师Xxx完成日期2016年6月16日目录1.设计题目 (4)2.设计目的及要求...................................................................... 错误!未定义书签。

2.1．目的.................................................................................... 错误!未定义书签。

2.2．要求.................................................................................... 错误!未定义书签。

3.设计内容 (4)4.设计分析 (5)4.1.空间复杂度 (5)4.2非递归线性搜索设计 (6)4.3递归线性搜索 (6)4.4二叉搜索设计 (6)5.设计实践 (7)5.1非递归线性搜索模块设计 (7)5.2递归线性搜索模块设计 (8)5.３二叉搜索模块设计 (8)5.4.主程序模块设计 (8)6测试方法 (10)7.程序运行效果 (11)8.设计心得 (13)搜索算法效率比较的设计1.概述算法是为求解一个问题需要遵循的、被清楚地指定的简单指令的集合。

解决一个问题，可能存在一种以上算法，当这些算法都能正确解决问题时，算法需要的资源量将成为衡量算法优良度的重要度量，例如算法所需的时间、空间等。

1.1.设计目的数据结构课程设计是为数据结构课程独立开设的实践性教学环节。

数据结构课程设计对于巩固数据结构知识，加强学生的实际动手能力和提高学生综合素质是十分必要的。

课程设计的目的：1．要求学生达到熟练掌握C语言的基本知识和技能。

2．了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力。

3．提高程序设计和调试能力。

学生通过上机实习，验证自己设计的算法的正确性。

学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。

4．培养算法分析能力。

分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。

5．初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。

1.2.设计要求数据结构课程设计用 C/C++编程实现。

课程设计的一般步骤：1．问题描述与分析：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？限制条件是什么？2．数据结构设计：为实现每个功能选择的逻辑结构和存储结构，分析原因及合理性。

3．软件结构设计：设计软件模块之间的结构。

4．算法设计：算法的设计及算法分析。

每个部分的算法设计说明，可以用流程图描述算法。

5．程序编码：把详细设计的结果进一步求精为程序设计语言程序。

源程序要按照软件工程的规则来编写，要求结构清晰，重要功能部分要加上清晰的程序注释。

6．调试分析：掌握调试工具的各种功能，设计测试数据，测试输出的结果。

并进行算法的时间复杂度和空间复杂度的分析。

7．总结：课程设计过程的收获，遇到问题以及解决问题的思路和方法，程序调试能力的思考，对数据结构这门课程的认识及思考等。

8．编写课程设计报告。

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

2.设计题目给定一个已排序的由N个整数组成的数列{0,1,2,3,……,N-1}，在该队列中查找指定整数，并观察不同算法的运行时间。

考虑两类算法：一个是线性搜索，从某个方向依次扫描数列中各个元素；另一个是二叉搜索法。

要完成的任务是：➢分别用递归和非递归实现线性搜索；➢分析最坏情况下，两个线性搜索算法和二叉搜索算法的复杂度；➢测量并比较这三个方法在N=100，500，1000，2000，4000，6000，8000，10000时的性能。

3.设计内容任何程序基本上都是要用特定的算法来实现的。

算法性能的好坏，直接决定了所实现程序性能的优劣。

此次对有关算法设计的基本知识作了简单的介绍。

针对静态查找问题，以搜索算法的不同实现，并对非递归线性搜索算法、递归线性搜索算法和二叉搜索算法这三种方法进行了比较和分析。

算法是为求解一个问题需要遵循的、被清楚地指定的简单指令的集合。

解决一个问题，可能存在一种以上的算法，当这些算法都能正确解决问题时，算法需要的资源量将成为衡量算法优良度的重要度量，列如算法所需的时间、空间等。

算法是对问题求解过程的一种描述，是为解决一个问题或一类问题给出的一个正确的，有限长的操作序列。

由于查找一个数的过程，无论运用哪种算法对于电脑来说速度都是非常快的，都爱1ms之内，无法用计时函数测试出来。

所以为了能够直观准确地表示出各个算法间的差异，此程序用了循环查找的方法，具体的思想是：先随机生成3000个数作为查找的数据源，再随机生成3000个数作为被查找的数，让当前的查找算法运行一趟，这样就相当于运行了3000次。

这样还不具有一定的客观性，用flag标记出刚刚运行完查找后的结果，从数据源中找到目标的数标记为1，没找到的标记为0，并以此存为两个数组，最后我们就可以使用这两个数组再次分别进行循环查找，同时开始计时，如此一来就可以计算出各个算法在查找成功的情况下需要多少时间，反之在没查找到的情况下需多长时间了。

4.设计分析表（List）是用来存放多个相同类型数据的数据结构之一。

对表的所有操作都可以通过使用数组来实现。

在本题目中，使用数组来存放数列。

虽然数组是动态指定的，但是还是需要对表的大小的最大值进行估计。

一般需要估计得大一些，从而会浪费一定的空间。

本题目中传递数组时，以常数参数const a[]的方式，这样可以防止在搜索是数据被修改。

两种线性搜索算法的程序结构分别为以下所示。

非递归线性搜索从数组的最左边开始，逐个比较，直到找到所搜索的对象或者直到最后搜索失败。

递归搜索从最右开始搜索。

为什么不从最左边开始？因为从左边开始，每次递归除要传递待处理数列的左边界外，还需要传递运算数组的右边界（即N-1，这在本题目里也是变化的）。

从而右边开始，每次只需传递数组的右边界（左边界固定为0）。

所谓时间复杂度：时间复杂度在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。

但有时我们想知道它变化时呈现什么规律。

为此，我们引入时间复杂度概念。

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。

记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),...， k次方阶O(nk),指数阶O(2n)。

随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

最坏时间复杂度和平均时间复杂度：最坏情况下的时间复杂度称最坏时间复杂度。

一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。

这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。

在最坏情况下的时间复杂度为T(n)=0(n)，它表示对于任何输入实例,该算法的运行时间不可能大于0(n)。

平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。

此算法可以通过非递归线性搜索，线性递归搜索以及二叉法三种来进行搜索算法效率比较，从中辨析出三种算法中哪种算法最有效。

同时在主函数中用clock()来调用库函数4.1.空间复杂度一个程序的空间复杂度是指运行完一个程序所需内存的大小。

利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。

一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。

程序执行时所需存储空间包括以下两部分。

固定部分。

这部分空间的大小与输入/输出的数据的个数多少、数值无关。

主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。

这部分属于静态空间。

可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。

这部分的空间大小与算法有关。

4.2非递归线性搜索设计在一个已知无序队列中找出与给定关键字相同的数的具体位置。

原理是让关键字与队列中的二叔从第一个开始逐个比较，直到找出与给定关键字相同的数为止。

它对于表的结构没有任何要求，其缺点是查找效率低；其优点是算法简单。

4.3递归线性搜索递归作为一种算法在程序设计语言中广泛应用，是指函数/过程/子程序在运行过程序中直接或间接调用自身而产生的重入现象，程序调用自身的编程技巧成为递归。

一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次城府计算，大大地减少了程序的代码量。

递归的能力在于用有线的语句来定义对象的无限集合。

用递归思想写出来的程序往往十分简洁易懂。

递归就是在过程或函数里调用自身；在使用递增归策略时，必须有一个明确的递归结束条件，成为递归出口。

4.4二叉搜索设计二叉搜索的算法思想是将数列按有序化（递增或递减）排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。

通过一次比较，将查找区间缩小一般。

流程图：5.设计实践5.1非递归线性搜索模块设计非递归线性搜索的特点在于它的，每一次进行搜索时总是从数组的最左边开始，逐个比较，直到找到所搜索的对象或者直到最后搜索失败。

int IterativeSequentialSearch(const int a[],int x,int n){ int i;for(i=0;i<n;i++)if(a[i]==x)return i;return -1;}5.2递归线性搜索模块设计递归线性搜索模块设计的特点在于它，每一次进行搜索都是从最右边开始搜索。