文档介绍：查找“查找”( Searching )及“排序”(Sorting) 是建立在数据结构上的两个重要运算。查找( 或检索) 是在给定信息集上寻找特定信息元素的过程。据统计,一些计算机、特别是商用计算机,其 CPU 处理时间约 25% ~75% 花费在查找或排序上。所以对查找和排序问题的处理,有时直接影响到计算机的工作效率。一、概述待查找的数据单位( 或数据元素) 称为记录。记录由若干数据项(或属性)组成,如学生记录: 其中, “学号”、“姓名”、“性别”、“年龄”等都是记录的数据项。若某个数据项的值能标识(或识别)一个或一组记录,称其为关键字( key )。若一个 key 能唯一标识一个记录,称此 key 为主 key 。如“学号”的值给定就唯一对应一个学生,不可能多个学生的学号相同,故“学号”在学生记录里可作为主 key 。若一个 key 能标识一组记录,称此 key 为次 key 。如“年龄”值为 20 时,可能有若干同学的年龄为 20 岁,故“年龄”可作次 key 。下面主要讨论对主 key 的查找。……年龄性别姓名学号 L=(R 1 R 2 …… R n), 其中 R i (l≤i≤n) 为记录,对给定的某个值 k, 在表 L 中确定 key=k 的记录的过程,称为查找。若表 L 中存在一个记录R i的 key=k , 记为 R i .key =k , 则查找成功,返回该记录在表 L 中的序号 i(或R i的地址),否则(查找失败)返回 0(或空地址 Null) 。 ,有顺序查找、折半查找、分块查找、树表查找及 Hash 表查找等等。查找算法的优劣将影响到计算机的使用效率,应根据应用场合选择相应的查找算法。 ,一是时间复杂度 T(n) ,n 为问题的体积, 此时为表长;二是空间复杂度 D(n) ;三是算法的结构等其他特性。对查找算法,主要分析其 T(n) 。查找过程是 key 的比较过程,时间主要耗费在各记录的 key 与给定 k 值的比较上。比较次数越多,算法效率越差(即 T(n) 量级越高),故用“比较次数”刻画算法的 T(n) 。另外,显然不能以查找某个记录的时间来作为 T(n) , 一般以“平均查找长度”来衡量 T(n) 。平均查找长度 ASL ( Average Search Length ): 对给定 k, 查找表 L中记录比较次数的期望值(或平均值),即: ??? ni iiCP ASL 1 P i为查找 R i的概率。等概率情况下 P i =1/n ;C i为查找 R i时 key 的比较次数(或查找次数)。二、顺序表的查找所谓顺序表(Sequential Table) , 是将表中记录(R 1 R 2 …… R n) 按其序号存储于一维数组空间,如图所示。其特点是相邻记录的物理位置也是相邻的。记录 R i的类型描述如下: typedef struct { keytype key; // 记录 key// …… // 记录其他项// }Retype; 其中,类型 keytype 是泛指,即 keytype 可以是 int、 float 、 char 或其他的结构类型等等。为讨论问题方便,一般取 key 为整型。顺序表类型描述如下: #define maxn 1024; // 表最大长度// typedef struct { Retype data[maxn ]; // 顺序表空间// int len ; // 当前表长,表空时 len =0// } sqlist ; 若说明: sqlist r, 则( [1] , ……, [ ]) 为记录表(R 1 …… R n), R i .key 为 [i].key, [0] 称为监视哨,为算法设计方便所设。 R n…… R 2R 1 1顺序查找算法及分析顺序查找(Sequential Search) 是最简单的一种查找方法。算法思路设给定值为 k, 在表(R 1 R 2 …… R n) 中,从 R n 开始,查找 key=k 的记录。若存在一个记录 R i(l≤i≤n )的 key 为k, 则查找成功,返回记录序号 i; 否则,查找失败,返回 0。算法描述 int sqsearch(sqlist r,keytype k) // 对表 r顺序查找的算法// { int i; [0].key=k; //k 存入监视哨// i= ; // 取表长// while([i].