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

использовали переменные – объекты программы, имеющие имя и значение.
С

точки зрения машинной реализации:
имя переменной соответствует адресу участка памяти, который для нее выделен, а значение переменной – содержимому этого участка.

Программный уровень Переменная Значение Имя
Машинный уровень Участок памяти Содержимое Адрес
Адреса – целочисленные шестнадцатеричные беззнаковые значения, их можно обрабатывать как целые числа.
Пример: char ch;
int x;
float sum;
1A2B 1A2C 1A2D 1A2F 1AB0 1AB1 1AB2
ch x sum

типа «указатель».
Мы будем рассматривать типизированные указатели, которые могут хранить адреса

только объектов определенного типа.
Определение Указатель – переменная, значением которой является адрес объекта конкретного типа.
Значение указателя может быть не равно никакому адресу. Это значение принимается за нулевой адрес. Для обозначения нулевого адреса используются специальные константы ( NULL ).
Пусть указатель p содержит адрес объекта X типа tData.
Графически будем изображать следующим образом:

p

q

x : tData

запросам программы в процессе работы программы. В качестве такой памяти

обычно используется вся свободная память компьютера.
Статическая память выделяется на этапе компиляции при запуске программы и освобождается при завершении работы программы.
Две основные процедуры для работы с динамической памятью: выделение и освобождение памяти.
Пример. struct tData { … };
tData *p;
C++ : p = new tData; delete p;
C : p = (struct tData*) malloc (sizeof (struct tData) ); free (p);
Индексация через массив указателей:
Вместо номеров элементов в индексном массиве записывают адреса элементов.
А: 2 6 1 4 … 3 5 8 7

В:

Динамически распределяемая память

массива a:
b = (&a1, &a2, &a3,

…, &an)
2) Производится сортировка любым методом, причем
а) при сравнении элементы массива a адресуются через b:
ai < ai-1 => a[bi ] < a[bi-1 ] => *bi < *bi-1
б) перестановки делаются только в массиве b:
ai <-> ai-1 => bi <-> bi-1 => bi <-> bi-1
Достоинство метода: исходные данные могут располагаться не только в массиве, а произвольно в динамической памяти.

queue – очередь

next – следующий
head – голова
tail – хвост
Определение Списком называется последовательность однотипных элементов, связанных между собой указателями.
head next NULL


data
Пример. Пусть tLE - тип элемента списка:
struct tLE { tLE *next; int data; } *head;

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

3

2

Однако, если оно является первым элементом структуры, то его адрес

совпадает с адресом элемента списка, и это позволяет оптимизировать многие операции со списками.
Рассмотрим два вида списков: стек и очередь.
Их отличия в способе и порядке добавления элементов.
Стек (простой список) - новый элемент добавляется в начало последовательности, а удаляться может только первый элемент списка.
Стек реализует дисциплину обслуживания LIFO
(Last Input, First Output).
Очередь - новый элемент добавляется в конец последовательности, удаляется первый элемент последовательности.
Очередь реализует дисциплину обслуживания FIFO
(First Input, First Output)

должны быть сделаны операции:

p ->data := <данные>
head




head
1) p->next := head
2) head := p .

p

1

2

1

2

p

Операция имеет смысл, если список не пустой (head≠NULL).
head

1)p := head .
2) head := p ->next
delete p .

1

2

p

head
DO (p ≠ NULL)
операция (*р)

p := p->next
OD

p

p

p

(непустой)
head



tail

1) p ->next := NULL
2) tail ->next := p
3) tail := p

2

3

1

p

head

tail

1) p ->next := NULL
2) head := p
3) tail := p

2

3

1

p

р в очередь

head

tail

1) p→Next := NULL
2) IF ( Head≠NULL) Tail→Next := p
ELSE Head := p
FI
3) Tail := p

2

3

1

обработка любого списка производится с начала, то операции исключения первого

элемента из очереди и просмотр очереди будут аналогичными стеку.
Иногда удобно рассматривать заголовок очереди как единое целое.
Это удобно, когда используется много очередей.
struct Queue { tLE *head;
tLE *tail; } Q;
Может быть даже использован массив очередей.

head

tail

Q

…, Sn - совокупность данных с последовательным доступом к элементам.
Пример

последовательности: линейный список.
Необходимо переставить элементы так, чтобы выполнялись неравенства:
S1 ≤ S2 ≤ S3 ≤ … ≤ Sn или S1≥ S2 ≥ S3 ≥ … ≥ Sn.
Последовательный доступ означает, что (k+1)-й элемент списка может быть получен путем просмотра предыдущих k элементов, причем просмотр возможен только в одном направлении (слева направо).
Это существенное ограничение последовательного доступа по сравнению с прямым доступом.
Методы сортировки, разработанные для массивов, не годятся для списков.

в очередь, описанный ранее, но рассмотрим оптимизированную версию:
а) не

пишем NULL в последнем элементе очереди, т.к. его адрес известен из указателя tail
б) сделаем поле next в элементе очереди первой компонентой, тогда его адрес совпадает с адресом элемента списка
в) зададим пустую очередь следующим образом:

head

Инициализация очереди: tail := (tLE*) &head
tail
head
Оптимизация:
1) tail->next=p
2) tail=p
Работает в два раза быстрее! tail

p

1

2

Q.Tail→Next:=List
Q.Tail:=List

List:=List→Next

List


Head



Tail

3

1

2