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

Поэлементная загрузка динамических структур данных


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


//------------------------------------------------------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-&#62val == vv) return p ;
if (p-&#62val &#62 vv)
pnext = FindTree(p-&#62fleft, vv, fd);
else
pnext = FindTree(p-&#62fright, 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*)&#38Elem, TSZ, 1, fd);
return pos;
}
// Замечание: функция добавления вершины в дерево не работает

// пустым деревом, поэтому этот случай необходимо

// рассматривать отдельно, перед ее вызовом.

void AppendTree(long pos, int vv, FILE *fd)
{
ftree Elem; // Автоматическая переменная

fseek(fd, pos, SEEK_SET); // для хранения текущей

fread((void*)&#38Elem, TSZ, 1, fd); // вершины дерева

if (Elem.val==vv) return;
if (Elem.val &#62 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*)&#38Elem, TSZ, 1, fd); // вершину дерева

}


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