c - 如何在内存中表示随机访问的文本文件 (C)

Question

我正在做一个项目，我需要读取内存中的文本(源)文件并能够执行随机访问(例如，检索对应于第 3 行第 15 列的地址)。

我想知道是否有一种既定的方法可以做到这一点，或者是否有特别适合这项工作的数据结构。我需要能够执行(可能是摊销的)恒定时间访问。我正在使用 C 语言工作，但如果值得的话，我愿意实现更高级别的数据结构。

我的第一个想法是使用大型缓冲区的链表来保存文件的字符数据。我还会制作一个数组，其索引是行号，内容是对应于行首的地址。该数组将根据需要重新分配。

附属问题:有人知道源文件的平均大小吗？我很惊讶没有在谷歌上找到这个。

澄清:

我关心的文件是源文件，所以它们的大小应该是可管理的，它们不应该被修改，并且行的长度是可变的(强硬希望限制在某个最大值)。

我正在处理的问题主要需要一个只读文件表示，但我对深入研究这个问题非常感兴趣。

结论:

在论文 Data Structures for Text Sequences 中对用于维护文件(具有读/插入/删除支持)的数据结构进行了非常有趣的讨论。 .

如果你只需要只读，只需要获取文件大小，使用 fread() 在内存中读取它，那么你必须维护一个动态数组，它将行号(索引)映射到指向文件中第一个字符的指针线。下面有人建议延迟构建这个数组，在很多情况下这似乎是个好主意。

Answer 1

我不太确定这里的问题是什么，但似乎有一点“我如何将文件保存在内存中”和“我如何索引它”。由于您需要随机访问文件的内容，因此最好建议您对文件进行内存映射，除非地址空间紧张。

我认为您无法避免线性遍历文件一次以找到行尾。如您所说，您可以创建指向每行开头的指针的索引。如果您不确定需要多少索引，请懒惰地(按需)创建它。如果在后续运行中需要它，您还可以将此索引存储到磁盘(作为偏移量，而不是指针)。您可以根据文件大小和预期的行长度来估计索引的大小。