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

两种常用查找算法的比较与实现摘 要：本次课程设计主要研究几种常用查找算法的比较与实现，查找的算法有很多种：静态查找表的顺序表、有序表、索引顺序表等查找结构；动态查找表的二叉排序树、哈希查找等查找结构。本次的课程设计主要研究两种常见的查找算法：顺序查找和折半查找，分析比较它们的时间复杂度，并且在此基础上用C语言对它们进行算法编程、调试和运行。关键词：C语言；顺序查找；折半查找;时间复杂度。1 引 言“数据结构”在计算机科学中是一门综合性的专业基础课，“数据结构”的研究不仅涉及到计算机硬件的研究范围，而且和计算机软件的研究有着密切的关系无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，一遍查找和存取数据元素更为方便。因此，可以认为“数据结构”是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。课程设计是我们专业课程知识综合应用的实践训练，是实践性教学的一个重要环节。而数据结构的课程设计，更要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。在日常生活中，人们几乎每天都要进行“查找”工作。例如，在电话号码薄中查阅“某单位”或“某人”的电话号码；在字典中查阅“某个词”的读音和含义等等。而同样地，在各种系统软件和应用软件中，也存在“查找”：如编译程序中符号表、信息处理表中相关信息的查找。所以，“查找”就是在一个含有众多的数据元素（或记录）的查找表中找出某个“特定的”数据元素（或记录）【1】。在计算机中进行查找的方法也会随数据结构不同而不同。在此，引入“查找表”的概念：同类数据元素构成的集合。所以，这次的课程设计就可以从静态查找表的几种典型的算法来实现对数据元素的查找的算法和操作的实现和比较。1.1课程设计背景数据结构课程设计作为独立的教学环节，是计算机相关专业集中实践环节系列之一，是学习完数据结构课程后进行的一次全面的综合练习。所以需要我们了解并掌握数据结构与算法的设计方法，并且具备初步的独立分析和设计能力，同时要掌握软件开发过程的问题分析、系统设计、程序编码测试等基本方法和技能，提高综合运用所学的理论知识和方法独立分析和解决问题的能力。所以这次课程设计的目的在于：加强学生对C语言的基本知识和技能；加深对数据结构基础理论和基本知识的理解，提高解决实际问题的实践能力；同时帮助调动学生的积极性和能动性，培养学生的自学、动手能力。1.2课程设计目标本次课程设计，我准备用不同的两种常见的查找方法：针对顺序查找表中查找方法，如顺序查找、折半查找等。并且通过用这些算法实现对某个“特定的”数据元素（关键字）的查找，分析这些操作的性能：它们各自的时间复杂度、空间复杂度和其它的一些性能，同时记录每种查找方法的优缺点，比较得出它们的查找效率和查找范围。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.顺序表的查找（1） 基本思想从查找表的一端开始，逐个将记录的关键字值和给定值进行比较，如果某个记录的关键字值和给定值相等，则称查找成功；否则，说明查找表中不存在关键字值为给定值的记录，则称查找失败。 （2）顺序查找算法流程图算法流程图如图3-1所示：图3-1：顺序查找算法流程图（3）顺序查找算法代码如下int Search_Seq(SSTable *table, ElemType key) /*在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为零。*/table-elem0=key; /设置哨兵int result=0; / 找不到时，返回0int i;for (i=table-length; i=1;i-) /从后往前找 if (table-elemi=key) result=i; /找到关键字的时候，该元素的位置break; return result; /找不到时返回顺序查找算法性能分析对于顺序查找，不论给定值key为何值，查找不成功时和给定值进行比较的关键字个数均为n+1.假设查找成功与不成功的可能性相同，对每个记录的查找概率也相等，则Pi=1/（2n）,此时顺序查找的平均查找长度为3：ASL= +(1/2)(n+1)=(3/4)(n+1)结论顺序查找的优点是算法简单，且对表的结构没有任何要求。它的缺点是查找效率低，因此，当表中元素个数比较多时，不宜采用顺序查找。 3.2.折半查找（1）使用折半查找必须具备两个前提条件a：要求查找表中的记录按关键字有序(假设：从小到大有序) b：只能适用于顺序存储结构 （2）基本思想先取查找表的中间位置的关键字值与给定关键字值作比较，若它们的值相等，则查找成功；如果给定值比该记录的关键字值大，说明要查找的记录一定在查找表的后半部分，则在查找表的后半部分继续使用折半查找；若给定值比该记录的关键字值小，说明要查找的记录一定在查找表的前半部分，则在查找表的前半部分继续使用折半查找，直到查找成功，或者查找失败。(3）查找流程图流程图如图3-2所示：图3-2：折半查找算法流程图(4）折半查找算法的代码int Search_Bin(SSTable *table, ElemType key)/*在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0.*/ int low=1; int high=table-length; /置区间初值 int result=0; / 找不到时，返回0 while(low elemmid=key)result=mid;break; /找到待查元素else if(keyelemmid)high=mid-1; /继续在前半区间进行查找elselow=mid+1; /继续在后半区间进行查找 return result;5 （5）折半查找算法性能分析在折半查找的过程中，每经过一次比较，查找范围都要缩小一半，所以折半查找的最大查找长度为 MSL=log2 n+1当n足够大时，可近似的表示为log2(n)。（6）结论折半查找要求查找表按关键字有序，而排序是一种很费时的运算；另外，折半查找要求表是顺序存储的，为保持表的有序性，在进行插入和删除操作时，都必须移动大量记录。因此，折半查找的高查找效率是以牺牲排序为代价的，它特别适合于一经建立就很少移动、而又经常需要查找的线性表。可见在查找速度上，折半查找比顺序查找速度要快的多，这是它的主要优点4。 4 测试分析1. 输入元素有误（1）：若输入的元素个数不合理，元素个数少于n，这种输入造成的的结果是系统一直等待元素的输入，即得不到结果。如图4-1所示：图4-1：输入元素个数少时的运行情况（2）若输入元素个数大于n时，系统将从第一个元素起，自动选取前n个元素作为有效元素，进行程序的后续运行。这种情况下的结果如图4-2所示：图4-2：输入元素个数多时的运行情况2. 查找失败这种情况是指在n个元素中没有与关键字相同的元素存在，所以程序运行的结果是查找失败。运行结果如图4-3所示：图4-3：查找失败时的运行情况3. 查找成功若查找成功，即元素输入无误，且有关键字存在的情况，这个时候的运行结果如图4-4所示5：图4-4：查找成功时的运行情况5 总结和体会5.1 课程设计总结“书到用时方恨少”。在这次课程设计，我感触最深的当属查阅大量的设计资料了，为了让自己的设计更加完善，查阅这方面的设计资料是十分必要的，看着那么大叠的书籍、资料摆在自己的面前，有些时候还要上网查阅相关知识点，并且还要整理出有用的知识点，这对于我来说，是在是个不小的挑战。所以，以后一定要多看自己专业方面的书籍，增长自己的知识。而且，写程序是一件十分需要耐心的活，一个不小心，后果就可能是几个小时的思考和调试，幸好这次的课题我并不陌生，所以，并没有自己想象中的艰难。但是，用的时间和精力却绝对也不少。5.2 心得与体会这次课程设计，使我对数据结构这门课程有了更深入的了解。数据结构是一门实践性较强的课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。一个人的力量是有限的，要想把课程设计做的更好，就要学会参考一定的资料，吸取别人的经验，让自己和别人的思想有机的结合起来，得出属于你自己的灵感。在本课程设计中，我明白了理论与实际应用相结合的重要性，并提高了自己组织数据及编写大型程序的能力。培养了基本的、良好的程序设计技能以及合作能力。这次课程设计同样提高了我的综合运用所学知识的能力。程序的编写需要有耐心，有些事情看起来很复杂，但问题需要一点一点去解决，分析问题，把问题一个一个划分，划分成小块以后就逐个去解决。再总体解决大的问题。这样做起来不仅有条理也使问题得到了轻松的解决。通过这两周的课程设计，我认识到数据结构是一门比较难的课程。需要多花时间上机练习。这次的程序训练培养了我实际分析问题、编程和动手能力，使我掌握了程序设计的基本技能，提高了我适应实际，实践编程的能力。参考文献：1严蔚敏，吴伟民. 数据结构:C语言版 清华大学出版社，2012.52MarkAllenWeiss.数据结构与算法分析C语言描述（英文版第二版）.北京：人民邮电出版社，20053李峰，谢中科.C语言程序设计.上海：复旦大学出版社，20114Baloukas, C., Risco-Martin, J. L., Atienza, D., et al. Optimization methodology of dynamic data structures based on genetic algorithms for multimedia embedded systemsJ. Journal of Systems and Software, 2009, 82(4): 590-602.5李春葆，尹为民.数据结构教程上机指导（第三版）.北京：清华大学出版社,2008附录：程序源代码：#include#include#includeusing namespace std;typedef int ElemType ;/用C语言定义顺序存储结构 typedef struct ElemType *elem; /数据元素存储空间基址，建表时按实际长度分配，0号单元留空 int length; /表的长度 SSTable; void Create(SSTable *table, int length); / 构建顺序表void Destroy(SSTable *table);int Search_Seq(SSTable *table, ElemType key);void Traverse(SSTable *table, void (*visit)(ElemType elem);void Create(SSTable *table, int length) / 构建顺序表 SSTable *t = (SSTable*) malloc(sizeof(SSTable);t-elem=(ElemType*)malloc(sizeof(ElemType)*(length+1);t-length=length;*table=t;void FillTable(SSTable *table) / 无序表的输入 ElemType *t=table-elem;for(int i=0; ilength; i+)t+;scanf(%d, t);getchar();void Destroy(SSTable *table) /销毁表free(table-elem);free(table);void PrintTable(SSTable *table) / 打印查找表中的元素 int i;ElemType *t=table-elem;for(i=0; ilength; i+) t+;printf(%d , *t);/顺序（哨兵）查找算法int Search_Seq(SSTable *table, ElemType key) /*在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为零。*/table-elem0=key; /设置哨兵int result=0; / 找不到时，返回0int i;for (i=table-length; i=1;i-) /从后往前找 if (table-elemi=key) result=i; /找到关键字的时候，该元素的位置break; return result; /找不到时返回 void Sort(SSTable *table ) / 排序算法 int i, j;ElemType temp; for (i=table-length; i=1 ;i-) / 从前往后找 for (j=1; jelemjtable-elemj+1) /从小到大排列temp=table-elemj;table-elemj=table-elemj+1; /元素后移table-elemj+1=temp; int Search_Bin(SSTable *table, ElemType key)/*在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0.*/ int low=1; int