【白话文严蔚敏数据结构】顺序文件

发布时间 2023-06-29 17:51:11作者: 小默同学

顺序文件就是逻辑顺序与物理顺序一致的文件叫做顺序文件,如果逻辑相邻物理相邻叫做连续文件,如果逻辑相邻物理不相邻叫做串联文件

顺序文件是根据记录的位置(绝对位置和相对位置都可以)进行存取的文件组织方式。顺序文件的优点是连续存取速度快,因此主要用于只进行顺序存取批量修改的情况。在进行直接存取时,如果对响应时间要求不严格,也可以使用顺序文件。

磁带是顺序存取的设备,只有顺序文件才能存到磁带上,磁带适合文件数据大,文件变化小的情况。对磁带文件进行修改的时候,要对文件进行复制一份,然后在复制的时候修改,对磁带文件进行添加的时候,只能添加到文件的末尾,存取磁带第 \(i\) 个记录时候,要先获得它前面的 \(i-1\) 个记录。为了修改更加方便,要求待复制的顺序文件按照关键字有序排列。

磁带文件的批处理有三条磁带,第一条磁带放主文件,第二条磁带放批处理命令,第三条磁带,放新的主文件。主文件按关键字有序,批处理命令按主文件顺序有序,然后将主文件和事务文件归并成一个新的主文件。

分析算法时间复杂度,如果主文件包含 \(n\) 个记录,事务文件包含 \(m\) 个记录。事务文件进行内部排序,最小时间复杂度为 \(O(mlogm)\) ,内部归并的时间复杂度为 \(O(n+m)\) ,总的内部处理时间为 \(O(n+mlogm)\)

对于一批需要进行处理的文件,可以将它们存储在磁带上,然后按照磁带上的顺序一个一个进行处理。更新不增加磁带长度时候,可以不用复制一条新的磁带,直接修改原来的主文件即可。