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

Как упоминалось выше, переменные типа «указатель» обычно использу­ют при реализации динамических переменных, в том числе и динамических структур данных.

Динамические структуры данных могут быть организованы линейно, в виде дерева и в виде сети.

Линейная динамическая структура представляет собой изменяемую по­следовательность элементов. Частными случаями таких структур являются:

· стеки, в которых разрешено добавлять элементы только в конец и уда­лять только последние элементы (рис. 7.8, а);

· очереди, в которых добавление элементов осуществляется в конец, а удаление - из начала (рис. 7.8, б);

· деки, которые допускают добавление и удаление элементов и с нача­ла, и с конца (рис. 7.8, в).

В древовидной структуре каждый элемент (вершина) ссылается на один или более элементов следующего уровня (рис. 7.8, г).

В сетевой структуре никаких ограничений на связи элементов не на­кладывается (рис. 7.8, д).

Линейные динамические структуры, такие, как стеки, очереди и деки, при известном максимальном количестве элементов в них можно реализо­вать в виде динамических или статических одномерных массивов.

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

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

· линейные односвязные списки - единственное адресное поле содер­жит адрес следующего элемента, если следующий элемент отсутствует, то в адресное поле заносят константу nil (рис. 7.9, о);

· кольцевые односвязные списки - единственное адресное поле содер­жит адрес следующего элемента, а последний элемент ссылается на первый (рис. 7.9, б);

· линейные двусвязные списки — каждый элемент содержит адреса пре­дыдущего и последующих элементов, соответственно,, первый элемент в ка­честве адреса предыдущего, а последний - в качестве адреса следующего элемента содержат nil (рис. 7.9, в);

· кольцевые двусвязные списки — каждый элемент содержит адреса пре­дыдущего и последующих элементов, причем первый элемент в качестве предыдущего содержит адрес последнего элемента, а последний элемент в качестве следующего - адрес первого элемента (рис. 7.9, г);

· n-связные списки - каждый элемент включает несколько адресных по­лей, в которых записаны адреса других элементов или nil (рис. 7.9, д).

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

Элемент двусвязного списка описывается с двумя адресными полями, например:

Соответственно элемент n-связного списка содержит заданное количест­во адресных полей.

У любого списка имеется хотя бы один указатель, размещенный в стати­ческой памяти, который содержит адрес первого элемента списка или кон­станту nil, если список пуст. Достаточно часто используют дополнительные указатели, в которых хранят адреса других элементов, например, адрес теку­щего элемента, адрес последнего элемента и т.п. Эти указатели также описы­ваются как «указатели на элемент», например:

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

Рассмотрим некоторые приемы работы со списками на примере линей­ных односвязных списков и бинарных деревьев.