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

Элементы в них однотипные, но количество их не фиксируется в структуре. Динамические структуры – это:

последовательность, стек,

очередь, дек,

список, деревья,

графы (на 2 курсе)

У каждого из этих типов своя дисциплина работы с элементами, она определяет свой набор допустимых операцийнад элементами.

1) Последовательность –характерен последовательный доступ к элементам,последовательно расположенным, так, что добраться до какого–то элемента можно только просмотрев все предшествующие ему. Поступающие элементы встают в конец последовательности, а читаются из её начала Этот тип данных реализован в языках в типе “последовательный файл” , все операции соответствуют операциям чтения из файла, записи в файл. Последовательность может быть закрыта, либо открыта для чтения из неё элементов, либо открыта для записи в неё элементов..

Операции:пусть S – последовательность элементов типа T.

1.Открыть последовательность S для чтения.

2.Читать элемент x типа T из последовательности S, если есть непрочитанные.

3. Проверить, есть ли непрочитанные элементы в последовательности.

4. Открыть последовательность S для записи.

5. Добавить элемент x типа T в последовательность S.

6. Закрыть последовательность S.

2) Стек –структура данных, в которой могут накапливаться однотипные данные, при этом выполняется условие: элементы можно выбирать из стека в порядке, обратном порядку их поступления. Это условие называют принципом LIFO: Last –In- First - Out (последний пришел, первый уйдёшь).

дно стека вершина

Пусть S – стек элементов типа Т.

Операции для работы со стеком:

1. Сделать стек S пустым: clrst (S).

2. Добавить элемент x типа Т в стек S: push(S, x).

3. Удалить элемент из непустого стека S: pop(S).

4. Проверить стек S на пустоту:

true , если S пустой

emptyst(S)= .

5. Выбрать элемент x типа Т из вершины стека без удаления: x = topst(S).

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

3) Очередь –структура данных, в которой элементы накапливаются в соответствии с принципом FIFO:

First –In- First- Out (первый пришел, первый уйдешь)

Операции для очереди q с элементами типа Т:

1. Сделать очередь q пустой: clrqu(q).

2. Добавить элемент a типа Т в очередь q :insqu (q, a).

3. Удалить элемент из непустой очереди q: remqu (q).

4. Проверить очередь q на пустоту:

true , если q пустая

emptyqu (q)= .

5. Выбрать элемент a типа Т из непустой очереди без удаления: a= topqu(q).

4. Дек – очередь с двумя концами (double ended queue)

 

Самим записать операции для дека