9.5. Структуры данных в двоичном файле
Последовательный двоичный файл
Технология сохранения данных в последовательном файле не меняется в зависимости от того, текстовые это данные или двоичные. В обоих случаях используются одни и те же принципы сохранения данных в последовательном саморазворачивающимся формате. Например, рекурсивный формат сохранения дерева, рассмотренный в 8.2 при реализации его в двоичном файле получается путем простой замены функций fprintf/fcsanf на fwrite/fread.
//------------------------------------------------------95-01.cpp
//-------------Сохранение дерева в двоичный последовательный поток
void save(tree *p, FILE *fd){
fwrite(&p->cnt,sizeof(int),1,fd); // Запись вершины во внутренней форме
fwrite(&p->val,sizeof(int),1,fd);
fwrite(&p->n,sizeof(int),1,fd);
for (int i=0;i<p->n;i++) // Рекурсивное сохранение потомков
save(p->ch[i],fd);
}
//-------------Загрузка дерева из двоичного последовательного потока
tree *load(FILE *fd){
tree *p=new tree;
fread(&p->cnt,sizeof(int),1,fd);
fread(&p->val,sizeof(int),1,fd);
fread(&p->n,sizeof(int),1,fd);
for (int i=0;i<p->n;i++)
p->ch[i]=load(fd);
return p; }Записи переменной длины
Запись переменной длины (ЗПД) - единица хранения, меняющая свою размерность в различных экземплярах. В формате записей переменной длины могут быть представлены данные различного вида: динамические массивы, строки текста, последовательности данных, имеющие собственный внутренний формат.
Имеется два основных способа хранения записей переменной длины в файле:
используется специальное значение или код - ограничитель записи. Типичным примером является строка текста в памяти, имеющая в качестве ограничителя символ '\0', который в файле превращается в последовательность символов '\r' и '\n'. В этом смысле обычный текстовый файл при работе с ним построчно есть файл записей переменной длины;
запись предваряется переменной-счетчиком, которая содержит длину этой записи. Содержимое записи при этом может быть любым, поскольку явно выделенные коды-ограничители отсутствуют (свойство прозрачности данных). Этот формат удобен еще и тем, что при чтении из последовательного файла программа, зная размерность записи, может сразу же резервировать необходимую динамическую память для ее размещения.
По своей природе такой файл является файлом последовательного доступа, поскольку определить адрес любой записи без знания размерности всех предыдущих не представляется возможным.
Интерпретация содержимого записи никак не связана со способом ее хранения. В следующем примере запись переменной длины хранит структурированную переменную (фиксированная размерность) и связанную с ней строка (переменная размерность). При сохранении в файл они объединяются в единую запись с общим счетчиком длины, а при чтении загружаются отдельно: структура – в динамическую переменную, а строка – в связанный с ней динамический массив.
//------------------------------------------------------95-02.cpp
//------ Структура + строка = запись переменной длины
struct vrec {
int dd,mm,yy; // Дата
char name[20]; // Строка ограниченной длины
char *addr; }; // Строка переменной длины (внешняя)
void put(FILE *fd, vrec &R){ // Добавление записи
int sz=sizeof(vrec)+strlen(R.addr)+1; // Общая длина
fwrite(&sz,sizeof(int),1,fd); // Запись счетчика длины
fwrite(&R,sizeof(vrec),1,fd); // Фиксированная часть
fwrite(R.addr,strlen(R.addr)+1,1,fd); // Переменная часть
}
vrec *get(FILE *fd){
int size=0; vrec *p;
if (fread(&size,sizeof(int),1,fd)==0)
return NULL;; // Чтение счетчика длины - конец файла
if (size < sizeof(vrec))
return NULL; // Короткая запись
p=new vrec; // Выделение памяти под struct
fread(p,sizeof(vrec),1,fd); // Постоянная часть записи
size -= sizeof( vrec); // Остаток записи - строка
p->addr=new char[size]; // Выделение памяти под строку
fread(p->addr,size,1,fd); // Переменная часть записи
return p; }Записи фиксированной длины
Файл записей фиксированной длины (ЗФД) фактически представляет собой обычный массив, размещенный в двоичном файле. При принятом в Си низкоуровневом представлении данных в файле, адрес любого элемента массива вычисляется по простой формуле A=A0+i*sizeof(type), где A0 – начальный адрес массива, а i – индекс (номер) его элемента. Таким образом, к его элементам возможен произвольный (прямой) доступ.
С точки зрения физического представления массивы различных типов идентичны и отличаются только размерностью элементов. Поэтому программа, работающая с файлом записей фиксированной длины, может быть универсальна и применима к любому типу. Но для этого в самом файле желательно хранить размерность элемента (а также их количество). В результате получаем следующий формат, имеющий, между прочим, избыточность. Последнее дает дополнительные гарантии корректности данных в файле.
рис. 95-2. Формат файла записей фиксированной длины
В начале файла хранится счетчик записей nr и размерность записи sz. Работу с файлом удобнее всего организовать в режиме сеанса. Для этого здесь и далее будем использовать структурированный тип со встроенными функциями (см. 5.3). Элементы данных структуры будут содержать фрагменты образа структур данных двоичного файла, а встроенные функции – выполнять требуемые операции. При открытии файла в память читаются значения nr и sz и проверяется его корректность: с учетом размерностей всех элементов его длина должна быть равна nrsz+2sizeof(int).
//------------------------------------------------------95-03.cpp
// Файл записей фиксированной длины
// Структурированный тип со встроенными функциями
struct BFILE{
FILE *fd; // Файл в stdio
int nr,sz; // Образ структур данных файла
int create(char *name,int sz0){ // Создать пустой файл
if ((fd=fopen(name,"wb"))==NULL)
return 0; // Создать новый для записи
int nr0=0; // Записать счетчик и размерность
fwrite((void*)&sz0,sizeof(int),1,fd);
fwrite((void*)&nr0,sizeof(int),1,fd);
fclose(fd); fd=NULL; return 1; }
// Открыть существующий файл с проверкой
int open(char *name,int sz0){
if (fd!=NULL) return 0; // Файл уже открыт
if ((fd=fopen(name,"rb+wb+"))==NULL)
return 0; // Открыть для чтения и записи
fread((void*)&sz,sizeof(int),1,fd); // Читать из файла nr и sz
fread((void*)&nr,sizeof(int),1,fd);
fseek(fd,0L,SEEK_END); // Соответствует ли длина файла
if (ftell(fd)!=
2*sizeof(int)+nr*sz) // значениям nr и sz?
{ fclose(fd); fd=NULL; return 0;}
return 1;}
// Читать запись с заданным номером из открытого файла
void *get(int i){
if (fd==NULL) return NULL; // Файл не открыт
if (i<0 || i>=nr) return NULL; // Номер записи некорректен
void *q=new char[sz]; // Выделить память (в байтах)
if (fseek(fd,2*sizeof(int)+i*sz,SEEK_SET)==EOF)
{ delete []q; return NULL; } // Позиционирование по
if (fread(q,sz,1,fd)!=1) // вычисляемому адресу
{ delete []q; return NULL; } // Ошибка чтения
return q; }
// Добавить запись
int append(void *pp){
if (fd==NULL) return NULL; // Файл не открыт
fseek(fd,0L,SEEK_END); // Установиться на конец файла
if (fwrite(pp,sz,1,fd)!=1)
return 0; // Добавить запись
nr++; // Обновить переменную nr в файле
fseek(fd,sizeof( int),SEEK_SET);
if (fwrite((void*)&nr,sizeof(int),1,fd)!=1)
return 0;
return 1; }};
Создание двоичного файла представляет собой отдельную операцию create. Она не просто создает «пустой» файл, а записывает туда исходное состояние структуры данных, в нашем случае нулевой счетчик записей и переданную размерность типа данных. Остальные операции выполняются в файле, открытом в режиме чтения/записи/добавления. Кроме добавления и получения записи по логическому номеру возможно еще и обновление существующих записей. Операция физического удаления записи, а также вставки в таком файле отсутствуют: сдвигать записи в файле не принято, а «сжатие» файла может быть произведено только при его полной перезаписи в новый файл.
//------------------------------------------------------95-03.cpp
void main(){
BFILE FF={NULL,0,0}; // Структура – файл ЗФД
double A[]={4,6,2,8,3,4,1,5,6};
int n=sizeof(A)/sizeof(double);
FF.create("95-03.dat",sizeof(double));
if (!FF.open("95-03.dat",sizeof(double))) return;
for (int i=0;i<n;i++) FF.append(&A[i]);
for (i=n-1; i>=0; i--){ // Чтение в обратном порядке
double *pd=(double*)FF.get(i);
printf("%lf\n",*pd); delete pd;
}}Приведенный main демонстрирует особенности такого файла: он работает только на дополнение, уже имеющиеся записи можно извлекать и обновлять в любом порядке.
Следующий пример показывает, насколько далеко можно зайти, используя только последовательное чтение и вычисление адресов в массивах. Таблица произвольной размерности (столбцы и строки), с любыми, закрепленными за столбцами типами данных, представляет собой параметризованный файл записей фиксированной длины: размерности записей, будучи фиксированными, вычисляются с использованием данных, хранящихся в том же файле, ближе к началу.
рис. 95-3. Формат файла с таблицей произвольной размерности
Конкретнее, в начале файла находятся размерности таблицы – количество столбцов nc и строк nr. За ними следуют описатели столбцов, которые являются записями фиксированной длины (структурированный тип cDef). Описатель столбца содержит имя, тип и размерность типа в байтах. Таким образом, каждый столбец имеет собственные характеристики. Далее располагаются записи (строки таблицы), которые также представляют собой записи фиксированной длины. Каждая из них состоит из набора полей, соответствующих столбцам, и ее размерность равна суммарной размерности данных в столбцах.
Перейдем теперь к вычислениям. Начальный адрес области данных adata в файле вычисляется по формуле sizeof(int)2+sizeof(cDef)nc как сумма размерностей предшествующих данных. Размерность строки таблицы lr вычисляется как сумма размерностей столбцов, которые хранятся в описателях lr=Σsizei (i=0..nc-1). И, наконец, адрес произвольной ячейки таблицы также может быть вычислен: Adr(i,j)=adata+i*lr+ Σsizek(k=0..j-1) – он складывается из начального адреса области данных, суммы размерностей предшествующих строк и суммы размерностей предшествующих полей в текущей строке.
В структурированном типе FTABLE находятся фрагменты образа структуры данных файла: размерности и динамический массив описателей столбцов. Процедура открытия такого файла реализуется в режиме «раскрутки» - прочитанные данные используются для определения количества и размерностей следующих за ними. Сначала читаются размерности таблицы, по ним создается динамический массив описателей и читается из файла. Размерность записи определяется как сумма размерностей столбцов.
//------------------------------------------------------95-04.cpp
//---- Файл - таблица произвольной размерности
struct cDef { // Описатель столбца
int type; // тип столбца
int size; // размерность столбца в байтах
char name[30]; }; // Имя столбца
struct FTABLE{
FILE *fd; // Файл в stdio
int nc; // Количество столбцов
int nr; // Количество строк
int lr; // Размер строки таблицы
long adata; // Начальный адрес области строк
cDef *ST; // Динамический массив описателей
//------ Открыть файл и прочитать описатели столбцов
int open(char *name) {
int i;
if ((fd=fopen(name,"rb"))==NULL) return 0;
fread(&nc,sizeof(int),1,fd); // Чтение nc
fread(&nr,sizeof(int),1,fd); // Чтение nr
ST= new cDef[nc]; // Память под массив описателей
fread(ST,sizeof(cDef),nc,fd); // Чтение массива описателей
adata=sizeof(int)*2+sizeof(cDef)*nc;
// Вычисление адреса области данных
for (i=0,lr=0; i<nc; i++) // Вычисление длины строки
lr += ST[i].size;
return 1;}
//------------------------------------------------------95-04.cpp
//----- Чтение элемента таблицы из столбца j строки i
void *get(int i, int j){
if (fd==NULL) return NULL;
if (nc <=j || nr <=i) return NULL;
for ( int k=0,lnt=0; k<j; k++) // Смещение j-го столбца в строке
lnt += ST[k].size; // как сумма длин предыдущих столбцов
void *data=new char[ST[j].size]; // Память под ячейку таблицы
fseek(fd, adata+i*lr+lnt,SEEK_SET);
fread(data,ST[j].size,1,fd); // Чтение ячейки таблицы по адресу
return data;}
};Указатели в файлах. Связанные записи
Структуры данных, содержащие указатели, могут быть «спроецированы» из внутренней памяти во внешнюю – двоичный файл. Само собой разумеется, что значение указателя, представляющего собой адрес указуемой переменной в памяти программы, не имеет никакого смысла при размещении той же переменной в файле. Тогда каждому указателю, связывающему две переменные в памяти, нужно сопоставить аналогичный указатель в файле (или файловый указатель). Его значением является позиция (адрес) переменной при ее размещении в файле.
При наличии записей в файле, связанных указателем, имеют место два способа их размещения. При записи структуры данных в файл «хвостом вперед» сначала размещаются указуемые записи с целью получения их адресов в файле, а затем записи, содержащие указатели. В принципе сохранение цепочки связанных записей в таком виде может производиться вообще без позиционирования (в режиме последовательного доступа).
#define FNULL -1L
struct x { int val; // Связанная запись в памяти
x *ptr; }; // Указатель в памяти
struct fx{ int val;
long fptr;}; // Файловый указатель
x a1 = {0,NULL}; x a2 = {1, &a1};
fx b1,b2; // a2 ссылается на a1
fseek(fd, 0L, SEEK_END); // Разместить в файле указуемую
b1.val=a1.val;
b2.fptr = ftell(fd); // запись b1 и сохранить ее адрес в b2
fwrite(&b1, sizeof(fx), 1, fd);
…
fseek(fd, 0L, SEEK_END); // Разместить в файле запись,
b2.val=a2.val;
fwrite(&b2, sizeof(fx), 1, fd); // содержащую файловый указательЕстественное размещение «головой вперед» несколько сложнее:
разместить в файле все указуемые записи структуры данных и запомнить их файловые адреса;
сформировать значения файловых указателей в записях структуры данных, расположенных в памяти;
обновить значения записей структуры данных в файле, то есть переписать их из памяти по тем же файловым адресам.
fseek(fd, 0L, SEEK_END); // Разместить в файле запись,
long pb2=ftell(fd);
b2.val=a2.val;
fwrite(&b2, sizeof(fx), 1, fd); // содержащую файловый указатель
…
fseek(fd, 0L, SEEK_END); // Разместить в файле указуемую
b1.val=a1.val;
b2.fptr = ftell(fd); // запись b1 и сохранить ее адрес в b2
fwrite(&b1, sizeof(fx), 1, fd);
fseek(fd, pb2, SEEK_SET); // Вернуться к записи со ссылкой
fwrite(&b2, sizeof(x), 1, fd); // и обновить ееТакой алгоритм единственно возможен в структуре данных с циклическим (перекрестными) ссылками, например, в циклическом списке или графе.
Массив указателей
На примере массива указателей можно продемонстрировать различные технологические приемы работы со структурами данных в двоичном файле. Но для начала дадим описание формата представления данных в двоичном файле, содержащем массив файловых указателей на строки. Это необходимо хотя бы потому, что в самой программе формат файла определяется очень «косвенно», через последовательность операций позиционирования и чтения/записи данных:
в начале файла содержится описание массива файловых указателей: его размерность sz, текущее количество строк (рабочих указателей) ns и абсолютный адрес самого массива указателей в файле p0. Это необходимо для будущего перераспределения памяти во время переполнения массива указателей: его новая копия увеличенной размерности будет копироваться в конец файла;
сам массив файловых указателей содержит абсолютные адреса строк;
строки представлены как записи переменной длины в формате «счетчик символов (int) символы строки (char). Символ – ограничитель строки также сохраняется в записи.
рис. 95-5. Формат файла с массивом указателей на строки
Для такого файла в памяти может быть создан идентичный образ структуры данных – это динамический массив указателей на строки. Для массива файловых указателей строится соответствующий ему образ в памяти - динамический массив переменных типа long. Он сначала заполняется, а затем уже записывается в файл. Входной текстовый файл прочитывается два раза, первый раз - для определения количества строк и размерности массива указателей, второй раз - для формирования структуры данных. Массив файловый указателей пишется в двоичный файл также два раза: в первый раз, чтобы «занять место», а во второй раз - чтобы записать сформированные адреса строк (обновление).
//------------------------------------------------------95-06.cpp
//---- Создание файла с массивом указателей из текстового файла
#define FNULL 0
void save(char *in, char *out){
FILE *fdi,*fdo; char c[80]; int ns;
if ((fdi=fopen(in,"r"))==NULL) return;
if ((fdo=fopen(out,"wb"))==NULL) return;
for (ns=0; fgets(c,80,fdi)!=NULL; ns++); // Количество строк
int sz=ns*1.2; // Размерность с учетом резерва
fseek(fdi,0l,SEEK_SET); // Вернуться к началу
long *pp = new long[sz]; // Образ массива файловых указателей
for (int i=0;i<sz;i++) pp[i]=FNULL;
long p0=2*sizeof(int)+sizeof(long); // Начальное смещением МУ
fwrite(&sz,sizeof(int),1,fdo); // Записать размерность МУ
fwrite(&ns,sizeof(int),1,fdo); // Записать количество строк
fwrite(&p0,sizeof(long),1,fdo); // Записать адрес МУ
fwrite(pp,sizeof(long),sz,fdo); // Записать «пустой» МУ
for (i=0; i<ns; i++) { // Повторное чтение строк
pp[i]=ftell(fdo); // Получить адрес i-ой строки в файле
fgets(c,80,fdi); // и сохранить в массиве указателей
int l=strlen(c)+1; // Переписать в формате ЗПД
fwrite(&l,sizeof(int),1,fdo);
fwrite(c,l,1,fdo); }
fseek(fdo,p0,SEEK_SET); // Обновить в файле массив
fwrite(pp,sizeof(long),sz,fdo); // файловых указателей
fclose(fdo);}В программе присутствует единственное позиционирование - перед обновлением массива файловых указателей. Все остальные данные (размерность, смещение, массив указателей, сами строки) сохраняются последовательно.
Функция загрузки иллюстрирует тот факт, что структура данных должна полностью создаваться в динамический памяти. Происходит это в два этапа. Сначала создается и загружается образ массива файловых указателей, для которого создается аналогичный массив указателей на строки, но уже в памяти. Затем читаются сами строки.
//------------------------------------------------------95-07.cpp
//----- Загрузка массива указателей на строки из двоичного файла
char **load(char *name) // Функция возвращает динамический
{ FILE *fd; int i,sz,ns; // массив указателей на строки
long *pp,p0; // Динамический массив файловых указателей
char **p; // Динамический МУ на строки
if ((fd=fopen(name,"rb"))==NULL) return NULL;
fread(&sz,sizeof(int),1,fd); // Прочитать размерность
fread(&ns,sizeof(int),1,fd); // Прочитать количество строк
fread(&p0,sizeof(long),1,fd); // и адрес массива файловых указателей
pp=new long[ns]; // Создать динамический массив
p=new char*[ns+1]; // файловых указателей и указателей на строки
fseek(fd,p0,SEEK_SET); // Позиционироваться на МУ в файле
fread(pp,sizeof(long),ns,fd); // Читать массив файловых указателей
for (i=0; i<ns; i++)
{ int sz;
fseek(fd,pp[i],SEEK_SET); // Установиться по i-му файловому
fread(&sz,sizeof(int),1,fd); // указателю и прочитать запись
p[i]=new char[sz]; // переменной длины - строку
fread(p[i],sz,1,fd); }
p[ns]=NULL; fclose(fd); return p;}Строки как записи переменной длины позволяют работать с файлом только в режиме последовательного доступа. Наличие в файле массива указателей позволяет извлекать их в произвольном порядке. При поэлементой загрузке структуры данных в память читаются только те данные, которые необходимы для выполнения текущей операции. Для этого достаточно трех операций чтения и двух позиционирований. Массив указателей также не читается полностью, из него извлекается указатель по адресу p0+sizeof(long)*num.
//------------------------------------------------------95-08.cpp
//---- Массив указателей на строки, чтение по логическому номеру
char *load(char *name, int num) // Возвращается строка =
{ FILE *fd; int i,n,sz; long p0,pp; // динамический массив
if ((fd=fopen(name,"rb"))==NULL)
return NULL; // Режим чтения двоичного файла
fread(&sz,sizeof(int),1,fd); // Считать размерность МУ
fread(&n,sizeof(int),1,fd); // Считать количество указателей
fread(&p0,sizeof(long),1,fd); // и начальный адрес МУ в файле
if (num>=n) return NULL; // Нет записи с таким номером
fseek(fd,p0+sizeof(long)*num,SEEK_SET);
fread(&pp,sizeof(long),1,fd); // Прочитать указатель с номером num
fseek(fd,pp,SEEK_SET); // Установиться на запись
fread(&sz,sizeof(int),1,fd); // Прочитать длину записи
char *p=new char[sz]; // Создать динамический массив
fread(p,sz,1,fd); // Прочитать запись - строку
fclose(fd); return p; } // Возвратить указатель на строкуОбратите внимание, что операция чтения переменной pp из файла и последующего позиционирования по ее значению функционально эквивалентна косвенному обращению по указателю (операция "*") при работе с аналогичными структурами данных в памяти.
В заключение рассмотрим вариант загрузки частичного образа двоичного файла. Имеются в виду управляющие структуры - заголовок и сам массив файловых указателей. Они используются наиболее часто, и поэтому будут храниться в виде элементов данных структурированной переменной (объекта). Работа с файлом будет производиться в режиме сеанса.
//------------------------------------------------------95-09.cpp
//---- Массив указателей на строки - загрузка управляющих данных
struct DMUS{
FILE *fd; // Файл в stdio
int sz,ns; // Данные заголовка
long p0, *pp; // Образ массива файловых указателей
// Открытие файла и загрузка управляющих структур
int open(char name[]){
if ((fd=fopen(name,"rb+wb+"))==NULL)
return 0; // Режим чтения/записи/добавления
fread(&sz,sizeof(int),1,fd); // Считать размерность МУ
fread(&ns,sizeof(int),1,fd); // Считать количество указателей
fread(&p0,sizeof(long),1,fd); // и начальный адрес МУ в файле
pp=new long[sz]; // Создать образ МУ
fseek(fd,p0,SEEK_SET); // и прочитать его содержимое из файла
fread(pp,sizeof(long),sz,fd);
return 1;
}
// Обновление управляющих структур
void updateSys(){
fseek(fd,0,SEEK_SET); // В начале файла
fwrite(&sz,sizeof(int),1,fd); // Обновить заголовок
fwrite(&ns,sizeof(int),1,fd);
fwrite(&p0,sizeof(long),1,fd);
fseek(fd,p0,SEEK_SET);
fwrite(pp,sizeof(long),sz,fd);}В дополнение к операции открытия файла реализуется операция обновления образа управляющих структур из памяти в двоичный файл. Затем решается проблема придания «динамичности» массиву файловых указателей. Встроенная функция extend, вызываемая во всех операциях, связанных с увеличением размерности, сначала делает проверку на возможное переполнение и перераспределяет память в массиве файловых указателей, удваивая его размерность. Затем она позиционируется в конец файла, и полученный при помощи функции ftell адрес запоминает в p0 как новый адрес массива файловых указателей. После чего вызов функции обновления управляющих данных updateSys сохранить расширенный массив по новому адресу в конце файла.
//------------------------------------------------------95-09.cpp
// Перераспределение памяти под массив файловых указателей
void extend(){
if (ns!=sz) return;
sz*=2; // расширить образ МУ в памяти
pp=(long*)realloc(pp,sizeof(long)*sz);
fseek(fd,0,SEEK_END); // Установиться на конец файла
p0=ftell(fd); // и получить новый адрес МУ в файле
updateSys(); // Обновить заголовок и МУ на новом месте
}После всего этого программирование операций над отдельными строками превращается в банальные операции над образом массива файловых указателей. Например, для вставки строки по логическому номеру необходимо записать ее в конец файла, а полученный адрес вставить в массив файловых указателей на нужную позицию.
//------------------------------------------------------95-09.cpp
// Чтение по логическому номеру
char *get(int k){
if (fd==NULL || k>=ns) return NULL;
fseek(fd,pp[k],SEEK_SET);
int ll;
fread(&ll,sizeof(int),1,fd); // Прочитать длину записи
char *p=new char[ll]; // Создать динамический массив
fread(p,ll,1,fd); // Прочитать запись - строку
return p; }
// вставка по логическому номеру
int insert(char *s, int k){
if (fd==NULL || k>=ns) return 0;
extend(); // Отработать переполнение
fseek(fd,0,SEEK_END); // Спозиционироваться в конец файла
for(int j=ns-1;j>=k;j--)
pp[j+1]=pp[j]; // Сдвинуть указатели в массиве
ns++; pp[k]=ftell(fd); // Записать адрес новой строки
int ll=strlen(s)+1;
fwrite(&ll,sizeof(int),1,fd); // Записать строку в формате ЗПД
fwrite(s,ll,1,fd);
return 1; }
// Закрытие файла
void close(){ updateSys(); fclose(fd); }};Обратите внимание, что при вставке строк содержимое массива файловых указателей будет обновляться в файле только при переполнении. Поэтому при закрытии файла эту процедуру необходимо повторить. Пример работы с аналогичной структурой данных в двоичном файле см. также в 11.6.
Деревья
При работе с деревом в режиме создания полного образа структуры данных программа поддерживает два вида вершин: вершина в памяти, содержащая обычные указатели и вершина в файле, содержащая массив файловых указателей. Небольшое различие заключается еще и в способе хранения строки, связанной с вершиной: в памяти она адресуется отдельным указателем, а в файле – размещается непосредственно за вершиной в формате записи переменной длины (вершина содержит счетчик символов строки).
Операции сохранения и загрузки являются рекурсивными. Функция сохранения вершины «меняет ее адрес в памяти на адрес в файле», т.е. дописывает вершину в файл, предварительно сохранив в ней адреса потомков. Такая процедура записи дерева «хвостом вперед» вообще обходится без позиционирования, т.е. работает с файлом как с последовательным. Единственное позиционирование происходит при обновлении в начале файла указателя на корневую вершину
//------------------------------------------------------95-10.cpp
//---- Сохранение дерева в файле "хвостом вперед"
struct tree { // Вершина дерева в памяти
char *str; // Строка в памяти
int n; // Количество потомков
tree *p[4]; // Указатели на потомков в памяти
};
struct ftree{ // Вершина дерева в файле
int n; // Количество потомков
long fp[4]; // Указатели на потомков в файле
int sz; }; // Длина строки в файле (ЗПД)
#define FNULL -1L
#define TSZ sizeof(ftree)
//------ Функция записи возвращает адрес размещенной вершины в файле
long PutTree(tree *q, FILE *fd){
if (q == NULL) return FNULL;
ftree CUR; CUR.n=q->n; // Текущая вершина - локальная переменная
long pos;
for (int i=0; i<q->n; i++) // Рекурсивное сохранение потомков
CUR.fp[i]=PutTree(q->p[i],fd);
pos = ftell(fd); // Адрес вершины
CUR.sz=strlen(q->str)+1; // Длина строки (ЗПД)
fwrite(&CUR,TSZ,1,fd); // Сохранить вершину
fwrite(q->str,CUR.sz,1,fd); // Сохранить строку
return pos;}
// В начало файла записывается указатель на головную
// вершину дерева
void SaveTree(tree *p, char *name){
FILE *fd; long pos0; // Указатель на корневую вершину
if ((fd=fopen(name,"wb")) ==NULL) return;
fwrite(&pos0,sizeof(long),1,fd); // Резервировать место под указатель
pos0 = PutTree(p,fd); // Сохранить дерево
fseek(fd,0L,SEEK_SET); // Обновить указатель
fwrite(&pos0,sizeof(long),1,fd);
fclose(fd);}Для сохранения дерева «головой вперед» требуются небольшие изменения. Рекурсивная функция записи сначала размещает текущую вершину и запоминает ее адрес в файле, и только затем вызывает самое себя для размещения потомков. Полученные после размещения файловые указатели запоминает в образе текущей вершины, после чего обновляет ее в файле.
//------------------------------------------------------95-11.cpp
//------ Функция записи возвращает адрес размещенной вершины в файле
long PutTree(tree *q, FILE *fd){
if (q == NULL) return FNULL;
ftree CUR; CUR.n=q->n; // Текущая вершина - локальная переменная
fseek(fd,0,SEEK_END); // Записать вершину - занять место
long pos=ftell(fd);
CUR.sz=strlen(q->str)+1; // Длина строки (ЗПД)
fwrite(&CUR,TSZ,1,fd); // Сохранить вершину
fwrite(q->str,CUR.sz,1,fd); // Сохранить строку
for (int i=0; i<q->n; i++) // Рекурсивное сохранение потомков
CUR.fp[i]=PutTree(q->p[i],fd);
fseek(fd,pos,SEEK_SET); // Обновить вершину
fwrite(&CUR,TSZ,1,fd); //
return pos;}Последовательность действий по чтению образа дерева из файла более простая: по имеющемуся адресу вершины рекурсивная функция загружает локальную переменную – образ текущей вершины, из которой берутся значения файловых указателей на другие вершины и процесс повторяется. Вершины дерева в памяти, наоборот, создаются как динамические переменные.
//------------------------------------------------------95-12.cpp
//----- Загрузка вершины дерева и потомков из файла
tree *GetTree(long pos, FILE *fd){ // Вход - адрес вершины в файле
if (pos == FNULL) return NULL; // Результат - указатель на
tree *q=new tree; // вершину поддерева в памяти
ftree A; // Текущая вершина из файла -
fseek(fd,pos,SEEK_SET); // в локальной переменной
fread(&A,sizeof(ftree),1,fd);
q->str=new char[A.sz]; // Загрузка строки - ЗПД
fread(q->str,A.sz,1,fd);
q->n=A.n;
for (int i=0; i<A.n; i++) // Рекурсивная загрузка потомков
q->p[i]=GetTree(A.fp[i],fd); // и сохранение указателей
return q; }
// В начале файла - файловый указатель на корневую вершину дерева
tree *LoadTree(char *name){
FILE *fd; long phead;
if ((fd = fopen(name,"rb")) ==NULL) return NULL;
fread(&phead, sizeof(long), 1, fd);
return GetTree(phead, fd); }Технологию поэлементной загрузки проиллюстрируем на примере двоичного дерева. Операции поиска и вставки являются линейно рекурсивными, поэтому просматривать (и загружать из файла) требуется не все вершины, а только вершины «по пути следования». Образ текущей вершины загружается в локальную переменную, строка - в динамический массив.
//------------------------------------------------------95-13.cpp
//------ Поиск в двоичном дереве по образцу с поэлементной загрузкой
struct ftree { // Вершина дерева в файле
long fl,fr; // Указатели на потомков в файле
int sz; }; // Длина строки в файле (ЗПД)
char *FindTree(long pos, char *key, FILE *fd){
ftree A; char *str;
if (pos == FNULL) return NULL;
fseek(fd, pos, SEEK_SET);
fread(&A, sizeof( ftree), 1, fd);
str=new char[A.sz]; // Чтение строки в динамический массив
fread(str,A.sz,1,fd);
if ( strncmp(str,key,strlen(key))==0)
return str; // Совпадение с образцом
char *pnext; // Найденная строка от потомка
if (strcmp(str,key) > 0)
pnext=FindTree(A.fl,key,fd);
else
pnext=FindTree(A.fr,key,fd);
delete str; // Уничтожить текущую строку
return pnext; } // и вернуть строку потомкаАналогичная схема имеет место, когда производятся изменения в структуре данных. Если это связано с изменением связей между элементами структуры, то переменные (образы вершин), в которых изменяются значения файловых указателей, необходимо обновлять в файле.
//------------------------------------------------------95-14.cpp
//---- Добавление новой вершины в двоичное дерево в двоичном файле
long AppendOne( char *str, FILE *fd){
long pos; // Добавить в файл новую вершину дерева
ftree Elem; // Образ вершины - локальная переменная
Elem.fr=Elem.fl=FNULL;
Elem.sz=strlen(str)+1;
fseek(fd,0L,SEEK_END);
pos = ftell(fd);
fwrite(&Elem,sizeof(ftree),1,fd);
fwrite(str, Elem.sz, 1, fd);
return pos; }
void AppendTree(long pos, char *newstr, FILE *fd){
ftree A; char *str;
fseek(fd, pos, SEEK_SET);
fread(&A, sizeof(ftree), 1, fd);
str=new char[A.sz]; // Чтение строки в динамический массив
fread(str,A.sz,1,fd); // в формате ЗПД
if ( strcmp(str,newstr)>0){ // Выбор поддерева
if (A.fl!=FNULL){ // Есть потомок - рекурсивный вызов
AppendTree(A.fl,newstr,fd);
delete str; return;} // Выход без обновления
else A.fl=AppendOne(newstr,fd);
} // Нет потомка - добавить в это место вершину
else {
if (A.fr !=FNULL){
AppendTree(A.fr,newstr,fd);
delete str; return; }
else A.fr = AppendOne(newstr,fd);
}
fseek(fd, pos, SEEK_SET); // Обновить текущую вершину дерева
fwrite(&A, sizeof( ftree), 1, fd);
delete str; }Замечание: функция добавления вершины в дерево не работает с пустым деревом, поэтому этот случай необходимо рассматривать отдельно перед ее вызовом.
Списки
Списки довольно редко используются в двоичных файлах, поскольку являются последовательными структурами данных, а весь эффект работы с файлами базируется на прямом доступе. Тем не менее, приведем пример построения односвязного списка в файле с поэлементной загрузкой в процессе упорядоченной вставки новых элементов. Обратите внимание на полную функциональную аналогию алгоритма работы с односвязным списком в памяти и в файле. Особенности работы с файлом заключаются в том, что для каждого активизируемого элемента структуры данных необходим аналогичный элемент в памяти, а для указателя на него - соответствующий файловый указатель. Так, если для включения в односвязный список с сохранением упорядоченности необходимо использовать текущий и предыдущий элементы списка, то необходимы две локальные структурированные переменные - текущий и предыдущий элементы списка cur и prev, а также два файловых указателя, определяющих их расположение в файле - fcur и fprev. В начале файла размещается заголовок списка - файловый указатель на первый элемент.
//------------------------------------------------------95-15.cpp
//--------- Односвязный список в файле. Поэлементная загрузка.
#define FNULL -1L
struct flist { // Определение элемента списка в файле
int val; // Значение элемента списка
long fnext; // Файловый указатель на следующий элемент
}; // При поэлементной работе flist *next не нужен
void show(FILE *fd) // Просмотр списка
{ flist cur; // Файловый указатель текущего элемента
long fcur; // Текущий элемент
fseek(fd,0L,SEEK_SET);
fread(&fcur,sizeof(long),1,fd); // Загрузить указатель на первый
for (; fcur!=FNULL; fcur=cur.fnext) {
fseek(fd,fcur,SEEK_SET); // Загрузка текущего элемента
fread(&cur,sizeof(flist),1,fd);
printf("%d ",cur.val);
} puts(""); }
// Включение с сохранением упорядоченности
void ins_sort(FILE *fd, int vv) {
flist cur,prev,lnew; // Текущий, предыдущий и новый элементы списка
long fnew,fcur,fprev; // Файловые указатели элементов списка
fseek(fd,0L,SEEK_SET);
fread(&fcur,sizeof(long),1,fd);
for (fprev=FNULL; fcur!=FNULL;
fprev=fcur, prev=cur, fcur=cur.fnext)
{ // Переход к следующему
fseek(fd,fcur,SEEK_SET); // с запоминанием предыдущего
fread(&cur,sizeof(flist),1,fd); // элемента и его адреса
if (cur.val > vv) break; // Поиск места - текущий > нового
}
lnew.val = vv;
lnew.fnext=fcur;
fseek(fd,0L,SEEK_END); // Заполнение нового элемента списка
fnew=ftell(fd); // Запись в файл и получение адреса
fwrite(&lnew,sizeof(flist),1,fd);
if (fprev==FNULL) { // Включение первым - обновить заголовок
fseek(fd,0L,SEEK_SET);
fwrite(&fnew,sizeof(long),1,fd);}
else { // Включение после предыдущего -
prev.fnext=fnew; // обновить предыдущий
fseek(fd,fprev,SEEK_SET);
fwrite(&prev,sizeof(flist),1,fd);
}}Лабораторный практикум
Файл записей переменной длины перед каждой записью содержит целое, определяющее длину этой записи. Написать функции ввода и вывода записи в такой файл. Функция ввода (чтения) должна возвращать размер очередной прочитанной записи. Использовать функции для работы с двумя файлами - строк и динамических массивов целых чисел.
Программа создает в файле массив указателей фиксированной размерности на строки текста. Размерность массива находится в начале файла, сами строки также хранятся в файле в виде записей переменной длины. Написать функции чтения/записи строки из файла по заданному номеру.
Программа переписывает дерево с ограниченным количеством потомков из памяти в файл записей фиксированной длины, заменяя указатели на вершины номерами записей в файле. Затем выполняет обратную операцию.
Дерево представлено в файле записей фиксированной длины естественным образом: если вершина дерева в файле находится в записи под номером N, то ее потомки - под номерами 2N и 2N+1. Корень дерева - запись с номером 1. Написать функции включения в дерево с сохранением упорядоченности и обхода дерева (вывод упорядоченных записей). (Необходимо учесть, что несуществующие потомки должны быть записями специального вида (например, пустой строкой)).
Упорядоченные по возрастанию строки хранятся в файле в виде массива указателей (см.вар.2). Написать функции включения строки в файл и вывода упорядоченной последовательности строк (просмотр файла).
Для произвольного текстового файла программа составляет файл записей фиксированной длины, содержащий файловые указатели на строки (см. л/р 6, вар.3). Используя массив указателей на строки из этого файла программа производит логическое удаление, перестановку и сортировку строк, не меняя самого текстового файла.
Выполнить задание 3 применительно к графу, представленному списковой структурой.
Составить файл записей фиксированной длины, в котором группы записей связаны в односвязные списки (например, списочный состав студентов различных групп). В начале файла предусмотреть таблицу заголовков списков. Написать функции дополнения и просмотра списка с заданным номером.
Создать файл, содержащий массив указателей на строки, представленные записями переменной длины. В начале файла - целая переменная - размерность массива указателей. Последовательность указателей ограничена NULL - указателем. Реализовать функции загрузки строки по логическому номеру и добавления строки по логическому номеру.
Создать файл, содержащий массив указателей на упорядоченные в алфавитном порядке строки, представленные записями переменной длины. Реализовать функцию двоичного поиска строки по строке-образцу, начало которой совпадает с искомой строкой.
В файле записей фиксированной длины содержится двоичное дерево. Вершина содержит знчение типа int, а также номера соответствующих записей для правого и левого потомков. Реализовать функцию включения нового значения в существующий файл в виде новой вершины двоичного дерева.
Вершина двоичного дерева содержит указатель на строку. Написать функции сохранения и загрузки дерева из файла. Вершина дерева должна содержать файловые указатели на потомков, а также файловый указатель на строку - запись переменной длины.
Вершина двоичного дерева содержит указатель на строку. Написать функции сохранения и загрузки дерева из файла. Вершина дерева должна быть записью переменной длины, содержать файловые указатели на потомков и строку.
Файл содержит односвязный список. Элемент списка содержит файловый указатель на следующий и строку - запись переменной длины. В начале файла - указатель на первый элемент списка. Реализовать функции просмотра списка и включения строки по номеру.
Файл содержит односвязный список. Элемент списка содержит файловый указатель на следующий и строку - запись переменной длины. В начале файла - указатель на первый элемент списка. Реализовать функции просмотра списка и включения строки с сохранением упорядоченности.
Вопросы без ответов Определите структуру данных в двоичном файле произвольного доступа путем анализа последовательности операций позиционирования и ввода-вывода.
Пример оформления тестового задания. Ввиду того, что для вызова большинства функций необходимо иметь двоичный файл соответствующего формата, можно ограничиться анализом текста программы.
//------------------------------------------------------95-16.cpp
//------------------------------------------------------
#define FNULL -1L
struct tree { tree *p[4]; char *s; }; // Вершина дерева в памяти
struct ftree { long fp[4]; int sz; }; // Вершина дерева в файле
tree *F(FILE *fd, long pos)
{ ftree A; // Текущая вершина из файла
if (pos==FNULL) return NULL; // NULL-указатель - выйти
tree *q = new tree; // Создать вершину в динам. памяти
fseek(fd,pos,SEEK_SET); // Позиционироваться на вершину
fread( (void*)&A, sizeof(ftree),1,fd); // в файле и читать ее
q->s= new char[A.sz+1]; // Строка запись переменной длины
fread(q->s,A.sz,1,fd); // следует сразу за вершиной
q->s[A.sz]=0; // Добавить ограничитель конца строки
for (int i=0; i<4; i++) // рекурсивная загрузка потомков
q->p[i]=F(fd,A .fp[i]);
return q; } // В начале файла корневая вершина
void main() { FILE *fd=fopen("a.dat","rb"); tree *head = F(fd,0L); }Несомненно, речь идет о дереве, которое строится в памяти, поскольку функция является рекурсивной и возвращает указатель на вершину дерева в памяти. Вершина дерева в памяти содержит до 4 указателей на потомков и указатель на связанную с ней строку. Функция создает в динамической памяти вершину дерева, получая в качестве параметров открытый файл и файловый указатель на место расположения текущей вершины. В файле также имеет место дерево, фиксированная часть вершины которого представлена структурой ftree. Текущая вершина в файле загружается в локальную переменную A. Вершина в файле содержит массив файловых указателей на потомков – fp и строку, представленную записью переменной длины. В самой структуре ftree имеется счетчик длины строки – sz. То, что чтение строки производится без позиционирования, говорит о том, что сама строка непосредственно следует за вершиной. В памяти программы строка размещается в отдельном динамическом массиве. В начале файла находится корневая вершина дерева (следует из main).
//------------------------------------------------------95-17.cpp
struct man { int dd,mm,yy; char *addr; };
//------------------------------------------------------ 1
man *F1(int n, FILE *fd)
{ man *p = new man;
fseek (fd, (long)sizeof( man)*n, SEEK_SET);
fread (p, sizeof( man),1,fd);
return(p); }
//------------------------------------------------------ 2
void *F2(FILE *fd)
{ int n; void *p;
fread(&n,sizeof(int),1,fd);
if (n==0) return(NULL);
p = ( void*) new char[n];
fread(p,n,1,fd);
return p; }
//------------------------------------------------------ 3
double *F3(FILE *fd)
{ int n; double *p;
fread(&n,sizeof(int),1,fd);
if (n==0) return(NULL);
p = new double[ n+1];
fread(p,sizeof(double),n,fd);
p[n]=0.0;
return p; }
//------------------------------------------------------ 4
#define FNULL -1L
struct xxx { long fnext; /*. . .*/ };
xxx *F4(int n,FILE *fd)
{ xxx *p; long p0;
p = new xxx;
fseek(fd,0L,SEEK_SET);
fread(&p0,sizeof(long),1,fd);
for (; p0!=FNULL && n!=0; n--, p0 = p->fnext) {
fseek(fd,p0,SEEK_SET);
fread(p,sizeof( xxx),1,fd); }
return p; }
//------------------------------------------------------ 5
man *F5(int n, FILE *fd)
{ long fp; man *p = new man;
fseek(fd, sizeof(long)*n,SEEK_SET);
fread(&fp,sizeof(long),1,fd);
fseek(fd,fp,SEEK_SET);
fread(p,sizeof(man),1,fd);
return p; }
//------------------------------------------------------ 6
void *F6(int n, FILE *fd)
{ int sz; void *p;
fseek(fd,0L,SEEK_SET);
fread(&sz,sizeof(int),1,fd);
p = ( void*) new char[sz];
fseek (fd, (long)sz * n +sizeof(int), SEEK_SET);
fread (p, sz,1,fd);
return p; }
//------------------------------------------------------ 7
void *F7(int n, FILE *fd)
{ int sz; void *p; long p0;
fseek(fd,0L,SEEK_SET);
fread(&sz,sizeof(int),1,fd);
fread(&p0,sizeof(long),1,fd);
p = (void*)new char[sz];
fseek (fd, p0 + sizeof(long)*n, SEEK_SET);
fread (&p0, sizeof(long),1,fd);
fseek(fd, p0, SEEK_SET);
fread(p, sz, 1, fd);
return p; }
//------------------------------------------------------ 8
char *F8(int n, FILE *fd)
{ char *p; long fp; int i;
fseek(fd, sizeof(long)*n,SEEK_SET);
fread(&fp,sizeof(long),1,fd);
fseek(fd,fp,SEEK_SET);
n = 80; p = new char [n];
for (i=0;; i++) {
if (i==n) p = (char*)realloc(p, n=n*2);
fread(p+i,1,1,fd);
if (p[i]=='\0') return p;
}
return p; }
//------------------------------------------------------ 9
#define FNULL -1L
char *F9(int n, FILE *fd)
{ long p0; int sz; char *p;
fseek(fd,0L,SEEK_SET);
fread(&p0,sizeof(long),1,fd);
for (; p0!=FNULL && n!=0; n--) {
fseek(fd,p0,SEEK_SET);
fread(&p0,sizeof(long),1,fd);
}
if (p0==FNULL) return(NULL);
fread(&sz,sizeof(int),1,fd);
p = new char[sz+1];
fread(p,sz,1,fd);
p[sz]='\0'; return p;}
//-------------------------------------------------------- 10
char *F10(FILE *fd)
{ int n; char *p;
fread(&n,sizeof(int),1,fd);
if (n==0) return(NULL);
p = new char[n];
fread(p,n,1,fd);
return p; }
//-------------------------------------------------------- 11
void F11(FILE *fd, char *s)
{ int n;
fseek(fd,0L,SEEK_END);
n = strlen(s)+1;
fwrite(&n,sizeof(int),1,fd);
fwrite(s,n,1,fd); }
//-------------------------------------------------------- 12
double *F12(FILE *fd)
{ int n, dn; double *p;
fread(&n,sizeof(int),1,fd);
if (n==0) return(NULL);
dn = n / sizeof(double);
p = new double[ dn+1];
p[0]=dn;
fread(p+1,sizeof(double), dn, fd);
return p; }
//-------------------------------------------------------- 13
void F13(FILE *fd, double *s, int dn)
{ int n;
n = dn * sizeof(double);
fseek(fd,0L,SEEK_END);
fwrite(&n,sizeof(int),1,fd);
fwrite(s,sizeof(double),dn,fd); }
//------------------------------------------------------ 14
void F14(FILE *fd)
{ int n; void *p;
fread(&n,sizeof(int),1,fd);
if (n==0) return;
p = ( void*) new char[n];
fread(p,n,1,fd);
switch (n) {
case sizeof(int): printf("%d ",*(int*)p); break;
case sizeof(long): printf("%ld ",*(long*)p); break;
default: printf("%s ",(char*)p); break;
} delete p; }
//------------------------------------------------------ 15
char *F15(int n, FILE *fd)
{ int m; char *p; long fp;
fseek(fd, sizeof(long)*n,SEEK_SET);
fread(&fp,sizeof(long),1,fd);
fseek(fd,fp,SEEK_SET);
fread(&m,sizeof(int),1,fd);
p=new char [m];
fread(p,m,1,fd);
return p ; }
//------------------------------------------------------ 16
char *F16(int n, FILE *fd1, FILE *fd2)
{ long pp; char *q;
fseek(fd1,n*sizeof(long),SEEK_SET);
fread(&pp,sizeof(long),1,fd1);
q = new char[80];
fseek(fd2,pp,SEEK_SET);
fgets(q,80,fd2);
return q; }
//------------------------------------------------------ 17
char **F17(FILE *fd)
{ int n,m,i; char **p; long *fp;
fseek(fd, 0L,SEEK_SET);
fread(&n,sizeof(int),1,fd);
p = new char *[n+1];
fp = new long[n];
fread(fp,sizeof(long),n,fd);
for (i=0; i<n; i++) {
fseek(fd, fp[i],SEEK_SET);
fread(&m,sizeof(int),1,fd);
p[i]= new char[m];
fread(p[i],m,1,fd);
}
p[n]=NULL; return p ; }
//------------------------------------------------------ 18
#define FNULL -1L
struct ooo { ooo *p[20]; char *s; long fs; long fp[20]; };
ooo *F18(FILE *fd, long pos)
{ int i,m; ooo *q;
if (pos==FNULL) return NULL;
q = new ooo;
fseek(fd,pos,SEEK_SET);
fread(q, sizeof(ooo),1,fd);
fseek(fd,q->fs,SEEK_SET);
fread(&m,sizeof(int),1,fd);
q->s= new char[m];
fread(q->s,m,1,fd);
for (i=0; i<20; i++) q->p[i]=F18(fd,q->fp[i]);
return q; }
void main() { FILE *fd; ooo *head = F18(fd,0L); }
//------------------------------------------------------ 19
man *F19(FILE *fd)
{ man *p; int n;
fread(&n,sizeof(int),1,fd);
p = new man;
fread (p, sizeof(man),1,fd);
n = n - sizeof(man);
p->addr = new char[n];
fread(p->addr,n,1,fd);
return p; }
//------------------------------------------------------ 20
void F20(FILE *fd, man *p)
{ int n = sizeof(man)+strlen(p->addr)+1;
fseek(fd,0L,SEEK_END);
fwrite(&n,sizeof(int),1,fd);
fwrite (p, sizeof(man),1,fd);
n = n - sizeof(man);
fwrite (p->addr, n,1,fd ); }