华清远见 数据结构

华清远见 数据结构

查找

华清远见 数据结构

“查找”(Searching)及“排序”(Sorting)是建立在数据结构上的两个重 要运算。查找(或检索)是在给定信息集上寻找特定信息元素的过程。据统计， 一些计算机、特别是商用计算机，其CPU处理时间约25%~75%花费在查找 或排序上。所以对查找和排序问题的处理，有时直接影响到计算机的工作 效率。 一、概 述 待查找的数据单位(或数据元素)称为记录。记录由若干数据项(或 属性)组成，如学生记录:学号 姓名 性别 年龄 ……

其中，“学号”、“姓名”、“性别”、“年龄”等都是记录的数 据项。若某个数据项的值能标识(或识别)一个或一组记录，称其为关键字 关键字 (key)。若一个key能唯一标识一个记录，称此key为主key。如“学号”的值 给定就唯一对应一个学生，不可能多个学生的学号相同，故“学号”在学 生记录里可作为主key。若一个key能标识一组记录，称此key为次key。如 “年龄”值为20时，可能有若干同学的年龄为20岁，故“年龄”可作次key。 下面主要讨论对主key的查找。

华清远见 数据结构

1.查找定义 查找定义 设记录表L=(R1 R2……Rn),其中Ri(l≤i≤n)为记录，对给定的某个值k, 在表L中确定key=k的记录的过程，称为查找。若表L中存在一个记录Ri 的key=k,记为Ri.key=k,则查找成功，返回该记录在表L中的序号i(或 Ri 的地址),否则(查找失败)返回0(或空地址Null)。 2.查找方法 . 查找方法很多，有顺序查找、折半查找、分块查找、树表查找及Hash 表查找等等。查找算法的优劣将影响到计算机的使用效率，应根据应用 场合选择相应的查找算法。 3.平均查找长度 . 评价一个算法优劣的量度，一是时间复杂度T(n),n为问题的体积， 此时为表长；二是空间复杂度D(n);三是算法的结构等其他特性。 对查找算法，主要分析其T(n)。查找过程是key的比较过程，时间主 要耗费在各记录的key与给定k值的比较上。比较次数越多，算法效率越 差(即T(n)量级越高),故用“比较次数”刻画算法的T(n)。另外，显 然不能以查找某个记录的时间来作为T(n),一般以“平均查找长度”来 衡量T(n)。 平均查找长度ASL(Average Search Length):对给定k,查找表L中 n 记录比较次数的期望值(或平均值),即： ASL = ∑ Pi C i

i =1 Pi为查找Ri的概率。等概率情况下Pi=1/n;Ci为查找Ri时key的比较次数(或查找次数)。

华清远见 数据结构

二、顺序表的查找 所谓顺序表(Sequential Table),是将表中记录(R1 R2……Rn)按其序号 存储于一维数组空间，如图所示。其特点是相邻记录的物理位置也是相 邻的。 R1 记录Ri的类型描述如下： R2 typedef struct … { keytype key; //记录key// … …… //记录其他项// Rn }Retype; 其中，类型keytype是泛指，即ke

ytype可以是int、float、char或其他的结 构类型等等。为讨论问题方便，一般取key为整型。 顺序表类型描述如下: #define maxn 1024; //表最大长度// typedef struct { Retype data[maxn]; //顺序表空间// int len; //当前表长，表空时len=0// }sqlist; 若说明：sqlist r,则(r.data[1],……,r.data[r.len])为记录表(R1……Rn), Ri.key为r.data[i].key, r.data[0]称为监视哨，为算法设计方便所设。

华清远见 数据结构

1 顺序查找算法及分析 顺序查找(Sequential Search)是最简单的一种查找方法。 算法思路 设给定值为k,在表(R1 R2……Rn)中，从Rn开始，查找key=k的记录。若 存在一个记录Ri (l≤i≤n)的key为k,则查找成功，返回记录序号i;否 则，查找失败，返回0。 算法描述 int sqsearch(sqlist r,keytype k) //对表r顺序查找的算法// { int i; r.data[0].key=k; //k存入监视哨// i=r.len; //取表长// while(r.data[i].key!=k) i--; //顺序查找// return(i); } 算 法 用 了 一 点 技 巧 ： 先 将 k 存 入 监 视 哨 ， 若 对 某 个 i(≠0) 有 r.data[i].key=k,则查找成功，返回i;若i从n递减到1都无记录的key为k, i再减1为0时，必有r.data[0].key=k,说明查找失败，返回i=0。

华清远见 数据结构

顺序查找 算法分析 设Ci(1≤i≤n)为查找第i记录的key比较次数(或查找次数): 若r.data[n].key=k, Cn=1; 若r.data[n-1].key=k, Cn-1=2; …… 若r.data[i].key=k, Ci=n-i+1; …… 若r.data[1].key=k, n C1=n n n +1 1 所以，ASL= ∑ Pi C i = n ∑ (n i + 1) =i =1 i =1

2

故ASL=O(n)。而查找失败时，查找次数等于n+l,同样为O(n)。 对查找算法，若ASL=O(n),则效率是最低的，意味着查找某记录几 乎要扫描整个表，当表长n很大时，会令人无法忍受。下面关于查找的 一些讨论，大多都是围绕降低算法的ASL量级而展开的。 2 折半查找算法及分析 当记录的key按关系≤或≥有序时，即： 可采用折半或二分法查找 R1.key≤R2.key≤……≤Rn.key (升序) (Binary Search)。 或 R1.key≥R2.key≥……≥Rn.key (降序)

华清远见 数据结构

算法思路 对给定值k,逐步确定待查记录所在区间，每次将搜索空间减少一半(折 半),直到查找成功或失败为止。 设两个指针(或游标)low、high,分别指向当前待查找表的上界(表头)和 下界(表尾)。对于表(R1 R2……Rn),初始时low=l、high=n,令： mid= (low + high) / 2 指向当前待查找表中间的那个记录。下面举例说明折半查找的过程。 例1 设记录表的key序列如下: 序号： 1 2 3 4 5 6 7 8 9 10 11 12 (n=12) 03 12 18 20 32 55 60 68 80 86 90 100

low high mid low high mid 现查找k=20的记录。 mid 1mid= (1 + 12) / 2 =6。因k<r.data[6].k …… 此处隐藏：7419字，全部文档内容请下载后查看。喜欢就下载吧 ……