Размещено на http://www.allbest.ru/

Татарский институт содействия бизнесу

Кафедра информационных технологий

Учебно-методическое пособие

СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ

Рекомендовано к печати научно-методическим советом ТИСБИ

Автор: А.Н. Козин

Рецензент: профессор В.С. Моисеев

Казань - 2003

Оглавление

Введение

Раздел 1. Основные структуры данных

1. Введение в структуры данных. Динамическое распределение памяти

1.1 Классификация структур данных

1.2 Переменные-указатели и динамическое распределение памяти

1.3 Дополнительные вопросы использования переменных-указателей

1.4 Контрольные вопросы по теме

2. Структуры данных "стек" и "очередь"

2.1 Что такое стек и очередь?

2.2 Статическая реализация стека

2.3 Динамическая реализация стека

2.4 Статическая реализация очереди

2.5 Динамическая реализация очереди

2.6 Практические задания

2.7 Контрольные вопросы по теме

3. Основы реализации списковых структур

3.1 Структуры данных типа "линейный список"

3.2 Первый способ статической реализации списка

3.3 Второй способ статической реализации списка

3.4 Управление памятью при статической реализации списков

3.5 Динамическая реализация линейных списков

3.6 Практические задания

3.7 Контрольные вопросы

4. Усложненные списковые структуры

4.1 Двунаправленные линейные списки

4.2 Комбинированные структуры данных: массивы и списки указателей

4.3 Комбинированные структуры данных: массивы и списки списков

4.4 Практические задания

4.5 Контрольные вопросы

5. Основные понятия о древовидных структурах

5.1 Основные определения

5.2 Двоичные деревья

5.3 Идеально сбалансированные деревья

5.4 Практические задания

5.5 Контрольные вопросы

6. Реализация поисковых деревьев

6.1 Двоичные деревья поиска

6.2 Добавление вершины в дерево поиска

6.3 Удаление вершины из дерева поиска

6.4 Практические задания

6.5 Контрольные вопросы

7. Дополнительные вопросы обработки деревьев. Графы

7.1 Проблемы использования деревьев поиска

7.2 Двоичные деревья с дополнительными указателями

7.3 Деревья общего вида (не двоичные)

7.4 Представление графов

7.5 Практические задания

7.6 Контрольные вопросы

Раздел 2. Алгоритмы сортировки и поиска

1. Классификация методов. Простейшие методы сортировки

1.1 Задача оценки и выбора алгоритмов

1.2 Классификация задач сортировки и поиска

1.3 Простейшие методы сортировки: метод обмена

1.4 Простейшие методы сортировки: метод вставок

1.5 Простейшие методы сортировки: метод выбора

1.6 Практическое задание

1.7 Контрольные вопросы

2. Улучшенные методы сортировки массивов

2.1 Метод Шелла

2.2 Метод быстрой сортировки

2.3 Пирамидальная сортировка

2.4 Практическое задание

2.5 Контрольные вопросы

3. Специальные методы сортировки

3.1 Простейшая карманная сортировка

3.2 Карманная сортировка для случая повторяющихся ключей

3.3 Поразрядная сортировка

3.4 Практическое задание

3.5 Контрольные вопросы

4. Поиск с использованием хеш-функций

4.1 Основные понятия

4.2 Разрешение конфликтов: открытое хеширование

4.3 Разрешение конфликтов: внутреннее хеширование

4.4 Практические задания

4.5 Контрольные вопросы

5. Внешний поиск и внешняя сортировка

5.1 Особенности обработки больших наборов данных

5.2 Организация внешнего поиска с помощью Б-деревьев

5.3 Б-дерево как структура данных

5.4 Поиск элемента в Б-дереве

5.5 Добавление вершины в Б-дерево

5.6 Удаление вершины из Б-дерева

5.7 Внешняя сортировка

5.8 Практические задания

5.9 Контрольные вопросы

Литература

Основные термины и понятия

Введение

В учебном пособии рассматриваются вопросы программной реализации основных важнейших структур данных, таких как стеки, очереди, списки, деревья и их различных комбинаций. Для большинства структур приводятся различные способы реализации - статические и динамические, даются рекомендации по их практическому применению. Во второй части приводятся алгоритмы сортировки данных, причем основное внимание уделяется методам сортировки массивов, включая все основные простейшие и улучшенные методы и несколько наиболее известных специальных.

Пособие содержит большое число примеров фрагментов программ, а также задания для самостоятельного практического решения. Выполнение практических заданий является абсолютно необходимым, поскольку именно оно развивает навыки самостоятельного написания, выполнения и отладки программ. Наиболее сложные задания имеют рекомендации по программной реализации, облегчающие их выполнение.

Материал учебного пособия соответствует содержанию Государственного образовательного стандарта по одноименному учебному курсу для студентов специальности "Программное обеспечение вычислительной техники и автоматизированных систем" и предполагает знание студентами основ классического структурного программирования. Отдельные темы пособия могут быть полезны и для студентов других специальностей, связанных с информационными и компьютерными технологиями.

Раздел 1. Основные структуры данных

1. Введение в структуры данных. Динамическое распределение памяти

1.1 Классификация структур данных

Типизация данных является одним из фундаментальных понятий современного программирования. Отнесение переменных к тому или иному типу позволяет установить внутренний формат хранения значений этой переменной и набор допустимых операций. Все распространенные языки программирования имеют набор базовых простейших типов данных (целочисленные, вещественные, символьные, логические) и возможность объединения их в составные наборы - массивы, записи, файлы. Понятие структуры данных определяется двумя моментами:

