Абстрактные структуры данных.

Часть 2 Последовательность.

Последовательность – это набор элементов разделенный на две части: первая часть состоит из всех элементов уже прочитанных к данному моменту времени (before), вторая часть состоит из всех непрочитанных элементов (after).

Основные операции производимые над последовательностью:

1. Конструктор – создает по умолчанию пустую последовательность.

2. Деструктор – уничтожает последовательность.

3. Доступ для чтения (Get) – считывает значение 1-го элемента непрочитанной части.

4. Доступ для изменения (Put, Set,…) –изменение значения 1-го элемента непрочитанной части.

5. Вперед (Skip) – изменение соотношения между прочитанной и непрочитанной частями.

6. Пуста ? (IsEmpty) – проверка является ли последовательность пустой или нет.

7. Сделать пустой (DoEmpty, Clear, … ) – выбрасывает все элементы из последовательности и делает пустыми обе части.

8. В конце ? (IsEnd) – проверяет совпадает ли прочитанная часть со всей последовательностью.

9. В начало (GoTop) – непрочитанная часть совпадает со всей последовательностью.

10. Добавить (Append) – добавляет элемент в конец непрочитанной части.

11. Прочесть очередной элемент (Read) – считывает элемент и увеличивает прочитанную часть на 1.(является дополнительной т.к имеются методы 3 и 5)

Если сравнить набор методов последовательности и набор методов потока то можно заметить, что поток – частный случай видоизменённой последовательности.

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

Принципы реализации:

1. Последовательность может быть организована на основе сплошной памяти в куче (массив, строка).

2. Односвязный список в куче.

3. На основе физического файла во внешней памяти.

Приведем пример реализации последовательности на основе односвязного списка.

1. Односвязный список без буфера

Для реализации последовательности на базе односвязного списка необходимо хранить также указатель на начало (Pb), на начало непрочитанной части (Pt), на конец (Pe).

2. Односвязный список с буфером.

Буферный элемент предназначен для того чтобы облегчить процесс написания программ, при наличии буфера программисту не требуется рассматривать отдельно случаи пустой и полной последовательности. Буферный элемент нужно размещать в конце последовательности, для того чтобы в случае пустой последовательности указательPt не указывал в пустоту.

Линейный двунаправленный список (L2 - список):

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

Набор методов для работы соL2 – списком:

1. Конструктор - создает по умолчанию пустой список.

2. Деструктор – уничтожает список.

3. Пуст ? (IsEmpty) - функция, проверяющая пустоту списка.

4. В начало\В конец – переход в начало\конец списка.

5. Доступ для чтения элемента до\за указателем (GetBefore\GetAfter). (д)

6. Доступ для изменения элемента до\за указателем. (д)

7. Вперед\назад - перемещение текущего указателя.

8. В конце\В начале – функция, проверяющая положение текущего указателя списка.

9. Вставить за\до – вставка элемента после\перед указателя.

10. Изъять за\до - изъятие элемента после\перед указателем.

11:.Удалить за\до – удаление в соответствующей части. (д)

12.Сделать пустым. (д)

(д) – методы, которые могут быть получены с помощью комбинации остальных.

Идея реализации.

1. на основе сплошной памяти

2. на основе двух стеков (аналогично 1, но не обязательно сплошная память)

3. на основе двусвязного списка.

Рассмотрим более подробно 3-ий способ реализации.

1-ый случай (без буфера). Схематично этот вариант можно показать следующим образом:

Вэтом случае не важно где хранить указательPt так как последний элемент части “до’’ и первый элемент части “после” имеют ссылки друг на друга. Необходимо также чтобы соответсвующие указатели первого и последнего элемента указывали на NIL.

2-ой случай (с буфером).

Указатель буферного элемента на предыдущий элемент, за ненадобностью может никуда не указывать. Указатель начала списка должен указывать на буфер.

3-ий случай (с двумя буферами)

Этот метод является симметричным, так как часть «до» является зеркальным отражением части «за» это свойство позволяет значительно упростить написание этой реализации.

4-й случай (с общим буфером).

Указатель буфера на следующий элемент указывает на последний элемент списка, а указатель на предыдущий элемент указывает на начало списка. Замкнутость этой организации позволяет добиться максимальной простоты программы реализующей L2-список.

Линейный однонаправленный список (L1-список ).

L1-список отличается от L2 – списка тем , что он обеспечивает последовательный просмотр элементов только от начала к концу списка. Передвинуть указатель назад нельзя. Кроме того, в L1 – списке работать можно только за указателем, т.е впереди по ходу движения.

Набор методов для работы с L1 – списком:

1.Конструктор - создает по умолчанию пустой список.

2.Деструктор – уничтожает список.

3.Пуст ? (IsEmpty) - функция, проверяющая пустоту списка.

4.В начало – переход в начало списка.

5.Доступ для чтения 1-го элемента за указателем (GetAfter). (д)

6.Доступ для изменения 1-го элемента за указателем. (д)

7.Вперед - перемещение текущего указателя вправо .

8.В конце – функция, проверяющая положение текущего указателя списка.

_____________________________________________________________________________________

9.Вставить – вставка элемента после указателя.

10.Изъять - изъятие элемента после указателем.

11.Удалить – удаление в соответствующей части. (д)

12.Сделать пустым. (д)(массовая).

Методы 1-8 совпадают с методами последовательности, методы 9-12 – собственные методы L1 – списка.

Идея реализации.

1. На основе сплошной памяти (массив фиксированной длины).

2. На основе двух стеков.

3. На основе односвязного списка без буфера.

Вэтом способе требуется указатель на последний элемент части «до» а также указатель на начало списка.

4. На основе односвязного списка с буфером.

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