计算机软件及应用DS查找.pptx

(Searching)的定义是:在含有n条记录的表(文件)中找出关键字等于给定值K的记录。若找到,则查找成功,返回该记录的信息或该记录在表(文件)中的位置;否则查找失败,返回相关的指示信息。若在查找的同时对表做修改操作(如插入和删除等),则相应的表称之为动态查找表(DynamicSearchTable)。否则称之为静态查找表(StaticSearchTable)。若整个查找过程都在内存进行,则称之为内查找;反之,若查找过程中需要访问外存,则称之为外查找查找表的数据结构表示如何分析算法优劣?主要分析算法运算时所需要的时间和其存储结构占用的内存空间。而对于查找算法,执行的时间通常取决于关键字的比较次数,所以本章经常用平均比较次数,即平均查找长度ASL(AverageSearchLength)其中:   1、n是结点的个数;   2、Pi是查找第i个结点的概率。若不特别声明,认为每个结点的查找概率相等,即          pl=p2……=pn=1/n   3、ci是找到第i个结点所需进行的比较次数ASL=平均查找长度ASL(AverageSearchLength)定义为:一、顺序查找(SequentialSearch)基本思想是:从表的一端开始,顺序扫描线性表,依次将扫描到的结点关键字和给定值K相比较。若当前扫描到的结点关键字与K相等,则查找成功;若扫描结束后,仍未找到关键字等于K的结点,则查找失败。 typedefstruct{KeyTypekey;/*KeyType由用户定义*/   InfoTypeotherinfo;/*此类型依赖于应用*/  }NodeType; typedefNodeTypeSeqlist[n+1];/*多出0号单元用作监视哨*/具体算法 intSeqSearch(SeqlistR,KeyTypeK)   {/*在顺序表R[1..n]中顺序查找关键字为K的结点,*//*成功时返回找到的结点位置,失败时返回0*/     inti;     R[0].key=K;/*设置监视哨*/     for(i=n;R[i].key!=K;i--);/*从表后往前找*/     returni;/*若i为0,表示查找失败,否则R[i]为要找的结点*/   }/*SeqSearch*/算法分析查找成功时的顺序查找的平均查找长度:在等概率情况下,pi=1/n(1≤i≤n),故成功的平均查找长度为      ASL==(n+…+2+1)/n=(n+1)/2即查找成功时的平均比较次数约为表长的一半。顺序查找的缺点查找效率低。顺序查找的优点算法简单,且对表的结构无任何要求,无论是用向量还是用链表来存放结点,也无论结点之间是否按关键字有序,它都同样适用。二分查找又称折半查找,它是一种效率较高的查找方法。二分查找要求:要求线性表是有序表,即表中结点按关键字有序,并且要用向量作为表的存储结构。不妨设有序表是递增有序的。二、二分查找