文档介绍：会计学
1
华清远见数据结构
设记录表L=(R1 R2……Rn)，其中Ri(l≤i≤n)为记录，对给定的某个值k，在表L中确定key=k的记录的过程，称为查找。若表L中存在一个记录Ri的key=k，=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中记录比较次数的期望值(或平均值)，即：
Pi为查找Ri的概率。等概率情况下Pi=1/n；Ci为查找Ri时key的比较次数(或查找次数)。
第1页/共52页
二、顺序表的查找
所谓顺序表(Sequential Table)，是将表中记录(R1 R2……Rn)按其序号存储于一维数组空间，如图所示。其特点是相邻记录的物理位置也是相邻的。
记录Ri的类型描述如下：
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]，……，[]）为记录表(R1……Rn)， [i].key, [0]称为监视哨，为算法设计方便所设。
R1
R2
…
…
Rn
第2页/共52页
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;
[0].key=k; //k存入监视哨//
i=; //取表长//
while([i].key!=k)
i--; //顺序查找//
return(i);
}
算法用了一点技巧：先将k存入监视哨，若对某个i(≠0)[i].key=k，则查找成功，返回i；若i从n递减到1都无记录的key为k，i再减1为0时，[0].key=k，说明查找失败，返回i=0。
第3页/共52页
顺序查找
算法分析 设Ci(1≤i≤n)为查找第i记录的key比较次数(或查找次数)：
[n].key=k， Cn=1；
[n-1].key=k， Cn-1=2；
……
[i].key=k， Ci=n-i+1；
……
[1].key=k， C1=n
故ASL=O(n)。而查找失败时，查找次数等于n+l，同样为O(n)。
对查找算法，若ASL=O(n)，则效率是最低的，意味着查找某记录几乎要扫描整个表，当表长n很大时，会令人无法忍受。下面关于查找的一些讨论，大多都是围绕降低算法的ASL量级而展开的。
2