Теория для изучения

Structuri dinamice de date

1.ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
2.ЛИНЕЙНЫЙ СПИСОК
3.СОЗДАНИЕ ЭЛЕМЕНТА СПИСКА
4.ДОБАВЛЕНИЕ УЗЛА
5.ПРОХОД ПО СПИСКУ
6.ПОИСК УЗЛА В СПИСКЕ
7.УДАЛЕНИЕ УЗЛА
8.ДВУСВЯЗНЫЙ СПИСОК
9.ОПЕРАЦИИ С ДВУСВЯЗНЫМ СПИСКОМ
10.ЦИКЛИЧЕСКИЕ СПИСКИ
11.СТЕК

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

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

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

2. Линейный список.

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

 Каждый элемент содержит также ссылку на следующий за ним элемент. У последнего в списке элемента поле ссылки содержит NULL. Чтобы не потерять список, мы должны где-то (в переменной) хранить адрес его первого узла – он называется «головой» списка. В программе надо объявить два новых типа данных – узел списка Node и указатель на него PNode. Узел представляет собой структуру, которая содержит три поля - строку, целое число и указатель на та-кой же узел. Правилами языка Си допускается объявление:



 В дальнейшем мы будем считать, что указатель Head указывает на начало списка, то есть, объявлен в виде:



 Первая буква «P» в названии типа PNode происходит от слова pointer – указатель (англ.) В начале работы в списке нет ни одного элемента, поэтому в указатель Head записывается нулевой адрес NULL. 

3. Создание элемента списка

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



После этого узел надо добавить к списку (в начало, в конец или в середину).

4. Добавление узла

4.1. Добавление узла в начало списка 

При добавлении нового узла NewNode в начало списка надо 1) установить ссылку узла NewNode на голову существующего списка и 2) установить голову списка на новый узел.








По такой схеме работает процедура AddFirst. Предполагается, что адрес начала списка хранится в Head. Важно, что здесь и далее адрес начала списка передается по ссылке, так как при добавлении нового узла он изменяется внутри процедуры.

4.2. Добавление узла после заданного.

 Дан адрес NewNode нового узла и адрес p одного из существующих узлов в списке. Тре-буется вставить в список новый узел после узла с адресом p. Эта операция выполняется в два этапа: 1) установить ссылку нового узла на узел, следующий за данным; 2) установить ссылку данного узла p на NewNode.
 

Последовательность операций менять нельзя, потому что если сначала поменять ссылку у узла p, будет потерян адрес следующего узла. 

4.3. Добавление узла перед заданным.

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

Такая процедура обеспечивает «защиту от дурака»: если задан узел, не присутствующий в списке, то в конце цикла указатель q равен NULL и ничего не происходит. Существует еще один интересный прием: если надо вставить новый узел NewNode до заданного узла p, вставляют узел после этого узла, а потом выполняется обмен данными между узлами NewNode и p. Таким образом, по адресу p в самом деле будет расположен узел с новыми данными, а по адресу NewNode – с теми данными, которые были в узле p, то есть мы решили задачу. Этот прием не сработает, если адрес нового узла NewNode запоминается где-то в программе и потом используется, поскольку по этому адресу будут находиться другие данные.

  4.4. Добавление узла в конец списка.

Для решения задачи надо сначала найти последний узел, у которого ссылка равна NULL, а затем воспользоваться процедурой вставки после заданного узла. Отдельно надо обработать случай, когда список пуст. 

5. Проход по списку.

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

6. Поиск узла в списке.

Часто требуется найти в списке нужный элемент (его адрес или данные). Надо учесть, что требуемого элемента может и не быть, тогда просмотр заканчивается при достижении конца списка. Такой подход приводит к следующему алгоритму: 1) начать с головы списка; 2) пока текущий элемент существует (указатель – не NULL), проверить нужное условие и перейти к следующему элементу; 3) закончить, когда найден требуемый элемент или все элементы списка просмотрены. Например, следующая функция ищет в списке элемент, соответствующий заданному слову (для которого поле word совпадает с заданной строкой NewWord), и возвращает его адрес или NULL, если такого узла нет. 


Вернемся к задаче построения алфавитно-частотного словаря. Для того, чтобы добавить новое слово в нужное место (в алфавитном порядке), требуется найти адрес узла, перед которым надо вставить новое слово. Это будет первый от начала списка узел, для которого «его» слово окажется «больше», чем новое слово. Поэтому достаточно просто изменить условие в цикле while в функции Find., учитывая, что функция strcmp возвращает «разность» первого и второго слова. 

