3.3Мультисписки в бинарных файлах

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

Правда при этом возникают дополнительные затраты на ведение списка "дыр", так как в этом случае образуется несколько видов "дыр", например дыры для университетов, дыры для факультетов и т.д. наиболее простым является поддержание соответствующего количества списков дыр.

Другим, более сложным но и более экономичным решением, является использование одного интегрированного списка, когда смежные дыры объединяются в одну дыру дыр. Дыры в таком списке, в общем случае, будут иметь разную размерность. При этом смежные дыры могут объединяться в одну дыру. Место для нового элемента в таком списке выбирается по принципу выбора первой подходящей по объему дыры с корректировкой размера и позиции начала возможной оставшейся свободной части дыры. Структура такого списка в файле приведена на рисунке 3.4.

Изложенного выше материала достаточно для самостоятельной реализации мультисписка на предложенных принципах.

Рисунок 3.4 – Физическая структура мультисписка на базе массивов указателей в файле

3.4Сохранение и восстановление мультисписка в динамической памяти

Рассмотрим эту задачу для случая, когда мультисписок представлен спомощью массивов указателей, содержащих информационные поля, характеризующие мультисписок.

Одним из первых практических вопросов, которые возникают при использовании мультисписков в динамической памяти для хранения реальных данных это вопрос сохранения такого мультисписка в файле и его восстановление в динамическую память.

На первый взгляд для хранения мультисписка в файле следует использовать предложенную выше структуру файла для представления мультисписка. Однако это сложное решение для поставленной задачи. Ведь здесь стоит вопрос только хранения, а не модификации структуры мультисписка.

Более простым наиболее интуитивно понятным решением является "разворачивание" мультисписка в одну последовательность. Фактически это обход сильноветвящегося дерева в прямом порядке. Абстрактным корнем такого дерева является указатель на начало списка верхнего уровня.

Для предложенного выше мультисписка это выглядит следующим образом.

В файл заносятся сведения о первом (текущем) университете и количестве факультетов этого университета.

Затем в файл заносятся сведения о его первом (текущем) факультете и количестве кафедр этого факультета.

Для этого факультета в файл заносятся сведения о его первой (текущей) кафедре и количестве преподавателей этой кафедры.

Для этой кафедры в файл заносятся сведения о всех ее преподавателях.

После чего выполняется переход к следующей кафедре данного факультета и т.д. пока не исчерпается список всех кафедр данного факультета.

После этого выполняется переход к следующему факультету данного университета и т.д. пока не исчерпается список всех факультетов данного университета.

После этого выполняется переход к следующему университету и т.д. пока не исчерпается список всех университетов.

Для организации в файле связей, идентичных связям в мультисписке, между иерархически соподчиненными элементами разных уровней мультисписка, занесенных в файл по предложенному выше способу, предлагается следующая схема.

Записи в файле для университетов, факультетов и кафедр кроме соответствующих информационных полей имеют по одному служебному полю Count -количество элементов в непосредственно подчиненном списке. Эта информация легко доступна из поля PosCnt соответствующего массива указателей. Служебное поле Count не требуются только для записей лекторы, так как у лекторов нет соподчиненных им списков элементов. Кроме того необходима начальная запись - заголовок, которая должна обязательно содержать информационное поле Count -количество университетов, и, возможно, ряд других полей по усмотрению разработчика.

Рисунок 3.5 – Логическая структура мультисписка «Министерство образования»

Схематически предложенная структура хранения мультисписка в файле представлена ниже.

3

У1

3

Ф11

0

Ф12

2

К121

0

К122

0

Ф13

0

У2

2

Ф21

3

К211

2

Л2111

Л2112

Количество факультетов у Университета 1

Кафедры факультета Ф12

Лекторы для кафедры

К211

Количество кафедр

У факультета Ф21

Количество

университетов

К212

0

К213

0

Ф22

0

У3

2

Ф31

0

Ф32

0

где У – университет;

Ф – факультет;

К – кафедра;

Л – лектор.

Рисунок 3.6 – Физическая структура сохранения в файле мультисписка «Министерство образования»

Содержимое введенных информационных полей используется при восстановлении мультисписка из файла.

