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

若在查找的同时对表做修改操作（如插入和删除等），则相应的表称之为动态查找表（Dynamic Search Table）。否则称之为静态查找表(Static Search Table)。
若整个查找过程都在内存进行，则称之为内查找；反之，若查找过程中需要访问外存，则称之为外查找
查找表的数据结构表示
第1页/共98页
如何分析算法优劣？主要分析算法运算时所需要的时间和其存储结构占用的内存空间。而对于查找算法，执行的时间通常取决于关键字的比较次数，所以本章经常用平均比较次数，即平均查找长度 ASL（Average Search Length）
第2页/共98页
其中：
   1、n是结点的个数；
   2、Pi是查找第i个结点的概率。若不特别声明
，认为每个结点的查找概率相等，即
           pl = p2…… = pn = 1/n
   3、ci是找到第i个结点所需进行的比较次数
平均查找长度 ASL（Average Search Length）定义为 ：
第3页/共98页
一、顺序查找(Sequential Search)
基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值K相比较。若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。
线性表的查找
第4页/共98页
基于顺序结构的顺序查找算法
类型说明
  typedef struct{
KeyType key； /*KeyType由用户定义*/
    InfoType otherinfo； /*此类型依赖于应用*/
   }NodeType；
  typedef NodeType Seqlist[n+1]；
/*多出0号单元用作监视哨*/
第5页/共98页
具体算法
  int SeqSearch(Seqlist R，KeyType K)
    { /*在顺序表R[1..n]中顺序查找关键字为K的结点，*/
/*成功时返回找到的结点位置，失败时返回0*/
      int i；
      R[0].key=K； /*设置监视哨*/
      for(i=n；R[i].key!=K;i--)；/*从表后往前找*/
      return i； /*若i为0，表示查找失败，否则R[i]为要找的结点*/
    } /*SeqSearch*/
第6页/共98页

算法分析
查找成功时的顺序查找的平均查找长度：
在等概率情况下，pi=1/n(1≤i≤n)，故成功的平均查找长度为
       ASL= =(n+…+2+1)/n=(n+1)/2
即查找成功时的平均比较次数约为表长的一半。
第7页/共98页
顺序查找的缺点
查找效率低。
顺序查找的优点
算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。
第8页/共98页
二分查找又称折半查找，它是一种效率较高的查找方法。
二分查找要求：要求线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。不妨设有序表是递增有序的。
二、二分查找
第9页/共98页
（1）首先确定该区间的中点位置         mid = （2）然后将中间位置记录的键值R[mid].key和所给关键字K进行比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找。
二分查找的基本思想是：
第10页/共98页