c - 磁盘上的链接列表数组

我试图找到如何在磁盘上存储和处理(搜索，添加，删除)链接列表数组。例如在内存中，它想

struct list {
 int a;
 struct list *next;
}LIST

LIST *array[ARRAY_SIZE]

int main{
...
 LIST *foo = array[pointer];
 /* Search */
 while(foo!=NULL){
   ...
   foo=foo->next
 }
}

我相信通过使用fseek()可以指向文件中数组的特定元素/结构。但是我不明白是否需要编写所有先前的元素。

可以在磁盘上动态分配吗？

如何将元素链接到链接列表中的另一个元素？
任何例子肯定会有所帮助!

最佳答案

好的，正如Amardeep所说，这听起来像是最好使用某种数据库(例如Berkeley DB)来完成的事情。但是还是让我们回答这些问题。

实际上，您可以使用fseek(或其系统调用lseek)来确定磁盘上的内容并稍后找到。如果您使用某种计算偏移量的方法，那么您将实现我们称为直接文件的内容；否则，您可能会存储一个索引，这会导致您偏向索引顺序方法。

是否可以通过动态分配来完成排序取决于文件系统。许多UNIX文件系统支持*稀疏*分配，这意味着如果分配块365，则不必分配块0到364。有些不分配。

假设您有一个长度为k的结构，看起来或多或少像这样:

(欺骗解析)

struct blk {
    // some stuff declared here
    long next;  // the block number of the next item
};

您创建第一个项目；将其块号设置为0。在一些可分辨的值(例如-1)旁边设置。

// Warning, this is off the cuff code, not compiled.
struct blk * b = malloc(sizeof(struct blk));
// also, you should really consider the case where malloc returns null.

// do some stuff with it, including setting the block next to 1.
lseek(file, 0, SEEK_SET);  // set the pointer at the front of the file
write(file, sizeof(struct blk), b);  // write it.
free(b);

// make a new block item
malloc(sizeof(struct blk));
// Do some stuff with it, and set next to 2.
lseek(file, 0, SEEK_CUR);  // leave the pointer where it was, end of item 0
write(file, sizeof(struct blk), b);  // write it.
free(b);

您现在在磁盘上有两个项目。继续进行下去，您最终将在磁盘上保留上千个项目。现在，要查找项目513，您只需

lseek(file, (sizeof(struct blk)*513), SEEK_SET);

您需要一个缓冲区；由于我们释放了以前的那些，我们将再做一次

b = malloc(sizeof(struck blk);

读取那么多字节

read(file, sizeof(struct blk), b);

po记录513在内存中由b指向。获取以下记录

lseek(file, (sizeof(struct blk)*b->next), SEEK_SET);