Таким образом сохранение мультисписка в файле реализуется с помощью системы вложенных друг в друга циклов. Переменная цикла каждого такого цикла принимает свое значение от 0 до содержимого поля Count соответствующего массива указателей, например для внешнего цикла это был массив указателей на университеты.

Следовательно для восстановления мультисписка из файла необходима такая же система вложенных друг в друга циклов.

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

typedef

struct FElmList

{

char Name[30];

int Accredit;

char Address[30];

int CountFct;

} TFListU;

typedef

struct FListF

{

char NameF[20];

. . .

int CountKaf;

}TFListF;

typedef

struct FListK

{

char NameK[20];

. . .

int CountLec;

}TFListK;

typedef

struct FListL

{

char NameL[20];

. . .

}TFListL;

typedef FILE* TFile;

:

Функция сохранения мультисписка в файле получает имя файла, в который будет сохранен мультисписок, файловый указатель и указатель на начало мультисписка – PtrArrU (указатель на начало списка университетов). Функция возвращает false если не удалось открыть файл.

bool SaveToFile(char* FileName, TFile &f, void * PtrArrU)

{

if ((f = fopen(FileName, "wb")) == NULL)

{

return false; // Если не удалось открыть файл

}

int CountU;

int i, j, k, n;

//Переменные для записи в файл элементов списка

TFListU Struct_Univ;

TFListF Struct_Fct;

TFListK Struct_Kaf;

TFListL Struct_Lec;

//Указатели на списоки элементов

void* PtrArrF;

void* PtrArrK;

void* PtrArrL;

CountU = ((int*)PtrArrU)[PosCnt]; //количество университетов

if (CountU == 0) //список унверситетов пуст

{

return true;

}

fwrite (&CountU, sizeof(CountU), 1, f); //запись в файл количества университетов

//цикл для университетов

for (I = 0; i < CountU; i++)

{

//Переписываем текущий университет в переменную для записи в файл

strcpy(Struct_Univ.Name, ((TListU*)(((void**)PtrArrU)[i]))->Name);

strcpy(Struct_Univ.Address,((TListU*)(((void**)PtrArrU)[i]))->Address);

Struct_Univ.Accredit = ((TListU*)(((void**)PtrArrU)[i]))->Accredit;

//…

Struct_Univ.CountFct = ((int*)(((TListU*)(((void**)PtrArrU)[i]))->

SubLevel))[PosCnt];

fwrite (&Struct_Univ, Struct_Univ), 1, f); //запись университета

//формирование указателя на массив факультетов

PtrArrF = ((TListU*)(((void**)PtrArrU)[i]))->SubLevel;

//цикл для факультетов

for ( j = 0; j < ((int*)PtrArrF)[PosCnt] ; j++)

{

//обработка записи для текущего факультета

strcpy(Struct_Fct.NameF, ((TListF*)(((void**)PtrArrF)[j]))->NameF);

//…

Struct_Fct.CountKaf= ((int*)(((TListF*)(((void**)PtrArrF)[j]))->

SubLevel))[PosCnt];

fwrite (&Struct_Fct, sizeof(Struct_Fct), 1 , f); //запись факультета

//формирование указателя на массив кафедр

PtrArrK = ((TListF*)(((void**)PtrArrF)[j]))->SubLevel;

//цикл для кафедр

for ( k = 0; k < ((int*)PtrArrK)[PosCnt]; k++)

{

//обработка записи для текущей кафедры

strcpy(Struct_Kaf.NameK, ((TListK*)(((void**)PtrArrK)[k]))->

NameK);

//…

Struct_Kaf.CountLec= ((int*)(((TListK*)(((void**)PtrArrK)[k]))->

SubLevel))[PosCnt];

fwrite (&Struct_Kaf, sizeof(Struct_Kaf),1, f); //запись кафедры

//формирование указателя на массив лекторов

PtrArrL = ((TListK*)(((void**)PtrArrK)[k]))->SubLevel;

//цикл для лекторов

for (n = 0; n < ((int*)PtrArrL)[PosCnt]; n++ )

{

//обработка записи для текущего лектора

strcpy(Struct_Lec.NameL, ((TListL*)(((void**)PtrArrL)[n]))->

NameL);

//…

fwrite(&Struct_Lec, sizeof(Struct_Lec), 1, f); //запись

лектора

} // for для n

} // for для k

} // for для j

} // for для i