· способом объединения отдельных компонент в единую структуру

· способами обработки как отдельных компонент структуры, так и всей структуры в целом.

Например, классическая структура МАССИВ есть объединение однотипных компонент, причем каждая компонента имеет фиксированный порядковый номер-индекс размещения в массиве. Доступ к элементам массива выполняется именно по этому индексу. Аналогично, структура ЗАПИСЬ является объединением разнотипных компонент-полей, доступ к которым выполняется по имени поля.

Обе эти стандартные структуры служат основой построения других важных структур, широко используемых в различных приложениях: стеки, очереди, списки, деревья, графы. Каждая из них имеет свои особенности объединения компонент и особенности обработки. Основные структуры данных представлены на следующей схеме.

Большинство дополнительных структур данных можно реализовать двумя способами:

· статически на основе массива

· динамически с помощью специальных переменных-указателей

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

Поскольку весьма часто возможны несколько способов реализации одной и той же структуры данных, возникает вопрос о едином унифицированном способе описания подобных структур. Такое описание принято называть абстрактным типом данных (АТД).

АТД - это формализованное описание (модель), определяющее организацию и набор возможных операций с описываемыми данными. Важность АТД определяется тем, что они позволяют отделить описание данных от их реализации и скрыть от пользователя детали реализации, оставив ему только открытый слой взаимодействия с данными - так называемый интерфейс. Даже простейшие встроенные типы данных можно описать в терминах АТД, хоть это и не имеет большого практического значения, т.к. простейшие типы встроены в сам язык программирования. Понятие АТД получило свое дальнейшее развитие в объектно-ориентированном программировании в виде фундаментального понятия "класс", рассмотрение которого выходит за рамки данного пособия.

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

1.2 Переменные-указатели и динамическое распределение памяти

Как известно, основными рабочими объектами в программах являются переменные. Имя переменной заменяет адрес области памяти, где при выполнении программы хранится значение этой переменной. Одной из важнейших функций компилятора является назначение адресов памяти всем переменным программы. Такое распределение памяти называют статическим - оно выполняется при компиляции программы на язык машины. Недостатком такого способа распределения памяти является его жесткость - для изменения объема памяти, выделенной под какую-либо переменную необходимо перекомпилировать программу.

Во многих задачах подобная статичность является очень неудобной, поэтому многие языки программирования, в частности С/С++ и Паскаль, реализуют другой способ создания переменных - динамический. Он позволяет создавать переменные в процессе выполнения программы в ответ на вызов специальных стандартных функций. При этом динамически выделяются необходимые области памяти, в которые заносятся значения соответствующих переменных. Когда необходимость в использовании таких переменных исчезает, соответствующие области памяти можно освободить для других целей. структура алгоритм обработка программа

Механизм динамического распределения памяти основан на использовании специальных переменных, которые называют указателями. Переменные-указатели или переменные ссылочного типа - это специальные переменные, значениями которых являются адреса областей памяти. Каждый указатель может адресовать некоторую область памяти, в которой могут находиться любые данные. Чаще всего под адрес отводится 4 байта. Необходимо четко различать переменную-указатель и адресуемую ею область памяти.

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

· ввести имя переменной

· связать эту переменную с адресуемыми данными, указав их тип или имя с помощью специального символа ^:

var указатель: ^ базовый тип;

Например, указатели на простейшие базовые типы вводятся следующим образом:

pInt: ^integer; {указатель на отдельное целое число}

pChar: ^char; {указатель на отдельный символ}

pString1, pStr2: ^string; {два указателя на символьные строки}

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

Например:

type TpString = ^string; {ссылочный тип для адресации текстовых строк}

var pStr1, pStr2: TpString; {переменные-указатели на строки}

Можно ввести указатели на структурные типы (массивы, записи), используя для этого предварительно объявленные типы:

type TMyArray = array [1..100]of integer;

var pMyArray1: ^TMyArray; {указатель на начало базового массива}.

Необходимо понимать, что объявление переменной-указателя НЕ приводит к выделению памяти для самих адресуемых данных: память выделяется ТОЛЬКО для указателя (например - 4 байта). Поэтому для правильного использования механизма динамического распределения памяти НЕ следует объявлять переменные базового типа (точнее, их объявлять можно, но к динамическому распределению памяти это никакого отношения не имеет). Например:

type TMyRecord = record

Field1: SomeType1;

Field2: SomeType2;

end;

var MyRec: TMyRecord; {обычная переменная-запись со статическим выделением памяти}

pMyRec: ^TMyRecord; {переменная-указатель на будущую структуру-запись с выделением памяти только для указателя, но не для самой записи!}

Динамическое создание переменных базового типа выполняется вызовом стандартной подпрограммы New с параметром-указателем, связанным с данным базовым типом:

New (pMyRec);

New (pStr1);

Данный вызов выполняет два следующих действия:

· обращается к операционной системе для выделения области памяти, необходимой для размещения переменной базового типа

· устанавливает начальный адрес этой области памяти в качестве значения переменной-указателя

Вызов New можно выполнять в любом месте в теле программы любое число раз, в том числе - циклически. Это позволяет при выполнении программы динамически создавать любое необходимое число переменных базового типа.

После выделения области памяти в неё можно записать необходимое значение, используя ссылочную переменную и символ ^ после ее имени:

pStr1^: = `Привет';

pInt^: = 1;

Комбинация имени переменной-указателя и символа ^ превращает указатель в переменную базового типа. С такой переменной можно делать все те операции, которые разрешены для базового типа.

Например:

pInt^: = pInt^ + 1;

pChar^: = `A';

