Поэлементная загрузка динамических структур данных
До сих пор мы рассматривали программы, полностью сохраняющие или загружающие динамическую структуру данных из файла. Но довольно часто требуется не вся структура данных, а лишь отдельные ее переменные, либо структура данных настолько велика, что не может быть размещена в памяти. Тогда используется более "изысканный" способ работы: в динамические переменные загружаются только те элементы, которые используются в процессе поиска или просто "движения" по структуре данных. Сложность этого способа состоит в том, что, во-первых, структура данных в памяти уже не соответствует структуре данных в файле (или соответствует фрагментарно), а во-вторых, необходимо строго следить за элементами структуры -динамическими переменными и своевременно их уничтожать. В качестве примера рассмотрим функцию поиска в дереве элемента с указанным значением. В процессе работы рекурсивной функции происходит загрузка только той цепочки вершин дерева, по которой производится поиск:
//------------------------------------------------------bk59-06.cpp
//------Поиск вершины с поэлементной загрузкой
ftree* FindTree(long pos, int vv, FILE *fd)
{
ftree *p, *pnext;
if (pos == FNULL) return NULL;
if ((p = new ftree)==NULL) return NULL;
fseek(fd, pos, SEEK_SET);
fread((void*)p, TSZ, 1, fd);
if (p->val == vv) return p ;
if (p->val > vv)
pnext = FindTree(p->fleft, vv, fd);
else
pnext = FindTree(p->fright, vv, fd);
delete p; // Уничтожить текущую вершину
return pnext; // и вернуть вершину - потомка
}
Аналогичная схема имеет место, когда производятся изменения в структуре данных. Если это связано с изменением связей между элементами структуры, то переменные, в которых изменяются значения файловых указателей, необходимо "обновлять" в файле:
//------------------------------------------------------bk59-07.cpp
//----- Добавление нового элемента в дерево, хранящееся в файле.
long AppendOne(int vv, FILE *fd)
{ // Добавить в файл новую
long pos; // вершину дерева
ftree Elem; // В памяти - автоматическая переменная
Elem.fright = Elem.fleft = FNULL;
Elem.val = vv;
fseek(fd, 0L, SEEK_END);
pos = ftell(fd);
fwrite((void*)&Elem, TSZ, 1, fd);
return pos;
}
// Замечание: функция добавления вершины в дерево не работает
// пустым деревом, поэтому этот случай необходимо
// рассматривать отдельно, перед ее вызовом.
void AppendTree(long pos, int vv, FILE *fd)
{
ftree Elem; // Автоматическая переменная
fseek(fd, pos, SEEK_SET); // для хранения текущей
fread((void*)&Elem, TSZ, 1, fd); // вершины дерева
if (Elem.val==vv) return;
if (Elem.val > vv)
{
if (Elem.fleft !=NULL)
{
AppendTree(Elem.fleft,vv,fd);
return;
}
else
Elem.fleft = AppendOne(vv,fd);
}
else
{
if (Elem.right !=NULL)
{
AppendTree(Elem.fright,vv,fd);
return;
}
else
Elem.fright = AppendOne(vv,fd);
}
fseek(fd, pos, SEEK_SET); // Обновить текущую
fwrite((void*)&Elem, TSZ, 1, fd); // вершину дерева
}