Эта функция вернет адрес узла, перед которым надо вставить новое слово (когда функция strcmp вернет положительное значение), или NULL, если слово надо добавить в конец списка.  

7.Удаление узла.

Удаление узла Эта процедура также связана с поиском заданного узла по всему списку, так как нам надо поменять ссылку у предыдущего узла, а перейти к нему непосредственно невозможно. Если мы нашли узел, за которым идет удаляемый узел, надо просто переставить ссылку. 


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

8.Двусвязный список.

Многие проблемы при работе с односвязным списком вызваны тем, что в них невозможно перейти к предыдущему элементу. Возникает естественная идея – хранить в памяти ссылку не только на следующий, но и на предыдущий элемент списка. Для доступа к списку используется не одна переменная-указатель, а две – ссылка на «голову» списка (Head) и на «хвост» - последний элемент (Tail).

Каждый узел содержит (кроме полезных данных) также ссылку на следующий за ним узел (поле next) и предыдущий (поле prev). Поле next у последнего элемента и поле prev у первого содержат NULL. 

В дальнейшем мы будем считать, что указатель Head указывает на начало списка, а указатель Tail – на конец списка:



Для пустого списка оба указателя равны NULL.  

9. Операции с двусвязным списком.

9.1. Добавление узла в начало списка.

 При добавлении нового узла NewNode в начало списка надо:
1) установить ссылку next узла NewNode на голову существующего списка и его ссылку prev в NULL;
2) установить ссылку prev бывшего первого узла (если он существовал) на NewNode;3) установить голову списка на новый узел;
4) если в списке не было ни одного элемента, хвост списка также устанавливается на новый узел.

9.2. Добавление узла в конец списка.

Благодаря симметрии добавление нового узла NewNode в конец списка проходит совершенно аналогично, в процедуре надо везде заменить Head на Tail и наоборот, а также поменять prev и next.  

9.3. Добавление узла после заданного.

Дан адрес NewNode нового узла и адрес p одного из существующих узлов в списке. Требуется вставить в список новый узел после p. Если узел p является последним, то операция сводится к добавлению в конец списка.
 Если узел p – не последний, то операция вставки выполняется в два этапа: 
1) установить ссылки нового узла на следующий за данным (next) и предшествующий ему (prev); 
2) установить ссылки соседних узлов так, чтобы включить NewNode в список.



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

9.4. Поиск узла в списке.

Проход по двусвязному списку может выполняться в двух направлениях – от головы к хвосту (как для односвязного) или от хвоста к голове.  

9.5. Удаление узла.

Эта процедура также требует ссылки на голову и хвост списка, поскольку они могут измениться при удалении крайнего элемента списка. На первом этапе устанавливаются ссылки соседних узлов (если они есть) так, как если бы удаляемого узла не было бы. Затем узел удаляется и память, которую он занимает, освобождается. Эти этапы показаны на рисунке внизу. Отдельно проверяется, не является ли удаляемый узел первым или последним узлом списка. 

10. Циклические списки.

 Иногда список (односвязный или двусвязный) замыкают в кольцо, то есть указатель next последнего элемента указывает на первый элемент, и (для двусвязных списков) указатель prev первого элемента указывает на последний. В таких списках понятие «хвоста» списка не имеет смысла, для работы с ним надо использовать указатель на «голову», причем «головой» можно считать любой элемент. 

11. Стек

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

По определению, элементы извлекаются из стека в порядке, обратном их добавлению в эту структуру, т.е. действует принцип "последний пришёл — первый ушёл".

Наиболее наглядным примером организации стека служит детская пирамидка, где добавление и снятие колец осуществляется как раз согласно определению стека.

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

Выделим типовые операции над стеком и его элементами:

• добавление элемента в стек;

• удаление элемента из стека;

• проверка, пуст ли стек;

• просмотр элемента в вершине стека без удаления;

• очистка стека.

 Чтобы привести этот код к классическому пониманию стека, достаточно заменить мои temp -переменные на (*MyList) и тогда даже при простом просмотре просмотренные данные будут сразу теряться. Удаляться не будут, но связь потеряется. И если так сделаете, то будут паразитировать эти призраки стека и пожирать вашу память отныне и вовеки веков. При работе с динамическими данными надо быть очень внимательным к памяти и не нужно этого забывать.

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

Для стека можно выполнить и другие нетипичные для него операции, но кроме как для лучшего понимания материала это вряд ли стоит делать

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