ReadLn (pStr1^);

pMyArray^ [i]: = 10;

pMyRec^.Field1: = соответствующее значение;

Обращаем внимание на последние два присваивания, конструкцию которых можно прокомментировать следующим образом:

· pMyArray и pMyRec - это имена ссылочных переменных

· pMyArray^ и pMyRec^ - это условные обозначения объектов базового типа, т.е. массива и записи соответственно

· pMyArray^ [i]и pMyRec^.Field1 - это обозначения отдельных элементов базового типа, т.е. i-го элемента массива и поля записи с именем Field1

C переменными ссылочного типа допустимы две операции:

1. Присваивание значения одной ссылочной переменной другой ссылочной переменной того же базового типа:

pInt1: = pInt2;

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

2. Сравнение двух ссылочных переменных на равенство или неравенство:

if pInt2 = pInt1 then …

В практических задачах довольно часто приходится использовать "пустые указатели", которые никуда не указывают. Для задания такого пустого указателя используется специальное служебное слово nil.

Например:

pInt1: = nil; {указатель ничего не адресует}

if pStr1 = nil then...{проверка указателя на пустоту}

Для освобождения динамически распределенной памяти используется вызов Dispose с параметром-указателем:

Dispose (pStr1);

После этого вызова соответствующая переменная-указатель становится неопределенной (НЕ путать с ПУСТЫМ указателем!) и ее нельзя использовать до тех пор, пока она снова не будет инициализирована с помощью вызова New или инструкции присваивания. Использование вызова Dispose может приводить к весьма неприятной ситуации, связанной с появлением так называемых "висячих" указателей: если два указателя адресовали одну и ту же область памяти (а это встречается очень часто), то вызов Dispose с одной из них оставляет в другой переменной адрес уже освобожденной области памяти и повторное использование этой переменной приведет либо к неверному результату, либо к аварийному завершению программы.

1.3 Дополнительные вопросы использования переменных-указателей

Иногда бывает удобно присваивать ссылочной переменной адрес базового объекта, используя для этого непосредственно сам объект. Для этого можно использовать специальный оператор взятия адреса @:

var x: real; {обычная переменная вещественного типа}

pReal: ^real; {указатель на вещественный тип}

begin

x:= 1.5; {обычная переменная x получает значение 1.5}

pReal:= @x; {указатель получает адрес размещения числа 1.5}

Write(pReal^: 6: 2); {вывод числа 1.5 с помощью указателя pReal}

end;

Принципиальное отличие данного способа использования указателя от ранее рассмотренного состоит в том, что здесь НЕ используется механизм динамического распределения памяти, т.е. НЕ используются стандартные функции New и Dispose: переменная x является обычной статической переменной, размещаемой в статической области памяти, просто доступ к ней по каким-то причинам организуется не напрямую, а с помощью ссылочной переменной.

Довольно мощным использованием указателей является объединение их в массив. Это можно сделать в силу того, что все переменные-указатели с одним и тем же базовым типом являются однотипными. Массивы указателей можно обрабатывать с помощью циклов. В качестве примера рассмотрим массив указателей на записи некоторой структуры.

type TRec = record {описание базового типа-записи}

x, y: integer;

name: string;

end;

TpRec = ^TRec; {описание ссылочного типа}

var ArrOfPointer: array [1..100]of TpRec;

{объявление массива указателей на записи}

begin

for i:= 1 to 100 do ArrOfPointer [i]^.x: = Random(100);

{цикл установки значений в поле x}

end.

При использовании указателей есть еще одна весьма мощная, но опасная возможность - так называемые нетипизированные указатели, которые не связаны ни с каким базовым типом и поэтому могут адресовать объекты любых типов. Подобные указатели объявляются с помощью служебного слова pointer:

var pAll: pointer;

Распределение и освобождение памяти для нетипизированных указателей производится с помощью специальных стандартных функций GetMem и FreeMem, которые имеют по два параметра - имя нетипизированного указателя и байтовый размер выделяемой области памяти. Для задания этого размера удобно использовать стандартную функцию SizeOf, которая принимает имя типа данных, а возвращает необходимый размер области памяти. Например:

type TRec = record {описание базового типа-записи}

x, y: integer;

name: string;

end;

var p1, p2: pointer; {объявление двух нетипизированных указателей}

begin

GetMem (p1, SizeOf (TRec)); {распределение памяти под объект-запись}

