6.4. Лекция 18. Операции со структурами и бинарными файлами
Самым простейшим вариантом бинарного файла является файл, хранящий структуры, которые не ссылаются друг на друга, т.е. не образуют линейный список.
Примечание.
Для изучения данной темы необходимо ознакомиться с принципами операций со структурами (см. пункт 4.3.3, лекция 13) и операциями над строками и принципами работы с текстовыми файлами (см. пункт 6.3, лекция 17), поскольку принципы работы с бинарными файлами, содержащими структуры основываются на ранее изложенном материале.
Рассмотрим отличия текстового и простейшего бинарного файла.
Формат текстового файла изображен на рис. 6.4.
Рис. 6.4 — Формат текстового файла
Пример текстового файла:
Alfimov V.V. 1981 2000.00
Esaulko A.I. 1981 1000.00
Shandrigin D.V. 1981 100.00
Формат текстового файла изображен на рис. 6.5.
Рисунок 6.5 — Формат бинарного файла
Пример бинарного файла изображен на рис. 6.6.
Рисунок 6.6 — Принтскрин примера бинарного файла
Примечание:
Для получения дополнительной информации смотрите методические указания к выполнению лабораторной работы №12 по дисциплине «Информатика и вычислительная техника» для студентов дневной формы обучения направления 6.050901 «Радиотехника». В 2 ч. Ч.2. Работа с файлами и структурами данных на языке С/С++ /СевНТУ; сост. С.Н. Бердышев, А.В. Лукьянчиков — Севастополь: Изд-во СевНТУ, 2008. — 16 с.
6.5. Лекция 19. Списки: операции с динамическими структурами данных; организация списков и их обработка
В случае, когда память под структуры данных в программе выделяется по мере необходимости отдельными блоками, связанными друг с другом с помощью указателей, то такую организацию памяти называют динамическими структурами данных.
Наиболее часто используют следующие динамические структуры, способные изменять размер во время выполнения программы:
— линейные списки;
— стеки;
— очереди;
— бинарные деревья.
6.5.1. Линейные списки
Линейным списком называется структура данных, при которой логический порядок следования элементов задается с помощью указателей.
Линейные списки могут быть:
— односвязными линейными списками;
— двусвязными линейными списками;
— односвязными линейными кольцевыми списками.
Примечания:
— элементы любой динамической структуры данных представляют собой структуры;
— каждый элемент списка содержит ключ;
— ключом может выступать любое из полей данных.
Односвязным (однонаправленным) линейным списком называют список, в котором каждый элемент ссылается на следующий элемент.
Диаграмма связей односвязного линейного списка представлена на рис. 6.7.
Рисунок 6.7 — Диаграмма связей в односвязном линейном списке
Двусвязным (двунаправленным) линейным списком называют список, в котором каждый элемент ссылается на предыдущий и следующий элементы.
Диаграмма связей двусвязного линейного списка представлена на рис. 6.8.
Рисунок 6.8 — Диаграмма связей в двусвязном линейном списке
Кольцевым списком называют список, у которого первый и последний элементы связаны указателями.
Диаграмма связей односвязного кольцевого списка представлена на рис. 6.9.
Рисунок 6.9 — Диаграмма связей в односвязном кольцевом списке
Примеры:
1. Элемент односвязного списка:
struct node
{
int data1;
char data2[15] ;
…
node *next;
} ;
2. Элемент двусвязного списка:
struct node
{
int data1;
char data2[15];
…
node *next;
node *prev;
} ;
Над списками можно выполнять следующие операции:
— начальное формирование списка (создание 1-го элемента);
— добавление элемента в конец списка;
— чтение элемента с заданным ключом;
— вставка элемента в заданное место списка (до или после элемента с заданным ключом);
— удаление элемента с заданным ключом;
— упорядочивание списка по ключу.
Вставку элемента в список можно описать диаграммой, представленной на рис. 6.10.
Рисунок 6.10 — Диаграмма связей элементов двумерного списка при вставке элемента в заданное место
Примеры:
1. Формирование первого элемента двусвязного списка:
node *first(int d)
{
node *pv=new node; // – выделение памяти под элемент
pv–>d = d; // – присваивание значения полю данных
pv–>next = NULL; // – обнуление указателей на следующий
pv–>prev = NULL; // – и предыдущий элементы (их еще нет)
return pv; // – передача в программу указателя на
} // – первый элемент списка
2. Добавление элемента в конец двусвязного списка:
void append(node **pend, int d)
{ node *pv=new node; // – выделение памяти под элемент
pv–>=d; // – присваивание значения полю данных
pv–>next=NULL; // – обнуление (следующего эл-та еще нет)
pv–>prev=*pend; // – указывает конец списка
// (куда добавляется элемент)
(*pend)–>next=pv; // – в предыдущем эл-те устанавливается
// – указатель на добавляемый эл-т
*pend=pv; // – обновление указателя на конец списка
}
3. Поиск элемента двусвязного списка по ключу:
node *find(node *const pbeg, int d)
{
node *pv=pbeg; // – указатель на первый эл-т списка
while(pv)
{
if(pv–>d == d) break;// – если значение совпало, то выход
pv=pv–>next; // – выбор следующего эл-та списка
}
return pv; // – передача в программу указателя
// на найденный элемент списка
}
4. Вставка элемента двусвязного списка в заданное место списка:
node insert (node *const pbeg, node **pend, int key, int d)
{
if(node *pkey=find(pbeg, key))
{ node*pv=new node;
pv–>d=d;
// 1 – установка связи нового эл-та с последующим:
pv–>next=pkey–>next;
// 2 – установка связи нового эл-та с предыдущим:
pv–>prev=pkey;
// 3 – установка связи предыдущего эл-та с новым:
pkey–>next=pv;
// 4 – установка связи последующего эл-та с новым:
(pv–>next)–>prev=pv; }
return pv;
}
5. Удаление элемента двусвязного списка:
bool remove (node **pbeg, node **pend, int key)
{ if (node *pkey=find(pbeg, key)) // выдел. памяти под указ. на эл-т
{ if (pkey==*pbeg) // если в начале списка
{ *pbeg=(*pbeg)–>next;
(*pbeg)–>prev=0; }
else if (pkey==*pend) // если в конце списка
{ *pend=(*pend)–>prev;
(*pend–>next=0) }
else // если в середине списка
{ (pkey–>prev)–>next=pkey–>next;
(pkey–>next)–>prev=pkey–>prev; }
delete pkey; // освобождение памяти (удаление)
return true; } // выход : эл-т найден и удален
return false; } // выход : эл-т не найден