return true;

fclose(f);

} //SaveToFile

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

Для предложенного выше файла это выглядит следующим образом:

В в куче выделяется место для массива указателей на университеты. Размер массива указателей определяется из значения начальной записи файла и записывается в переменную CountU. Формируются служебные элементы массива.

Затем в куче выделяется место для первого (текущего) университета и заносятся сведения об этом университете.

После чего в куче выделяется место для массива указателей на факультеты данного университета. Размер массива указателей определяется из значения поля CountFct записи файла для обрабатываемого университета. Формируются служебные элементы массива.

Адрес массива указателей на факультеты заносится в поле, содержащее указатель на подсписок у текущего университета.

Затем в куче выделяется место для первого (текущего) факультета и заносятся сведения об этом факультете.

После чего в куче выделяется место для массива указателей на кафедры данного факультета. Размер массива указателей определяется из значения поля CountKaf записи файла для обрабатываемого факультета. Формируются служебные элементы массива.

Адрес массива указателей на кафедры заносится в поле, содержащее указатель на подсписок у текущего факультета.

Затем в куче выделяется место для первой (текущей) кафедры и заносятся сведения об этой кафедре.

После чего в куче выделяется место для массива указателей на преподавателей данной кафедры. Размер массива указателей определяется из значения поля CountLec записи файла для обрабатываемой кафедры. Формируются служебные элементы массива.

Адрес массива указателей на преподавателей заносится в поле, содержащее указатель на подсписок у текущей кафедры.

Затем в куче последовательно выделяется место для текущего преподавателя и заносятся сведения об этом преподавателе.

После чего выполняется переход к следующей кафедре данного факультета и т.д.

Затем выполняется переход к следующему факультету данного университета и т.д.

После чего выполняется переход к следующему университету и т.д.

Следовательно для восстановления мультисписка из файла необходима такая же система вложенных друг в друга циклов. Переменная цикла каждого такого цикла должна принимать свои значения от 0 до содержимого поля Count соответствующей записи файла. Так для внешего цикла – цикл перебора университетов, верхняя граница цикла определяется из значения CountU начальной записи файла. Для следующего по вложенности цикла - цикл перебора факультетов, верхняя граница цикла определяется из поля CountFct записи для текущего университета и т.д.

bool RestoreMltListFromFile(char* FileName, TFile &f, void * &PtrArrU)