p1^.name:= `Text';

p2:= p1; {оба указателя адресуют одну и ту же область}

FreeMem (p1, SizeOf (TRec));

{освобождение памяти и деактуализация указателя p1}

end.

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

1.4 Контрольные вопросы по теме

1. Что включает в себя понятие структуры данных?

2. Назовите основные линейные структуры данных и их разновидности

3. Назовите основные нелинейные структуры данных и их разновидности

4. В чем состоят отличия статического и динамического распределения памяти?

5. Что такое переменные ссылочного типа (указатели)?

6. Что включает описание переменных-указателей?

7. Приведите примеры описания простых переменных-указателей

8. Как вводится переменная-указатель на текстовые строки (2 способа)?

9. Как вводится переменная-указатель на массив?

10. Как вводится переменная-указатель на структуру-запись?

11. Какая память выделяется транслятором при объявлении переменных-указателей?

12. Какие стандартные подпрограммы используются для динамического выделения и освобождения памяти?

13. Что происходит при выполнении подпрограммы New?

14. Как выполняется установка необходимого значения в динамически выделенную область памяти?

15. Если р - переменная-указатель, то что определяет выражение p^?

16. Если р - переменная-указатель на массив, то как можно определить i-ый элемент массива?

17. Если p - переменная-указатель на запись, то как можно определить некоторое поле этой записи?

18. Какие операции разрешены с переменными-указателями?

19. Что такое "пустой указатель" и как он задается?

20. Что происходит при вызове стандартной подпрограммы Dispose?

21. Какие неприятности могут возникать при использовании подпрограммы Dispose?

22. Как можно переменной-указателю непосредственно присвоить адрес базового объекта?

23. Как задается оператор взятия адреса и для чего он используется?

24. Как задается массив указателей?

25. Если Pointers есть массив указателей, то что определяет выражение Pointers [j]^?

26. Что такое нетипизированные указатели и как они описываются?

27. Какие стандартные функции используются для распределения и освобождения памяти с нетипизированными указателями?

28. Приведите пример записи функции для распределения памяти с нетипизированным указателем.

29. Приведите пример записи функции для освобождения памяти с нетипизированным указателем.

2. Структуры данных "стек" и "очередь"

2.1 Что такое стек и очередь?

Стек - это линейная структура данных, в которую элементы добавляются и удаляются только с одного конца, называемого вершиной стека. Стек работает по принципу "элемент, помещенный в стек последним, извлечен будет первым". Иногда этот принцип обозначается сокращением LIFO (Last In - First Out, т.е. последним зашел - первым вышел).

Очередь - это линейная структура данных, в которую элементы добавляются с одного конца (конец очереди), а удаляются - с другого (начало очереди). Очередь работает по принципу "элемент, помещенный в очередь первым, извлечен будет тоже первым". Иногда этот принцип обозначается сокращением FIFO (First In - First Out, т.е. первым зашел - первым вышел). Элементами стеков и очередей могут быть любые однотипные данные. В простейшем случае - целые числа, чаще всего - записи заранее определенной структуры. Стеки и очереди очень широко используются в системных программах, в частности - в операционных системах и компиляторах. Программная реализация стеков и очередей возможна двумя способами:

· статически с помощью массива

· динамически с помощью механизма указателей

2.2 Статическая реализация стека

Пусть в стеке требуется сохранять целые числа, причем заранее известно их максимальное количество. Тогда для реализации стека надо объявить массив и одну переменную - указатель вершины стека (SP - Stack Pointer). Будем считать, что стек-массив заполняется (растет) от первых элементов массива к последним. Тогда указатель SP может определять либо последнюю занятую ячейку массива, либо первую свободную ячейку. Выберем второй способ. Тогда для пустого стека переменная SP = 1 (если индексация элементов массива начинается с 1), и при каждом добавлении нового элемента переменная SP увеличивается на 1, а при удалении - уменьшается на 1. Последовательность операций для массива из пяти элементов показана на следующей схеме

Со стеком связываются две основные операции: добавление (вталкивание, PUSH) элемента в стек и удаление (выталкивание, POP) элемента из стека.

Добавление включает в себя:

· проверку возможности добавления (стек-массив заполнен полностью?)

· размещение нового элемента в ячейке, определяемой значением переменной SP

· увеличение SP на 1

Удаление включает в себя:

· проверку возможности удаления (стек пустой?)

· уменьшение SP на 1

· извлечение элемента из ячейки, определяемой значением переменной SP.

2.3 Динамическая реализация стека

В отличие от статической реализации на основе массива, при использовании механизма динамического выделения памяти в стек можно занести любое число элементов. Ограничением является только размер области памяти, выделяемой для размещения динамически создаваемых переменных. При динамической реализации элементы стека могут располагаться в ЛЮБЫХ свободных областях памяти, но при этом необходимо как-то связывать соседние элементы друг с другом. Это приводит к необходимости добавления в каждый элемент стека нового связующего поля для хранения адреса соседнего элемента. Тем самым, каждый элемент стека должен представлять собой запись, состоящую из двух компонент:

· информационная составляющая с полезной смысловой информацией

· связующая составляющая для хранения адреса соседнего элемента

Учитывая специфику стека, указатели должны следовать от последнего элемента (вершина стека) к первому (дно стека).

В этом случае физическое размещение элементов в памяти НЕ обязано всегда соответствовать логическому порядку следования элементов. Логический порядок элементов определяется адресными частями при проходе от последнего элемента к первому. Структура оперативной памяти в этом случае может выглядеть следующим образом:



Для построения логического порядка следования элементов достаточно знать вершинный элемент, все остальное восстанавливается по адресным частям элементов независимо от их реального размещения в памяти.

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

Как реализовать связующее поле? Поскольку в связующих полях должны храниться адреса, то следует использовать переменные ссылочного типа.

Что должны адресовать эти переменные? Элементы стека, т.е. записи определенного типа. Следовательно, прежде всего надо ввести ссылочный тип, связанный с базовым типом-записью, а затем - описать базовый тип как запись с необходимыми полями, одно из которых должно быть ссылочного типа:

type pStackItem = ^ TStackItem;

{ссылочный тип для адресации элементов стека}

TStackItem = record

{базовый тип, определяющий структуру элементов стека}

inf: integer; {информационная часть}

next: pStackItem;

{ссылочная часть: поле для адреса следующего элемента}

end;

Какие ссылочные переменные необходимы для поддержки работы стека? Во-первых, всегда необходимо знать адрес элемента, находящегося на вершине стека, т.е. помещенного в стек самым последним:

var sp: pStackItem;

Тогда конструкция sp^.inf будет представлять саму информационную часть, а конструкция sp^.next - адрес предыдущего элемента, который был помещен в стек непосредственно перед текущим.

Кроме того, для прохода по стеку от вершинного элемента к самому первому элементу необходима вспомогательная ссылочная переменная (например - с именем pCurrent). Она на каждом шаге прохода по стеку должна определять адрес текущего элемента. В самом начале прохода надо установить значение pCurrent = sp, а затем циклически менять его на значение pCurrent^.next до тех пор, пока не будет достигнут первый элемент стека. Очевидно, что для прохода надо использовать цикл с неизвестным числом повторений, а признаком его завершения должно быть получение в поле pCurrent^.next пустой ссылки nil. Отсюда следует, что ссылочное поле самого первого элемента стека должно содержать значение nil.

Тогда схематично проход по стеку можно представить следующим образом:

pCurrent: = sp; {начинаем проход с вершины стека}

While pCurrent <> nil do

begin

Writeln (pCurrent ^. Inf); {вывод инф. части текущего элемента}

pCurrent: = pCurrent^.next; {переход к следующему элементу}

end;

Как выполняется добавление нового элемента в вершину стека?

Необходимые шаги:

· выделить память для размещения нового элемента с помощью вспомогательной ссылочной переменной pTemp и стандартной программы new(pTemp); адрес этой области памяти сохраняется как значение переменной pTemp

· заполнить информационную часть нового элемента (например: ReadLn(pTemp^.inf))

· установить адресную часть нового элемента таким образом, чтобы она определяла адрес бывшего вершинного элемента: pTemp^.next: = sp;

· изменить адрес вершины стека так, чтобы он определял в качестве вершины новый элемент: sp: = pTemp;

В этой последовательности шагов важен их порядок. Перестановка шагов 3 и 4 приведет к неправильной работе алгоритма вставки, т.к. на шаге 4 происходит изменение указателя sp, который перед этим на шаге 3 используется для установки правильного адреса в ссылочной части нового элемента.

Как выполняется удаление элемента с вершины стека?

Необходимые шаги:

· с помощью вспомогательной переменной рTemp адресуем удаляемый элемент:

рTemp:= sp;

· изменяем значение переменной sp на адрес новой вершины стека:

sp: = sp^.next;

· каким-то образом обрабатываем удаленный с вершины элемент, например - просто освобождаем занимаемую им память вызовом Dispose(рTemp), или включаем его во вспомогательную структуру (например - стек удаляемых элементов).

Сравнение статической и динамической реализации стека: при статической реализации расходуется меньше памяти, но требуется знание максимального числа элементов в стеке-массиве; динамическая реализация более гибкая, но каждый элемент стека дополнительно расходует память на ссылочную часть (чаще всего - 4 байта), что при большом числе элементов может стать весьма ощутимым.

2.4 Статическая реализация очереди

Пусть в очереди требуется сохранять целые числа, причем заранее известно их максимальное количество. Тогда для реализации очереди надо объявить массив и две переменные - указатель начала очереди First и указатель конца очереди Last. Будем считать, что очередь-массив заполняется (растет) от первых элементов массива к последним. Тогда указатель First будет определять первую занятую ячейку массива, а указатель Last - первую свободную ячейку. Тогда пустую очередь определим, как First = Last = 1 (если индексация элементов массива начинается с 1), и при каждом добавлении нового элемента переменная Last увеличивается на 1, а при удалении на 1 увеличивается указатель First. Последовательность операций для массива из пяти элементов показана на следующей схеме:

Рассмотренная выше простейшая реализация очереди-массива имеет один существенный недостаток: освобождающиеся при удалении ячейки в начале массива НЕ используются при последующих добавлениях, и поэтому при интенсивном использовании очереди быстро может возникнуть ситуация, когда указатель Last выходит за пределы массива, тогда как в начале массива есть свободные ячейки.

Для устранения этого недостатка можно использовать два подхода:

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

· более эффективно использовать так называемую кольцевую очередь, в которой при достижении указателем Last конца массива добавление производится в начало массива:

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

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

Само добавление элемента в очередь выполняется следующим образом:

· проверить возможность добавления (в массиве есть свободные ячейки?)

· добавить элемент в массив по индексу Last

· изменить указатель Last на 1

· если Last выходит за пределы массива, то установить Last в 1

· увеличить счетчик числа элементов в очереди

Удаление элемента из очереди:

· проверить возможность удаления (в очереди есть элементы?)

· извлечь элемент из массива по индексу First и выполнить с ним необходимые действия

· увеличить указатель First на 1

· если First выходит за пределы массива, то установить First в 1

· уменьшить счетчик числа элементов в очереди.

2.5 Динамическая реализация очереди

Аналогично стеку, каждый элемент очереди должен иметь ссылку на следующий за ним элемент, поэтому элемент очереди объявляется как запись с двумя полями - информационное поле и связующее поле. Но для реализации операций с очередью необходимы уже две переменные: указатель pFirst на начало очереди и указатель pLast на конец очереди.

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

Основные операции с динамической очередью:

· проверка отсутствия элементов в очереди

· добавление нового элемента в конец очереди

· удаление элемента из начала очереди

· проход по очереди от начала к концу.

Добавление нового элемента немного по-разному реализуется для пустой и непустой очереди. Аналогично, по-разному выполняется удаление из очереди, содержащей один или более одного элемента. Для того, чтобы эти операции во всех случаях выполнялись единообразно, часто используется следующий прием: в начало очереди вводится фиктивный элемент-заголовок, который НИКОГДА не удаляется и всегда содержит адрес первого элемента очереди.

В этом случае создание пустой очереди включает в себя:

· выделение памяти для заголовка с помощью указателя pFirst

· занесение в ссылочную часть заголовка пустого указателя nil

· установка указателя конца очереди pLast = pFirst

Схемы пустой и непустой очереди приводятся на следующих рисунках:

Необходимые описания типов и переменных:

type pQueueItem = ^ TQueueItem;

{ссылочный тип для адресации элементов очереди}

TQueueItem = record {базовый тип: структура элемента очереди}

inf: integer; {информационная часть}

next: pQueueItem;

{ссылочная часть: адрес следующего элемента}

end;

var pFirst, pLast: pQueueItem;

Тогда условие пустой очереди можно записать следующим образом:

pFirst^.next = nil

Для прохода по очереди от первого реального элемента к последнему необходимо:

· ввести вспомогательную ссылочную переменную pTemp

· установить pTemp в адрес первого реального элемента: pTemp:= pFirst^.next

· организовать цикл по условию достижения конца очереди

· в цикле обработать очередной элемент с помощью указателя pTemp и изменить этот указатель: pTemp:= pTemp^.next

Добавление элемента в конец очереди выполняется следующим образом:

· выделить память для нового элемента с помощью стандартной функции New и вспомогательной ссылочной переменной pTemp:

· заполнить поля нового элемента, в частности в связующую часть установить значение nil: pTemp^.next:= nil

· изменить связующую часть бывшего последнего элемента таким образом, чтобы она адресовала новый добавленный элемент: pLast^.next:= pTemp;

· изменить значение указателя pLast так, чтобы он указывал новый последний элемент: pLast:= pTemp;

Удаление элемента из начала очереди (но после заголовка!) выполняется следующим образом:

· адресуем удаляемый элемент с помощью вспомогательной переменной pTemp: pTemp:= pFirst^.next;

· изменить связующую часть заголовка так, чтобы она указывала на второй элемент очереди, который теперь должен стать первым: pFirst^.next:= pTemp^.next

· если после удаления в списке не остаётся реальных элементов, то необходимо изменить указатель pLast: pLast:= pFirst

· обработать удаленный элемент, например - освободить занимаемую им память с помощью стандартной подпрограммы Dispose (pTemp) или включить его во вспомогательную очередь удаленных элементов.

Сравнение двух способов реализации очереди полностью аналогично стеку. Интересной разновидностью очереди являются приоритетные очереди, в которых элементы выстраиваются не только в порядке поступления, но и в соответствии с их приоритетами: сначала идут более приоритетные элементы, потом - все менее приоритетные. Одноприоритетные элементы располагаются в порядке поступления. Это требует изменения процедуры добавления элемента в очередь: надо прежде всего найти место в очереди, куда должен вставиться новый элемент в соответствии с его приоритетом, а потом уже выполнить саму вставку. Фактически, приоритетную очередь можно рассматривать как разновидность упорядоченного линейного списка. Реализация линейных списков подробно рассматривается в следующей теме.

2.6 Практические задания

Задание 1. Реализовать программу, выполняющую стандартный набор операций со стеком на основе массива:

· проверку пустоты стека

· проверку заполненности стекового массива

· добавление элемента в вершину стека

· удаление элемента из вершины стека

· вывод текущего состояния стека на экран.

Требования:

· все действия должны быть оформлены как процедуры или функции

· добавлению/удалению должна предшествовать проверка возможности выполнения этих операций

· главная программа реализует следующий набор действий:

· инициализация пустого стека

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

Задание 2. Реализовать тот же набор действий на основе динамического распределения памяти.

Требования аналогичны заданию 1, за исключением того, что проверку заполненности стека проводить не надо. Пустой стек задается установкой sp:= nil.

Задание 3. Добавить в предыдущую программу возможность занесения в стек сразу нескольких значений. Количество вводимых значений должно запрашиваться у пользователя, а сами значения можно формировать случайным образом с помощью функции Random (не забыть предварительно вызвать функцию Randomize). Проверить работоспособность программы при различных количествах вводимых элементов, в том числе - для больших значений (десятки тысяч элементов).

Задание 4 (дополнительно). Добавить в предыдущую программу следующие возможности:

· при удалении элемента из основного стека запросить у пользователя, что делать далее с этим элементом: действительно удалить с освобождением памяти или включить его в вершину вспомогательного стека удаленных элементов

· при добавлении нового элемента запросить у пользователя происхождение этого элемента: действительно создание нового элемента или выбор его с вершины вспомогательного стека

· вывод содержимого вспомогательного стека удаленных элементов

Задание 5. Реализовать программу, выполняющую стандартный набор операций с кольцевой очередью на основе массива:

· проверку пустоты очереди

· проверку заполненности очереди

· добавление элемента в конец очереди

· удаление элемента из начала очереди

· вывод текущего состояния очереди на экран

Требования к программе:

· все действия должны быть оформлены как процедуры или функции

· добавлению/удалению должна предшествовать проверка возможности выполнения этих операций

· главная программа реализует следующий набор действий:

· инициализация пустой очереди

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

Задание 6. Реализовать тот же набор действий на основе динамического распределения памяти.

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

Задание 7. Написать программу для моделирования работы очереди со случайным числом добавляемых и удаляемых элементов.

Пусть за единицу времени (например - 1 минуту) в очередь либо добавляется, либо удаляется случайное число элементов в количестве от 1 до 3-х. Одновременно добавление и удаление НЕ происходит. Для наглядности элементами пусть являются большие латинские буквы (коды ASCII от 65 до 90), выбираемые случайным образом. Тип операции с очередью (добавление или удаление) также задается случайно. Это приводит к тому, что очередь случайно растет и убывает. Программа должна наглядно показывать состояние очереди в каждый момент времени.

Рекомендации по разработке программы.

За основу взять предыдущую программу, внеся в ее процедуры следующие изменения:

· процедура добавления вместо запроса у пользователя информационной части нового элемента должна получать ее как входной параметр;

· процедура удаления должна выполнять удаление одного элемента только если очередь НЕ пустая.

Главная программа должна:

· после создания пустой очереди, содержащей только заголовок, инициировать датчик псевдослучайных чисел (процедура Randomize) и вывести соответствующее сообщение;

· организовать цикл с выходом при вводе пользователем какого-либо специального символа (например - буквы q);

· сгенерировать случайное число в диапазоне от 1 до 100 и проверить его четность с помощью операции взятия остатка от деления этого числа на 2;

· если число четное - реализовать операцию добавления, если нечетное - операцию удаления;

· в том и другом случае выполнить:

генерацию случайного числа добавляемых или удаляемых символов в диапазоне от 1 до 3-х

вывод сообщения о выполняемом действии и количестве добавляемых/удаляемых элементов

выполнение цикла для добавления или удаления заданного числа элементов с вызовом соответствующих процедур работы с очередью, причем при добавлении новый символ должен генерироваться случайно с помощью его кода (диапазон 65-90) с последующим преобразованием кода в сам символ с помощью стандартной функции CHR;

· вывести текущее состояние очереди

· запросить у пользователя символ для окончания цикла (при выполнении программы для продолжения работы цикла можно просто дважды нажать клавишу ввода)

После отладки программы надо выполнить ее несколько раз для следующих ситуаций:

· случайное число добавляемых и удаляемых элементов одинаково (например - от 1 до 3-х)

· число добавляемых элементов чуть больше (в среднем!) числа удаляемых (например, добавляется случайное количество элементов в диапазоне от 1 до 4-х, а удаляется - от 1 до 3-х)

· число удаляемых элементов чуть больше числа добавляемых

Для каждого случая выполнить программу при достаточно большом числе добавлений/удалений (30-40) и сделать вывод о поведении очереди.

2.7 Контрольные вопросы по теме

1. Что такое стековый принцип сохранения элементов?

2. Какие основные операции реализуются для стеков?

3. Какие шаги выполняются при добавлении элемента в стек-массив?

4. Какие шаги выполняются при удалении элемента из стека-массива?

5. Какие особые ситуации возможны при реализации стека с помощью массива?

6. Какую структуру должен иметь элемент стека при динамической реализации?

7. Что такое физический и логический порядок следования элементов в стеке?

8. Как между собой связываются соседние элементы стека?

9. Какие типы данных необходимы для динамической реализации стека?

10. Какие переменные необходимы для реализации операций с динамическим стеком?

11. Как реализуется проход по динамическому стеку?

12. Как выполняется добавление элемента в динамический стек?

13. Как выполняется удаление элемента из динамического стека?

14. Сравните динамическую и статическую реализации стека

15. Что такое структура данных типа очередь?

16. Какие основные операции необходимы для реализации структур типа очередь?

17. Как реализуется очередь с помощью массива?

18. Как работает кольцевая очередь, реализованная с помощью массива?

19. Какие особые ситуации возможны при реализации очереди с помощью массива?

20. Как выполняется добавление элемента в очередь-массив?

21. Как выполняется удаление элемента из очереди-массива?

22. На чем основана динамическая реализация очереди?

23. Зачем в очередь вводится фиктивный заголовочный элемент?

24. Что включает в себя создание пустой динамической очереди с заголовком?

25. Какие типы данных необходимы для динамической реализации очереди?

26. Какие переменные используются для реализации основных операций с динамической очередью?

27. Как реализуется проход по динамической очереди?

28. Как реализуется добавление элемента в динамическую очередь?

29. Как реализуется удаление элемента из динамической очереди?

30. Какие особенности имеет приоритетная очередь?

31. Сравните статическую и динамическую реализации очереди.

3. Основы реализации списковых структур

3.1 Структуры данных типа "линейный список"

Линейный список - это набор связанных однотипных элементов, в котором каждый элемент каким-то образом определяет следующий за ним элемент. В отличие от стека и очереди, добавление нового элемента возможно в любом месте списка, также можно удалить любой элемент списка. Ясно, что списковые структуры являются более гибкими, но и немного более сложными в реализации. Фактически, стеки и очереди можно считать частными случаями списков, в которых добавление и удаление элементов может выполняться только на концах.

Стандартный набор операций со списком включает:

· добавление нового элемента после заданного или перед заданным элементом с проверкой возможности добавления элемента

· удаление заданного элемента

· проход по списку от первого элемента к последнему с выполнением заданных действий

· поиск в списке заданного элемента.

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

3.2 Первый способ статической реализации списка

Он основан на том, что логический номер элемента списка полностью соответствует номеру ячейки массива, где этот элемент хранится: первый элемент списка - в первой ячейке массива, второй - во второй, третий - в третьей и т.д.

Элемент 1	Элемент 2	Элемент 3	.......	Элемент N

Проверка наличия в массиве хотя бы одного элемента и хотя бы одной свободной ячейки выполняется элементарно с помощью счетчика числа элементов списка. Проход по списку - также элементарен. Поиск заданного элемента сводится к обычному поиску в массиве.

Как выполнить вставку нового элемента внутри списка, например - в ячейку с номером i < N? Для освобождения ячейки i все элементы списка начиная с номера i и до N надо сдвинуть вправо на одну ячейку (конечно, если в массиве есть еще хотя бы одна свободная ячейка). Копирование надо начинать с последней ячейки, т.е. N - на место N+1, N-1 - на место N, и т.д. i - на место i+1. В освободившуюся ячейку i записывается новый элемент.

Аналогично (с точностью до наоборот) выполняется удаление любого внутреннего элемента: освобождается ячейка i и все последующие элементы сдвигаются влево на одну ячейку, т.е. i+1 - на место i, i+2 - на место i+1, и т.д., элемент N - в ячейку N-1.

Возникает вопрос о трудоемкости выполнения подобных операций перемещения ячеек массива. Если каждый элемент списка, размещенный в одной ячейке массива представляет собой запись с большим числом объемистых полей, то затраты на подобное перемещение могут стать слишком большими. Здесь выходом может быть изменение структуры элемента списка: в массиве хранятся ТОЛЬКО УКАЗАТЕЛИ (АДРЕСА) информационных частей и перемещение производится только этих указателей, сами информационные части остаются на своих местах. Учитывая все возрастающие скорости работы современных процессоров и наличие в их архитектуре быстрых команд группового копирования байтов, можно считать данный метод реализации списков вполне работоспособным.

3.3 Второй способ статической реализации списка

Второй способ реализации списка на основе массива использует принцип указателей (но БЕЗ динамического распределения памяти). В этом случае каждый элемент списка (кроме последнего) должен содержать номер ячейки массива, в которой находится следующий за ним элемент. Это позволяет РАЗЛИЧАТЬ физический и логический порядок следования элементов в списке. Удобно (но НЕ обязательно) в начале массива ввести фиктивный элемент-заголовок, который всегда занимает нулевую ячейку массива, никогда не удаляется и указывает индекс первого реального элемента списка. В этом случае последний элемент списка (где бы он в массиве не располагался) должен в связующей части иметь некоторое специальное значение-признак, например - индекс 0.

Схема физического размещения элементов списка в массиве:

Соответствующая схема логического следования элементов списка:

Тогда необходимые объявления могут быть следующими:

Const N = 100;

Type TListItem = record

Inf: <описание>;

Next: integer;

end;

Var StatList: array [0.. N]of TListItem;

Рассмотрим реализацию основных списковых операций.

Условие пустоты списка: StatList [0].Next = 0;

Проход по списку:

· ввести вспомогательную переменную Current для отслеживания текущего элемента списка и установить Current:= StatList [0].Next;

· организовать цикл по условию Current = 0, внутри которого обработать текущий элемент StatList [Current].Inf и изменить указатель Current на следующий элемент: Current:= StatList [Current].Next

Поиск элемента аналогичен проходу, но может заканчиваться до достижения конца списка:

Current:= StatList [0].Next;

While (Current <> 0) and (StatList [Current].Inf <> `значение' do

