Динамические структуры данных

 

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

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

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

Элемент любой динамической структуры данных представляет собой структуру (struct), содержащую поля для хранения данных и для указателя.

struct Node {

int d;

Node *p;

};

Линейные списки

Самый простой способ связать множество элементов – сделать так, чтобы каждый элемент содержал ссылку на следующий. Такой список называется однонаправленным (односвязным). Если добавить в каждый элемент вторую ссылку на предыдущий элемент, получится двунаправленный список (двусвязный), если последний элемент связать указателем с первым, получится кольцевой список.

Пример структуры двунаправленного линейного списка:

struct DvSpisok {

int d;

Node *next; //указатель на следующий элемент

Node *pred; //указатель на предыдущий элемент

};

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

– начальное формирование списка (создание первого элемента);

– добавление элемента в конец списка;

– чтение элемента с заданным ключом;

– вставка элемента в заданное место списка (до или после элемента с заданным ключом);

– удаление элемента с заданным ключом;

– упорядочивание списка по ключу.

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

Стеки

Стеком называется структура данных, в которой элемент, занесённый первым, извлекается последним. Стек реализует принцип обслуживания LIFO (последним пришёл – первым ушёл). В алгоритме быстрой сортировки стек используется для хранения границ неупорядоченных фрагментов. Стек – это частный случай однонаправленного списка, добавление элементов в который и выборка из которого выполняются с одного конца, называемого вершиной стека. Другие операции со стеком не определены. При выборке элемент исключается из стека. Стеки широко применяются в системном ПО, компиляторах и в различных рекурсивных алгоритмах.

Рассмотрим программу, которая формирует стек из пяти целых чисел (1, 2, 3, 4, 5) и выводит его на экран. Функция помещения в стек по традиции называется push, а выборки из стека - pop. Указатель top для работы со стеком всегда ссылается на его вершину.

Итак, опишем структуру, зная, что каждый элемент стека должен содержать целое число и указатель на следующий элемент:

…

struct Stack {

int d;

Stack *p;

};

//---------------------------Начальное формирование стека:

Stack* first(int d)

{

Stack *pv = new Stack; // Описываем вспомогательную переменную-указатель pv и заносим // в неё адрес нового элемента стека, который создаётся с помощью операции new.

pv->d = d; pv->p = 0; // занесение первого элемента в стек

return pv;

}

//---------------------------Занесение в стек:

void push(Stack **top, int d) // в функцию передаются элементы стека и указ. на вершину

{

Stack *pv = new Stack;

pv->d = d; //информационное поле структуры заполняется переданными в функцию значениями.

pv->p = *top; // новый элемент становится вершиной стека и поле его указателя ссылается

*top = pv; // на ранее помещённый в стек элемент.

}

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

//---------------------------Выборка из стека:

int pop(Stack **top)

{

int temp = (*top)->d;

Stack *pv = *top;

*top = (*top)->p;

delete pv; // удаление элемента

return temp;

}

//---------------------------Главная функция:

int main(int argc, char* argv[])

{

Stack *top = first(1); // занесение первого элемента в стек

for (int i = 2; i<6; i++) push(&top, i); // занесение в стек элементов, путём передачи этих элементов и указателя на вершину стека в функцию push.

while (top) cout << pop(&top) << " ";

return 0;

}

Результат работы программы: 5 4 3 2 1

Очереди

Очередь – это частный случай однонаправленного списка, добавление элементов в который выполняется в один конец, а выборка – из другого конца. Таким образом, для очереди определены всего две операции: помещение в конец и выборка из начала. При выборке элемент удаляется из очереди (аналогично стеку и в противоположность списку). Очередь реализует принцип обслуживания FIFO (первым пришёл – первым ушёл). В программировании очереди применяются, например при диспетчеризации задач ОС, буферизованном вводе/выводе.

Рассмотрим программу, которая формирует очередь из пяти целых чисел и выводит её на экран. Указатель на начало очереди назовём pbeg, а указатель на конец – pend.

struct Node {

int d;

Node *p;

};

//---------------------------Начальное формирование очереди:

Node* first(int d)

{

Node *pv = new Node;

pv->d = d; pv->p = 0;

return pv;

}

//---------------------------Добавление в конец:

void add(Node **pend, int d)

{

Node *pv = new Node;

pv->d = d; pv->p = 0;

(*pend)->p = pv;

*pend = pv;

}

//---------------------------Выборка:

int del(Node **pbeg)

{

int temp = (*pbeg)->d;

Node *pv = *pbeg;

*pbeg = (*pbeg)->p;

delete pv;

return temp;

}

//---------------------------Главная функция:

int main(int argc, char* argv[])

{

Node *pbeg = first(1);

Node *pend = pbeg;

for(int i=2; i<6; i++) add(&pend, i);

while(pbeg) cout << del(&pbeg) << ' ';

return 0;

}

Результат работы программы: 1 2 3 4 5.

Из кода этой программы видно, что у неё очень много общего с предыдущей. Функции начального формирования очереди и стека, а также функции выборки абсолютно идентичны. Функция first формирует первый элемент очереди и возвращает указатель на него. Функция add выполняет добавление в конец, поэтому ей передаётся указатель на конец очереди и элемент, который следует добавить. Выборка выполняется из начала очереди, при этом указатель на её начало изменяется.

 

Контрольная работа

 

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

…

int main() {

…

cout << "\n Budete redaktirovat?(y/n): "; cin >> ans;

if(ans=='y') redakt_po_name(ma, KZ);

cout << "\n Sohranit izmeneniya?(y/n): "; cin >> ans;

if(ans=='y') savefile(ma, KZ, dlz);

…

}

void redakt_po_name(Avia *tb, int& N) {

char namer[R];

cout << "\n Ukagite naimenovanie reisa: "; cin >> namer;

int l = strlen(namer);

int ks=0; //êîë-âî ñîâïàäåíèé

for(int i=0; i<N; i++) {

if(strncmp(namer, tb[i].reis, l)==NULL) {

cout << "\nVvedite novoe imya reisa: "; cin >> tb[i].reis;

cout << "\nVvedite tip samoleta: "; cin >> tb[i].tips;

cout << "\nVvedite kol. prod. biletov: "; cin >> tb[i].kpb;

cout << "\nVvedite stoimost bileta: "; cin >> tb[i].cb;

ks++;

}

}

if(ks==0) { cout << "\n Takogo reisa net!"; }

}

//---------------------------------------------------------------------------

void savefile(Avia m[], int M, int dz) {

ofstream fout("c:\\os\\aviabase3_red.dat", ios::binary);

if(!fout) { cout << "\n Oshibka zapisi v fail!"; getch(); return; }

fout.write(reinterpret_cast<char*>(m), M*dz);

fout.close();

}

 

Лекция 4 (14,5 стр.)