Информатика и технология программирования

         

Односвязный список в файле


Наиболее показателен примером структуры данных при поэлементной загрузке данных в память является односвязный список. В приведенном ниже примере следует обратить внимание на полную функциональную аналогию алгоритма работы с односвязным списком в памяти и в файле. Особенности работы с файлом заключаются в том, что для каждого активизируемого элемента структуры данных необходим аналогичный элемент в памяти, а для указателя на него - соответствующий файловый указатель. Так, если для включения в односвязный список с сохранением упорядоченности необходимо использовать текущий и предыдущий элементы списка, то необходимы две локальные структурированные переменные - текущий и предыдущий элементы списка cur и prev, а также два файловых указателя, определяющих их расположение в файле - fcur и fprev . В начале файла размещается заголовок списка - файловый указатель на первый элемент.


//------------------------------------------------------bk59-11.cpp


// Список в файле. Поэлементная работа . В начале файла -


// заголовок - указатель на первый элемент.


&#35define FNULL -1L
struct flist // Определение элемента списка


{
int val; // Значение элемента списка


long fnext; // Файловый указатель на следующий элемент


}; // При поэлементной работе flist *next не нужен


void show(FILE *fd) // Просмотр списка


{ flist cur; // Файловый указатель текущего элемента


long fcur; // Текущий элемент


fseek(fd,0L,SEEK_SET);
fread(&#38fcur,sizeof(long),1,fd); // Загрузить указатель на первый


for (; fcur!=FNULL; fcur=cur.fnext)
{ // Загрузка текущего элемента


fseek(fd,fcur,SEEK_SET);
fread(&#38cur,sizeof(flist),1,fd);
printf("%d ",cur.val);
}
puts("");}


void ins_sort(FILE *fd, int vv)
{ // Включение с сохранением упорядоченности


fl ist cur,prev,lnew; // Текущий и предыдущий и новый элементы списка


long fnew,fcur,fprev; // Файловые указателя элементов списка


fseek(fd,0L,SEEK_SET);
fread(&#38fcur,sizeof(long),1,fd);
for (fprev=FNULL; fcur!=FNULL;


fprev=fcur, prev=cur, fcur=cur.fnext)
{ // Переход к следующему с запоминанием

fseek(fd,fcur,SEEK_SET); // предыдущего элемента и его адреса

fread(&#38cur,sizeof(flist),1,fd);
if (cur.val &# 62 vv) break; // Поиск места - текущий &#62 нового

}

lnew.val = vv;
lnew.fnext=fcur;
fseek(fd,0L,SEEK_END); // Заполнение нового элемента списка

fnew=ftell(fd); // Запись в файл и получение адреса

fwrite(&#38lnew,sizeof(flist),1,fd);

if (fprev==FNULL) // Включение первым -

{ // обновить заголовок

fseek(fd,0L,SEEK_SET);
fwrite(&#38fnew,sizeof(long),1,fd);
}
else // Включение после предыдущего -

{
prev.fnext=fnew; // обновить предыдущий

fseek(fd,fprev,SEEK_SET);
fwrite(&#38prev,sizeof(flist),1,fd);
}}


Содержание раздела