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

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

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

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

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

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

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

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

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


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


Рис. 7.8. Динамические структуры:

а - стек; б - очередь; в - дек; г - древовидная; д - сетевая

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

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

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

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

Рис. 7.9.

Списки:

а - линейный односвязный; б - линейный односвязный кольцевой; в - линейный двусвязный; г - двусвязный кольцевой; д - п-связный


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

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

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

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

Туре ре = Лelement; {тип указателя}

element = record

name: string fl 6J; {информационное поле 1} telefon:string[7]; {информационное поле 2} р: ре; {адресное поле}

end;

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

Туре ре - Aelement; {тип указателя} element = record

пате: stringfloj; {информационное поле 1} telefon:string[7]; {информационное поле 2} prev: ре; {адресное поле «предыдущий»}

next: ре; {адресное поле «следующий»}

end;

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

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

Varfirst, last, q: ре;...

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

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

7.4.

<< | >>
Источник: Иванова Г.С. Основы программирования. 2002

Еще по теме Динамические структуры данных:

  1. СТЕРЕОТИП ДИНАМИЧЕСКИЙ
  2. ПСИХОЛОГИЯ ДИНАМИЧЕСКАЯ
  3. АНАЛИЗ КАУЗАЛЬНО-ДИНАМИЧЕСКИЙ
  4. Динамическая медитация
  5. В динамических методах
  6. ПСИХИКА: ПОНИМАНИЕ ДИНАМИЧЕСКОЕ
  7. Динамический смысл аспектов
  8. ПРОЦЕСС ПСИХИЧЕСКИЙ: ХАРАКТЕРИСТИКА ДИНАМИЧЕСКАЯ
  9. 46. Динамические процессы в малой группе
  10. СОЦИОЛОГИЧЕСКИЙ АНАЛИЗ СЕМЬИ В ЕДИНСТВЕ СТРУКТУРНЫХ И ДИНАМИЧЕСКИХ КООРДИНАТ
  11. ЛЕКЦИЯ 12 2.3. Динамические процессы городской жизни