下载文档原格式
数据结构最基础的十大算法数据结构是计算机科学中的重要分支，它研究如何组织和存储数据以便于访问和修改。
在数据结构中，算法是解决问题的关键。
下面将介绍数据结构中最基础的十大算法。
1. 线性搜索算法线性搜索算法是最简单的算法之一，它的作用是在一个列表中查找一个特定的元素。
该算法的时间复杂度为O(n)，其中n是列表中元素的数量。
2. 二分搜索算法二分搜索算法是一种更高效的搜索算法，它的时间复杂度为O(log n)。
该算法要求列表必须是有序的，它通过将列表分成两半来查找元素，直到找到目标元素为止。
3. 冒泡排序算法冒泡排序算法是一种简单的排序算法，它的时间复杂度为O(n^2)。
该算法通过比较相邻的元素并交换它们的位置来排序列表。
4. 快速排序算法快速排序算法是一种更高效的排序算法，它的时间复杂度为O(nlog n)。
该算法通过选择一个基准元素并将列表分成两部分来排序列表。
5. 插入排序算法插入排序算法是一种简单的排序算法，它的时间复杂度为O(n^2)。
该算法通过将每个元素插入到已排序的列表中来排序列表。
6. 选择排序算法选择排序算法是一种简单的排序算法，它的时间复杂度为O(n^2)。
该算法通过选择最小的元素并将其放在列表的开头来排序列表。
7. 堆排序算法堆排序算法是一种更高效的排序算法，它的时间复杂度为O(n log n)。
该算法通过将列表转换为堆并进行排序来排序列表。
8. 归并排序算法归并排序算法是一种更高效的排序算法，它的时间复杂度为O(n log n)。
该算法通过将列表分成两部分并将它们合并来排序列表。
9. 哈希表算法哈希表算法是一种高效的数据结构，它的时间复杂度为O(1)。
该算法通过将键映射到哈希表中的位置来存储和访问值。
10. 树算法树算法是一种重要的数据结构，它的时间复杂度取决于树的深度。
树算法包括二叉树、AVL树、红黑树等。
以上是数据结构中最基础的十大算法，它们在计算机科学中有着广泛的应用。
常见的字符串匹配算法分析比较字符串是计算机领域中最常见的数据结构之一。
而计算机领域中的一个重要任务就是查找和比较字符串。
在实际应用中，字符串匹配算法如匹配关键字、拼写检查、文本比较等，是一个必要且重要的工具。
在此，本文将为大家介绍几种常见的字符串匹配算法及其优缺点，在选择算法时可以参考。
1.朴素字符串匹配算法朴素字符串匹配算法，也被称为暴力匹配算法，是字符串匹配算法中最简单的算法。
其思路是从文本的第一个字符开始与模式串的第一个字符依次比较，如果不成功就将模式串向右移动一位，直到模式串匹配成功。
算法效率较低，但实现简单。
2.Boyer-Moore算法Boyer-Moore算法是一种高效的字符串查找算法，该算法通过先进行坏字符规则和好后缀规则的比较而快速跳过无用的匹配。
其基本思路是先将模式串从右往左匹配，当发现匹配不上时，通过坏字符规则将模式串向右移，在移动过程中通过好后缀规则进一步加快匹配速度。
Boyer-Moore算法适合于长串和短模串、任意字符集的串匹配。
3.KMP算法KMP算法是由Knuth-Morris-Pratt三个人设计的，是一种著名的字符串匹配算法。
KMP算法优化了朴素匹配算法，通过预处理模式串信息（即计算next数组），能够快速地匹配文本串。
其核心思想是通过next数组记录当前位置前缀字符串中的最长公共前后缀，并通过将模式串向右移动来加快匹配速度。
KMP算法适用于模式串较短但匹配次数较多的情况。
4.Rabin-Karp算法Rabin-Karp算法是一种依赖于哈希思想的字符串匹配算法。
该算法通过哈希函数将文本和模式串的哈希值计算出来，从而利用哈希表快速匹配。
相比较于前面介绍的算法，Rabin-Karp算法无须进行模式串的比较，它的匹配速度也较快。
总结：在选择字符串匹配算法时需要根据不同的实际需求来进行选择。
朴实算法虽然算法效率不高，但是它的实现简单理解容易；Boyer-Moore算法的应用范围广，特别适用于在字符集较大时的匹配；KMP算法比较简单，容易实现，并且适用于较短的模式串；Rabin-Karp算法能够快速匹配，而且能减少一部分的比较。
(完整版)《搜索算法》知识点总结1. 搜索算法的概念搜索算法是计算机科学中的一类算法，用于在一个数据集合中查找指定的数据项。
搜索算法的目标是通过最少的计算操作来找到目标数据项，以提高效率。
2. 常见的搜索算法2.1 线性搜索线性搜索是最简单的搜索算法之一，它从数据集合的第一个元素开始逐个比较，直到找到目标数据项或者遍历整个数据集合。
线性搜索的时间复杂度为O(n)，其中n为数据集合的大小。
2.2 二分搜索二分搜索是一种高效的搜索算法，它适用于有序的数据集合。
它将数据集合分为两部分，并与目标数据项进行比较，然后根据比较结果确定继续搜索的方向。
通过每次排除一半的数据，二分搜索的时间复杂度为O(log n)，其中n为数据集合的大小。
2.3 哈希搜索哈希搜索通过将数据项映射到哈希表中的特定索引位置来进行搜索。
通过哈希函数，可以快速找到目标数据项所在的位置。
哈希搜索的时间复杂度为O(1)，但需要额外的存储空间来存储哈希表。
2.4 深度优先搜索深度优先搜索是一种递归的搜索算法，它从起始点开始一直沿着一个路径搜索，直到找到目标数据项或者无法继续搜索。
如果搜索失败，则回溯到上一个节点，并探索其他路径。
深度优先搜索在有向图和无向图中均适用。
2.5 广度优先搜索广度优先搜索是一种逐层扩展的搜索算法，它从起始点开始，先访问所有直接相邻的节点，然后再访问相邻节点的邻居节点。
通过队列数据结构，广度优先搜索可以按层次进行遍历，直到找到目标数据项。
广度优先搜索适用于无权图和加权图。
3. 搜索算法的应用场景搜索算法在各种领域和实际问题中广泛应用，包括但不限于以下几个方面：- 文本搜索：在大规模的文本数据集中查找关键字或短语。
- 图像搜索：根据图像特征找到相似的图像。
- 数据库查询：根据指定条件查询数据库中的记录。
- 路径规划：在地图上找到最短路径或最优路径。
- 推荐系统：根据用户的兴趣和偏好推荐相关的内容。
- 人工智能：在机器研究和深度研究中的搜索空间优化等。
各种搜索引擎算法的分析和比较在互联网上搜索所需信息或资讯，搜索引擎成为了人们必不可少的工具。
然而，搜索引擎的搜索结果是否准确、全面，搜索速度是否快速等方面，关键在于搜索引擎的算法，因此，搜索引擎算法成为了搜索引擎核心竞争力的来源。
目前，主流的搜索引擎包括Google、Baidu、Yahoo、Bing等，但它们的搜索结果和排序结果却存在着很大的差异。
这些搜索引擎的搜索结果背后都有不同的算法，下面将对目前主流的几种搜索引擎的算法进行分析和比较。
1. Google算法Google算法是目前全球最流行的搜索引擎算法，其搜索结果广受用户信任。
Google算法最重要的要素是页面权重（PageRank），其名字最初来源于Google的创始人之一拉里·佩奇的名字。
页面权重是根据页面链接的数量和链接网站的权重计算得到的一个评分系统，也就是所谓的“链接分”。
除此之外，Google还有很多其他的评分规则，比如页面初始状态、页面内部链接等。
可以说，Google的算法非常复杂，它使用了很多技术来确保其搜索引擎结果的质量。
2. Baidu算法Baidu是中国主流的搜索引擎，其搜索算法相较于Google来说较为简单。
Baidu的搜索结果主要依靠页面的标题、关键词、描述等元素，因此其搜索结果的可靠性稍逊于Google。
不过，Baidu的形态分析算法却是非常出色的，可以识别图片和视频等多种形态的信息。
除此之外，Baidu还使用了一些人工智能技术，例如深度学习算法来优化搜索结果。
3. Bing算法Bing是由微软开发的搜索引擎，其搜索结果以关键词匹配为核心来实现。
在关键词匹配的基础上，Bing还使用了一些机器学习和推荐算法来优化搜索结果。
另外，Bing还使用类似Google的页面权重评分系统来实现页面的排序。
除此之外，Bing还注重在搜索结果页面中显示质量较高的结果，而不局限于排序前十的结果。
4. Yahoo算法Yahoo算法是基于文本内容分析的搜索引擎算法。
数据结构课程设计报告搜索算法效率比较的设计专业 计算机科学与技术学生姓名Xxxxx班级Xxxx 学号Xxxx 指导教师 Xxx完成日期2016年6月16日目录1.设计题目 (3)2.设计目的及要求 (3)2.1．目的 (3)2.2．要求 (3)3.设计内容 (3)4.设计分析 (4)4.1.空间复杂度 (5)4.2非递归线性搜索设计 (5)4.3递归线性搜索 (5)4.4二叉搜索设计 (6)5.设计实践 (7)5.1非递归线性搜索模块设计 (7)5.2递归线性搜索模块设计 (7)5.３二叉搜索模块设计 (7)5.4.主程序模块设计 (8)6测试方法 (10)7.程序运行效果 (11)8.设计心得 (12)搜索算法效率比较的设计1.设计题目给定一个已排序的由N个整数组成的数列{0,1,2,3,……,N-1}，在该队列中查找指定整数，并观察不同算法的运行时间。
考虑两类算法：一个是线性搜索，从某个方向依次扫描数列中各个元素；另一个是二叉搜索法。
要完成的任务是：分别用递归和非递归实现线性搜索；分析最坏情况下，两个线性搜索算法和二叉搜索算法的复杂度；测量并比较这三个方法在N=100，500，1000，2000,4000,6000,8000，10000时的性能。
2.设计目的及要求2.1．目的（1）需要同学达到熟练掌握C语言的基本知识和技能；（2）基本掌握面向对象程序设计的基本思路和方法；（3）能够利用所学的基本知识和技能，解决简单的程序设计问题；2.2．要求学生必须仔细阅读数据结构，认真主动完成课设的要求，有问题及时主动通过各种方式与教师联系沟通；要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己计划完成情况；独立思考，课程设计中各任务的设计和调试哦要求独立完成，遇到问题可以讨论，可以通过同学间相互讨论而解决。
3.设计内容任何程序基本上都是要用特定的算法来实现的。
算法性能的好坏，直接决定了所实现程序性能的优劣。
数据结构与搜索引擎算法的优化在当今信息化时代，搜索引擎在我们的生活中扮演着重要的角色。
而搜索引擎背后的数据结构和优化算法则是其高效运行的关键。
本文将探讨数据结构与搜索引擎算法的优化，并分析其对搜索引擎性能的影响。
一、数据结构的选择与搜索引擎性能搜索引擎需要处理大量的数据，如何高效地组织和存储这些数据成为一个关键问题。
数据结构的选择直接影响到搜索引擎的性能。
1.哈希表哈希表是一种常见的数据结构，其通过将关键字映射为索引来实现数据的快速访问。
在搜索引擎中，哈希表可用于存储网页的URL和相关信息，以便用户快速检索。
然而，哈希表在处理冲突和扩容时可能会带来较大的开销，需要进行优化。
2.倒排索引倒排索引是搜索引擎中常用的一种数据结构，用于实现关键字与文档之间的映射。
通过倒排索引，搜索引擎可以快速从大量的文档中找到包含用户查询关键字的文档。
倒排索引的构建需要对文档进行预处理、分词和排序等操作，提高了搜索效率。
3.红黑树红黑树是一种自平衡二叉搜索树，用于在搜索引擎中快速存储和检索数据。
红黑树的插入和删除操作比较高效，并且可以保持树的平衡。
在搜索引擎中，红黑树可用于存储关键字与对应网页的相关信息，提高搜索的效率。
二、搜索引擎算法的优化除了选择合适的数据结构，搜索引擎还需要通过算法的优化来提高搜索的效率和准确性。
1.排名算法排名算法是搜索引擎中最重要的算法之一，它决定了搜索结果的排序方式。
目前，常用的排名算法包括PageRank算法、TF-IDF 算法和BM25算法等。
这些算法通过分析页面的链接结构、关键字出现频率和相关性等指标，对网页进行排序，使用户能够获得最相关的搜索结果。
2.索引算法索引算法用于构建和更新搜索引擎的索引，以便用户能够快速找到相关的网页。
常见的索引算法包括倒排索引和B树索引等。
倒排索引基于关键字的出现频率和位置信息，快速定位到包含关键字的文档；而B树索引通过有序存储关键字，提高了搜索的效率。
3.查询优化算法查询优化算法用于对用户查询进行优化，提高搜索结果的准确性和响应速度。
深度优先搜索和广度优先搜索的比较和优化第一节比较一、深度优先搜索的特点是：1、从上面几个实例看出，可以用深度优先搜索的方法处理的题目是各种各样的。
有的搜索深度是已知和固定的，如例题2-4，2-5，2-6；有的是未知的，如例题2-7、例题2-8；有的搜索深度是有限制的，但达到目标的深度是不定的。
但也看到，无论问题的内容和性质以及求解要求如何不同，它们的程序结构都是相同的，即都是深度优先算法（一）和深度优先算法（二）中描述的算法结构，不相同的仅仅是存储结点数据结构和产生规则以及输出要求。
2、深度优先搜索法有递归以及非递归两种设计方法。
一般的，当搜索深度较小、问题递归方式比较明显时，用递归方法设计好，它可以使得程序结构更简捷易懂。
当搜索深度较大时，如例题2-5、2-6。
当数据量较大时，由于系统堆栈容量的限制，递归容易产生溢出，用非递归方法设计比较好。
3、深度优先搜索方法有广义和狭义两种理解。
广义的理解是，只要最新产生的结点（即深度最大的结点）先进行扩展的方法，就称为深度优先搜索方法。
在这种理解情况下，深度优先搜索算法有全部保留和不全部保留产生的结点的两种情况。
而狭义的理解是，仅仅只保留全部产生结点的算法。
本书取前一种广义的理解。
不保留全部结点的算法属于一般的回溯算法范畴。
保留全部结点的算法，实际上是在数据库中产生一个结点之间的搜索树，因此也属于图搜索算法的范畴。
4、不保留全部结点的深度优先搜索法，由于把扩展出的结点从数据库中弹出删除，这样，一般在数据库中存储的结点数就是深度值，因此它占用的空间较少，所以，当搜索树的结点较多，用其他方法易产生内存溢出时，深度优先搜索不失为一种有效的算法。
5、从输出结果可看出，深度优先搜索找到的第一个解并不一定是最优解。
例如例题2-8得最优解为13，但第一个解却是17。
如果要求出最优解的话，一种方法将是后面要介绍的动态规划法，另一种方法是修改原算法：把原输出过程的地方改为记录过程，即记录达到当前目标的路径和相应的路程值，并与前面已记录的值进行比较，保留其中最优的，等全部搜索完成后，才把保留的最优解输出。
数据结构中的查找算法总结静态查找是数据集合稳定不需要添加删除元素的查找包括：1. 顺序查找2. 折半查找3. Fibonacci4. 分块查找静态查找可以⽤线性表结构组织数据，这样可以使⽤顺序查找算法，再对关键字进⾏排序就可以使⽤折半查找或斐波那契查找等算法提⾼查找效率，平均查找长度：折半查找最⼩，分块次之，顺序查找最⼤。
顺序查找对有序⽆序表均适⽤，折半查找适⽤于有序表，分块查找要求表中元素是块与块之间的记录按关键字有序动态查找是数据集合需要添加删除元素的查找包括： 1. ⼆叉排序树 2. 平衡⼆叉树 3. 散列表 顺序查找适合于存储结构为顺序存储或链接存储的线性表。
顺序查找属于⽆序查找算法。
从数据结构线形表的⼀端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相⽐较，若相等则表⽰查找成功 查找成功时的平均查找长度为： ASL = 1/n(1+2+3+…+n) = (n+1)/2 ; 顺序查找的时间复杂度为O(n)。
元素必须是有序的，如果是⽆序的则要先进⾏排序操作。
⼆分查找即折半查找，属于有序查找算法。
⽤给定值value与中间结点mid的关键字⽐较，若相等则查找成功；若不相等，再根据value 与该中间结点关键字的⽐较结果确定下⼀步查找的⼦表 将数组的查找过程绘制成⼀棵⼆叉树排序树，如果查找的关键字不是中间记录的话，折半查找等于是把静态有序查找表分成了两棵⼦树，即查找结果只需要找其中的⼀半数据记录即可，等于⼯作量少了⼀半，然后继续折半查找，效率⾼。
根据⼆叉树的性质，具有n个结点的完全⼆叉树的深度为[log2n]+1。
尽管折半查找判定⼆叉树并不是完全⼆叉树，但同样相同的推导可以得出，最坏情况是查找到关键字或查找失败的次数为[log2n]+1，最好的情况是1次。
时间复杂度为O(log2n)； 折半计算mid的公式 mid = (low+high)/2;if(a[mid]==value)return mid;if(a[mid]>value)high = mid-1;if(a[mid]<value)low = mid+1; 折半查找判定数中的结点都是查找成功的情况，将每个结点的空指针指向⼀个实际上不存在的结点——外结点，所有外界点都是查找不成功的情况，如图所⽰。
常见查找算法的优缺点分析在计算机科学中，查找算法是一种用于在数据集合中查找特定元素的方法。
不同的查找算法在时间复杂度、空间复杂度和适用场景等方面存在差异。
下面我们就来详细分析几种常见查找算法的优缺点。
首先是顺序查找算法。
这是最简单也是最直观的一种查找方法。
它的基本思路是从数据集合的开头，依次比较每个元素，直到找到目标元素或者遍历完整个集合。
顺序查找的优点在于实现简单，理解容易，对于小型数据集或者无序数据集来说，是一种可行的选择。
而且，它不需要对数据进行预处理，如排序等操作。
然而，其缺点也很明显。
当数据量较大时，顺序查找的效率非常低，因为它的平均时间复杂度为 O(n)，其中 n 是数据集合的元素个数。
这意味着，随着数据量的增加，查找所需的时间会线性增长。
接下来是二分查找算法。
这种算法要求数据集合是有序的。
它通过不断将数据集一分为二，比较目标元素与中间元素的大小，从而缩小查找范围，逐步逼近目标元素。
二分查找的优点十分突出。
它的时间复杂度为 O(log n)，效率比顺序查找高得多。
在大型有序数据集上，能够显著减少查找时间。
但二分查找也有其局限性。
首先，它要求数据集必须是有序的，如果数据集经常变动，维护有序性的成本可能会很高。
其次，对于小型数据集，由于其实现相对复杂，可能不如顺序查找来得直接和高效。
然后是哈希查找算法。
哈希查找通过将关键码值映射到一个特定的地址，从而实现快速查找。
哈希查找的最大优点就是查找速度极快，平均时间复杂度接近O(1)，无论数据集的大小如何。
只要哈希函数设计得好，能够有效地避免冲突，就可以在常数时间内完成查找。
不过，哈希查找也并非完美。
哈希函数的设计是一个关键问题，如果设计不当，可能会导致大量的冲突，从而影响查找效率。
而且，当数据量增加时，可能需要重新调整哈希表的大小，这会带来一定的额外开销。
再说说插值查找算法。
它是二分查找的一种改进，根据要查找的关键字与查找表中最大最小关键字的比较结果，来选择合适的中间值进行比较。
第8 章排序技术课后习题讲解1. 填空题⑴排序的主要目的是为了以后对已排序的数据元素进行（）。
【解答】查找【分析】对已排序的记录序列进行查找通常能提高查找效率。
⑵对n个元素进行起泡排序，在（）情况下比较的次数最少，其比较次数为（）。
在（）情况下比较次数最多，其比较次数为（）。
【解答】正序，n-1，反序，n(n-1)/2⑶对一组记录（54, 38, 96, 23, 15, 72, 60, 45, 83）进行直接插入排序，当把第7个记录60插入到有序表时，为寻找插入位置需比较（）次。
【解答】3【分析】当把第7个记录60插入到有序表时，该有序表中有2个记录大于60。
⑷对一组记录（54, 38, 96, 23, 15, 72, 60, 45, 83）进行快速排序，在递归调用中使用的栈所能达到的最大深度为（）。
【解答】3⑸对n个待排序记录序列进行快速排序，所需要的最好时间是（），最坏时间是（）。
【解答】O(nlog2n)，O(n2)⑹利用简单选择排序对n个记录进行排序，最坏情况下，记录交换的次数为（）。
【解答】n-1⑺如果要将序列（50，16，23，68，94，70，73）建成堆，只需把16与（）交换。
【解答】50⑻对于键值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从键值为（）的结点开始。
【解答】60【分析】60是该键值序列对应的完全二叉树中最后一个分支结点。
2. 选择题⑴下述排序方法中，比较次数与待排序记录的初始状态无关的是（）。
A插入排序和快速排序B归并排序和快速排序C选择排序和归并排序D插入排序和归并排序【解答】C【分析】选择排序在最好、最坏、平均情况下的时间性能均为O(n2)，归并排序在最好、最坏、平均情况下的时间性能均为O(nlog2n)。
⑵下列序列中，（）是执行第一趟快速排序的结果。
A [da，ax，eb，de，bb] ff [ha，gc]B [cd，eb，ax，da] ff [ha，gc，bb]C [gc，ax，eb，cd，bb] ff [da，ha]D [ax，bb，cd，da] ff [eb，gc，ha]【解答】A【分析】此题需要按字典序比较，前半区间中的所有元素都应小于ff，后半区间中的所有元素都应大于ff。
1
数据结构课程设计
算法分析：搜索算法效率比较
专业 Xxxx
学生姓名 xxxx
班级 xxxxx
学
号 xxxxxxxxxxx
目录
1 设计题目 (1)
2 设计分析 (2)
3 设计实现 (3)
4测试方法 (6)
5测试结果 (7)
6 设计小结 (7)
1.设计题目
给定一个已排序的由N个整数组成的数列{0,1,2,3,……,N-1}，在该队列中查找指定整数，并观察不同算法的运行时间。
考虑两类算法：一个是线性搜索，从某个方向依次扫描数列中各个元素；另一个是二叉搜索法。
要完成的任务是：
分别用递归和非递归实现线性搜索；
分析最坏情况下，两个线性搜索算法和二叉搜索算法的复杂度；
测量并比较这三个方法在N=100，500，1000，2000，4000，6000，8000，10000时的性能。
3
2.设计分析
5
在实际测试中，当程序运行时间太快，会无法获得实际运行时间。
为了避免这种情
况，可以将同一操作运行K 遍，得到1秒以上的时间，再将结果除以重复次数K 得到平均时间。
若单重循环还不能达到目的，可用多重嵌套循环解决。
3 设计实现
#include <time.h>
#include <stdio.h>
clock_t start, stop; /* clock_t 是内置数据类型，用于计时 */
double duration; /* 记录函数运行时间，以秒为单位*/
/***********非递归线性搜索x ***********/
int IterativeSequentialSearch(const int a[],int x,int n)
{
int i;
for(i=0;i<n;i++)
if(a[i]==x) /* 找到x */
return i;
return -1; /* 未找到x */
/*********** 递归线性搜索x ***********/
int RecursiveSequentialSearch(const int a[],int x,int n)
{
if(n==0)
return -1; /* 未找到x */
if(a[n-1]==x) /* 找到x */
return n-1;
return RecursiveSequentialSearch(a,x,n-1); /* 继续递归线性搜索*/ }
/***********二叉搜索x ***********/
int BinarySearch(const int a[],int x,int n)
{
int low,mid,high; /*数组的左右边界*/
low=0;high=n-1;
while(low<=high)
{
mid=(low+high)/2; /*计算居中元素*/
if(a[mid]<x) /*比居中元素大*/
low=mid+1; /*改变左边界*/
else if(a[mid]>x) /*比居中元素小*/
high=mid-1; /*改变右边界*/
else return mid; /*找到x */
}
return -1; /* 未找到x */
}
int main ( )
/* clock() 返回函数运行时间*/
int i,n,x,a[10000];
long k,l;
printf("Please enter n:\n");
scanf("%d",&n); /* 输入数据*/
if(n<100||n>10000) /*处理异常输入*/
{
printf("error!");
return -1;
}
x=n; /* 指定要查找的数*/
for(i=0;i<n;i++) /*数组初始化*/
a[i]=i;
printf("Please enter iterations:\n"); /*为了更准确地计算运行时间，我们可以重复多次调用算法，再取平均值*/
scanf("%ld",&k);
if(k<1) /*处理异常输入*/
{
printf("error!");
return -1;
}
/*********** 非递归线性搜索***********/
start = clock(); /* 记录函数的开始时间*/
for(l=0;l<k;l++)
IterativeSequentialSearch(a,x,n);
stop = clock(); /*记录函数的结束时间*/
duration = ((double)(stop - start))/CLK_TCK; /*计算函数运行时间*/
printf("\nIterativeSequentialSearch:\nIterations:%ld\nTicks:%d\nTotal Time:%.8lf\nDuration:%.8lf\n",k,(int)(stop-start),duration,duration/k);/*输出花费时间*/
/*********** 递归线性搜索***********/
7
start = clock(); /*记录函数的开始时间*/
for(l=0;l<k;l++)
RecursiveSequentialSearch(a,x,n);
stop = clock(); /*记录函数的结束时间*/
duration = ((double)(stop - start))/CLK_TCK; /*计算函数运行时间*/
printf("\nRecursiveSequentialSearch:\nIterations:%ld\nTicks:%d\nTotal Time:%.8lf\nDuration:%.8lf\n",k,(int)(stop-start),duration,duration/k);/* 输出花费时间*/
/***********二叉搜索***********/
printf("\nIterations of Binary Search is 100 times of iterations more than other two searchs\n");
k=100*k; /*由于二叉搜索的时间比较快，为了避免出现0秒，二叉搜索算法调用的次数是线性搜索的100倍*/
start = clock(); /*记录函数的开始时间*/
for(l=0;l<k;l++)
BinarySearch(a,x,n);
stop = clock(); /*记录函数的结束时间*/
duration = ((double)(stop - start))/CLK_TCK; /*输出花费时间*/
printf("\nBinarySearch:\nIterations:%ld\nTicks:%d\nTotal
Time:%.8lf\nDuration:%.8lf\n",k, (int)(stop-start), duration,duration/k);/* 输出花费时间*/
return 1;
}
4.测试方法
1.按题目要求分别输入N = 100, 500, 1000, 2000, 4000, 6000, 8000, 10000, 对于每一
个N要选择不同的重复调用次数K，直到测试结果趋于稳定。
2.按要求输入数据，测试程序能否对输入内容进行数据合法性的检测并进行相应的异常处理。
例如N =0, -500, 100000,或者K=0,-1等，考察程序对异常情况进行处理的能力。
5 测试结果
6 设计小结
在这次为期五个半天的课程设计里，也让我从中有所收获。
虽说是五个半天，但在课后还是花了不少时间。
首先就由于用的是C语言编写，所以又拿起了大一的C教材课本，以此来弥补一些知识，但最主要的还是数据结构教材。
看教材中的程序时，发现一个程序设计就是算法与数据结构的结合体，看程序有时都看不懂，更别提自己编译了，觉得自己在这方面需要掌握的内容还有很多狠多。
通过这段时间的课程设计，我认识到数据结构是一门比较难的课程。
需要多花时间上机练习。
这次的程序训练培养了我实际分析问题、编程和动手能力，使我掌握了程序设计的基本技能，提高了我适应实际，实践编程的能力。
总的来说，这次课程设计让我获益匪浅，对数据结构也有了进一步的理解和认识。
但也让我认识到我还有很多的不足，需要大量的学习，以此来达到能力的提高及熟练的应用。
9。
