1、 两种常用查找算法的 比较与实现 摘摘 要：要：本次课程设计主要研究几种常用查找算法的比较与实现，查找的算法有很多种： 静态查找表的顺序表、有序表、索引顺序表等查找结构；动态查找表的二叉排序树、哈 希查找等查找结构。本次的课程设计主要研究两种常见的查找算法：顺序查找和折半查 找，分析比较它们的时间复杂度，并且在此基础上用 C 语言对它们进行算法编程、调试 和运行。 关键词：关键词：C 语言；顺序查找；折半查找;时间复杂度。 1 1 引引 言言 “数据结构”在计算机科学中是一门综合性的专业基础课，“数据结构”的研究不 仅涉及到计算机硬件的研究范围，而且和计算机软件的研究有着密切的关系无论是编译
2、程序还是操作系统，都涉及到数据元素在存储器中的分配问题。在研究信息检索时也必 须考虑如何组织数据，一遍查找和存取数据元素更为方便。因此，可以认为“数据结构” 是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。 课程设计是我们专业课程知识综合应用的实践训练，是实践性教学的一个重要环 节。而数据结构的课程设计，更要求学生在数据结构的逻辑特性和物理表示、数据结构 的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程 序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。 在日常生活中，人们几乎每天都要进行“查找”工作。例如，在电话号码薄中查阅 “某单
3、位”或“某人”的电话号码；在字典中查阅“某个词”的读音和含义等等。而同 样地，在各种系统软件和应用软件中，也存在“查找” ：如编译程序中符号表、信息处 理表中相关信息的查找。所以， “查找”就是在一个含有众多的数据元素（或记录）的 查找表中找出某个“特定的”数据元素（或记录） 【1】。 在计算机中进行查找的方法也会随数据结构不同而不同。在此，引入“查找表”的 概念：同类数据元素构成的集合。所以，这次的课程设计就可以从静态查找表的几种典 型的算法来实现对数据元素的查找的算法和操作的实现和比较。 1.11.1 课程设计背景课程设计背景 数据结构课程设计作为独立的教学环节，是计算机相关专业集中实践环
4、节系列 之一，是学习完数据结构课程后进行的一次全面的综合练习。所以需要我们了解并 掌握数据结构与算法的设计方法，并且具备初步的独立分析和设计能力，同时要掌握软 件开发过程的问题分析、系统设计、程序编码测试等基本方法和技能，提高综合运用所 学的理论知识和方法独立分析和解决问题的能力。所以这次课程设计的目的在于：加强 学生对 C 语言的基本知识和技能；加深对数据结构基础理论和基本知识的理解，提高解 决实际问题的实践能力；同时帮助调动学生的积极性和能动性，培养学生的自学、动手 能力。 1.21.2 课程设计目标课程设计目标 本次课程设计， 我准备用不同的两种常见的查找方法： 针对顺序查找表中查找方法
5、， 如顺序查找、折半查找等。并且通过用这些算法实现对某个“特定的”数据元素（关键 字）的查找，分析这些操作的性能：它们各自的时间复杂度、空间复杂度和其它的一些 性能，同时记录每种查找方法的优缺点，比较得出它们的查找效率和查找范围。 2 2 设计概要设计概要 2.1 2.1 问题描述问题描述 对于不同的查找算法，它们各自的时间复杂度和空间复杂度不同，查找的思想和算 法也明显不同， 所以要分析它们的特点和效率， 我们要多方面比较： 要比较时间复杂度， 我们可以从它们的查找长度侧面比较出来；而它们算法的实现就要熟悉它们的查找思 想，熟练应用 C 语言编写合适的程序。 2.2 2.2 设计思路设计思路
6、 静态查找表有顺序表和链式表两种表示方法，在这次的课程设计里，我用顺序 存储表来表示这两种查找算法的程序。 我的设计思路及步骤如下： （1）熟悉两种算法的编程思想,画出流程图。 （2）先编写两种算法的子程序，再遍写主程序调用它们。 （3）分步调试子程序和主程序，直到不再出现错误，然后运行程序，检查是否和 自己当初的设想一样，一直到结果能让自己满意。 （4）比较得出两种查找算法的优缺。 2.3 2.3 相关的知识点相关的知识点 （1 1）C C 语言表示静态查找表的顺序存储结构语言表示静态查找表的顺序存储结构 typedef struct ElemType *elem; /数据元素存储空间基址，建表时按实际长度分配，0 号单元 留空 int length; /表的长度 SSTable; （2 2）查找算法）查找算法的衡量指标的衡量指标 查找可能产生“成功”与“不成功”两种结果，但在实际应用的大多数情况 下，查找成功的可能性比不成功的可能性大得多，特别是在记录数中 n 很大时， 查找不成功的概率可以忽略不计。当查找不
