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

       

Связанные записи в файлеФайловый указатель


При размещении в файле динамических структур данных возникает вопрос, каким образом в файле будут представлены указатели, которые используются в переменных динамических структур данных. Само собой разумеется, что значение указателя, представляющего собой адрес указуемой переменной в памяти программы, никакого смысла при размещении той же переменной в файле не имеет. Но тогда обычному указателю, связывающему две переменные в памяти, нужно сопоставить аналогичный указатель в файле -назовем его ФАЙЛОВЫМ УКАЗАТЕЛЕМ. Его значением является позиция (адрес) переменной при ее размещении в файле. Как известно, позиция в файле определяется значением типа long, поэтому файловый указатель не является типизированным: тип его одинаков для любой переменной. Теперь рассмотрим подробнее задачу размещения связанных переменных (или записей). Если структурированная переменная а1 имеет указатель ptr на переменную a2 , то при размещении в файле переменная a1 должна получить еще один дополнительный параметр -файловый указатель fptr на место размещения в файле переменной a2. Сформировать значение файлового указателя можно следующим образом:



-если указуемая переменная (a2) еще не размещена в файле, позиционироваться на конец файла, получить текущую позицию как значение ее адреса в файле и записать переменную в файл. Если указуемая переменная уже размещена в файле, то просто использовать адрес ее размещения;



-полученный адрес указуемой переменной (a2) в файле сохранить как значение файлового указателя (fptr) в переменной, содержащей обычный указатель (ptr в a1);



-сохранить переменную (a2) в файле.


&#35define FNULL -1L
struct x
{
int val;
x *ptr;
long fptr;
} a2 = {0,NULL,FNULL}, a1 = {1, &#38a2, FNULL};


fseek(fd, 0L, SEEK_END);
a1.fptr = ftell(fd);
fwrite((void*)a1-&#62ptr, sizeof(x), 1, fd);


fseek(fd, 0L, SEEK_END);
fwrite((void*)&#38a1, sizeof(x), 1, fd);

Таким образом, структура данных, имеющая указатели, размещается в файле "хвостом вперед", то есть сначала размещаются указуемые переменные с целью получения их адресов в файле, а затем переменные, содержащие указатели.
Если такой алгоритм по каким- либо причинам нежелателен или невозможен (например, для циклического списка или графа), то можно поступить следующим образом:


-разместить в файле все переменные структуры данных и запомнить их адреса в файле;


-сформировать значения файловых указателей в переменных структуры данных, расположенных в памяти;


-"обновить" значения переменных структуры данных в файле, то есть переписать их из памяти по тем же файловым адресам.

Проиллюстрируем оба варианта на примере сохранения дерева в файле. В первом случае дерево записывается в файл "потомками вперед", причем в режиме последовательного доступа без позиционирования. Фактически получается файл записей фиксированной длины, в котором записи связаны между собой и образуют дерево с головной вершиной в конце файла:



//------------------------------------------------------bk59-03.cpp

&#35include &#60stdio.h&#62
&#35include &#60alloc.h&#62
struct ftree
{
int val;
struct ftree *left,*right; // Указатели в памяти

long fleft,fright; // Указатели в файле

};

&#35define FNULL -1L
&#35define TSZ sizeof(ftree)

//------ Функция записи возвращает адрес вершины в файле

//

long PutTree(ftree *p, FILE *fd)
{
long pos;
if (p == NULL) return(FNULL);
p -&#62fleft = PutTree(p-&#62left,fd);
p -&#62fright = PutTree(p-&#62right,fd);
pos = ftell(fd);
fwrite( (void*)p, TSZ, 1, fd);
return(pos);
}
//------ Функция формирует файл записей фиксированной длины

// В начало файла записывается указатель на головную

// вершину дерева

void SaveTree(ftree *p, char *name)
{
long pos0; // Указатель на головную запись

FILE *fd;
if ((fd=fopen(name,"wb")) ==NULL) return;
// Резервировать место под указатель

fwrite(&#38pos0, sizeof(long), 1, fd);
pos0 = PutTree(p,fd);
fseek(fd, 0L, SEEK_SET); // Обновить указатель

fwrite( (void*)&#38pos0, sizeof(long), 1, fd);
return;
}

Во втором случае рекурсивная функция записи сначала размещает текущую вершину и запоминает ее адрес в файле.


Затем рекурсивно вызывает самое себя для размещения правого и левого поддерева. Полученные после размещения файловые указатели запоминает в текущей вершине, после чего "обновляет" ее в файле:





//------------------------------------------------------bk59-04.cpp

//------Вариант функции записи вершины дерева в файл

long PutTree_(ftree *p, FILE *fd)
{
long cpos; // Адрес в файле текущей

if (p==NULL) return(FNULL); // вершины дерева

fseek(fd, 0L, SEEK_END);
cpos = ftell(fd);
fwrite((void*)p, TSZ, 1, fd); // Записать в файл текущую вершину

p-&#62fright = PutTree(p-&#62right,fd);
p-&#62fleft = PutTree(p-&#62left,fd);
fseek(fd, cpos, SEEK_SET); // Обновить текущую вершину

fwrite((void*)p, TSZ, 1, fd);
return cpos;
}

Последовательность действий по чтению динамической структуры данных более простая: по имеющемуся адресу из файла читается переменная, из которой берутся значения файловых указателей на другие переменные и процесс повторяется. Структура данных в памяти формируется, как правило, с использованием динамических переменных. В качестве примера рассмотрим загрузку дерева из файла, сформированного любым из двух указанных способов:



//------------------------------------------------------bk59-05.cpp

//----- Функция возвращает указатель на динамическую

// переменную - вершину дерева, считывая ее и связанное

// с ней поддерево из файла

ftree *GetTree(long pos, FILE *fd)
{
struct ftree *p;
if (pos == FNULL) return NULL;
if ((p = new ftreeTSZ) ==NULL) return NULL;
fseek(fd,pos,SEEK_SET);
fread((void *)p, TSZ, 1, fd);
p -&#62left = GetTree(p -&#62fleft,fd);
p -&#62right = GetTree(p-&#62fright,fd);
return p;
}
//----- Функция открывает файл и читает файловый указатель

// на головную вершину дерева, по которой загружает дерево

// в память

ftree *LoadTree(char *name)
{
FILE *fd;
long phead;
if ((fd = fopen(name,"rb")) ==NULL) return(NULL);
fread((void*)&#38phead, sizeof(long), 1, fd);
return GetTree(phead, fd);
}


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