Реализация очереди на основе массива .
Лекция 5.
Замечание. В языке С++ были рассмотрены данные простых и сложных типов. Перед новой темой можно привести некоторую классификацию данных:
· по структуре:
=данные статической структуры, которые получают структуру при описании и сохраняют её (не нарушая) до конца программы: данные стандартного типа (например, int), массив сохраняет количество элементов, объявленное в описании, и др.
=данные динамической структуры, в которых не фикситруется количество элементов, они могут быть пустые, могут состоять из одного, двух и более элементов, которые могут добавляться и удаляться из этих данных.
· по способу размещения:
= статически размещаемые данные: int X; float a[100], память которых сохраняется за ними в течении всей программы, пока работает их область действия.
=динамически размещаемые данные: память для них выделяется по операции new, существуют они пока эта память не будет освобождена.
Динамические структуры данных.
Элементы в них однотипные, но количество их не фиксируется в структуре. Динамические структуры – это:
| последовательность, стек, | очередь, дек, | список, деревья, | графы (на 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)
 | |||||||||||||
 | | | | |  | ||||||||
Самим записать операции для дека
Реализация очереди на основе массива .
0 1 2 3 4 . . . . . . . . . . size . . . . . . . . . . . . . . . . NN -1
 х
| х | х | х | х |
beg
|
|
|
Очередь циклическая. Примером такой очереди в нашем ПК является буфер клавиатуры. В данном примере будет описана очередь, реализованная на массиве, и программа, использующая очередь для одного алгоритма. Программа многофайловая, состоит из 3-х файлов:
1-ый файл – заголовочный –описывает тип структуры-очереди, объявляет прототипы функций - операций, это интерфейсный файл.
2-ой файл – файл реализации содержит описание функций- операций, спецификации этого типа данных
3-ий файл – главный файл с алгоритмом, использующим очереди.
Абстрактный тип данных (АТД) – это тип данных (набор значений и совокупность операций для этих значений), доступ к которому осуществляется только через интерфейс. Программа, которая использует АТД, называется клиентской (3-ий файл).
Дата добавления: 2021-03-18; просмотров: 135; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!