顺序文件是根据记录的序号或记录的相对位置来进行存取的文件组织方式。
它的特点是:
①存取第i个记录,必须先搜索在它之前的i-1个记录。
②插入新的记录时只能加在文件的末尾。
③若要更新文件中的某个记录,则必须将整个文件进行复制。
顺序处理文件的搜索(顺序文件已按关键字排序)
搜索方法:
有序表上的各种搜索方法原则上都可以用于顺序处理文件的搜索,如顺序搜索和二分搜索等。
但是由于文件是外存上的数据结构,在考虑算法时,必须立足于尽量减少访外次数,因此顺序处理文件的搜索算法有自己的特点。
下面介绍顺序处理文件上的分块插值搜索。
分块插值搜索
设文件由n个记录R0,R1,…,Rn-1组成,并已知记录的关键字值按递增顺序排列:
K0,K1,…,Kn-1
K0是最小关键字值,Kn-1是最大关键字值。此n个记录顺序存储在m个(物理)块中。现要在该文件中搜索关键字值为K的记录。
分块插值搜索的做法是首先在m个块范围内决定被读入内存进行搜索的块号。
设有m块的文件,第一次被读入内存的块号i按下式计算:
设Li和Hi分别是第i块的最小和最大关键字值,
(1)若K<Li, 则下一次被搜索的块号的范围为[1,i-1];
(2)若Li<=K <=Hi,则i即为所求的块,可将该块读入内存,并在该块中去搜索待查关键字值K;
(3)若K>Hi,则下一次被搜索的块号范围为[i+1,m]。
一般情况下,设low和high分别是搜索范围内的最小块号和最大块号。L和H分别是该搜索范围内的最小关键字值和最大关键字值。则下一次读入内存的块号i为:
若K<Li,则下一次被搜索的块号的范围为[low,i-1],并且新的H将是Li;
若Li<=K <=Hi,则i即为所求的块,可在该块中去搜索待查关键字值K;
若K>Hi,则下一次被搜索的块号的范围为[i+1,high],并且新的L将是Hi。
(上面的方法类似于高等数学中的拉格朗日中值定理,理解不了的自己去翻翻高数书)