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

Сентябрь 5, 2022

Главная
Алгебра
Динамические структуры данных

Содержание

2. Для удобства работы с адресами в языках программирования введены переменные типа «указатель». Мы будем рассматривать типизированные
3. Основные операции с указателями
4. Динамически распределяемая память – память, которая выделяется и освобождается по запросам программы в процессе работы программы.
5. Построение индексного массива адресов 1) В массив b записываются адреса элементов массива a: b = (&a1,
6. Словарь list – список (простой) queue – очередь next – следующий head – голова tail –
7. Поле Next может занимать произвольное место в структуре элементов списка. Однако, если оно является первым элементом
8. Основные операции со стеком 1) Добавление элементов в начало стека. Предварительно должны быть сделаны операции: p
9. Основные операции со стеком 2) Исключение первого элемента из списка Операция имеет смысл, если список не
10. Основные операции со стеком 3) Просмотр списка head p := head DO (p ≠ NULL) операция
11. Основные операции с очередью 1) а) Добавление элемента в конец очереди (непустой) head tail 1) p
12. Основные операции с очередью 1) б) Добавление в пустую очередь head tail 1) p ->next :=
13. Основные операции с очередью 1) в) Добавление элемента по адресу р в очередь head tail 1)
14. 2) 3) Исключение первого элемента из очереди, просмотр очереди. Т.к. обработка любого списка производится с начала,
15. Задача сортировки последовательностей Пусть дана последовательность S = S1, S2, S3, …, Sn - совокупность данных
16. Рассмотрим операции: 1) Постановка элемента в конец очереди: Можно использовать алгоритм постановки в очередь, описанный ранее,
18. Скачать презентацию

Слайд 2

Для удобства работы с адресами в языках программирования введены переменные типа

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

x : tData

Слайд 3

Основные операции с указателями

Слайд 4

Динамически распределяемая память – память, которая выделяется и освобождается по запросам

программы в процессе работы программы. В качестве такой памяти обычно используется вся свободная память компьютера.
Статическая память выделяется на этапе компиляции при запуске программы и освобождается при завершении работы программы.
Две основные процедуры для работы с динамической памятью: выделение и освобождение памяти.
Пример. 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
В:

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

Слайд 5

Построение индексного
массива адресов
1) В массив b записываются адреса элементов массива

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
Достоинство метода: исходные данные могут располагаться не только в массиве, а произвольно в динамической памяти.

Слайд 6

Словарь list – список (простой)
queue – очередь
next – следующий

head – голова
tail – хвост
Определение Списком называется последовательность однотипных элементов, связанных между собой указателями.
head next NULL
data
Пример. Пусть tLE - тип элемента списка:
struct tLE { tLE *next; int data; } *head;

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

Слайд 7

Поле Next может занимать произвольное место в структуре элементов списка. Однако,

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

Слайд 8

Основные операции со стеком
1) Добавление элементов в начало стека.
Предварительно должны быть

сделаны операции:
<выделение памяти по адресу p>
p ->data := <данные>
head
head
1) p->next := head
2) head := p .
p

Слайд 9

Основные операции со стеком
2) Исключение первого элемента из списка
Операция имеет

смысл, если список не пустой (head≠NULL).
head
1)p := head .
2) head := p ->next
delete p .

Слайд 10

Основные операции со стеком
3) Просмотр списка
head
p := head
DO (p

≠ NULL)
операция (*р)
p := p->next
OD

Слайд 11

Основные операции с очередью
1) а) Добавление элемента в конец
очереди (непустой)
head
tail

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

Слайд 12

Основные операции с очередью
1) б) Добавление в пустую очередь
head
tail
1)

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

Слайд 13

Основные операции с очередью
1) в) Добавление элемента по адресу р

в очередь
head
tail
1) p→Next := NULL
2) IF ( Head≠NULL) Tail→Next := p
ELSE Head := p
FI
3) Tail := p

Слайд 14

2) 3) Исключение первого элемента из очереди, просмотр очереди.
Т.к. обработка

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

head

tail

Слайд 15

Задача сортировки последовательностей
Пусть дана последовательность S = S1, S2, S3, …,

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

Слайд 16

Рассмотрим операции:
1) Постановка элемента в конец очереди:
Можно использовать алгоритм постановки в

очередь, описанный ранее, но рассмотрим оптимизированную версию:
а) не пишем NULL в последнем элементе очереди, т.к. его адрес известен из указателя tail
б) сделаем поле next в элементе очереди первой компонентой, тогда его адрес совпадает с адресом элемента списка
в) зададим пустую очередь следующим образом:
head
Инициализация очереди: tail := (tLE*) &head
tail
head
Оптимизация:
1) tail->next=p
2) tail=p
Работает в два раза быстрее! tail

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

Содержание

Для удобства работы с адресами в языках программирования введены переменные типа

Основные операции с указателями

Динамически распределяемая память – память, которая выделяется и освобождается по запросам

Построение индексного массива адресов1) В массив b записываются адреса элементов массива

Словарь list – список (простой) queue – очередь next – следующий

Поле Next может занимать произвольное место в структуре элементов списка. Однако,

Основные операции со стеком1) Добавление элементов в начало стека.Предварительно должны быть

Основные операции со стеком2) Исключение первого элемента из списка Операция имеет

Основные операции со стеком3) Просмотр списка headp := head DO (p

Основные операции с очередью1) а) Добавление элемента в конец очереди (непустой)headtail

Основные операции с очередью1) б) Добавление в пустую очередь headtail 1)

Основные операции с очередью 1) в) Добавление элемента по адресу р

2) 3) Исключение первого элемента из очереди, просмотр очереди. Т.к. обработка

Задача сортировки последовательностейПусть дана последовательность S = S1, S2, S3, …,

Рассмотрим операции:1) Постановка элемента в конец очереди:Можно использовать алгоритм постановки в

Похожие презентации