Массив связанных списков на диске - PullRequest
Новая
       10

Массив связанных списков на диске

1 голос
/ 17 октября 2010

Я пытаюсь найти способ хранения и обработки (поиска, добавления, удаления) массива связанных списков на диске. Например, в памяти, он хотел бы 

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. Как я буду связывать один элемент с другим в связанном списке? Любой пример, безусловно, поможет!

1 Ответ

3 голосов
/ 17 октября 2010

Хорошо, как говорит Амардип, это звучит как то, что лучше всего делать практически с использованием какой-либо базы данных, например, или Berkeley DB. Но давайте все равно ответим на вопросы.

  1. вы действительно можете использовать fseek (или его системный вызов lseek), чтобы определить, где что-то находится на диске, и найти его позже. Если вы используете какой-то метод вычисления смещения, вы реализуете то, что мы использовали для вызова файла direct ; в противном случае вы можете сохранить индекс, который ведет вас к последовательному индексируемому методу *1008*.

  2. может ли это быть сделано с помощью динамического выделения, зависит от файловой системы. Многие файловые системы UNIX поддерживают * разреженное * распределение, что означает, что если вы выделяете блок 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);

Теперь у вас есть два элемента на диске. продолжайте в том же духе, и в итоге у вас будет тысяча элементов на диске. Теперь, чтобы найти предмет № 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);
...