数据结构课程设计两种常用查找算法比较与实现.doc

两种常用查找算法的 比较与实现 摘 要：本次课程设计主要研究几种常用查找算法的比较与实现，查找的算法有很多种：静态查找表的顺序表、有序表、索引顺序表等查找结构；动态查找表的二叉排序树、哈希查找等查找结构。本次的课程设计主要研究两种常见的查找算法：顺序查找和折半查找，分析比较它们的时间复杂度，并且在此基础上用C语言对它们进行算法编程、调试和运行。 关键词：C语言；顺序查找折半查找课程设计是我们专业课程知识综合应用的实践训练 本次课程设计，我准备用不同的两种常见的查找方法：针对顺序查找表中查找方法，如顺序查找、折半查找等。并且通过用这些算法实现对某个“特定的”数据元素（关键字）的查找，分析这些操作的性能：它们各自的时间复杂度、空间复杂度和其它的一些性能，同时记录每种查找方法的优缺点，比较得出它们的查找效率和查找范围。 2 设计概要 2.1 问题描述 对于不同的查找算法，它们各自的时间复杂度和空间复杂度不同，查找的思想和算法也明显不同，所以要分析它们的特点和效率，我们要多方面比较：要比较时间复杂度，我们可以从它们的查找长度侧面比较出来；而它们算法的实现就要熟悉它们的查找思想，熟练应用C语言编写合适的程序。 2.2 设计思路 静态查找表有顺序表和链式表两种表示方法，在这次的课程设计里，我用顺序存储表来表示这两种查找算法的程序。 我的设计思路及步骤如下： （1）熟悉两种算法的编程思想,画出流程图。 （2）先编写两种算法的子程序，再遍写主程序调用它们。 （3）分步调试子程序和主程序，直到不再出现错误，然后运行程序，检查是否和 自己当初的设想一样，一直到结果能让自己满意。 （4）比较得出两种查找算法的优缺。 2.3 相关的知识点 （1）C语言表示静态查找表的顺序存储结构 typedef struct { ElemType *elem; //数据元素存储空间基址，建表时按实际长度分配，0号单元留空 int length; //表的长度 } SSTable; （2）查找算法的衡量指标 查找可能产生“成功”与“不成功”两种结果，但在实际应用的大多数情况下，查找成功的可能性比不成功的可能性大得多，特别是在记录数中n很大时，查找不成功的概率可以忽略不计。当查找不成功的情况不能忽视时，查找算法的平均长度应该是查找成功时的平均查找长度与查找不成功时的平均查找长度之和，平均查找长度为： ASL= 其中，n为元素的个数； ci是查找第i 个记录需进行的比较次数；pi是查找第i个记录的概率，一般可认为查找每个记录的概率是相等的，即p1=p2=…=pn=1/n【2】。 3 算法分析及程序编写 3.1.顺序表的查找 基本思想 从查找表的一端开始，逐个将记录的关键字值和给定值进行比较，如果某个记录的关键字值和给定值相等，则称查找成功；否则，说明查找表中不存在关键字值为给定值的记录，则称查找失败。 （2）顺序查找算法流程图 算法流程图如图3-1所示： 图3-1：顺序查找算法流程图 （3）顺序查找算法代码如下 int Search_Seq(SSTable *table, ElemType key) { /*在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为零。*/ table-elem[0]=key; //设置哨兵 int result=0; // 找不到时，返回0 int i; for (i=table-length; i=1;i--) { //从后往前找 if (table-elem[i]==key) { result=i; //找到关键字的时候，该元素的位置 break; } } return result; //找不到时返回 } 4顺序查找算法性能分析 对于顺序查找，不论给定值key为何值，查找不成功时和给定值进行比较的关键字个数均为n+1.假设查找成功与不成功的可能性相同，对每个记录的查找概率也相等，则Pi=1/（2n） +(1/2)(n+1) =(3/4)(n+1) 5结论 顺序查找的优点是算法简单，且对表的结构没有任何要求。它的缺点是查找效率低，因此，当表中元素个数比较多时，不宜采用顺序查找。 3.2.折半查找 （1）使用折半查找必须具备两个前提条件 a：要求查找表中的记录按关键字有序(假设：从小到大有序) b：只能适用于顺序存储结构 （2）基本思想 先取查找表的中间位置的关键字值与给定关键字值作比较，若它们的值相等，则查找成功；如果给定值比