{

//Если произошла ошибка открытия файла

if ((f = fopen(FileName, "rb")) == NULL)

{

return false;

}

int CountU;

//переменные для считывания из файла элементов списка

TFListU Struct_Univ;

TFListF Struct_Fct;

TFListK Struct_Kaf;

TFListL Struct_Lec;

//указатели на массивы указателей на элементы списка

void* PtrArrF;

void* PtrArrK;

void* PtrArrL;

// указатели на создаваемые в куче элементы списка

void* PtrU;

void* PtrF;

void* PtrK;

void* PtrL;

int i, j, k, n;

//выделение памяти для массива указателей на университеты

// считывание количества университетов из файла

fread(&CountU, sizeof(CountU), 1, f);

/*выделение места под считанный размер списка плюс место для служебной информации*/

PtrArrU = new void*[CountU+2];

/*формирование действующего указателя PtrArU в новом массиве

указателей

PtrArrU = (void*)(((int)PtrArrU) + sizeof(int) * 2);

/*установка значения количества элементов списка в массиве*/

((int*)PtrArrU)[PosCnt] = CountU;

/*установка размера массива*/

((int*)PtrArrU)[PosSize] = CountU;

//цикл для восстановления университетов

for (I = 0; I < CountU; i++)

{

fread(&Struct_Univ, sizeof (Struct_Univ), 1, f );

//выделение памяти для текущего университета

PtrU = new TListU;

((void**)PtrArrU)[i]= PtrU; /*сохранение указателя на текущий университет в

массиве указателей на университеты*/

//формирование полей текущего университета

strcpy(((TListU*)PtrU)->Name, Struct_Univ.Name );

strcpy(((TListU*)PtrU)->Address, Struct_Univ.Address);

((TListU*)PtrU)->Accredit = Struct_Univ.Accredit;

//…

//выделение памяти для массива указателей на факультеты

PtrArrF = new void*[Struct_Univ.CountFct+2];

/*формирование действующего указателя PtrArF в новом массиве указателей*/

PtrArrF = (void*)(((int)PtrArrF) + sizeof(int) * 2);

/*установка значения количества элементов списка факультетов в массиве

( (int*) PtrArrF) [PosCnt] =Struct_Univ.CountFct;

/*установка размера массива указателей на факультеты*/

((int*)PtrArrF)[PosSize] = Struct_Univ.CountFct;

/*Указатель на список факультетов заносим в поле SubLevel текущего

университета – так получается связь университета с его подсписком факультетов*/

((TListU*)PtrU)->SubLevel = PtrArrF;

//цикл для восстановления факультетов

for (j=0; j < Struct_Univ.CountFct ; j++ )

{

fread(&Struct_Fct, sizeof(Struct_Fct), 1 ,f );

//выделение памяти для текущего факультета

PtrF = new TListF;

((void**)PtrArrF)[j] = PtrF; //сохранение указателя на текущий

факультет

//формирование полей текущего факультета

strcpy( ( (TListF*)PtrF)->NameF, Struct_Fct.NameF);

//…

//выделение памяти для массива указателей на кафедры

PtrArrK = new void* [Struct_Fct.CountKaf+2];

/*формирование действующего указателя PtrArK в новом

массиве указателей*/

PtrArrK= (void*)(((int)PtrArrK) + sizeof(int) * 2);

//установка значения количества элементов списка кафедр в массиве

((int*)PtrArrK)[PosCnt] = Struct_Fct.CountKaf;

/*установка размера массива спиская кафедр*/

((int*)PtrArrK)[PosSize] = Struct_Fct.CountKaf;

/*Формирование поля – указатель на подсписок у факультета*/

/*Заносим в это поле указатель на массив указателей на кафедры*/

((TListF*)PtrF) -> SubLevel = PtrArrK;

//цикл для восстановления кафедр

for (k = 0; k < Struct_Fct.CountKaf ; k++ )

{

fread(&Struct_Kaf, sizeof(Struct_Kaf),1 , f);

//выделение памяти для текущей кафедры

PtrK = new TListK;

((void**)PtrArrK)[k] = PtrK; /*сохранение указателя на текущую

кафедру*/

//формирование полей текущей кафедры

strcpy(((TListK*)PtrK)->NameK, Struct_Kaf.NameK);

//…

//выделение памяти для массива указателей на лекторов

PtrArrL = new void*[Struct_Kaf.CountLec+2];

/*формирование действующего указателя PtrArL в новом

массиве указателей*/

PtrArrL= (void*)(((int)PtrArrL) + sizeof(int) * 2);

/*установка значения количества элементов списка

преподавателей в массиве*/

((int*)PtrArrL)[PosCnt] = Struct_Kaf.CountLec;

/*установка размера массива*/

((int*)PtrArrL)[PosSize] = Struct_Kaf.CountLec;

/*Формирование поля – указатель на подсписок у кафедры*/

/*Заносим в это поле указатель на массив указателей на

преподавателей*/

((TListK*)PtrK)->SubLevel = PtrArrL;

//цикл для восстановления преподавателей

for (n = 0; n < Struct_Kaf.CountLec ; n++ )

{

fread(&Struct_Lec, sizeof(Struct_Lec), 1, f);

/*Выделение памяти дял текущего преподавателя*/ PtrL = new TListL;

((void**)PtrArrL)[n] = PtrL; /*сохранение указателя на теку-

щего преподавателя в массиве указателей*/

//формирование полей текущего преподавателя

strcpy(((TListL*)PtrL)->NameL, Struct_Lec.NameL);

//…

}

}

}

}

return true;

} /*RestoreMltListFromFile*/