3

ディスク上のリンクされたリストの配列を保存および処理 (検索、追加、削除) する方法を見つけようとしています。たとえば、メモリでは、

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
 }
}
  1. fseek() を使用すると、ファイル内の配列の特定の要素/構造を指すことができると思います。しかし、以前のすべての要素を記述する必要があるかどうかはわかりません。
  2. これは、ディスク上の動的割り当てで実行できますか?
  3. リンクされたリスト内の要素を別の要素にリンクするにはどうすればよいですか? どの例も確かに役立ちます！
4

1 に答える 1

4

わかりました、Amardeep が言うように、これは、Berkeley DB のようなある種のデータベースを実際に使用して実行するのが最善の方法のように思えます。とにかく質問に答えましょう。

  1. 実際、fseek (またはそのシステム コール lseek) を使用して、ディスク上のどこに何かがあるかを判断し、後で見つけることができます。オフセットを計算する何らかの方法を使用する場合は、私たちが直接ファイルと呼んでいたものを実装しています。それ以外の場合は、インデックスを格納する可能性があり、インデックス付きの順次方式に移行します。

  2. 動的割り当てで実行できるかどうかは、ファイルシステムに依存します。多くの UNIX ファイル システムは * sparse* 割り当てをサポートしています。つまり、ブロック 365 を割り当てる場合、ブロック 0 から 364 を割り当てる必要はありません。一部のファイル システムは割り当てません。

  3. 多かれ少なかれ次のような長さ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);

これで、ディスク上に 2 つのアイテムができました。これを続ければ、最終的にはディスク上に 1000 個のアイテムが存在することになります。さて、アイテム番号 513 を見つけるには、

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

バッファが必要です。以前のものを解放したので、別のものを作成します

b = malloc(sizeof(struck blk);

そのバイト数を読み取る

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

また、poofレコード 513 は、 が指すメモリ内にありますb。次のレコードを取得します

lseek(file, (sizeof(struct blk)*b->next), SEEK_SET);
于 2010-10-17T02:38:35.330 に答える