Current:= StatList [Current].Next;

If Current = 0 then `поиск неудачен' else `элемент найден';

Добавление элемента после заданного:

· проверка возможности добавления с помощью счетчика текущего числа элементов в списке

· определение каким-то образом элемента, после которого надо добавить новый элемент (например - запрос у пользователя)

· поиск этого элемента в списке; пусть его индекс есть i

· определение номера свободной ячейки массива для размещения нового элемента (методы определения будут рассмотрены ниже); пусть этот номер равен j

· формирование связующей части нового элемента, т.е. занесение туда номера ячейки из связующей части элемента i: StatList [j].next:= StatList [i].next;

· изменение связующей части элемента i на номер j: StatList [i].next:= j;

· занесение данных в информационную часть нового элемента StatList [j].inf;

Аналогично производится добавление нового элемента перед заданным, правда здесь приходится дополнительно узнавать номер ячейки, в которой находится элемент, предшествующий заданному. Это требует небольшого изменения процедуры поиска заданного элемента: вместе с индексом искомого элемента должен определяться индекс его предшественника. Для этого вводится вспомогательная переменная целого типа, которая в процессе поиска заданного элемента "отстает" на один элемент и тем самым всегда указывает предшественника искомого элемента.

Алгоритм добавления элемента перед заданным включает следующие шаги:

· проверка возможности добавления с помощью счетчика текущего числа элементов в списке

· определение каким-то образом элемента, перед которым надо добавить новый элемент (например - запрос у пользователя)

· поиск этого элемента в списке с одновременным отслеживанием элемента-предшественника; пусть индекс заданного элемента есть i, а индекс его предшественника - s

· определение номера свободной ячейки массива для размещения нового элемента (методы определения будут рассмотрены ниже); пусть этот номер равен j

· формирование связующей части нового элемента, т.е. занесение туда индекса i: StatList [j].next:= i;

· изменение связующей части элемента-предшественника с индекса i на индекс j: StatList [s].next:= j;

· занесение данных в информационную часть нового элемента StatList [j].inf;

Удаление заданного элемента (естественно, в случае его наличия в списке) также требует изменения связующей части у элемента-предшественника. Это изменение позволяет "обойти" удаляемый элемент и тем самым исключить его из списка.

Необходимые шаги:

· определение каким-то образом удаляемого элемента (например - запрос у пользователя)

· поиск удаляемого элемента в списке с одновременным отслеживанием элемента-предшественника; пусть индекс удаляемого элемента есть i, а индекс его предшественника - s

...