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

 

СОДЕРЖАНИЕ

ВВЕДЕНИЕ....................................................................................................................................... 4

1. CТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ............................................................................ 4

1.1. Понятие структур данных и алгоритмов................................................................... 4

1.2. Информация и ее представление в памяти.............................................................. 7

1.2.1. Природа информации.............................................................................................. 7

1.2.2. Хранение информации............................................................................................. 7

1.3. Системы счисления.......................................................................................................... 9

1.3.1. Непозиционные системы счисления................................................................... 9

1.3.2. Позиционные системы счисления...................................................................... 9

1.3.3. Изображение чисел в позиционной системе счисления............................ 10

1.3.4. Перевод чисел из одной системы счисления в другую............................. 11

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

1.5. Операции над структурами данных........................................................................... 14

1.6. Структурность данных и технология программирования.................................. 15

2. ПРОСТЫЕ СТРУКТУРЫ ДАННЫХ.................................................................................... 17

2.1. Числовые типы................................................................................................................. 18

2.1.1. Целые типы................................................................................................................ 18

2.1.2. Вещественные типы............................................................................................... 22

2.1.3. Десятичные типы.................................................................................................... 30

2.1.4. Операции над числовыми типами.................................................................... 32

2.2. Битовые типы.................................................................................................................. 33

2.3. Логический тип.............................................................................................................. 34

2.4. Символьный тип............................................................................................................. 35

2.5. Перечислимый тип....................................................................................................... 36

2.6. Интервальный тип.......................................................................................................... 37

2.7. Указатели........................................................................................................................... 38

2.7.1. Физическая структура указателя.......................................................................... 39

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

2.7.3. Операции над указателями.................................................................................. 41

3. СТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ........................................................................... 43

3.1. Векторы.............................................................................................................................. 44

3.2. Массивы............................................................................................................................. 47

3.2.1. Логическая структура............................................................................................. 47

3.2.2. Физическая структура............................................................................................. 47

3.2.3. Операции................................................................................................................... 48

3.2.4. Адресация элементов с помощью векторов Айлиффа............................. 50

3.2.5. Специальные массивы.......................................................................................... 52

3.3. Множества......................................................................................................................... 58

3.3.1. Числовые множества.............................................................................................. 59

3.3.2. Символьные множества........................................................................................ 60

3.3.3. Множество из элементов перечислимого типа........................................... 60

3.3.4. Множество от интервального типа................................................................... 61

3.3.5. Операции над множествами............................................................................... 62

3.4. Записи................................................................................................................................ 62

3.4.1. Логическое и машинное представление записей........................................ 62

3.4.2. Операции над записями....................................................................................... 64

3.5. Записи с вариантами..................................................................................................... 64

3.6. Таблицы............................................................................................................................. 67

3.7. Операции логического уровня над статическими структурами. Поиск..... 68

3.7.1. Последовательный или линейный поиск...................................................... 69

3.7.2. Бинарный поиск...................................................................................................... 69

3.8. Операции логического уровня над статическими структурами. Сортировка 71

3.8.1. Сортировки выборкой............................................................................................ 73

3.8.2. Сортировки включением...................................................................................... 79

3.8.3. Сортировки распределением.............................................................................. 91

3.8.4. Сортировки слиянием........................................................................................... 95

4. Полустатические структуры данных.............................................................................. 98

4.1. Характерные особенности полустатических структур....................................... 98

4.2. Стеки................................................................................................................................... 98

4.2.1. Логическая структура стека.................................................................................. 98

4.2.2. Машинное представление стека и реализация операций......................... 99

4.2.3. Стеки в вычислительных системах................................................................. 101

4.3. Очереди FIFO............................................................................................................... 103

4.3.1. Логическая структура очереди.......................................................................... 103

4.3.2. Машинное представление очереди FIFO и реализация операций..... 103

4.3.3. Очереди с приоритетами................................................................................... 105

4.3.4. Очереди в вычислительных системах.......................................................... 105

4.4. Деки................................................................................................................................... 106

4.4.1. Логическая структура дека................................................................................. 106

4.4.2. Деки в вычислительных системах.................................................................. 108

4.5. Строки............................................................................................................................... 108

4.5.1. Логическая структура строки............................................................................. 108

4.5.2. Операции над строками...................................................................................... 110

4.5.3. Представление строк в памяти......................................................................... 112

5. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ............................ 122

5.1. Связное представление данных в памяти............................................................. 122

5.2. Связные линейные списки......................................................................................... 124

5.2.1. Машинное представление связных линейных списков............................ 124

5.2.2. Реализация операций над связными линейными списками................... 126

5.2.3. Применение линейных списков...................................................................... 133

5.3. Мультисписки................................................................................................................ 137

5.4. Нелинейные разветвленные списки...................................................................... 139

5.4.1. Основные понятия................................................................................................. 139

5.4.2. Представление списковых структур в памяти............................................. 141

5.4.3. Операции обработки списков........................................................................... 143

5.5. Язык программирования LISP.................................................................................. 152

5.6. Управление динамически выделяемой памятью.............................................. 153

6. НЕЛИНЕЙНЫЕ СТРУКТУРЫ ДАННЫХ......................................................................... 158

6.1.Графы................................................................................................................................. 158

6.1.1. Логическая структура, определения................................................................ 158

6.1.2. Машинное представление оpгpафов............................................................... 160

6.2. Деревья............................................................................................................................. 164

6.2.1. Основные определения....................................................................................... 164

6.2.2. Логическое представление и изображение деревьев.............................. 166

6.2.3. Бинарные деревья................................................................................................. 167

6.2.4. Представление любого дерева, леса бинарными деревьями............... 168

6.2.5. Машинное представление деревьев в памяти ЭВМ.................................... 171

6.2.6. Основные операции над деревьями............................................................... 174

6.2.7. Приложения деревьев......................................................................................... 188

6.2.8 Деревья Хаффмена (деревья минимального кодирования).................... 188

6.2.9 Деревья при работе с арифметическими выражениями........................... 189

6.2.10 Формирование таблиц символов..................................................................... 192

6.2.11 Сбалансированные деревья................................................................................ 197

Л И Т Е Р А Т У Р А.................................................................................................................. 220

 

 

ВВЕДЕНИЕ

Они служат базовыми элементами любой машинной
программы. В организации структур данных и
процедур их обработки заложена возможность
проверки правильности работы программы.
Никлас Вирт

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

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

· выполняемые над ними операции физического и логического уровней;

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

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

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

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

Понятие структур данных и алгоритмов

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

Информация и ее представление в памяти

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

Природа информации

В теоретико-информационном смысле информация рассматривается как мера разрешения неопределенности. Предположим, что имеется n возможных состояний… n H = - СУММА ( p(i) * log2 (p(i)) ).

Хранение информации

Некоторые из наиболее важных регистров содержатся в центральном процессоре компьютера. Центральный процессор содержит регистры (иногда называемые… Оперативная память предназначена для запоминания более постоянной по своей… Во время выполнения программы ее команды и данные в основном размещаются в ячейках оперативной памяти. Полное…

Системы счисления

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

Непозиционные системы счисления

Системы счисления, подобные римской, обеспечивают частичное решение проблемы представления большого количества объектов. В римской системе…

Позиционные системы счисления

Система счисления с основанием десять, или десятичная система является позиционной. Рассмотрим, например, число 1303. Его можно представить в… (Здесь и далее символ ^ используется как знак операции возведения в… В позиционной системе могут быть представлены и дробные числа. Например, одна четвертая записывается в виде 0.25, что…

Изображение чисел в позиционной системе счисления

n Ar = R^m * СУММА (a[i]*R^(-i)) , (1.1) i=1

Перевод чисел из одной системы счисления в другую

При переводе правильной дроби из одной системы счисления в другую систему счисления дробь следует умножать на основание системы счисления, в которую… Например, 1) перевести дробное число 0.243 из десятичной системы счисления в… 0.243(10) ---> 0.0011111(2).

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

Теперь можно дать более конкретное определение данного на машинном уровне представления информации.

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

Под СТРУКТУРОЙ ДАННЫХ в общем случае понимают множество элементов данных и множество связей между ними. Такое определение охватывает все возможные подходы к структуризации данных, но в каждой конкретной задаче используются те или иные его аспекты. Поэтому вводится дополнительная классификация структур данных, направления которой соответствуют различным аспектам их рассмотрения. Прежде чем приступать к изучению конкретных структур данных, дадим их общую классификацию по нескольким признакам.

Понятие "ФИЗИЧЕСКАЯ структура данных" отражает способ физического представления данных в памяти машины и называется еще структурой хранения, внутренней структурой или структурой памяти.

Рассмотрение структуры данных без учета ее представления в машинной памяти называется абстрактной или ЛОГИЧЕСКОЙ структурой. В общем случае между логической и соответствующей ей физической структурами существует различие, степень которого зависит от самой структуры и особенностей той среды, в которой она должна быть отражена. Вследствие этого различия существуют процедуры, осуществляющие отображение логической структуры в физическую и, наоборот, физической структуры в логическую. Эти процедуры обеспечивают, кроме того, доступ к физическим структурам и выполнение над ними различных операций, причем каждая операция рассматривается применительно к логической или физической структуре данных.

Различаются ПРОСТЫЕ (базовые, примитивные) структуры (типы) данных и ИНТЕГРИРОВАННЫЕ (структурированные, композитные, сложные). Простыми называются такие структуры данных, которые не могут быть расчленены на составные части, большие, чем биты. С точки зрения физической структуры важным является то обстоятельство, что в данной машинной архитектуре, в данной системе программирования мы всегда можем заранее сказать, каков будет размер данного простого типа и какова структура его размещения в памяти. С логической точки зрения простые данные являются неделимыми единицами. Интегрированными называются такие структуры данных, составными частями которых являются другие структуры данных - простые или в свою очередь интегрированные. Интегрированные структуры данных конструируются программистом с использованием средств интеграции данных, предоставляемых языками программирования.

В зависимости от отсутствия или наличия явно заданных связей между элементами данных следует различать НЕСВЯЗНЫЕ структуры (векторы, массивы, строки, стеки, очереди) и СВЯЗНЫЕ структуры (связные списки).

Весьма важный признак структуры данных - ее изменчивость - изменение числа элементов и (или) связей между элементами структуры. В определении изменчивости структуры не отражен факт изменения значений элементов данных, поскольку в этом случае все структуры данных имели бы свойство изменчивости. По признаку изменчивости различают структуры СТАТИЧЕСКИЕ, ПОЛУСТАТИЧЕСКИЕ, ДИНАМИЧЕСКИЕ. Классификация структур данных по признаку изменчивости приведена на рис. 1.1. Базовые структуры данных, статические, полустатические и динамические характерны для оперативной памяти и часто называются оперативными структурами. Файловые структуры соответствуют структурам данных для внешней памяти.

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

Важный признак структуры данных - характер упорядоченности ее элементов. По этому признаку структуры можно делить на ЛИНЕЙНЫЕ И НЕЛИНЕЙНЫЕ структуры.

В зависимости от характера взаимного расположения элементов в памяти линейные структуры можно разделить на структуры с ПОСЛЕДОВАТЕЛЬНЫМ распределением элементов в памяти (векторы, строки, массивы, стеки, очереди) и структуры с ПРОИЗВОЛЬНЫМ СВЯЗНЫМ распределением элементов в памяти ( односвязные, двусвязные списки). Пример нелинейных структур - многосвязные списки, деревья, графы.

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

Информация по каждому типу однозначно определяет:

· 1) структуру хранения данных указанного типа, т.е. выделение памяти и представление данных в ней, с одной стороны, и интерпретирование двоичного представления, с другой;

· 2) множество допустимых значений, которые может иметь тот или иной объект описываемого типа;

· 3) множество допустимых операций, которые применимы к объекту описываемого типа.

В последующих главах данного пособия рассматриваются структуры данных и соответствующие им типы данных. При описании базовых (простых) типов и при конструировании сложных типов мы ориентировались в основном на язык PASCAL. Этот язык использовался и во всех иллюстративных примерах. PASCAL был создан Н.Виртом специально для иллюстрирования структур данных и алгоритмов и традиционно используется для этих целей. Читатель знакомый с любым другим процедурным языком программирования общего назначения (C, FORTRAN, ALGOL, PL/1 и т.д.), без труда найдет аналогичные средства в известном ему языке.

Операции над структурами данных

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

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

Например, в PL/1 оператор DECLARE N FIXED DECIMAL приведет к выделению адресного пространства для переменной N. В FORTRAN ( Integer I ), в PASCAL ( I:integer ), в C ( int I ) в результате описания типа будет выделена память для соответствующих переменных. Для структур данных, объявленных в программе, память выделяется автоматически средствами систем программирования либо на этапе компиляции, либо при активизации процедурного блока, в котором объявляются соответствующие переменные. Программист может и сам выделять память для структур данных, используя имеющиеся в системе программирования процедуры/функции выделения/освобождения памяти. В объектно-ориентированных языках программирования при разработке нового объекта для него должны быть определены процедуры создания и уничтожения.

Главное заключается в том, что независимо от используемого языка программирования, имеющиеся в программе структуры данных не появляются "из ничего", а явно или неявно объявляются операторами создания структур. В результате этого всем экземплярам структур в программе выделяется память для их размещения.

Операция уничтожения структур данных противоположна по своему действию операции создания. Некоторые языки, такие как BASIC, FORTRAN не дают возможности программисту уничтожать созданные структуры данных. В языках PL/1, C, PASCAL структуры данных, имеющиеся внутри блока, уничтожаются в процессе выполнения программы при выходе из этого блока. Операция уничтожения помогает эффективно использовать память.

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

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

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

Структурность данных и технология программирования

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

ПРОСТЫЕ СТРУКТУРЫ ДАННЫХ

Рис. 2.1. Структура простых типов PASCAL.

 

Числовые типы

Целые типы

С помощью целых чисел может быть представлено количество объектов, являющихся дискретными по своей природе (т.е. счетное число объектов).

Представление в памяти.

Например, +10 и -15 в двоичном виде можно представить так: Число Знаковый бит Величина +10 …   Отметим, что по соглашению 0 используется для представления знака плюс и 1 - для минуса. Такое представление удобно…

Таблица 2.1

Иными словами, диапазон возможных значений целых типов зависит от их внутреннего представления, которое может занимать 1, 2 или 4 байта. В таблице 2.1 приводится перечень целых типов, размер памяти для их внутреннего представления в битах, диапазон возможных значений.

Машинное представление беззнаковых типов.

К беззнаковым типам в PASCAL относятся типы BYTE и WORD.

Формат машинного представления чисел типа BYTE приведен на рис 2.2. а).

Например: 1). Машинное представление числа 45:

45=2^5+2^3+2^2+2^0 = 00101101

2). Машинное представление границ диапазона

допустимых значений чисел 0 и 255:

0: 00000000; 255: 11111111.

Рис. 2.2. Формат машинного представления беззнаковых чисел

Формат машинного представления чисел типа WORD приведен на рис. 2.2. б).

Например: 1). Машинное представление числа 258:

257=2^8+2^1 = 00000010 00000001.

2). Машинное представление границ:

0: 00000000 00000000; 65535: 11111111 11111111.

 

Машинное представление чисел со знаком.

Формат машинного представления чисел типа SHORTINT приведен на рис 2.3. а) где s-знаковый разряд числа. Для положительных чисел s=0, для… Например, машинное представление чисел в формате shortint: 1). 0: 00000000;

Рис. 2.3. Формат машинного представления чисел со знаком

На рис 2.3 s-знаковый бит числа. При этом, если s=0, то число положительное, если s=1 - число отрицательное. Цифры определяют номера разрядов памяти.

Машинное представление данных типа COMP. . 0 Тип COMP предназначен для работы с большими целыми числами (см. таблицу 2.1). Поэтому числа данного типа представляются в памяти в соответствии с правилами представления целых чисел со знаком - в дополнительном коде. Но для удобства пользователей при вводе и выводе значений чисел в этом формате допускается использование формы записи чисел характерных для вещественных чисел (в виде мантиссы и порядка).

Рис. 2.4. Формат машинного представления данных типа COMP

где s - знаковый разряд числа (если s=0,то число положительное, если s=1 - число отрицательное )

Например: машинное представление чисел в формате COMP:

+512 0..0 00000010 0..0 0..0 0..0 0..0 0..0 0..0

-512 0..0 11111110 1..1 1..1 1..1 1..1 1..1 1..1

Вещественные типы

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

Представление вещественных чисел в памяти.

Формат для представления чисел с плавающей точкой содержит одно или два поля фиксированной длины для знаков. Количество позиций для значащих цифр…

Рис. 2.5. Формат представления вещественных чисел

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

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

Таким образом, для представления вещественных чисел в памяти ЭВМ порядок p вещественного числа представляется в виде характеристики путем добавления смещения (старшего бита порядка):

Х = 2^(n-1) + k + p, (2.1)

где:

· n - число бит, отведенных для характеристики,

· p - порядок числа,

· k - поправочный коэффициент фирмы IBM, равный +1 для real

· и -1 для форматов single, double, extended.

Формулы для вычисления характеристики и количество бит, необходимых для ее хранения, приведены в таблице 2.2.

Тип	Харрактеристика	Кол-во бит на хар-ку
real	x = 2^7 + p + 1
single	x = 2^7 + p - 1
double	x = 2^10 + p - 1
extended	x = 2^14 + p - 1

Таблица 2.2

Следующим компонентом представляемого в машине числа с плавающей точкой является мантисса. Для увеличения количества значащих цифр в представлении числа и исключения переполнения при умножении мантиссу обычно подвергают нормализации. Нормализация означает, что мантисса (назовем ее F), кроме случая, когда F=0, должна находиться в интервале

R^(-1) <= F < 1.

Для двоичной системы счисления R=2. Тогда в связи с тем, что 2^(-1) <= F < 1, ненулевая мантисса любого хранимого числа с плавающей точкой должна начинаться с двоичной единицы. В этом и заключается одно из достоинств двоичной формы представления числа с плавающей точкой. Поскольку процесс нормализации создает дробь, первый бит которой равен 1, в структуре некоторых машин эта еди- ница учитывается, однако не записывается в мантиссу. Эту единицу часто называют скрытой единицей, а получающийся дополнительный бит используют для увеличения точности представления чисел или их диапазона.

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

В IBM PC нормализованная мантисса содержит свой старший бит слева от точки. Иными словами нормализованная мантисса в IBM PC принадлежит интервалу 1 <= F < 2. В памяти машины для данных типа real, single, double этот бит не хранится, т.е. является "скрытым" и используется для увеличения порядка в форматах single или для хранения знака в формате real. Для положительных и отрицательных чисел нормализованная мантисса в памяти представлена в прямом коде.

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

Число бит для хранения мантиссы и порядка зависит от типа вещественного числа. Суммарное количество байтов, диапазоны допустимых значений чисел вещественных типов, а также количество значащих цифр после запятой в представлении чисел приведены в таблице 2.3.

Тип	Диапазон значений	Значащие цифры	Размер в байтах
real	2.9*10^(-39)..1.7*10^38	11-12
single	1.4*10^(-45)..3.4*10^38	7-8
double	4.9*10^(-324)..1.8*10^308	15-16
extended	3.1*10^(-4944)..1.2*10^4932	19-20

Таблица 2.3

Алгоритм формирования машинного представления вещественного числа в памяти ЭВМ

· 1). Число представляется в двоичном коде. · 2). Двоичное число нормализуется. При этом для чисел, больших единицы,… · 3). По формуле из таблицы 2.2 с учетом типа вещественного числа определяется характеристика.

Машинное представление данных типа REAL

мл. байт ст. байт а: 7 0 15 8 23 16 31 24 39 32 47 40 x....x м....м м....м м....м м....м sм...м

Машинное представление данных типа SINGLE

мл. байт ст. байт 7 0 15 8 23 22 16 31 30 24 - номера разрядов памяти м....м м....м х м...м s х...х

Машинное представление данных типа DOUBLE

мл.байт ст.байт 7 0 15 8 23 16 31 24 39 32 47 40 55 52 51 48 63 56 м...м м...м м...м м...м м...м м...м х..х м...м s x..x

Машинное представление данных типа EXTENDED

мл.байт ст. байт 7 0 15 8 23 16 31 24 39 32 47 40 55 48 63 56 71 64 79 72 м..м м..м м..м м..м м..м м..м м..м м..м х..х sх..х

Десятичный тип с фиксированной точкой.

DECIMAL FIXED (m.d) или DECIMAL FIXED (m). Первое описание означает, что данное представляется в виде числа, состоящего… Внутримашинное представление данного типа носит название десятичного упакованного формата. Примеры представления чисел…

Рис.2.6. Машинное представление десятичных чисел в упакованном формате

Каждая десятичная цифра числа занимает полбайта (4 двоичных разряда) и представляется в этом полубайте ее двоичным кодом. Еще полбайта занимает знак числа, который представляется двоичным кодом 1010 - знак "+" или 1011 - знак "-". Представление занимает целое число байт и при необходимости дополняется ведущим нулем.

Тип шаблона.

В языке PL/1 тип шаблона описывается в программе, как: PICTURE '9...9'.

Это означает, что данное представляет собой целое число, содержащее столько цифр, сколько девяток указано в описании.

Рис.2.7. Машинное представление десятичных чисел в зонном формате

Внутримашинное представление этого типа, так называемый десятичный зонный формат, весьма близок к такому представлению данных, которое удобно пользователю: каждая десятичная цифра представляется байтом: содержащим код символа соответствующей цифры. В IBM System/390, которая аппаратно поддерживает зонный формат, применяется символьный код EBCDIC, в котором код символа цифры содержит в старшем полубайте код 1111, а в младшем - двоичный код цифры числа. Знак не входит в общее число цифр в числе, для представления знака в старшем полубайте последней цифры числа код 1111 заменяется на 1010 - знак "+" или 1011 - знак "-".

Примеры представления чисел в зонном формате приведены на рис.2.7.

Операции над числовыми типами

Над числовыми типами, как и над всеми другими, возможны прежде всего четыре основных операции: создание, уничтожение, выбор, обновление. Специфические операции над числовыми типами - хорошо известные всем арифметические операции: сложение, вычитание, умножение, деление. Операция возведения в степень в некоторых языках также является базовой и обозначается специальным символом или комбинацией символов (^ - в BASIC, ** - в PL/1), в дру- гих - выполняется встроенными функциями (pow в C).

Обратим внимание на то, что операция деления по-разному выполняется для целых и вещественных чисел. При делении целых чисел дробная часть результата отбрасывается, как бы близка к 1 она ни была. В связи с этим в языке PASCAL имеются даже разные обозначения для деления вещественных и целых чисел - операции "/" и "div" соответственно. В других языках оба вида деления обозначаются одинаково, а тип деления определяется типом операндов. Для целых операндов возможна еще одна операция - остаток от деления - ("mod" - в PASCAL, "%" - в C).

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

Поскольку одни и те же операции допустимы для разных числовых типов, возникает проблема арифметических выражений со смешением типов. Это создает некоторые неудобства для программистов, так как в реальных задачах выражения со смешанными типами встречаются довольно часто. Поэтому большинство языков допускает выражения, операнды которых имеют разные числовые типы, но обрабаты- ваются такие выражения в разных языках по-разному. В языке PL/1, например, все операнды выражения приводятся к одному типу - к типу той переменной, в которую будет записан результат, а затем уже выражение вычисляется. В языке же C преобразование типов выполняется в процессе вычисления выражения, при выполнении каждой отдельной операции, без учета других операций; каждая операция вычисляется с точностью самого точного участвующего в ней операнда. Программист, использующий выражения со смешением типов, должен точно знать правила их вычисления для выбранного языка.

Битовые типы

Представление битовых типов.

В языке PL/1 существует специальный тип данных - строка битов, объявляемый в программе, как: BIT(n). Данные этого типа представляют собой последовательность бит длиною n. Строка…

Операции над битовыми типами.

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

Операции булевой алгебры - НЕ (not), ИЛИ (or), И (and), исключающее ИЛИ (xor). Эти операции и по названию, и по смыслу похожи на операции над логическими операндами, но отличие в их применении к битовым операндам состоит в том, что операции выполняются над отдельными разрядами операндов.

Так операция НЕ состоит в том, что каждый разряд операнда изменяет значение на противоположный. Выполнение операции, например, ИЛИ над двумя битовыми операндами состоит в том, что выполняется ИЛИ между первым разрядом первого операнда и первым разрядом второго операнда, это дает первый разряд результата; затем выполняется ИЛИ между вторым разрядом первого операнда и вторым разрядом второго, получается второй разряд результата и т.д.

Ниже даны примеры выполнения побитовых логических операций:

а). x = 01101100 в). x = 01101100

not x = 10010011 y = 11001110

x and y = 01001100

б). x = 01101100 г). x = 01101100

y = 11001110 y = 11001110

x or y = 11101110 x xor y = 10100010

В некоторых языках (PASCAL) побитовые логические операции обозначаются так же, как и операции над логическими операндами и распознаются по типу операндов. В других языках (C) для побитовых и общих логических операций используются разные обозначения. В третьих (PL/1) - побитовые операции реализуются встроенными функциями языка.

Операции сдвигов выполняют смещение двоичного кода на заданное количество разрядов влево или вправо. Из трех возможных типов сдвига (арифметический, логический, циклический) в языках программирования обычно реализуется только логический (например, операциями shr, shl в PASCAL).

В операциях сравнения битовые данные интерпретируются как целые без знака, и сравнение выполняется как сравнение целых чисел. Битовые строки в языке PL/1 - более общий тип данных, к которому применимы также операции над строковыми данными, рассматриваемые в главе 4.

Логический тип

Данные логического типа занимают один байт памяти. При этом значению false соответствует нулевое значение байта, а значению true соответствует любое… Однако следует иметь в виду, что при выполнении операции присваивания… Над логическими типами возможны операции булевой алгебры - НЕ (not), ИЛИ (or), И (and), исключающее ИЛИ (xor) -…

Символьный тип

Значение символьного типа char занимает в памяти 1 байт. Код от 0 до 255 в этом байте задает один из 256 возможных символов ASCII таблицы. Например: символ "1" имеет ASCII код 49, следовательно машинное… ASCII, однако, не является единственно возможным множеством. Другим достаточно широко используемым множеством является…

Перечислимый тип

Логическая структура.

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

type color=(red,blue,green);

work_day=(mo,tu,we,th,fr);

winter_day=(december,january,february);

Машинное представление.

var B,С:color; begin B:=bluе; (* B=1 *) C:=green; (* С=2 *)

Операции.

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

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

Интервальный тип

Логическая структура.

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

Машинное представление.

var A: 220..250; (* Занимает 1 байт *) В: 2221..2226; (* Занимает 2 байта *) C: 'A'..'K'; (* Занимает 1 байт *)

Операции.

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

Базовый тип	Максимально допустимый диапазон	Размер требуемой памяти
ShortInt	-128..127	1 байт
Integer	-32768..32767	2 байта
LongInt	-2147483648..2147483647	4 байта
Byte	0..255	1 байт
Word	0..65535	2 байта
Char	chr(ord(0))..chr(ord(255))	1 байт
Boolean	False..True	1 байт

Таблица 2.4

Примечание: запись chr(ord(0)) в таблице следует понимать как: символ с кодом 0.

А) Интервальный тип от символьного: определение кода символа и, наоборот, символа по его коду.

Пусть задана переменная типа tz:'d'..'h'. Данной переменной присвоено значение 'e'. Байт памяти отведенный под эту переменную будет хранить ASCII-код буквы 'e' т.е. 01100101 (в 10-ом представлении 101).

Б) Интервальный тип от перечислимого: определение порядкового номера идентификатора по его значению и, наоборот, по номеру идентификатора - его значение.

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

Указатели

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

Физическая структура указателя

Машинное слово этого процессора имеет размер 16 двоичных разрядов. Если использовать представление адреса в одном слове, то можно адресовать 64…

Рис 2.8. Вычисление полного адреса в микропроцессоре i8086.

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

Еще раз повторим, что физическая структура адреса принципиально различна для разных аппаратных архитектур. Так, например, в микропроцессоре i386 обе компоненты адреса 32-разрядные; в процессорах семейства S/390 адрес представляется в виде 31-разрядного смещения в одном из 19 адресных пространств, в процессоре Power PC 620 одним 64-разрядным словом может адресоваться вся как оперативная, так и внешняя память.

Операционная система MS DOS была разработана именно для процессора i8086 и использует описанную структуру адреса даже, когда выполняется на более совершенных процессорах. Однако, это сегодня единственная операционная система, в среде которой программист может работать с адресами в реальной памяти и с физической структурой адреса. Все без исключения современные модели процессоров аппаратно выполняют так называемую динамическую трансляцию адресов и совместно с современными операционными системами обеспечивают работу программ в виртуальной (кажущейся) памяти. Программа разрабатывается и выполняется в некоторой виртуальной памяти, адреса в которой линейно изменяются от 0 до некоторого максимального значения. Виртуальный адрес представляет собой число - номер ячейки в виртуальном адресном пространстве. Преобразование виртуального адреса в реальный производится аппаратно при каждом обращении по виртуальному адресу. Это преобразование выполняется совершенно незаметно (прозрачно) для программиста, поэтому в современных системах программист может считать физической структурой адреса структуру виртуального адреса. Виртуальный же адрес представляет собой целое число без знака. В разных вычислительных системах может различаться разрядность этого числа. Большинство современных систем обеспечивают 32-разрядный адрес, позволяющий адресовать до 4 Гбайт памяти, но уже существуют системы с 48 и даже 64-разрядными адресами.

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

Var ipt : ^integer; cpt : ^char; или в языке C: int *ipt; char *cpt;

Операции над указателями.

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

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

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

Операция выборки - одноместная, ее операндом является типизированный (обязательно!) указатель, результат - данные, выбранные из памяти по адресу, заданному операндом. Тип результата определяется типом указателя-операнда.

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

К указателю можно прибавить целое число или вычесть из него целое число. Поскольку память имеет линейную структуру, прибавление к адресу числа даст нам адрес области памяти, смещенной на это число байт (или других единиц измерения) относительно исходного адреса. Результат операций "указатель + целое", "указатель - целое" имеет тип "указатель".

Можно вычесть один указатель из другого (оба указателя-операнда при этом должны иметь одинаковый тип). Результат такого вычитания будет иметь тип целого числа со знаком. Его значение показывает на сколько байт (или других единиц измерения) один адрес отстоит от другого в памяти.

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

Операции адресной арифметики выполняются только над типизированными указателями. Единицей измерения в адресной арифметике является размер объекта, который указателем адресуется. Так, если переменная ipt определена как указатель на целое число (int *ipt), то выражение ipt+1 даст адрес, больший не на 1, а на количество байт в целом числе (в MS DOS - 2). Вычитание указателей также дает в результате не количество байт, а количество объектов данного типа, помещающихся в памяти между двумя адресами. Это справедливо как для указателей на простые типы, так и для указателей на сложные объекты, размеры которых составляют десятки, сотни и более байт.

В связи с имеющимися в языке C расширенными средствами работы с указателями, следует упомянуть и о разных представлениях указателей в этом языке. В C указатели любого типа могут быть ближними (near) и дальними (far) или (huge). Эта дифференциация связана с физической структурой адреса в i8086, которая была рассмотрена выше. Ближние указатели представляют собой смещение в текущем сегменте, для представления такого указателя достаточно одного 16-разрядного слова. Дальние указатели представляются двумя 16-разрядными словами - сегментом и смещением. Разница между far или huge указателями состоит в том, что для первых адресная арифметика работает только со смещением, не затрагивая сегментную часть адреса, таким образом, операции адресной арифметики могут изменять адрес в диапазоне не более 64 Кбайт; для вторых - в адресной арифметике участвует и сегментная часть, таким образом, предел изменения адреса - 1 Мбайт.

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

СТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ

Каждую структуру данных характеризуют еЯ логическим и физическим представлениями. Очень часто говоря о той или иной структуре данных, имеют в виду… Статические структуры в языках программирования связаны со структурированными…

Векторы

Логическая структура.

Вектор (одномерный массив) - структура данных с фиксированным числом элементов одного и того же типа типа. Каждый элемент вектора имеет уникальный в рамках заданного вектора номер. Обращение к элементу вектора выполняется по имени вектора и номеру требуемого элемента.

Машинное представление. Адресация элементов структур.

В языках программирования вектор представляется одномерным массивом с синтаксисом описания вида (PASCAL): < Имя > : array [n..k] of < тип >; где n-номер первого элемента, k-номер последнего элемента. Представление в памяти вектора будет такое, как показано на…

Рис. 3.1. Представление вектора в памяти

где @ Имя -адрес вектора или, что тоже самое, адрес первого элемента вектора,

Sizeof(тип)-размер слота (количество байтов памяти для записи одного элемента вектора), (k-n)*Sizeof(тип) - относительный адрес элемента с номером k, или, что тоже самое, смещение элемента с номером k.

Например:

var m1:array[-2..2] of real;

представление данного вектора в памяти будет как на рис. 3.2.

Рис. 3.2. Представление вектора m1 в памяти

В языках, где память распределяется до выполнения программы на этапе компиляции (C, PASCAL, FORTRAN), при описании типа вектора граничные значения индексов должны определены. В языках, где память может распределяться динамически (ALGOL, PL/1), значения индексов могут быть заданы во время выполнения программы.

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

ByteSise = ( k - n + 1 ) * Sizeof (тип)

Обращение к i-тому элементу вектора выполняется по адресу вектора плюс смещение к данному элементу. Смещение i-ого элемента вектора определяется по формуле:

ByteNumer = ( i- n ) * Sizeof (тип),

а адрес его: @ ByteNumber = @ имя + ByteNumber.

где @ имя - адрес первого элемента вектора.

Например: var МAS: array [ 5..10 ] of word.

Базовый тип элемента вектора - Word требует 2 байта, поэтому на каждый элемент вектора выделяется по два байта. Тогда таблица 3.1 смещений элементов вектора относительно @Mas выглядит так:

Смещение (байт)	+ 0	+ 2	+ 4	+ 6	+ 8	+ 10
Идентификатор поля	MAS[5]	MAS[6]	MAS[7]	MAS[8]	MAS[9]	MAS[10]

Таблица 3.1

Этот вектор будет занимать в памяти: (10-5+1)*2 = 12 байт.
Смещение к элементу вектора с номером 8: (8-5)*2 = 6
Адрес элемента с номером 8: @ MAS + 6.

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

@Имя[i] = @Имя + i*Sizeof(тип) - n*Sizeof(тип) (3.1)

Это вычисление не может быть выполнено на этапе компиляции, так как значение переменной i в это время еще неизвестно. Следовательно, вычисление адреса элемента должно производиться на этапе выполнения программы при каждом обращении к элементу вектора. Но для этого на этапе выполнения, во-первых, должны быть известны параметры формулы (3.1): @Имя Sizeof(тип), n, а во-вторых, при каждом обращении должны выполняться две операции умножения и две - сложения. Преобразовав формулу (3.1) в формулу (3.2),

@Имя[i] = A0 + i*Sizeof(тип) -- (3.2)

A0 = @Имя - n*Sizeof(тип) --

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

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

Можно ли обойтись без дескриптора вектора?

В языке C, например, дескриптор вектора отсутствует, точнее, не сохраняется на этапе выполнения. Индексация массивов в C обязательно начинается с нуля. Компилятор каждое обращение к элементу массива заменяет на последовательность команд, реализующую частный случай формулы (3.1) при n = 0:

@Имя[i] = @Имя + i*Sizeof(тип)

Программисты, привыкшие работать на C, часто вместо выражения вида: Имя[i] употребляют выражение вида: *(Имя+i).

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

 

Массивы

Логическая структура

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

Физическая структура

  Рис. 3.3. Физическая структура двумерного массива из (k1-n1+1) строк и… Многомерные массивы хранятся в непрерывной области памяти. Размер слота определяется базовым типом элемента массива.…

Таблица 3.2

Этот массив будет занимать в памяти: (5-3+1)*(8-7+1)*2=12 байт; а адрес элемента Mas[4,8]:

@Mas+((4-3)*(8-7+1)+(8-7)*2 = @Mas+6

Операции

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

В соответствии с формулами (3.3), (3.4) и по аналогии с вектором (3.1), (3.2) для двумерного массива c границами изменения индексов:

[B(1)..E(1)][B(2)..E(2)], размещенного в памяти по строкам, адрес элемента с индексами [I(1),I(2)] может быть вычислен как:

Addr[I(1),I(2)] = Addr[B(1),B(2)] +

{ [I(1)-B(1)] * [E(2)-B(2)+1] + [I(2)-B(2)] }*SizeOf(Тип) (3.5)

Обобщая (3.5) для массива произвольной размерности:

Mas[B(1)..E(2)][B(2)..E(2)]...[B(n)..E(n)]

получим:

Addr[I(1),I(2),...,I(n)] = Addr[B(1),B(2),...B(n)] -

n n (3.6)

- Sizeof(Тип)*СУММА[B(m)*D(m)] + Sizeof(Тип)*СУММА[I(m)*D(m)]

m=1 m=1

где Dm зависит от способа размещения массива. При размещении по строкам:

D(m)=[E(m+1)-B(m+1)+1]*D(m+1), где m = n-1,...,1 и D(n)=1

при размещении по столбцам:

D(m)=[E(m-1)-B(m-1)+1]*D(m-1), где m = 2,...,n и D(1)=1

При вычислении адреса элемента наиболее сложным является вычисление третьей составляющей формулы (3.6), т.к. первые две не зависят от индексов и могут быть вычислены заранее. Для ускорения вычислений множители D(m) также могут быть вычислены заранее и сохраняться в дескрипторе массива. Дескриптор массива, таким образом, содержит:

· начальный адрес массива - Addr[I(1),I(2),...,I(n)];

· число измерений в массиве - n;

· постоянную составляющую формулы линеаризации (первые две составляющие формулы (3.6);

· для каждого из n измерений массива:

· значения граничных индексов - B(i), E(i);

· множитель формулы линеаризации - D(i).

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

Например, если в PL/1-программе объявлен двумерный массив:

DECLARE A(10,10) BINARY FIXED;

то выражение: A[*,I] - будет обращаться к одномерному массиву, состоящему из элементов: A(1,I), A(2,I),...,A(10,I).

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

например: A(*,I) = A(*,I) + 1

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

Адресация элементов с помощью векторов Айлиффа

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

Рис. 3.4. Представление массивов с помощью векторов Айлиффа

Для массива любой мерности формируется набор дескрипторов: основного и несколько уровней вспомогательных дескрипторов, называемых векторами Айлиффа. Каждый вектор Айлиффа определЯнного уровня содержит указатель на нулевые компоненты векторов Айлиффа следующего, более низкого уровня, а векторы Айлиффа самого нижнего уровня содержат указатели групп элементов отображаемого масси- ва. Основной дескриптор массива хранит указатель вектора Айлиффа первого уровня. При такой организации к произвольному элементу В(j1,j2,...,jn) многомерного массива можно обратиться пройдя по цепочке от основного дескриптора через соответствующие компоненты векторов Айлиффа.

На рис. 3.4 приведена физическая структура трЯхмерного массива В[4..5,-1..1,0..1], представленная по методу Айлиффа. Из этого рисунка видно, что метод Айлиффа, увеличивая скорость доступа к элементам массива, приводит в то же время к увеличению суммарного объЯма памяти, требуемого для представления массива. В этом заключается основной недостаток представления массивов с по- мощью векторов Айлиффа.

Специальные массивы

На практике встречаются массивы, которые в силу определенных причин могут записываться в память не полностью, а частично. Это особенно актуально для массивов настолько больших размеров, что для их хранения в полном объеме памяти может быть недостаточно. К таким массивам относятся симметричные и разреженные массивы.

Симметричные массивы.

На практике для работы с симметричной матрицей разрабатываются процедуры для: а) преобразования индексов матрицы в индекс вектора, б) формирования вектора и… В приложении приведен пример программы для работы с симметричной матрицей.

Разреженные массивы.

Различают два типа разреженных массивов: · 1) массивы, в которых местоположения элементов со значениями отличными от… · 2) массивы со случайным расположением элементов.

Массивы с математическим описанием местоположения нефоновых элементов.

Элементы, значения которых являются фоновыми, называют нулевыми; элементы, значения которых отличны от фонового, - ненулевыми. Но нужно помнить, что… Ненулевые значения хранятся, как правило, в одномерном массиве, а связь между… На практике для работы с разреженным массивом разрабатываются функции:

Разреженные массивы со случайным расположением элементов.

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

 

Ё 0 0 6 0 9 0 0 Ё

Ё 2 0 0 7 8 0 4 Ё

Ё10 0 0 0 0 0 0 Ё

Ё 0 0 12 0 0 0 0 Ё

Ё 0 0 0 3 0 0 5 Ё

Пусть есть матрица А размерности 5*7, в которой из 35 элементов только 10 отличны от нуля.

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

Доступ к элементу массива A с индексами i и j выполняется выборкой индекса i из вектора ROW, индекса j из вектора COLUM и значения элемента из… Более эффективное представление, с точки зрения требований к памяти и времени… Представление матрицы А, данное на рис. 3.5 сокращает требования к объему памяти более чем в 2 раза. Для больших…

Рис. 3.5. Последовательное представление разреженных матриц.

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

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

Рис.3.6. Формат вершины для представления разреженных матриц

На рис. 3.7 приведена многосвязная структура, в которой используются вершины такого типа для представления матрицы А, описанной ранее в данном пункте. Циклический список представляет все строки и столбцы. Список столбца может содержать общие вершины с одним списком строки или более. Для того, чтобы обеспечить использование более эффективных алгоритмов включения и исключения элементов, все списки строк и столбцов имеют головные вершины. Головная вершина каждого списка строки содержит нуль в поле С; аналогично каждая головная вершина в списке столбца имеет нуль в поле R. Строка или столбец, содержащие только нулевые элементы, представлены головными вершинами, у которых поле LEFT или UP указывает само на себя.

Рис. 3.7. Многосвязная структура для представления матрицы A

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

Множества

Логическая структура.

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

Физическая структура.

Число байтов, выделяемых для данных типа множество, вычисляется по формуле: ByteSize = (max div 8)-(min div 8) + 1, где max и min - верхняя и нижняя… Номер байта для конкретного элемента Е вычисляется по формуле: ByteNumber = (E div 8)-(min div 8),

Числовые множества

Стандартный числовой тип, который может быть базовым для формирования множества - тип byte.

Множество хранится в памяти как показано в таблице 3.3.

Таблица 3.3

где @S - адрес данного типа множество.

Бит поля установлен в 1, если элемент входит в множество, и в 0 - если не входит.

Например, S : set of byte; S:=[15,19];

Содержимое памяти при этом будет следующим:

@S+0 - 00000000 @S+2 - 00001000

@S+1 - 10000000 . . . . . .

@S+31 - 00000000

Символьные множества

Символьные множества хранятся в памяти также как и числовые множества. Разница лишь в том, что хранятся не числа, а коды ASCII символов.

Например, S : set of char; S:=['A','C'];

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

@S+0 - 00000000 . . . . . .

. . . . . . @S+31 - 00000000

@S+8 - 00001010

Множество из элементов перечислимого типа

Пример: Type Video=(MDA,CGA,HGC,EGA,EGAm,VGA,VGAm,SVGA,PGA,XGA);

Рис. 3.8. Распределение памяти для переменной типа set of Video

Если выполнить оператор S:=[CGA,SVGA], содержимое памяти при этом будет:

@S+0 - 10000010

@S+1 - 00000000

Множество от интервального типа

Например, type S=10..17; var I:set of S;

Рис. 3.9. Представление переменной типа set of S

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

Например, Type S = 510..520;

Var I : S;

begin I:=[512]; end.

Представление в памяти переменной I будет:

@i+0 - 00000000 @i+1 - 00000001

Операции над множествами

Пусть S1, S2, S3 : set of byte , Над этими множествами определены следующие специфические операции:

· 1) Объединение множеств: S2+S3. Результатом является множество, содержащее элементы обоих исходных множеств.

· 2) Пересечение множеств: S2*S3. Результатом является множество, содержащее общие элементы обоих исходных множеств.

· 3) Проверка на вхождение элемента в множество: a in S1. Результатом этой операции является значение логического типа - true, если элемент a входит в множество S1, false - в противном случае.

Записи

Логическое и машинное представление записей

Пример записи - совокупность сведений о некотором студенте. Объект "студент" обладает свойствами: · "личный номер" - характеризуется целым положительным числом,

Рис. 3.10. Представление в памяти переменной типа record в виде последовательности полей

б) в виде связного списка с указателями на значения полей записи. При такой организации имеет место быстрое обращение к элементам, но очень неэкономичный расход памяти для хранения. Структура хранения в памяти связного списка с указателями на элементы приведена на рис. 3.11.

Рис. 3.11. Представление в памяти переменной типа record в виде связного списка.

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

В соответствии с общим подходом языка C дескриптор записи (в этом языке записи называются структурами) не сохраняется до выполнения программы. Поля структуры просто располагаются в смежных слотах памяти, обращения к отдельным полям заменяются на их адреса еще на этапе компиляции.

Полем записи может быть в свою очередь интегрированная структура данных - вектор, массив или другая запись. В некоторых языках программирования (COBOL, PL/1) при описании вложенных записей указывается уровень вложенности, в других (PASCAL, C) - уровень вложенности определяется автоматически.

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

type rec = record

f1 : integer;

f2 : char[2];

f3 : rec; end;

Как компилятор будет выделять память для такой записи? Для поля f1 будет выделено 2 байта, для поля f2 - 2 байта, а поле f3 - запись, которая в свою очередь состоит из f1 (2 байта), f2 (2 байта) и f3, которое... и т.д. Недаром компилятор C, встретив подобное описание, выдает сообщение о нехватке памяти.

Однако, полем записи вполне может быть указатель на другую такую же запись: размер памяти, занимаемой указателем известен и проблем с выделением памяти не возникает. Этот прием широко используется в программировании для установления связей между однотипными записями (см. главу 5).

Операции над записями

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

< имя переменной-записи >.< имя поля >

Так, для записи, описанной в начале п.3.5.1, конструкции: stud1.num и stud1.math будут обеспечивать обращения к полям num и math соответственно.

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

Большинство языков программирования поддерживает некоторые операции, работающие с записью, как с единым целым, а не с отдельными ее полями. Это операции присваивания одной записи значения другой однотипной записи и сравнения двух однотипных записей на равенство/неравенство. В тех же случаях, когда такие операции не поддерживаются языком явно (язык C), они могут выполняться над отдельными полями записей или же записи могут копироваться и сравниваться как неструктурированные области памяти.

Записи с вариантами

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

Для задач подобного рода развитые языки программирования (C, PASCAL) предоставляют в распоряжение программиста записи с вариантами. Запись с вариантами состоит из двух частей. В первой части описываются поля, общие для всех групп объектов, моделируемых записью. Среди этих полей обычно бывает поле, значение которого позволяет идентифицировать группу, к которой данный объект принадлежит и, следовательно, какой из вариантов второй части записи должен быть использован при обработке. Вторая часть записи содержит описания непересекающихся свойств - для каждого подмножества таких свойств - отдельное описание. Язык программирования может требовать, чтобы имена полей-свойств не повторялись в разных вариантах (PASCAL), или же требовать именования каждого варианта (C). В первом случае идентификация поля, находящегося в вариантной части записи при обращении к нему ничем не отличается от случая простой записи:

< имя переменной-записи >.< имя поля >

Во втором случае идентификация немного усложняется:

< имя переменной-записи >.< имя варианта >.< имя поля >

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

Запись с вариантами для такой задачи в языке PASCAL выглядит, как:

type figure = record

fig_type : char; { тип фигуры }

x0, y0 : word; { координаты опорной точки }

color : byte; { цвет }

case fig_t : char of

'C': ( radius : word); { радиус окружности }

'R': (len1, len2 : word); { длины сторон прямоугольника }

'T': (x1,y1,x2,y2 : word); { координаты двух вершин }

end;

а в языке C, как:

typedef struct

{ char fig_type; /* тип фигуры */

unsigned int x0, y0; /* координаты опорной точки */

unsigned char color; /* цвет */

union

{ struct

{ unsigned int radius; /* радиус окружности */

} cyrcle;

struct

{ unsigned int len1, len2; /* длины сторон прямоугольника */

} rectangle;

struct

{ unsigned int x1,y1,x2,y2; /* координаты двух вершин */

} triangle;

} fig_t;

} figure;

И если в программе определена переменная fig1 типа figure, в которой хранится описание окружности, то обращение к радиусу этой окружности в языке PASCAL будет иметь вид: fig1.radius, а в C: fig1.circle.radius

Поле с именем fig_type введено для представления идентификатора вида фигуры, который, например, может кодироваться символами: "C"- окружность или "R"- прямоугольник, или "T"- треугольник.

Выделение памяти для записи с вариантами показано на рис.3.12.

Рис.3.12. Выделение памяти для записи с вариантами

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

Таблицы

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

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

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

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

Операции логического уровня над статическими структурами. Поиск

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

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

· - степенные - O(N^a);

· - линейные - O(N);

· - логарифмические - O(logA(N)). (Здесь и далее запись вида "logА" обозначает "логарифм по основанию А").

Эффективность степенных алгоритмов обычно считается плохой, линейных - удовлетворительной, логарифмических - хорошей.

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

В последующем изложении все описания алгоритмов даны для работы с таблицей, состоящей из записей R[1], R[2], ..., R[N] с ключами K[1], K[2], ..., K[N]. Во всех случаях N - количество элементов таблицы. Программные примеры для сокращения их объема работают с массивами целых чисел. Такой массив можно рассматривать как вырожденный случай таблицы, каждая запись которой состо- ит из единственного поля, которое является также и ключом. Во всех программных примерах следует считать уже определенными: константу N- целое положительное число, число элементов в массиве; константу EMPTY - целое число, признак "пусто" (EMPTY=-1); тип - type SEQ = array[1..N] of integer; сортируемые последовательности.

Последовательный или линейный поиск

Для последовательного поиска в среднем требуется (N+1)/2 сравнений. Таким образом, порядок алгоритма - линейный - O(N). Программная иллюстрация линейного поиска в неупорядоченном массиве приведена в… {===== Программный пример 3.4 =====}

Бинарный поиск

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

Таблица 3.4

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

Рекурсивная процедура бинарного поиска представлена в программном примере 3.6. Для выполнения поиска необходимо при вызове процедуры задать значения ее формальных параметров b и е - 1 и N соответственно, где b, e - граничные индексы области поиска.

 

{===== Программный пример 3.6 =====}

Function BinSearch( a: SEQ; key, b, e : integer) : integer;

Var i : integer;

begin

if b > e then BinSearch:=EMPTY { проверка ширины интервала }

else begin

i:=(b+e) div 2; { середина интервала }

if a[i]=key then BinSearch:=i {ключ найден, возврат индекса}

else if a[i] < key then { поиск в правом подинтервале }

BinSearch:=BinSearch(a,key,i+1,e)

else { поиск в левом подинтервале }

BinSearch:=BinSearch(a,key,b,i-1);

end; end;

Известно несколько модификаций алгоритма бинарного поиска, выполняемых на деревьях, которые будут рассмотрены в главе 5.

Операции логического уровня над статическими структурами. Сортировка

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

Из всех задач программирования сортировка, возможно, имеет самый богатый выбор алгоритмов решения. Назовем некоторые факторы, которые влияют на выбор алгоритма (помимо порядка алгоритма).

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

2). Исходная упорядоченность входного множества: во входном множестве (даже если оно сгенерировано датчиком случайных величин) могут попадаться упорядоченные участки. В предельном случае входное множество может оказаться уже упорядоченным. Одни алгоритмы не учитывают исходной упорядоченности и требуют одного и того же времени для сортировки любого (в том числе и уже упорядоченного) множества данного объема, другие выполняются тем быстрее, чем лучше упорядоченность на входе.

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

4). Сложность алгоритма является не последним соображением при его выборе. Простой алгоритм требует меньшего времени для его реализации и вероятность ошибки в реализации его меньше. При промышленном изготовлении программного продукта требования соблюдения сроков разработки и надежности продукта могут даже превалировать над требованиями эффективности функционирования.

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

1). Стратегия выборки. Из входного множества выбирается следующий по критерию упорядоченности элемент и включается в выходное множество на место, следующее по номеру.

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

3). Стратегия распределения. Входное множество разбивается на ряд подмножеств (возможно, меньшего объема) и сортировка ведется внутри каждого такого подмножества.

4). Стратегия слияния. Выходное множество получается путем слияния маленьких упорядоченных подмножеств.

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

Сортировки выборкой

Сортировка простой выборкой.

Алгоритм сортировки простой выборкой иллюстрируется программным примером 3.7. В программной реализации алгоритма возникает проблема значения ключа… {===== Программный пример 3.7 =====}

Обменная сортировка простой выборкой.

Обменная сортировка простой выборкой показана в программном примере 3.8. Процедура имеет только один параметр - сортируемый массив. {===== Программный пример 3.8 =====} Procedure Sort(var a : SEQ);

Таблица 3.5

Очевидно, что обменный вариант обеспечивает экономию памяти. Очевидно также, что здесь не возникает проблемы "пустого" значения. Общее число сравнений уменьшается вдвое - N*(N-1)/2, но порядок алгоритма остается степенным - O(n^2). Количество перестановок N-1, но перестановка, по-видимому, вдвое более времяемкая операция, чем пересылка в предыдущем алгоритме.

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

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

Пузырьковая сортировка.

Порядок пузырьковой сортировки - O(N^2). Среднее число сравнений - N*(N-1)/2 и таково же среднее число перестановок, что значительно хуже, чем для… Еще одно достоинство пузырьковой сортировки заключается в том, что при… Во-первых, можно ввести некоторую логическую переменную, которая будет сбрасываться в false перед началом каждого…

Таблица 3.6

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

Сортировка Шелла.

Пример 3.10 иллюстрирует сортировку Шелла. {===== Программный пример 3.10 =====} Procedure Sort( var a : seq);

Таблица 3.7

 

Сортировки включением

Сортировка простыми вставками.

Алгоритм сортировки простыми вставками иллюстрируется программным примером 3.11. {===== Программный пример 3.11 =====} Procedure Sort(a : Seq; var b : Seq);

Пузырьковая сортировка вставками.

{===== Программный пример 3.12 =====} Procedure Sort (var a : Seq); Var i, j, k, t : integer;

Таблица 3.8

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

Еще одна группа включающих алгоритмов сортировки использует структуру дерева. Мы рекомендуем читателю повторно вернуться к рассмотрению этих алгоритмов после ознакомления с главой 6.

Сортировка упорядоченным двоичным деревом.

Турнирная сортировка.

Например, для последовательности чисел a: 16 21 8 14 26 94 30 1 такое дерево будет иметь вид пирамиды, показанной на рис.3.13.

Рис.3.13. Пирамида турнирной сортировки

В примере 3.12 приведена программная иллюстрация алгоритма турнирной сортировки. Она нуждается в некоторых пояснениях. Построение пирамиды выполняется функцией Create_Heap. Пирамида строится от основания к вершине. Элементы, составляющие каждый уровень, связываются в линейный список, поэтому каждый узел дерева помимо обычных указателей на потомков - left и right - содержит и указатель на "брата" - next. При работе с каждым уровнем указатель содержит начальный адрес списка элементов в данном уровне. В первой фазе строится линейный список для нижнего уровня пирамиды, в элементы которого заносятся ключи из исходной последовательности. Следующий цикл while в каждой своей итерации надстраивает следующий уровень пирамиды. Условием завершения этого цикла является получение списка, состоящего из единственного элемента, то есть, вершины пирамиды. Построение очередного уровня состоит в попарном переборе элементов списка, составляющего предыдущий (нижний) уровень. В новый уровень переносится наименьшее значение ключа из каждой пары.

Следующий этап состоит в выборке значений из пирамиды и формирования из них упорядоченной последовательности (процедура Heap_Sort и функция Competit). В каждой итерации цикла процедуры Heap_Sort выбирается значение из вершины пирамиды - это наименьшее из имеющихся в пирамиде значений ключа. Узел-вершина при этом освобождается, освобождаются также и все узлы, занимаемые выбранным значением на более низких уровнях пирамиды. За освободившиеся узлы устраивается (снизу вверх) состязание между их потомками. Так, для пирамиды, исходное состояние которой было показано на рис 3. , при выборке первых трех ключей (1, 8, 14) пирамида будет последовательно принимать вид, показанный на рис.3.14 (символом x помечены пустые места в пирамиде).

Рис.3.14. Пирамида после последовательных выборок

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

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

{===== Программный пример 3.12 =====}

{ Турнирная сортировка }

type nptr = ^node; { указатель на узел }

node = record { узел дерева }

key : integer; { данные }

left, right : nptr; { указатели на потомков }

next : nptr; { указатель на "брата" }

end;

{ Создание дерева - функция возвращает указатель на вершину

созданного дерева }

Function Heap_Create(a : Seq) : nptr;

var i : integer;

ph2 : nptr; { адрес начала списка уровня }

p1 : nptr; { адрес нового элемента }

p2 : nptr; { адрес предыдущего элемента }

pp1, pp2 : nptr; { адреса соревнующейся пары }

begin

{ Фаза 1 - построение самого нижнего уровня пирамиды }

ph2:=nil;

for i:=1 to n do begin

New(p1); { выделение памяти для нового эл-та }

p1^.key:=a[i]; { запись данных из массива }

p1^.left:=nil; p1^.right:=nil; { потомков нет }

{ связывание в линейный список по уровню }

if ph2=nil then ph2:=p1 else p2^.next:=p1;

p2:=p1;

end; { for }

p1^.next:=nil;

{ Фаза 2 - построение других уровней }

while ph2^.next<>nil do begin { цикл до вершины пирамиды }

pp1:=ph2; ph2:=nil; { начало нового уровня }

while pp1<>nil do begin { цикл по очередному уровню }

pp2:=pp1^.next;

New(p1);

{ адреса потомков из предыдущего уровня }

p1^.left:=pp1; p1^.right:=pp2;

p1^.next:=nil;

{ связывание в линейный список по уровню }

if ph2=nil then ph2:=p1 else p2^.next:=p1;

p2:=p1;

{ состязание данных за выход на уровень }

if (pp2=nil)or(pp2^.key > pp1^.key) then p1^.key:=pp1^.key

else p1^.key:=pp2^.key;

{ переход к следующей паре }

if pp2<>nil then pp1:=pp2^.next else pp1:=nil;

end; { while pp1<>nil }

end; { while ph2^.next<>nil }

Heap_Create:=ph2;

end;

{ Реорганизация поддерева - функция возвращает

указатель на вершину реорганизованного дерева }

Function Competit(ph : nptr) : nptr;

begin

{ определение наличия потомков, выбор потомка для

реорганизации, реорганизация его }

if (ph^.left<>nil)and(ph^.left^.key=ph^.key) then

ph^.left:=Competit(ph^.left)

else if (ph^.right<>nil) then

ph^.right:=Competit(ph^.right);

if (ph^.left=nil)and(ph^.right=nil) then begin

{ освобождение пустого узла }

Dispose(ph); ph:=nil;

end;

else

{ состязание данных потомков }

if (ph^.left=nil) or

((ph^.right<>nil)and(ph^.left^.key > ph^.right^.key)) then

ph^.key:=ph^.right^.key

else ph^.key:=ph^.left^.key;

Competit:=ph;

end;

{ Сортировка }

Procedure Heap_Sort(var a : Seq);

var ph : nptr; { адрес вершины дерева }

i : integer;

begin

ph:=Heap_Create(a); { создание дерева }

{ выборка из дерева }

for i:=1 to N do begin

{ перенос данных из вершины в массив }

a[i]:=ph^.key;

{ реорганизация дерева }

ph:=Competit(ph);

end;

end;

Построение дерева требует N-1 сравнений, выборка - N*log2(N) сравнений. Порядок алгоритма, таким образом, O(N*log2(N)). Сложность операций над связными структурами данных, однако, значительно выше, чем над статическими структурами. Кроме того, алгоритм неэкономичен в отношении памяти: дублирование данных на разных уровнях пирамиды приводит к тому, что рабочая область памяти содержит примерно 2*N узлов.

Сортировка частично упорядоченным деревом.

Например, последовательность чисел: 3 20 12 58 35 30 32 28 будет представлена в виде дерева, показанного на рис.3.15 .

Рис.3.15. Частично упорядоченное дерево

Представление дерева в виде пирамиды наглядно показывает нам, что для такого дерева можно ввести понятия "начала" и "конца". Началом, естественно, будет считаться вершина пирамиды, а концом - крайний левый элемент в самом нижнем ряду (на рис.3.15 это 58).

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

Алгоритм вставки состоит в следующем. Новый элемент вставляется на первое свободное место за концом дерева (на рис.3.15 это место обозначено символом "*"). Если ключ вставленного элемента меньше, чем ключ его предка, то предок и вставленный элемент меняются местами. Ключ вставленного элемента теперь сравнивается с ключом его предка на новом месте и т.д. Сравнения заканчиваются, когда ключ нового элемента окажется больше ключа предка или когда новый элемент "выплывет" в вершину пирамиды. Пирамида, показанная на рис.3.15, построена именно последовательным включением в нее чисел из приведенного ряда. Если мы включим в нее, например, еще число 16, то пирамида примет вид, представленный на рис.3.16. (Символом "*" помечены элементы, перемещенные при этой операции.)

Рис.3.16. Частично упорядоченное дерево, включение элемента

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

Рис.3.17. Частично упорядоченное дерево, исключение элемента

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

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

12 16 28 20 35 30 32 58

В таком представлении отпадает необходимость хранить в составе узла дерева указатели, так как адреса потомков могут быть вычислены. Для узла, представленного элементом массива с индексом i индексы его левого и правого потомков будут 2*i и 2*i+1 соответственно. Для узла с индексом i индекс его предка будет i div 2.

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

· процедура InitST - инициализация модуля, установка начального значения nt;

· функция InsertST - вставка в дерево нового элемента; функция возвращает false, если в дереве нет свободного места, иначе - true;

· функция DeleteST - выборка из дерева минимального элемента; функция возвращает false, если дерево пустое, иначе - true;

· функция CheckST - проверка состояния дерева: ключ минимального элемента возвращается в выходном параметре, но элемент не исключается из дерева; а возвращаемое значение функции - 0 - если дерево пустое, 1 - если дерево заполнено не до конца, 2 - если дерево заполнено до конца.

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

· функция Down - обеспечивает спуск свободного места из вершины пирамиды в ее основание, функция возвращает индекс свободного места после спуска;

· процедура Up - обеспечивающая всплытие элемента с заданного места.

{===== Программный пример 3.13 =====}

{ Сортировка частично упорядоченным деревом }

Unit SortTree;

Interface

Procedure InitSt;

Function CheckST(var a : integer) : integer;

Function DeleteST(var a : integer) : boolean;

Function InsertST(a : integer) : boolean;

Implementation

Const NN=16;

var tr : array[1..NN] of integer; { дерево }

nt : integer; { индекс последнего эл-та в дереве }

{** Всплытие эл-та с места с индексом l **}

Procedure Up(l : integer);

var h : integer; { l - индекс узла, h - индекс его предка }

x : integer;

begin

h:=l div 2; { индекс предка }

while h > 0 do { до начала дерева }

if tr[l] < tr[h] then begin { ключ узла меньше, чем у предка }

x:=tr[l]; tr[l]:=tr[h]; tr[h]:=x; { перестановка }

l:=h; h:=l div 2; { предок становится текущим узлом }

end

else h:=0; { конец всплытия }

end; { Procedure Up }

{** Спуск свободного места из начала дерева **}

Function Down : integer;

var h, l : integer; { h - индекс узла, l - индекс его потомка }

begin

h:=1; { начальный узел - начало дерева }

while true do begin

l:=h*2; { вычисление индекса 1-го потомка }

if l+1 <= nt then begin { у узла есть 2-й потомок }

if tr[l] <= tr[l+1] then begin { 1-й потомок меньше 2-го }

tr[h]:=tr[l]; { 1-й потомок переносится в текущ.узел }

h:=l; { 1-й потомок становится текущим узлом }

end

else begin { 2-й потомок меньше 1-го }

tr[h]:=tr[l+1]; { 2-й потомок переносится в текущ.узел }

h:=l+1; { 2-й потомок становится текущим узлом }

end;

end

else

if l=nt then begin { 1-й потомок есть, 2-го нет }

tr[h]:=tr[l]; { 1-й потомок переносится в текущ.узел }

Down:=l; Exit; { спуск закончен }

end

else begin { потомков нет - спуск закончен }

Down:=h; Exit;

end;

end; { while }

end; { Function Down }

{** Инициализация сортировки деревом **}

Procedure InitSt;

begin

nt:=0; { дерево пустое }

end; { Procedure InitSt }

{** Проверка состояния дерева **}

Function CheckST(var a : integer) : integer;

begin

a:=tr[1]; { выборка эл-та из начала }

case nt of { формирование возвращаемого значения функции }

0: { дерево пустое } CheckSt:=0;

NN: { дерево полное } CheckSt:=2;

else { дерево частично заполнено } CheckSt:=1;

end;

end; { Function CheckST }

{** Вставка эл-та a в дерево **}

Function InsertST(a : integer) : boolean;

begin

if nt=NN then { дерево заполнено - отказ } InsertST:=false

else begin { в дереве есть место }

nt:=nt+1; tr[nt]:=a; { запись в конец дерева }

Up(nt); { всплытие }

InsertSt:=true;

end;

end; { Function InsertST }

{** Выборка эл-та из дерева **}

Function DeleteST(var a : integer) : boolean;

var n : integer;

begin

if nt=0 then { дерево пустое - отказ } DeleteST:=false

else begin { дерево не пустое }

a:=tr[1]; { выборка эл-та из начала }

n:=Down; { спуск свободного места в позицию n }

if n < nt then begin

{ если свободное место спустилось не в конец дерева }

tr[n]:=tr[nt]; { эл-т из конца переносится на своб.место }

Up(n); { всплытие }

end;

nt:=nt-1;

DeleteSt:=true;

end;

end; { Function DeleteST }

END.

Если применять сортировку частично упорядоченным деревом для упорядочения уже готовой последовательности размером N, то необходимо N раз выполнить вставку, а затем N раз - выборку. Порядок алгоритма - O(N*log2(N)), но среднее значение количества сравнений примерно в 3 раза больше, чем для турнирной сортировки. Но сортировка частично упорядоченным деревом имеет одно существенное преимущество перед всеми другими алгоритмами. Дело в том, что это самый удобный алгоритм для "сортировки on-line", когда сортируемая последовательность не зафиксирована до начала сортировки, а меняется в процессе работы и вставки чередуются с выборками. Каждое изменение (добавление/удаление элемента) сортируемой последовательности потребует здесь не более, чем 2*log2(N) сравнений и перестановок, в то время, как другие алгоритмы потребуют при единичном изменении переупорядочивания всей последовательности "по полной программе".

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

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

{===== Программный пример 3.14 =====}

{ Формирование отсортированных последовательностей в файле }

Uses SortTree;

var x : integar; { считанное число }

y : integer; { число в вершине дерева }

old : integer; { последнее выведенное число }

inp : text; { входной файл }

out : text; { выходной файл }

bf : boolean; { признак начала вывода последовательности }

bx : boolean; { рабочая переменная }

begin

Assign(inp,'STX.INP'); Reset(inp);

Assign(out,'STX.OUT'); Rewrite(out);

InitST; { инициализация сортировки }

bf:=false; { вывод последовательности еще не начат }

while not Eof(inp) do begin

ReadLn(inp,x); { считывание числа из файла }

{ если в дереве есть свободное место - включить в дерево }

if CheckST(y) <= 1 then bx:=InsertST(x)

else { в дереве нет свободного места }

if (bf and (x < old)) or (not bf and (x < y)) then begin

{ вывод содержимого дерева }

while DeleteST(y) do Write(out,y:3,' ');

WriteLn(out);

bf:=false; { начало новой последовательности }

bx:=InsertST(x); { занесение считанного числа в дерево }

end

else begin { продолжение формирования последовательности }

if x < y then begin { вывод считанного числа }

Write(out,x:3,' '); old:=x;

end;

else begin { вывод числа из вершины дерева }

bx:=DeleteST(y);

Write(out,y:3,' '); old:=y;

{ занесение считанного в дерево }

bx:=InsertST(x);

end;

bf:=true; { вывод последовательности начался }

end;

end;

Close(inp);

{ вывод остатка }

while DeleteST(y) do Write(out,y:3,' ');

WriteLn(out); Close(out);

end.

 

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

Поразрядная цифровая сортировка.

Порядок алгоритма качественно линейный - O(N), для сортировки требуется D*N операций анализа цифры. Однако, в такой оценке порядка не учитывается… Во-первых, операция выделения значащей цифры будет простой и быстрой только… Во-вторых, в оценке алгоритма не учитываются расходы времени и памяти на создание и ведение групп. Размещение групп в…

Таблица 3.9

Быстрая сортировка Хоара.

Используются два индекса - i и j - с начальными значениями 1 и N соответственно. Ключ K[i] сравнивается с ключом K[j]. Если ключи удовлетворяют… Процедура сортировки в примере 3.16 рекурсивная. При ее вызове должны быть…  

Таблица 3.10

Сортировки слиянием.

Алгоритмы сортировки слиянием, как правило, имеют порядок O(N*log2(N)), но отличаются от других алгоритмов большей сложностью и требуют большого числа пересылок. Алгоритмы слияния применяются в основном, как составная часть внеш- ней сортировки, которая более подробно будет рассматриваться нами во втором томе нашего пособия. Здесь же для понимания принципа слияния мы приводим простейший алгоритм слияния в оперативной памяти.

 

Сортировка попарным слиянием.

Важнейшей частью алгоритма является слияние двух упорядоченных множеств. Эту часть алгоритма мы опишем строго. · 1. [Начальные установки]. Определить длины первого и второго исходных… · 2. [Цикл слияния]. Выполнять шаг 3 до тех пор, пока i1<=l1 и i2<=l2.

Таблица 3.11

Полустатические структуры данных

Характерные особенности полустатических структур

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

Стеки

Логическая структура стека

Основные операции над стеком - включение нового элемента (английское название push - заталкивать) и исключение элемента из стека (англ. pop -… Полезными могут быть также вспомогательные операции: · определение текущего числа элементов в стеке;

Рис 4.1. Включение и исключение элементов из стека.

Как видно из рис. 4.1, стек можно представить, например, в виде стопки книг (элементов), лежащей на столе. Присвоим каждой книге свое название, например A,B,C,D... Тогда в момент времени, когда на столе книг нет, про стек аналогично можно сказать, что он пуст, т.е. не содержит ни одного элемента. Если же мы начнем последовательно класть книги одну на другую, то получим стопку книг (допустим, из n книг), или получим стек, в котором содержится n элементов, причем вершиной его будет являться элемент n+1. Удаление элементов из стека осуществляется аналогичным образом т. е. удаляется последовательно по одному элементу, начиная с вершины, или по одной книге из стопки.

Машинное представление стека и реализация операций

При занесении элемента в стек элемент записывается на место, определяемое указателем стека, затем указатель модифицируется таким образом, чтобы он… Операция исключения элемента состоит в модификации указателя стека (в… Операция очистки стека сводится к записи в указатель стека начального значения - адреса начала выделенной области…

Стеки в вычислительных системах

Предположим, имеется процедура A, которая вызывает процедуру B, а та в свою очередь - процедуру C. Когда выполнение процедуры A дойдет до вызова B,… В микропроцессорах семейства Intel, как и в большинстве современных… Системы программирования для блочно-ориентированных языков (PASCAL, C и др.) используют стек для размещения в нем…

Очереди FIFO

Логическая структура очереди

Основные операции над очередью - те же, что и над стеком - включение, исключение, определение размера, очистка, неразрушающее чтение.

Машинное представление очереди FIFO и реализация операций

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

Очереди с приоритетами

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

Очереди в вычислительных системах

Очередь является одним из ключевых понятий в многозадачных операционных системах (Windows NT, Unix, OS/2, ЕС и др.). Ресурсы вычислительной системы… Также в современных операционных системах одним из средств взаимодействия…

Деки

Логическая структура дека

Операции над деком: · включение элемента справа; · включение элемента слева;

Рис. 4.2. Состояния дека в процессе изменения.

На рис. 4.2 в качестве примера показана последовательность состояний дека при включении и удалении пяти элементов. На каждом этапе стрелка указывает с какого конца дека (левого или правого) осуществляется включение или исключение элемента. Элементы соответственно обозначены буквами A, B, C, D, E.

Физическая структура дека в статической памяти идентична структуре кольцевой очереди. Разработать программный пример, иллюстрирующий организацию дека и операции над ним не сложно по образцу примеров 4.1, 4.3. В этом модуле должны быть реализованы процедуры и функции:

Function DeqWrRight(a: data): boolean; - включение элемента справа;

Function DeqWrLeft(a: data): boolean; - включение элемента слева;

Function DeqRdRight(var a: data): boolean; - исключение элемента справа;

Function DeqRdLeft(var a: data) : boolean; - исключение элемента слева;

Procedure DeqClr; - очистка;

Function DeqSize : integer; - определение размера.

 

Деки в вычислительных системах

Однако, в качестве примера такой системной поддержки рассмотрим организацию буфера ввода в языке REXX. В обычном режиме буфер ввода связан с…

Строки

Логическая структура строки

Строки обладают следующими важными свойствами: · их длина, как правило, переменна, хотя алфавит фиксирован; · обычно обращение к символам строки идет с какого-нибудь одного конца последовательности, т.е важна упорядоченность…

Операции над строками

Базовыми операциями над строками являются:

· определение длины строки;

· присваивание строк;

· конкатенация (сцепление) строк;

· выделение подстроки;

· поиск вхождения.

Операция определения длины строки имеет вид функции, возвращаемое значение которой - целое число - текущее число символов в строке. Операция присваивания имеет тот же смысл, что и для других типов данных.

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

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

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

· завершать программу аварийно с локализацией и диагностикой ошибки;

· ограничивать длину результата в соответствии с объемом отведенной памяти;

Операция выделения подстроки выделяет из исходной строки последовательность символов, начиная с заданной позиции n, с заданной длиной l. В языке PASCAL соответствующая функция называется COPY. В языках PL/1, REXX соответствующая функция - SUBSTR - обладает интересным свойством, отсутствующим в PASCAL. Функция SUBSTR может употребляться в левой части оператора присваивания. Например, если исходное значение некоторой строки S - 'ABCDEFG', то выполнение оператора: SUBSTR(S,3,3)='012'; изменит значение строки S на - 'AB012FG'.

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

· аварийное завершение программы с диагностикой ошибки;

· формирование результата меньшей длины, чем задано, возможно даже - пустой строки.

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

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

· выделение из исходной строки подстроки, начиная с позиции 1, длиной n1-1;

· выделение из исходной строки подстроки, начиная с позиции n2+1, длиной длина исходной строки - n2;

· сцепление подстрок, полученных на предыдущих шагах.

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

 

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

ВЕКТОРНОЕ ПРЕДСТАВЛЕНИЕ СТРОК.

Самым простым способом является представление строки в виде вектора постоянной длинны. При этом в памяти отводится фиксированное количество байт, в… На рис.4.3 приведена схема, на которой показано представление двух строк:…

Рис. 4.3. Представление строк векторами постоянной длины

ПРЕДСТАВЛЕНИЕ СТРОК ВЕКТОРОМ ПЕРЕМЕННОЙ ДЛИНЫ С ПРИЗНАКОМ КОНЦА.

Рис. 4.4. Представление строк переменной длины с признаком конца

ПРЕДСТАВЛЕНИЕ СТРОК ВЕКТОРОМ ПЕРЕМЕННОЙ ДЛИНЫ СО СЧЕТЧИКОМ.

Рис.4.5. Представление строк переменной длины со счетчиком

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

ВЕКТОР С УПРАВЛЯЕМОЙ ДЛИНОЙ.

Хотя такое представление строк не обеспечивает экономии памяти, проектировщики систем программирования, как видно, считают это приемлемой платой за…

Рис.4.6. Представление строк вектором с управляемой длиной

В программном примере 4.4 приведен модуль, реализующий представление строк вектором с управляемой длиной и некоторые операции над такими строками. Для уменьшения объема в примере в секции Implementation определены не все процедуры/функции. Предоставляем читателю самостоятельно разработать прочие объявленные в секции Interface подпрограммы. Дескриптор строки описывается типом _strdescr, который в точности повторяет структуру, показанную на рис.4.6. Функция NewStr выделяет две области памяти: для дескриптора строки и для области данных строки. Адрес дескриптора строки, возвращаемый функцией NewStr - тип varstr - является той переменной, значение которой указывается пользователем модуля для идентификации конкретной строки при всех последующих операциях с нею. Область данных, указатель на которую заносится в дескрипторе строки - тип _dat_area - описана как массив символов максимального возможного объема - 64 Кбайт. Однако, объем памяти, выделяемый под область данных функцией NewStr, как правило, меньший - он задается параметром функции. Хотя индексы в массиве символов строки теоретически могут изменяться от 1 до 65535, значение индекса в каждой конкретной строке при ее обработке ограничивается полем maxlen дескриптора данной строки. Все процедуры/функции обработки строк работают с символами строки как с элементами вектора, обращаясь к ним по индексу. Адрес вектора процедуры получают из дескриптора строки. Обратите внимание на то, что в процедуре CopyStr длина результата ограничивается максимальной длиной целевой строки.

{==== Программный пример 4.4 ====}

{ Представление строк вектором с управляемой длиной }

Unit Vstr;

Interface

type _dat_area = array[1..65535] of char;

type _strdescr = record { дескриптор строки }

maxlen, curlen : word; { максимальная и текущая длины }

strdata : ^_dat_area; { указатель на данные строки }

end;

type varstr = ^_strdescr; { тип - СТРОКА ПЕРЕМЕННОЙ ДЛИНЫ }

Function NewStr(len : word) : varstr;

Procedure DispStr(s : varstr);

Function LenStr(s : varstr) : word;

Procedure CopyStr(s1, s2 : varstr);

Function CompStr(s1, s2 : varstr) : integer;

Function PosStr(s1, s2 : varstr) : word;

Procedure ConcatStr(var s1: varstr; s2 : varstr);

Procedure SubStr(var s1 : varstr; n, l : word);

Implementation

{** Создание строки; len - максимальная длина строки;

ф-ция возвращает указатель на дескриптор строки }

Function NewStr(len : word) : varstr;

var addr : varstr;

daddr : pointer;

begin

New(addr); { выделение памяти для дескриптора }

Getmem(daddr,len); { выделение памяти для данных }

{ занесение в дескриптор начальных значений }

addr^.strdata:=daddr; addr^.maxlen:=len; addr^.curlen:=0;

Newstr:=addr;

end; { Function NewStr }

Procedure DispStr(s : varstr); {** Уничтожение строки }

begin

FreeMem(s^.strdata,s^.maxlen); { уничтожение данных }

Dispose(s); { уничтожение дескриптора }

end; { Procedure DispStr }

{** Определение длины строки, длина выбирается из дескриптора }

Function LenStr(s : varstr) : word;

begin

LenStr:=s^.curlen;

end; { Function LenStr }

Procedure CopyStr(s1, s2 : varstr); { Присваивание строк s1:=s2}

var i, len : word;

begin

{ длина строки-результата м.б. ограничена ее макс. длиной }

if s1^.maxlen s2; -1 - если s1 < s2 }

Function CompStr(s1, s2 : varstr) : integer;

var i : integer;

begin i:=1; { индекс текущего символа }

{ цикл, пока не будет достигнут конец одной из строк }

while (i <= s1^.curlen) and (i <= s2^.curlen) do

{ если i-ые символы не равны, функция заканчивается }

begin if s1^.strdata^[i] > s2^.strdata^[i] then

begin CompStr:=1; Exit; end;

if s1^.strdata^[i] < s2^.strdata^[i] then

begin CompStr:=-1; Exit; end;

i:=i+1; { переход к следующему символу }

end;

{ если выполнение дошло до этой точки, то найден конец одной из строк, и все сравненные до сих пор символы были равны; строка меньшей длины считается меньшей }

if s1^.curlens2^.curlen then CompStr:=1

else CompStr:=0;

end; { Function CompStr }

.

.

END.

СИМВОЛЬНО - СВЯЗНОЕ ПРЕДСТАВЛЕНИЕ СТРОК.

ОДНОНАПРАВЛЕННЫЙ ЛИНЕЙНЫЙ СПИСОК.

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

Рис.4.7. Представление строки однонаправленным связным списком

ДВУНАПРАВЛЕННЫЙ ЛИНЕЙНЫЙ СПИСОК.

В каждый элемент списка добавляется также указатель на предыдущий элемент, как показано на рис.4.8. Двустороннее сцепление допускает двустороннее движение вдоль списка, что может значительно повысить эффективность выполнения некоторых строковых операция. При этом на каждый символ строки необходимо два указателя , т.е. 4-8 байт.

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

БЛОЧНО - СВЯЗНОЕ ПРЕДСТАВЛЕНИЕ СТРОК.

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

МНОГОСИМВОЛЬНЫЕ ЗВЕНЬЯ ФИКСИРОВАННОЙ ДЛИНЫ.

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

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

 

МНОГОСИМВОЛЬНЫЕ ЗВЕНЬЯ ПЕРЕМЕННОЙ ДЛИНЫ.

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

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

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

МНОГОСИМВОЛЬНЫЕ ЗВЕНЬЯ С УПРАВЛЯЕМОЙ ДЛИНОЙ.

Пример представления строки в виде звеньев с управляемой длиной 8 показан на рис.4.11.

Рис.4.11. Представление строки звеньями управляемой длины

В программном примере 4.5 приведен модуль, реализующий представление строк звеньями с управляемой длиной. Даже с первого взгляда видно, что он значительно сложнее, чем пример 4.4. Это объясняется тем, что здесь вынуждены обрабатывать как связные (списки блоков), так и векторные (массив символов в каждом блоке) структуры. Поэтому при последовательной обработке символов строки процедура должна сохранять как адрес текущего блока, так и номер текущего символа в блоке. Для этих целей во всех процедурах/функциях используются переменные cp и bi соответственно. (Процедуры и функции, обрабатывающие две строки - cp1, bi1, cp2, bi2.) Дескриптор строки - тип _strdescr - и блок - тип _block - в точности повторяют структуру, показанную на рис.4.10. Функция NewStr выделяет память только для дескриптора строки и возвращает адрес дескриптора - тип varstr - он служит идентификатором строки при последующих операциях с нею. Память для хранения данных строки выделяется только по мере необходимости. Во всех процедурах/функциях приняты такие правила работы с памятью:

· если выходной строке уже выделены блоки, используются эти уже выделенные блоки;

· если блоки, выделенные выходной строке исчерпаны, выделяются новые блоки - по мере необходимости;

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

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

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

{==== Программный пример 4.5 ====}

{ Представление строки звеньями управляемой длины }

Unit Vstr;

Interface

const BLKSIZE = 8; { число символов в блоке }

type _bptr = ^_block; { указатель на блок }

_block = record { блок }

i1, i2 : byte; { номера 1-го и последнего символов }

strdata : array [1..BLKSIZE] of char; { символы }

next : _bptr; { указатель на следующий блок }

end;

type _strdescr = record { дескриптор строки }

len : longint; { длина строки }

first, last : _bptr; { указ.на 1-й и последний блоки }

end;

type varstr = ^_strdescr; { тип - СТРОКА ПЕРЕМЕННОЙ ДЛИНЫ }

Function NewStr : varstr;

Procedure DispStr(s : varstr);

Function LenStr(s : varstr) : longint;

Procedure CopyStr(s1, s2 : varstr);

Function CompStr(s1, s2 : varstr) : integer;

Function PosStr(s1, s2 : varstr) : word;

Procedure ConcatStr(var s1: varstr; s2 : varstr);

Procedure SubStr(var s : varstr; n, l : word);

Implementation

Function NewBlock :_bptr; {Внутр.функция-выделение нового блока}

var n : _bptr;

i : integer;

begin

New(n); { выделение памяти }

n^.next:=nil; n^.i1:=0; n^.i2:=0; { начальные значения }

NewBlock:=n;

end; { NewBlock }

{*** Внутр.функция - освобождение цепочки блока, начиная с c }

Function FreeBlock(c : _bptr) : _bptr;

var x : _bptr;

begin { движение по цепочке с освобождением памяти }

while c<>nil do begin x:=c; c:=c^.next; Dispose(x); end;

FreeBlock:=nil; { всегда возвращает nil }

end; { FreeBlock }

Function NewStr : varstr; {** Создание строки }

var addr : varstr;

begin

New(addr); { выделение памяти для дескриптора }

{ занесение в дескриптор начальных значений }

addr^.len:=0; addr^.first:=nil; addr^.last:=nil;

Newstr:=addr;

end; { Function NewStr }

Procedure DispStr(s : varstr); {** Уничтожение строки }

begin

s^.first:=FreeBlock(s^.first); { уничтожение блоков }

Dispose(s); { уничтожение дескриптора }

end; { Procedure DispStr }

{** Определение длины строки, длина выбирается из дескриптора }

Function LenStr(s : varstr) : longint;

begin

LenStr:=s^.len;

end; { Function LenStr }

{** Присваивание строк s1:=s2 }

Procedure CopyStr(s1, s2 : varstr);

var bi1, bi2 : word; { индексы символов в блоках для s1 и s2 }

cp1, cp2 : _bptr; { адреса текущих блоков для s1 и s2 }

pp : _bptr; { адрес предыдущего блока для s1 }

begin

cp1:=s1^.first; pp:=nil; cp2:=s2^.first;

if s2^.len=0 then begin

{ если s2 пустая, освобождается вся s1 }

s1^.first:=FreeBlock(s1^.first); s1^.last:=nil;

end

else begin

while cp2<>nil do begin { перебор блоков s2 }

if cp1=nil then begin { если в s1 больше нет блоков }

{ выделяется новый блок для s1 }

cp1:=NewBlock;

if s1^.first=nil then s1^.first:=cp1

else if pp<>nil then pp^.next:=cp1;

end;

cp1^:=cp2^; { копирование блока }

{ к следующему блоку }

pp:=cp1; cp1:=cp1^.next; cp2:=cp2^.next;

end; { while }

s1^.last:=pp; { последний блок }

{ если в s1 остались лишние блоки - освободить их }

pp^.next:=FreeBlock(pp^.next);

end; { else }

s1^.len:=s2^.len;

end; { Procedure CopyStr }

{** Сравнение строк - возвращает:

0, если s1=s2; 1 - если s1 > s2; -1 - если s1 < s2 }

Function CompStr(s1, s2 : varstr) : integer;

var bi1, bi2 : word;

cp1, cp2 : _bptr;

begin

cp1:=s1^.first; cp2:=s2^.first;

bi1:=cp1^.i1; bi2:=cp2^.i1;

{ цикл, пока не будет достигнут конец одной из строк }

while (cp1<>nil) and (cp2<>nil) do begin

{ если соответств.символы не равны, ф-ция заканчивается }

if cp1^.strdata[bi1] > cp2^.strdata[bi2] then begin

CompStr:=1; Exit;

end;

if cp1^.strdata[bi1] < cp2^.strdata[bi2] then begin

CompStr:=-1; Exit;

end;

bi1:=bi1+1; { к следующему символу в s1 }

if bi1 > cp1^.i2 then begin cp1:=cp1^.next; bi1:=cp1^.i1; end;

bi2:=bi2+1; { к следующему символу в s2 }

if bi2 > cp2^.i2 then begin cp2:=cp2^.next; bi2:=cp2^.i1; end;

end;

{ мы дошли до конца одной из строк,

строка меньшей длины считается меньшей }

if s1^.len < s2^.len then CompStr:=-1

else if s1^.len > s2^.len then CompStr:=1

else CompStr:=0;

end; { Function CompStr }

.

.

END.

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

ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ

Связное представление данных в памяти

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

Связные линейные списки

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

Машинное представление связных линейных списков

На рис. 5.1 приведена структура односвязного списка. На нем поле INF - информационное поле, данные, NEXT - указатель на следующий элемент списка. Каждый список должен иметь особый элемент, называемый указателем начала списка или головой списка, который обычно по формату отличен от остальных элементов. В поле указателя последнего элемента списка находится специальный признак nil, свидетельствующий о конце списка.

Рис.5.1. Структура односвязного списка

Однако, обработка односвязного списка не всегда удобна, так как отсутствует возможность продвижения в противоположную сторону. Такую возможность обеспечивает двухсвязный список, каждый элемент которого содержит два указателя: на следующий и предыдущий элементы списка. Структура линейного двухсвязного списка приведена на рис. 5.2, где поле NEXT - указатель на следующий элемент, поле PREV - указатель на предыдущий элемент. В крайних элементах соответствующие указатели должны содержать nil, как и показано на рис. 5.2.

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

Рис.5.2. Структура двухсвязного списка

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

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

Рис.5.3. Структура кольцевого двухсвязного списка

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

 

Реализация операций над связными линейными списками

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

Перебор элементов списка.

Алгоритм перебора для односвязного списка представляется программным примером 5.1. {==== Программный пример 5.1 ====} { Перебор 1-связного списка }

Вставка элемента в список.

Вставка элемента в середину односвязного списка показана на рис.5.4 и в примере 5.2.

Рис.5.4. Вставка элемента в середину 1-связного списка

{==== Программный пример 5.2 ====}

{ Вставка элемента в середину 1-связного списка }

Procedure InsertSll(prev : sllptr; inf : data);

{ prev - адрес предыдущего эл-та; inf - данные нового эл-та }

var cur : sllptr; { адрес нового эл-та }

begin

{ выделение памяти для нового эл-та и запись в его инф.часть }

New(cur); cur^.inf:=inf;

cur^.next:=prev^.next; { эл-т, следовавший за предыдущим теперь

будет следовать за новым }

prev^.next:=cur; { новый эл-т следует за предыдущим }

end;

Рисунок 5.5 представляет вставку в двухсвязный список.

Рис.5.5. Вставка элемента в середину 2-связного списка

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

Рис.5.6. Вставка элемента в начало 1-связного списка

Программный пример 5.3 представляет процедуру, выполняющую вставку элемента в любое место односвязного списка.

{==== Программный пример 5.3 ====}

{ Вставка элемента в любое место 1-связного списка }

Procedure InsertSll

var head : sllptr; { указатель на начало списка, может измениться в

процедуре, если head=nil - список пустой }

prev : sllptr; { указатель на эл-т, после к-рого делается вставка,

если prev-nil - вставка перед 1-ым эл-том }

inf : data { - данные нового эл-та }

var cur : sllptr; { адрес нового эл-та }

begin

{ выделение памяти для нового эл-та и запись в его инф.часть }

New(cur); cur^.inf:=inf;

if prev <> nil then begin { если есть предыдущий эл-т - вставка в

середину списка, см. прим.5.2 }

cur^.next:=prev^.next; prev^.next:=cur;

end

else begin { вставка в начало списка }

cur^.next:=head; { новый эл-т указывает на бывший 1-й эл-т списка;

если head=nil, то новый эл-т будет и последним эл-том списка }

head:=cur; { новый эл-т становится 1-ым в списке, указатель на

начало теперь указывает на него }

end; end;

Удаление элемента из списка.

Удаление элемента из односвязного списка показано на рис.5.7.

Рис.5.7. Удаление элемента из 1-связного списка

Очевидно, что процедуру удаления легко выполнить, если известен адрес элемента, предшествующего удаляемому (prev на рис.5.7.а). Мы, однако, на рис. 5.7 и в примере 5.4 приводим процедуру для случая, когда удаляемый элемент задается своим адресом (del на рис.5.7). Процедура обеспечивает удаления как из середины, так и из начала списка.

{==== Программный пример 5.4 ====}

{ Удаление элемента из любого места 1-связного списка }

Procedure DeleteSll(

var head : sllptr; { указатель на начало списка, может

измениться в процедуре }

del : sllptr { указатель на эл-т, к-рый удаляется } );

var prev : sllptr; { адрес предыдущего эл-та }

begin

if head=nil then begin { попытка удаления из пустого списка

асценивается как ошибка (в последующих примерах этот случай

учитываться на будет) }

Writeln('Ошибка!'); Halt;

end;

if del=head then { если удаляемый эл-т - 1-й в списке, то

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

head:=del^.next

else begin { удаление из середины списка }

{ приходится искать эл-т, предшествующий удаляемому; поиск производится перебором списка с самого его начала, пока не будет найдет эл-т, поле next к-рого совпадает с адресом удаляемого элемента }

prev:=head^.next;

while (prev^.next<>del) and (prev^.next<>nil) do

prev:=prev^.next;

if prev^.next=nil then begin

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

Writeln('Ошибка!'); Halt;

end;

prev^.next:=del^.next; { предыдущий эл-т теперь указывает

на следующий за удаляемым }

end;

{ элемент исключен из списка, теперь можно освободить

занимаемую им память }

Dispose(del);

end;

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

Рис.5.8. Удаление элемента из 2-связного списка

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

Перестановка элементов списка.

Рис.5.9. Перестановка соседних элементов 1-связного списка

{==== Программный пример 5.5 ====}

{ Перестановка двух соседних элементов в 1-связном списке }

Procedure ExchangeSll(

prev : sllptr { указатель на эл-т, предшествующий

переставляемой паре } );

var p1, p2 : sllptr; { указатели на эл-ты пары }

begin

p1:=prev^.next; { указатель на 1-й эл-т пары }

p2:=p1^.next; { указатель на 2-й эл-т пары }

p1^.next:=p2^.next; { 1-й элемент пары теперь указывает на

следующий за парой }

p2^.next:=p1; { 1-й эл-т пары теперь следует за 2-ым }

prev^.next:=p2; { 2-й эл-т пары теперь становится 1-ым }

end;

В процедуре перестановки для двухсвязного списка (рис.5.10.) нетрудно учесть и перестановку в начале/конце списка.

Копирование части списка.

Рис.5.10. Перестановка соседних элементов 2-связного списка

Копирование для односвязного списка показано в программном примере 5.6.

{==== Программный пример 5.6 ====}

{ Копирование части 1-связного списка. head - указатель на

начало копируемой части; num - число эл-тов. Ф-ция возвращает

указатель на список-копию }

Function CopySll ( head : sllptr; num : integer) : sllptr;

var cur, head2, cur2, prev2 : sllptr;

begin

if head=nil then { исходный список пуст - копия пуста }

CopySll:=nil

else begin

cur:=head; prev2:=nil;

{ перебор исходного списка до конца или по счетчику num }

while (num>0) and (cur<>nil) do begin

{ выделение памяти для эл-та выходного списка и запись в него

информационной части }

New(cur2); cur2^.inf:=cur^.inf;

{ если 1-й эл-т выходного списка - запоминается указатель на

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

if prev2<>nil then prev2^.next:=cur2 else head2:=cur2;

prev2:=cur2; { текущий эл-т становится предыдущим }

cur:=cur^.next; { продвижение по исходному списку }

num:=num-1; { подсчет эл-тов }

end;

cur2^.next:=nil; { пустой указатель - в последний эл-т

выходного списка }

CopySll:=head2; { вернуть указатель на начало вых.списка }

end; end;

Слияние двух списков.

{==== Программный пример 5.7 ====} { Слияние двух списков. head1 и head2 - указатели на начала списков. На результирующий список указывает head1 }

Применение линейных списков

В программном примере 5.8 показана организация стека на односвязном линейном списке. Это пример функционально аналогичен примеру 4.1 с той… Стек представляется как линейный список, в котором включение элементов всегда… {==== Программный пример 5.8 ====}

Мультисписки

· участников ликвидации аварии; · переселенцев из зараженной зоны; · лиц, состоящих на квартирном учете;

Рис.5.11. Пример мультисписка

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

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

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

Нелинейные разветвленные списки

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

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

В обработке нелинейный список определяется как любая последовательность атомов и списков (подсписков), где в качестве атома берется любой объект, который при обработке отличается от списка тем, что он структурно неделим.

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

(a,(b,c,d),e,(f,g))

( )

((a))

Первый список содержит четыре элемента: атом a, список (b,c,d) (содержащий в свою очередь атомы b,c,d), атом e и список (f,g), элементами которого являются атомы f и g. Второй список не содержит элементов, тем не менее нулевой список, в соответствии с нашим определением является действительным списком. Третий список состоит из одного элемента: списка (a), который в свою очередь содержит атом а.

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

Рис.5.12. Схематическое представление разветвленного списка

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

Порядок. Над элементами списка задано транзитивное отношение, определяемое последовательностью, в которой элементы появляются внутри списка. В списке (x,y,z) атом x предшествует y, а y предшествует z. При этом подразумевается, что x предшествует z. Данный список не эквивалентен списку (y,z,x). При представлении списков графическими схемами порядок определяется горизонтальными стрелками. Горизонтальные стрелки истолковываются следующим образом: элемент из которого исходит стрелка,предшествует элементу, на который она указывает.

Глубина. Это максимальный уровень, приписываемый элементам внутри списка или внутри любого подсписка в списке. Уровень элемента предписывается вложенностью подсписков внутри списка, т.е.числом пар круглых скобок, окаймляющих элемент. В списке, изображенном на рис.5.12), элементы a и e находятся на уровне 1, в то время как оставшиеся элементы - b, c, d, f и g имеют уровень 2. Глубина входного списка равна 2. При представлении списков схемами концепции глубины и уровня облегчаются для понимания, если каждому атомарному или списковому узлу приписать некоторое число l. Значение l для элемента x, обозначаемое как l(x), является числом вертикальных стрелок, которое необходимо пройти для того, чтобы достичь данный элемент из первого элемента списка. На рис.5.12 l(a)=0, l(b)=1 и т.д. Глубина списка является максимальным значением уровня среди уровней всех атомов списка.

Длина - это число элементов уровня 1 в списке. Например, длина списка на рис.5.12 равна 3.

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

< операнд 1 > < знак операции > < операнд 2 >

Рис.5.13. Схема списка, представляющего алгебраическое выражение

Выражение:

(a+b)*(c-(d/e))+f

будет вычисляться в следующем порядке:

a+b

d/e

c-(d/e)

(a+b)*(c-d/e)

(a+b)*(c-d/e)+f

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

(((a,+,b),*,(c,-,(d,/,e)),+,f)

Глубина этого списка равна 4, длина - 3.

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

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

 

Рис.5.14. Структура элемента разветвленного списка

Элементы списка могут быть двух видов: атомы - содержащие данные и узлы - содержащие указатели на подсписки. В атомах не используется поле down элемента списка, а в узлах - поле data. Поэтому логичным является совмещение этих двух полей в одно, как показано на рис.5.15.

Рис.5.15. Структура элемента разветвленного списка

Поле type содержат признак атом/узел, оно может быть 1-битовым. Такой формат элемента удобен для списков, атомарная информация которых занимает небольшой объем памяти. В этом случае теряется незначительный объем памяти в элементах списка, для которых не требуется поля data. В более общем случае для атомарной информации необходим относительно большой объем памяти. Наиболее распространенный в данной ситуации формат структуры узла представленный на рис.5.16.

Рис. 5.16. Структура элемента разветвленного списка

В этом случае указатель down указывает на данные или на подсписок. Поскольку списки могут составляться из данных различных типов, целесообразно адресовать указателем down не непосредственно данные, а их дескриптор, в котором может быть описан тип данных, их длина и т.п. Само описание того, является ли адресуемый указателем данных объект атомом или узлом также может находиться в этом дескрипторе. Удобно сделать размер дескриптора данных таким же, как и элемента списка. В этом случае размер поля type может быть расширен, например, до 1 байта и это поле может индицировать не только атом/подсписок, но и тип атомарных данных, поле next в дескрипторе данных может использоваться для представления еще какой-то описательной информации, например, размера атома. На рис.5.17 показано представление элементами такого формата списка: (КОВАЛЬ,(12,7,53),d). Первая (верхняя) строка на рисунке представляет элементы списка, вторая - элементы подсписка, третья - дескрипторы данных, четвертая - сами данные. В поле type каждого элемента мы использовали коды: n - узел, S - атом, тип STRING, I - атом, тип INTEGER, C - атом, тип CHAR.

Рис.5.17. Пример представления списка элементами одного формата

Операции обработки списков

Базовыми операциями при обработке списков являются операции (функции): car, cdr, cons и atom.

Операция car в качестве аргумента получает список (указатель на начало списка). Ее возвращаемым значением является первый элемент этого списка (указатель на первый элемент). Например:

· если X - список (2,6,4,7), то car(X) - атом 2;

· если X - список ((1,2),6), то car(X) - список (1,2);

· если X - атом то car(X) не имеет смысла и в действительности не определено.

Операция cdr в качестве аргумента также получает список. Ее возвращаемым значением является остаток списка - указатель на список после удаления из него первого элемента. Например:

· если X - (2,6,4), то cdr(X) - (6,4);

· если X - ((1,2),6,5), то cdr(X) - (6,5);

· если список X содержит один элемент, то cdr(X) равно nil.

Операция cons имеет два аргумента: указатель на элемент списка и указатель на список. Операция включает аргумент-элемент в начало аргумента-списка и возвращает указатель на получившийся список. Например:

· если X - 2, а Y - (6,4,7), то cons(X,Y) - (2,6,4,7);

· если X - (1,2), Y - (6,4,7), то cons(X,Y) - ((1,2),6,4,7).

Операция atom выполняет проверку типа элемента списка. Она должна возвращать логическое значение: true - если ее аргумент является атомом или false - если ее аргумент является подсписком.

В программном примере 5.11 приведена реализация описанных операций как функций языка PASCAL. Структура элемента списка, обрабатываемого функциями этого модуля определена в нем как тип litem и полностью соответствует рис.5.16. Помимо описанных операций в модуле определены также функции выделения памяти для дескриптора данных - NewAtom и для элемента списка - NewNode. Реали- зация операций настолько проста, что не требует дополнительных пояснений.

{==== Программный пример 5.11 ====}

{ Элементарные операции для работы со списками }

Unit ListWork;

Interface

type lpt = ^litem; { указатель на элемент списка }

litem = record

typeflg : char; { Char(0) - узел, иначе - код типа }

down : pointer; { указатель на данные или на подсписок }

next: lpt; { указатель на текущем уровне }

end;

Function NewAtom(d: pointer; t : char) : lpt;

Function NewNode(d: lpt) : lpt;

Function Atom(l : lpt) : boolean;

Function Cdr(l : lpt) : lpt;

Function Car(l : lpt) : lpt;

Function Cons(l1, l : lpt) : lpt;

Function Append(l1,l : lpt) : lpt;

Implementation

{*** создание дескриптора для атома }

Function NewAtom(d: pointer; t : char) : lpt;

var l : lpt;

begin New(l);

l^.typeflg:=t; { тип данных атома }

l^.down:=d; { указатель на данные }

l^.next:=nil; NewAtom:=l;

end;

{*** создание элемента списка для подсписка }

Function NewNode(d: lpt) : lpt;

var l : lpt;

begin

New(l);

l^.typeflg:=Chr(0); { признак подсписка }

l^.down:=d; { указатель на начало подсписка }

l^.next:=nil;

NewNode:=l;

end;

{*** проверка элемента списка: true - атом, false - подсписок }

Function Atom(l : lpt) : boolean;

begin { проверка поля типа }

if l^.typeflg=Chr(0) then Atom:=false

else Atom:=true;

end;

Function Car(l : lpt) : lpt; {выборка 1-го элемента из списка }

begin Car:=l^.down; { выборка - указатель вниз } end;

Function Cdr(l : lpt) : lpt;{исключение 1-го элемента из списка}

begin Cdr:=l^.next; { выборка - указатель вправо } end;

{*** добавление элемента в начало списка }

Function Cons(l1,l : lpt) : lpt;

var l2 : lpt;

begin l2:=NewNode(l1); { элемент списка для добавляемого }

l2^.next:=l; { в начало списка }

Cons:=l2; { возвращается новое начало списка }

end;

{*** добавление элемента в конец списка }

Function Append(l1,l : lpt) : lpt;

var l2, l3 : lpt;

begin

l2:=NewNode(l1); { элемент списка для добавляемого }

{ если список пустой - он будет состоять из одного эл-та }

if l=nil then Append:=l2

else begin { выход на последний эл-т списка }

l3:=l; while l3^.next <> nil do l3:=l3^.next;

l3^.next:=l2; { подключение нового эл-та к последнему }

Append:=l; { функция возвращает тот же указатель }

end; end;

END.

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

{==== Программный пример 5.12 ====}

{ Вторичные функции обработки списков }

Unit ListW1;

Interface

uses listwork;

Function Append(x, l : lpt) : lpt;

Function ListRev(l, q : lpt) : lpt;

Function FlatList(l, q : lpt) : lpt;

Function InsList(x, l : lpt; m : integer) : lpt;

Function DelList(l : lpt; m : integer) : lpt;

Function ExchngList(l : lpt; m : integer) : lpt;

Implementation

{*** добавление в конец списка l нового элемента x }

Function Append(x, l : lpt) : lpt;

begin

{ если список пустой - добавить x в начало пустого списка }

if l=nil then Append:=cons(x,l)

{ если список непустой

- взять тот же список без 1-го эл-та - cdr(l);

- добавить в его конец эл-т x;

- добавить в начало 1-й эл-т списка }

else Append:=cons(car(l),Append(x,cdr(l)));

end; { Function Append }

{*** Реверс списка l; список q - результирующий, при первом

вызове он должен быть пустым }

Function ListRev(l, q : lpt) : lpt;

begin

{ если входной список исчерпан, вернуть выходной список }

if l=nil then ListRev:=q

{ иначе: - добавить 1-й эл-т вх.списка в начало вых.списка,

- реверсировать, имея вх. список без 1-го эл-та, а вых.список

- с добавленным эл-том }

else ListRev:=ListRev(cdr(l),cons(car(l),q));

end; { Function ListRev }

{*** Превращение разветвленного списка l в линейный; список q

- результирующий, при первом вызове он должен быть пустым }

Function FlatList(l, q : lpt) : lpt;

begin

{ если входной список исчерпан, вернуть выходной список }

if l=nil then FlatList:=q

else

{ если 1-й эл-т вх. списка - атом, то

- сделать "плоской" часть вх. списка без 1-го эл-та;

- добавить в ее начало 1-й эл-т }

if atom(car(l)) then

FlatList:=cons(car(l),FlatList(cdr(l),q))

{ если 1-й эл-т вх. списка - подсписок, то

- сделать "плоской" часть вх.списка без 1-го эл-та;

- сделать "плоским" подсписок 1-го эл-та }

else FlatList:=FlatList(car(l),FlatList(cdr(l),q));

end; { Function FlatList }

{*** вставка в список l элемента x на место с номером m

( здесь и далее нумерация эл-тов в списке начинается с 0 ) }

Function InsList(x, l : lpt; m : integer) : lpt;

begin

{ если m=0, эл-т вставляется в начало списка }

if m=0 then InsList:=cons(x,l)

{ если список пустой, он и остается пустым }

else if l=nil then InsList:=nil

{ - вставить эл-т x на место m-1 в список без 1-го эл-та;

- в начало полученного списка вставить 1-й эл-т }

else InsList:=cons(car(l),InsList(x,cdr(l),m-1));

end; { Function InsList }

{*** удаление из списка l на месте с номером m }

Function DelList(l : lpt; m : integer) : lpt;

begin

{ если список пустой, он и остается пустым }

if l=nil then DelList:=nil

{ если m=0, эл-т удаляется из начала списка }

else if m=0 then DelList:=cdr(l)

{ - удалить эл-т x на месте m-1 в список без 1-го эл-та;

- в начало полученного списка вставить 1-й эл-т }

else DelList:=cons(car(l),DelList(cdr(l),m-1));

end; { Function DelList }

{*** перестановка в списке l эл-тов местах с номерами m и m+1 }

Function ExchngList(l : lpt; m : integer) : lpt;

begin { если список пустой, он и остается пустым }

if l=nil then ExchngList:=nil

else if m=0 then

{если m=0, а следующего эл-та нет, список остается без изменений}

if cdr(l)=nil then ExchngList:=l

{ если m=0 ( обмен 0-го и 1-го эл-тов):

- берется список без двух 1-ых эл-тов - cdr(cdr(l));

- в его начало добавляется 0-й эл-т;

- в начало полученного списка добавляется 1-й эл-т - car(cdr(l))}

else ExchngList:= cons(car(cdr(l)),cons(car(l),cdr(cdr(l))))

else ExchngList:=cons(car(l),ExchngList(cdr(l),m-1));

end; { Function ExchngList }

END.

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

Функция Append добавляет элемент x в конец списка l. Рассмотрим ее выполнение на примере вызова: Append(4,(1,2,3)).

Поскольку аргумент-список не пустой, выполняется ветвь else. Она содержит оператор:

Append:=cons(car(l),Append(x,cdr(l)));

Важно точно представить себе последовательность действий по выполнению этого оператора:

· car(l) = 1;

· cdr(l) = (2,3);

· Append(4,(2,3))) - при этом рекурсивном вызове выполнение вновь пойдет по ветви else, в которой:

· car(l) = 2;

· cdr(l) = (3);

· Append(4,(3))) - выполнение вновь пойдет по ветви else, в которой:

· car(l) = 3;

· cdr(l) = nil;

· Append(4,nil) - в этом вызове список-аргумент пустой, поэтому выполнится Append:=cons(4,nil) и вызов вернет список: (4);

· cons(car(l),Append(x,cdr(l))) - значения аргументов функции cons - для этого уровня вызовов: cons(3,(4)) = (3,4);

· на этом уровне Append возвращает список (3,4);

· cons(car(l),Append(x,cdr(l))) - на этом уровне: cons(2,(3,4)) = (2,3,4);

· на этом уровне Append возвращает список (2,3,4);

· cons(car(l),Append(x,cdr(l))) - на этом уровне: cons(1,(2,3,4)) = (1,2,3,4);

· на этом уровне Append возвращает список (1,2,3,4).

Функция ListRev выполняет инвертирование списка - изменения порядка следования его элементов на противоположный. При обращении к функции ее второй аргумент должен иметь значение nil. Пример: ListRev(1,(2,3),4),nil).

Входной список не пустой, поэтому выполнение идет по ветви else, где:

ListRev:=ListRev(cdr(l),cons(car(l),q));

Последовательность действий:

· cdr(l) = ((2,3),4);

· car(l) = 1;

· cons(car(l),q) = (1) - список q при этом - пустой;

· рекурсивный вызов ListRev( ((2,3),4), (1)):

· cdr(l) = (4);

· car(l) = (2,3);

· cons(car(l),q) = ((2,3),1) - список q - (1);

· рекурсивный вызов ListRev((4), ((2,3),1)):

· cdr(l) = nil;

· car(l) = 4;

· cons(car(l),q) = (4,(2,3),1);

· рекурсивный вызов ListRev(nil, (4,(2,3),1)):

· поскольку исходный список пустой, вызов возвращает список: (4,(2,3),1);

· вызов возвращает список: (4,(2,3),1);

· вызов возвращает список: (4,(2,3),1);

· вызов возвращает список: (4,(2,3),1).

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

· вся арифметика - целочисленная;

· программа не проверяет правильность исходной записи;

· в выражении не допускается унарный минус.

{==== Программный пример 5.13 ====}

{ Калькулятор. Вычисление арифметических выражений }

program Calc;

Uses ListWork;

type cptr = ^char;

iptr = ^ integer;

const { цифровые символы }

digits : set of char = ['0'..'9'];

{ знаки операций с высоким приоритетом }

prty : set of char = ['*','/'];

var s : string; { исходная строка }

n : integer; { номер текущего символа в исх. строке }

{*** Представление исходной строки в списочной форме }

Function Creat_Lst : lpt;

var lll : lpt; { указатель на начало текущего списка }

s1 : char; { текущий символ строки }

st : string; { накопитель строки-операнда }

{* Создание атома для Integer }

Procedure NewInt;

var ip : iptr; cc : integer;

begin

if Length(st) > 0 then begin

{ если в st накоплено цифровое представление числа,

оно переводится в тип integer, для него создается атом и

записывается в конец списка }

New(ip); Val(st,ip^,cc);

lll:=Append(NewAtom(ip,'I'),lll);

st:=''; { накопитель строки сбрасывается }

end; end; { Procedure NewInt }

Procedure NewChar; { Создание атома для Char }

var cp : cptr;

begin { выделяется память для 1 символа, в ней

сохраняется значение s1, для него создается атом,

записывается в конец списка}

New(cp); cp^:=s1;

lll:=Append(NewAtom(cp,'C'),lll);

end; { Procedure NewChar }

begin { Function Creat_Lst }

{ исходный список пустой, накопитель строки - пустой }

lll:=nil; st:='';

while n <= length(s) do begin { цикл до конца исходной строки }

s1:=s[n]; n:=n+1;

case s1 of

'(' : { начало скобочного подвыражения: для него создается

новый список - Creat_Lst, который оформляется как подсписок -

NewNode и добавляется в конец текущего списка - Append }

lll:=Append(NewNode(Creat_Lst),lll);

')' : { конец скобочного выражения - последнее число в

скобках добавляется в конец текущего списка и текущий список

сформирован - конец функции }

begin

NewInt; Creat_Lst:=lll; Exit;

end;

else {begin} { цифра или знак операции }

if s1 in Digits then { цифры накапливаются в st }

st:=st+s1

else begin { знак операции }

NewInt; { созд. атом для ранее накопленного числа }

NewChar; { созд. атом для знака }

end; { end;} end; { case } end; { while }

NewInt; { созд. атом для ранее накопленного числа }

Creat_Lst:=lll;

end; { Function Creat_Lst }

{*** Выделение в подсписки высокоприоритетных операций }

Function FormPrty(l : lpt) : lpt;

var op1, op, op2 : lpt; { 1-й операнд, знак, 2-й операнд }

l2,l3 : lpt;

cp: ^char;

begin

l2:=nil; { выходной список пустой }

{ выделение 1-го операнда }

op1:=car(l); l:=cdr(l);

{ если 1-й операнд - подсписок - обработка подсписка }

if not atom(op1) then op1:=FormPrty(op1);

while l<>nil do begin { до опустошения исходного списка }

{ выделение знака операции }

op:=car(l); l:=cdr(l);

{ выделение 2-го операнда }

op2:=car(l); l:=cdr(l);

{ если 2-й операнд - подсписок - обработка подсписка }

if not atom(op2) then op2:=FormPrty(op2);

if cptr(op^.down)^ in prty then

{ если знак операции приоритетный, то создается подсписок:

1-й операнд, знак, 2-й операнд, этот подсписок далее является 1-ым

операндом }

op1:=cons(op1,cons(op,cons(op2,nil)))

else begin { если знак неприоритетный, 1-й операнд и знак

записываются в выходной список, 2-й операнд далее является 1-ым

операндом }

l2:=Append(op,Append(op1,l2));

op1:=op2;

end; end;

FormPrty:=Append(op1,l2); { последний операнд добавляется в

выходной список }

end; { Function FormPrty }

{*** Вычисление выражения }

Function Eval(l : lpt) : integer;

var op1, op, op2 : lpt;

begin

{ выделение 1-го операнда }

op1:=car(l); l:=cdr(l);

{ если 1-й операнд - подсписок - вычислить его выражение }

if not atom(op1) then iptr(op1^.down)^:=Eval(op1);

while l <> nil do begin

{ выделение знака операции }

op:=car(l); l:=cdr(l);

{ выделение 2-го операнда }

op2:=car(l); l:=cdr(l);

{ если 2-й операнд - подсписок - вычислить его выражение }

if not atom(op2) then iptr(op2^.down)^:=Eval(op2);

{ выполнение операции, результат - в op1 }

case cptr(op^.down)^ of

'+' : iptr(op1^.down)^:=iptr(op1^.down)^+iptr(op2^.down)^;

'-' : iptr(op1^.down)^:=iptr(op1^.down)^-iptr(op2^.down)^;

'*' : iptr(op1^.down)^:=iptr(op1^.down)^*iptr(op2^.down)^;

'/' : iptr(op1^.down)^:=iptr(op1^.down)^ div iptr(op2^.down)^;

end;

end;

Eval:=iptr(op1^.down)^; { возврат последнего результата }

end; { Function Eval }

{*** Главная программа }

var l : lpt;

begin

write('>'); readln(s); { ввод исходной строки }

{ формирование списка }

n:=1; l:=Creat_Lst;

{ выделение приоритетных операций }

l:=FormPrty(l);

{ вычисление и печать результата }

writeln(s,'=',Eval(l));

END.

Выполнение программы состоит во вводе строки, представляющей исходное выражение и последовательных обращений к трем функциям: Creat_Lst, FormPrty и Eval.

Функция Creat_Lst преобразует исходную строку в список. В функции поэлементно анализируются символы строки. Различаемые символы: левая круглая скобка, правая скобка, знаки операций и цифры. Цифровые символы накапливаются в промежуточной строке. Когда встречается символ-разделитель - правая скобка или знак операции накопленная строка преобразуется в число, для него создается атом с типом 'I' и включается в конец списка. Для знака операции создается атом с типом 'C' и тоже включается в конец списка. Левая скобка приводит к рекурсивному вызову Creat_Lst. Этот вызов формирует список для подвыражения в скобках, формирование списка заканчивается при появлении правой скобки. Для сформированного таким образом списка создается узел, и он включается в основной список как подсписок. Так, например, для исходной строки:

5+12/2-6*(11-7)+4

функцией Creat_Lst будет сформирован такой список:

(5,+,12,/,2,-,6,*,(11,-,7),+,4)

Следующая функция - FormPrty - выделяет в отдельные подсписки операции умножения и деления, имеющие более высокий приоритет, и их операнды. Функция просматривает список и выделяет в нем последовательные тройки элементов "операнд-знак-операнд". Если один из операндов является подсписком, то он обрабатывается функцией FormPrty. Если знак является одним из приоритетных знаков, то из тройки формируется подсписок, который становится первым операндом для следующей тройки. Если знак не приоритетный, то второй операнд тройки становится первым для следующей тройки. Список нашего примера после обработки его функцией FormPrty превратится в:

(5,+,(12,/,2),-,(6,*,(11,-,7)),+,4)

Наконец, функция Eval выполняет вычисления. Она во многом похожа на функцию FormPrty: в ней также выделяются тройки "операнд 1- 0знак-операнд". Если один или оба операнда являются подсписками, то сначала вычисляются эти подсписки и заменяются на атомы - результаты вычисления. Если оба операнда - атомы, то над ними выполняется арифметика, задаваемая знаком операции. Поскольку в первую очередь вычисляются подсписки, то подвыражения, обозначен- ные скобками в исходной строке, и операции умножения и деления выполняются в первую очередь. Для нашего примера порядок вычислений будет таков:

 

12 / 2 = 6; 5 + 6 = 11; 11 - 7 = 4; 6 * 4 = 24;

24 + 4 = 28; 11 - 28 = -17

 

Язык программирования LISP

Сама LISP-программа представляется как список, записанный в скобочной форме. Элементами простого программного списка является имя операции/функции и… Системы программирования LISP строятся и как компиляторы, и как… Другие языки обработки списков, например IPL-V, COMMIT в большей мере ориентированы на решение прикладных задач, а не…

Управление динамически выделяемой памятью

В современных вычислительных средах большая часть вопросов, связанных с управлением памятью решается операционными системами или системами… В общем случае при распределении памяти должны быть решены следующие… · способ учета свободной памяти;

НЕЛИНЕЙНЫЕ СТРУКТУРЫ ДАННЫХ

Графы

Логическая структура, определения

Многосвязная структура обладает следующими свойствами: · 1) на каждый элемент (узел, вершину) может быть произвольное количество… · 2) каждый элемент может иметь связь с любым количеством других элементов;

Рис.6.1. Граф неориентированный (а) и ориентированный (б).

Для ориентированного графа число ребер, входящих в узел, называется полустепенью захода узла, выходящих из узела -полустепенью исхода. Количество входящих и выходящих ребер может быть любым, в том числе и нулевым. Граф без ребер является нуль-графом.

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

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

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

Логически структура-граф может быть представлена матрицей смежности или матрицей инцидентности.

Матрицей смежности для n узлов называется квадратная матрица adj порядка n. Элемент матрицы a(i,j) равен 1, если узел j смежен с узлом i (есть путь < i,j >), и 0 -в противном случае (рис.6.2).

Рис.6.2. Графа и его матрица смежности

Если граф неориентирован, то a(i,j)=a(j,i), т.е. матрица симметрична относительно главной диагонали.

Матрицы смежности используются при построении матриц путей, дающих представление о графе по длине пути: путь длиной в 1 - смежный участок - , путь длиной 2 - (< A,B >,< B,C >), ... в n смежных участков: где n - максимальная длина, равная числу узлов графа. На рис.6.3 даны путевые матирцы пути adj2, adj3, adj4 для графа рис.6.2.

Рис.6.3. Матрицы путей

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

Рис.6.4. Матрицы инцидентности

Машинное представление оpгpафов

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

МАТРИЧНОЕ ПРЕДСТАВЛЕНИЕ ОРГРАФОВ.

Например, для простого ориентированного графа, изображенного на рис.6.2 массив определяется как: mas:array[1..4,1..4]=((0,1,0,0),(0,0,1,1),(0,0,0,1),(1,0,1,0)) Матрицы смежности применяются, когда в графе много связей и матрица хорошо заполнена.

СВЯЗНОЕ ПРЕДСТАВЛЕНИЕ ОРГРАФОВ.

В первом варианте два типа элементов - атомарный и узел связи (см. раздел 5.5). На рис.6.5 показана схема такого представления для графа рис.6.2.… ( < A,B >, < B,C >, < C,D >, < B,D >, < D,C >…

Рис.6.5. Машинное представление графа элементами двух типов

Более рационально представлять граф элементами одного формата, двойными: атом-указатель и указатель-указатель или тройными: указатель-data/down-указатель (см.раздел 5.5). На рис.6.6 тот же граф представлен элементами одного формата.

Рис.6.6. Машинное представление графа однотипными элементами

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

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

Пусть дана часть каpты доpожной сети и нужно найти наилучший маpшpут от города 1 до города 5. Такая задача выглядит достаточно пpостой, но "наилучший" маpшpут могут опpеделять многие фактоpы. Например: (1) pасстояние в километpах; (2) вpемя пpохождения маpшpута с учетом огpаничений скоpости; (3) ожидаемая пpодолжительность поездки с учетом доpожных условий и плотности движения; (4) задеpжки, вызванные пpоездом чеpез гоpода или объездом гоpодов; (5) число гоpодов, котоpое необходимо посетить, напpимеp, в целях доставки гpузов. Задачи о кpатчайших путях относятся к фундаментальным задачам комбинатоpной оптимизации.

Сpеди десятков алгоpитмов для отыскания кpатчайшего пути один из лучших пpинадлежит Дейкстpе. Алгоpитм Дейкстpы, опpеделяющий кpатчайшее pасстояние от данной веpшины до конечной, легче пояснить на пpимеpе. Рассмотpим гpаф, изобpаженный на pис.6.7, задающий связь между гоpодами на каpте доpог. Пpедставим гpаф матpицей смежности A, в котоpой: A(i,j)-длина pебpа между узлами i и j. Используя полученную матрицу и матрицы, отражающие другие факторы, можно определить кратчайший путь.

Рис.6.7. Часть дорожной карты, представленная в виде взвешенного графа и его матрицы смежности

{========== Программный пример 6.1 ==============}

{ Алгоритм Дейкстры }

Program ShortWay;

Const n=5; max=10000;

Var a: Array [1..n,1..n] of Integer;

v0,w,edges: Integer;

from,tu,length: Array [1..n] of Integer;

Procedure adjinit;

{ Эта пpоцедуpа задает веса pебеp гpафа посpедством

опpеделения его матpицы смежности A pазмеpом N x N }

Var i,j: Integer;

Begin

{ "Обнуление" матpицы (веpшины не связаны) }

For i:=1 to n do

For j:=1 to n do a[i,j]:=max;

For i:=1 to n do a[i,i]:=0;

{ Задание длин pебеp, соединяющих смежные узлы гpафа }

a[1,2]:=12; a[1,3]:=18; a[1,4]:=10;

a[2,1]:=12; a[2,3]:=6; a[2,5]:=9;

a[3,1]:=18; a[3,2]:=6; a[3,4]:=7; a[3,5]:=3;

a[4,1]:=10; a[4,3]:=7; a[4,5]:=15;

a[5,2]:=9; a[5,3]:=3; a[5,4]:=15;

End;

Procedure printmat;

{ Эта пpоцедуpа выводит на экpан дисплея матpицу

смежности A взвешенного гpафа }

Var i,j: Integer;

Begin writeln;

writeln('Матpица смежности взвешенного гpафа (',n,'x',n,'):');

writeln;

For i:=1 to n do

Begin write ('Ё');

For j:=1 to n do

If a[i,j]=max Then write(' ----') Else write(a[i,j]:6);

writeln(' Ё')

End; writeln;

writeln (' ("----" - pебpо отсутствует)')

End;

Procedure dijkst;

{ Эта пpоцедуpа опpеделяет кpатчайшее pасстояние от начальной веpшины V0 до конечной веpшины W в связном гpафе с неотpицательными весами с помощью алгоpитма, пpинадлежащего Дейкстpе.

Результатом pаботы этой пpоцедуpы является деpево кpатчайших путей с коpнем V0.

---- Входные и выходные пеpеменные ---
A(I,J)	длина pебpа, соединяющего веpшины I и J. Если pебpо отсутствует, то A(I,J)=10000 (пpоизвольному большому числу).
V0	начальная веpшина.
W	конечная веpшина.
N	веpшины в гpафе пpонумеpованы 1,...,N.
FROM(I) TU(I)	содеpжит I-е pебpо в деpеве кpатчайших путей от веpшины FROM(I) к веpшине TU(I)
LENGTH(I)	длины LENGTH(I).
EDGES	число pебеp в деpеве кpатчайших путей на данный момент.

 

--- Внутpенние пеpеменные ---
DIST(I)	кpатчайшее pасстояние от UNDET(I) до частичного деpева кpатчайших путей.
NEXT	очеpедная веpшина, добавляемая к деpеву кpатчайших путей.
NUMUN	число неопpеделенных веpшин.
UNDET(I)	список неопpеделенных веpшин.
VERTEX(I)	веpшины частичного деpева кpатчайших путей, лежащие на кpатчайшем пути от UNDET(I) до V0. }

Label stpoint;

Var dist,undet,vertex: array[1..n] of Integer;

next,numun,i,j,k,l,jk: Integer;

Begin

edges:=0; next:=v0; numun:=n-1;

For i:=1 to n do

Begin undet[i]:=i; dist[i]:=a[v0,i]; vertex[i]:=v0 End;

undet[v0]:=n; dist[v0]:=dist[n];

goto stpoint;

Repeat

{ Исключение вновь опpеделенной веpшины из списка неопpеделенных}

dist[k]:=dist[numun]; undet[k]:=undet[numun];

vertex[k]:=vertex[numun];

{ Остались ли неопpеделеные веpшины ? }

dec(numun);

{ Обновление кpатчайшего pасстояния до всех неопpеделенных веpшин }

For i:=1 to numun do

Begin j:=undet[i]; jk:=l+a[next,j];

If dist[i] > jk Then Begin vertex[i]:=next; dist[i]:=jk End

End;

stpoint:{Запоминание кpатчайшего pасст.до неопpеделенной веpшины}

k:=1; l:=dist[1];

For i:=1 to numun do

If dist[i] < l Then Begin l:=dist[i]; k:=i End;

{ Добавление pебpа к деpеву кpатчайших путей }

inc(edges); from[edges]:=vertex[k]; tu[edges]:=undet[k];

length[edges]:=l; next:=undet[k]

Until next = w { Достигли ли мы w }

End;

Procedure showway;

{ Эта пpоцедуpа выводит на экpан дисплея кpатчайшее pасстояние между

веpшинами V0 и W взвешенного гpафа, опpеделенное пpоцедуpой dijkst }

Var i: Integer;

Begin

writeln; writeln('Кpатчайшее pасстояние между');

writeln('узлами ',v0,' и ',w,' pавно ',length[edges])

End;

{ Основная пpогpамма }

Begin

adjinit; printmat; v0:=1;w:=5;

dijkst; showway; readln

End.

 

Деревья

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

· 1. Cуществует единственный элемент (узел или вершина), на который не ссылается никакой другой элемент - и который называется КОРНЕМ (рис. 6.8,… · 2. Начиная с корня и следуя по определенной цепочке указателей,… · 3. На каждый элемент, кроме корня, имеется единственная ссылка, т.е. каждый элемент адресуется единственным…

Рис. 6.8. Дерево

Рис. 6.9. Лес

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

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

Вершина ориентированного дерева, полустепень исхода которой равна нулю, называется КОНЦЕВОЙ (ВИСЯЧЕЙ) вершиной или ЛИСТОМ; все остальные вершины дерева называют вершинами ветвления. Длина пути от корня до некоторой вершины называется УРОВНЕМ (НОМЕРОМ ЯРУСА) этой вершины. Уровень корня ориентированного дерева равен нулю, а уровень любой другой вершины равен расстоянию (т.е. модулю разности номеров уровней вершин) между этой вершиной и корнем. Ориентированное дерево является ациклическим графом, все пути в нем элементарны.

Во многих приложениях относительный порядок следования вершин на каждом отдельном ярусе имеет определенное значение. При представлении дерева в ЭВМ такой порядок вводится автоматически, даже если он сам по себе произволен. Порядок следования вершин на некотором ярусе можно легко ввести, помечая одну вершину как первую, другую - как вторую и т.д. Вместо упорядочивания вершин можно задавать порядок на ребрах. Если в ориентированном дереве на каждом ярусе задан порядок следования вершин, то такое дерево называется УПОРЯДОЧЕННЫМ ДЕРЕВОМ.

Введем еще некоторые понятия, связанные с деревьями. На рис.6.10 показано дерево:

Узел X называется ПРЕДКОМ (или ОТЦОМ), а узлы Y и Z называются НАСЛЕДНИКАМИ (или СЫНОВЬЯМИ) их соответственно между собой называют БРАТЬЯМИ. Причем левый сын является старшим сыном, а правый - младшим. Число поддеревьев данной вершины называется СТЕПЕНЬЮ этой вершины. ( В данном примере X имеет 2 поддерева, следовательно СТЕПЕНЬ вершины X равна 2).

Рис.6.10. Дерево

Если из дерева убрать корень и ребра, соединяющие корень с вершинами первого яруса, то получится некоторое множество несвязанных деревьев. Множество несвязанных деревьев называется ЛЕСОМ (рис. 6.9).

Логическое представление и изображение деревьев.

МЕТОД ВЛОЖЕННЫХ СКОБОК

(V0(V1(V2(V5)(V6))(V3)(V4))(V7(V8)(V9(V10))))

Рис.6.11. Представление дерева : а)- исходное дерево, б)- оглавление книг, в)- граф, г)- диаграмма Венна

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

Бинарные деревья.

При m=2 такие деревья называются соответственно БИНАРНЫМИ, или ПОЛНЫМИ БИНАРНЫМИ. На рисунке 6.12(a) изображено бинарное дерево, 6.12(b)- полное бинарное…

Рис. 6.13. Изображения бинарных деревьев

Бинарные деревья, изображенные на рис.6.13(a) и 6.13(d), представляют собой разные позиционные деревья, хотя они не являются разными упорядоченными деревьями.

В позиционном бинарном дереве каждая вершина представлена единственным образом посредством строки символов над алфавитом {0,1}, при этом корень характеризуется пустой строкой. Любой сын вершины "u" характеризуется строкой, префикс (начальная часть) которой является строкой, характеризующей "u".

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

Представить m-арное дерево в памяти ЭВМ сложно, т.к. каждый элемент дерева должен содержать столько указателей, сколько ребер выходит из узла (при m-3,4.5.6... соответствует 3,4,5,6... указателей). Это приведет к повышенному расходу памяти ЭВМ, разнообразию исходных элементов и усложнит алгоритмы обработки дерева. Поэтому m-арные деревья, лес необходимо привести к бинарным для экономии памяти и упрощению алгоритмов. Все узлы бинарного дерева представляются в памяти ЭВМ однотипными элементами с двумя указателями (см.разд. 6,2,5), кроме того, операции над двоичными деревьями выполняются просто и эффективно.

Представление любого дерева, леса бинарными деревьями.

Правило построения бинарного дерева из любого дерева: · 1. В каждом узле оставить только ветвь к старшему сыну (вертикальное… · 2. Соединить горизонтальными ребрами всех братьев одного отца;

Рис.6.14. Исходное дерево

Рис.6.15 Промежуточный результат перестройки дерева

Рис. 6.16. Представление дерева в виде бинарного

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

Правило построения бинарного дерева из леса: корни всех поддеревьев леса соединить горизонтальными связями. В полученном дереве узлы в данном примере будут располагаться на трех уровнях. Далее перестраивать по ранее рассмотренному плану: в начале поддерево с корнем А, затем В и затем Н. В результате преобразования упорядоченного леса в бинарное дерево получается полное бинарное дерево с левым и правым поддеревом.

Рис.6.17. Упорядоченный лес

Рис.6.18. Промежуточный результат перестройки леса

Рис. 6.19. Представление леса в виде 2-го дерева

В результате преобразования упорядоченного леса в бинарное дерево получается полное бинарное дерево с левым и правым поддеревом.

Машинное представление деревьев в памяти ЭВМ.

Чаще всего используется связное представление деревьев, т.к. оно очень сильно напоминает логическое. Связное хранение состоит в том, что задается… где LPTR - указатель на левое поддерево, RPTR - указатель на правое поддерево,… Рассмотрим машинное представление бинарного дерева, изображенного на рис. 6.20.

Рис. 6.20. Логическое представление дерева

Рис. 6.21. Машинное связное представление дерева представленного на рис.6.20

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

Выбор метода последовательного представления деревьев определяется также набором тех операций, которые должны быть выполнены над древовидными структурами. (Пример статистической древовидной структуры - пирамидальный метод сортировки). Простейший метод представления дерева в виде последовательной структуры заключается во введении вектора FATHER, задающего отбор для всех его вершин. Этот метод можно использовать также для представления леса. Недостаток метода - он не отображает упорядочения вершин дерева. Если в предыдущем примере поменять местами вершины 9 и 10, последовательное представление останется тем же.

Рис. 6.22. Диаграммы дерева: а) исходное б) перестройка в бинарное

Последовательное представление дерева, логическая диаграмма которого дана на рис. 6.22 , задается следующим образом:

i 1 2 3 4 5 6 7 8 9 10

FATHER [i] 0 1 1 1 2 3 3 7 4 4 ,

где ветви определяются как

{(FATHER[i],i)}, i = 2,3,...,10.

Вершины 2,3,4 являются сыновьями вершины 1, вершина 5 - сыном вершины 2, вершины 6,7 - сыновьями вершины 3, вершина 8 имеет отца вершина 7 и вершины 9 и 10 - сыновья вершины 4.

Числовые поля данных используются здесь, чтобы упростить представление дерева. Корневая вершина не имеет отца, поэтому вместо отца для нее задается нулевое значение.

Общее правило: если T обозначает индекс корневой вершины дерева, то FATHER[T] = 0.

Другой метод последовательного представления деревьев заключается в использовании физической смежности элементов машинной памяти вместо одного из полей LPTR или RPTR, например, способ опускания полей, т.е. чтобы вершины появлялись в нисходящем порядке. Дерево (рис.6.22б), можно описать как:

Рис. 6.23. Последовательное представление дерева методом опускания полей

где RPTR,DATA и TAG представляют векторы. В данном методе указатель LPTR не требуется, т.к. если бы он не был пуст, то указывал бы на вершину, стоящую непосредственно справа от данной. Вектор TAG - бинарный вектор, в котором единицы отмечают концевые вершины исходного дерева. При таком представлении имеются значительные потери памяти, т.к. свыше половины указателей RPTR оказываются пустыми. Эти пустые места можно использовать путем установки указателя RPTR каждой данной вершины на вершину, которая следует непосредственно за поддеревом, расположенном под ней. В таком представлении поле RPTR переименовывается в RANGE:

Рис. 6.24. Последовательное представление дерева с размещением вершин в возрастающем порядке

В этом случае поле TAG не требуется поскольку концевой узел определяется условием RANGE(P) = P + 1.

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

Рис. 6.25. Последовательное представление дерева на основе восходящего обхода

В заключении приведем два важных понятия.

Подобие бинарных деревьев - два дерева подобны, если они имеют одинаковую структуру ( форму ).

Эквивалентные бинарные деревья - два дерева эквивалентные, если они подобны, и если соответствующие вершины у них содержат одинаковую информацию.

Основные операции над деревьями.

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

· 1) Поиск узла с заданным ключом ( Find ).

· 2) Добавление нового узла ( Dob ).

· 3) Удаление узла ( поддерева ) ( Udal ).

· 4) Обход дерева в определенном порядке:

· Нисходящий обход ( процедура Preorder , рекурсивная процедура r_Preoder);

· Смешанный обход (процедура Inorder, рекурсивная процедура r_Inorder);

· Восходящий обход ( процедура Postorder, рекурсивная процедура r_Postorder).

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

· процедура включения в стек при нисходящем обходе (Push_st);

· функция извлечения из стека при нисходящем обходе (Pop_st);

· процедура включения в стек при восходящем и смешанном обходе (S_Push);

· функция извлечения из стека при восходящем и смешанном обходе (S_Pop).

Для прошитых деревьев:

· функция нахождения сына данного узла ( Inson );

· функция нахождения отца данного узла ( Inp );

· процедура включения в дерево узла слева от данного (leftIn);

ПОИСК ЗАПИСИ В ДЕРЕВЕ( Find ).

Пусть построено некоторое дерево и требуется найти звено с ключом X. Сначала сравниваем с X ключ, находящийся в корне дерева. В случае равенства… · 1) найдена вершина, содержащая ключ, равный ключу X; · 2) в дереве отсутствует вершина, к которой нужно перейти для выполнения очередного шага поиска.

ДОБАВЛЕНИЕ НОВОГО УЗЛА ( Dop ).

Алгоритм поиска нужной вершины, вообще говоря, тот же самый, что и при поиске вершины с заданным ключом. Эта вершина будет найдена в тот момент,… {=== Программный пример 6.3. Добавление звена ===} Procedure Dob (k:KeyType; var d:TreePtr; zap:data);

ОБХОД ДЕРЕВА.

Бинарное дерево можно обходить тремя основными способами: нисходящим, смешанным и восходящим ( возможны также обратный нисходящий, обратный… Схематично алгоритм обхода двоичного дерева в соответствии с нисходящим… · 1. В качестве очередной вершины взять корень дерева. Перейти к пункту 2.

Рис.6.26. Схема дерева

НИСХОДЯЩИЙ ОБХОД (Preorder, r_Preorder).

  {=== Программный пример 6.4. Нисходящий обход ===} Procedure Preorder (t: TreePtr);

Таблица 6.1

РЕКУРСИВНЫЙ НИСХОДЯЩИЙ ОБХОД.

· 1). Обработка корневой вершины; · 2). Нисходящий обход левого поддерева; · 3). Нисходящий обход правого поддерева.

CМЕШАННЫЙ ОБХОД (Inorder, r_Inorder).

· 1) Спуститься по левой ветви с запоминанием вершин в стеке; · 2) Если стек пуст то перейти к п.5; · 3) Выбрать вершину из стека и обработать данные вершины;

Таблица 6.2

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

· 1) Смешанный обход левого поддерева;

· 2) Обработка корневой вершины;

· 3) Смешанный обход правого поддерева.

Текст программы рекурсивной процедуры ( r_Inorder ) демонстрируется в программном примере 6.7.

{=== Программный пример 6.7. Рекурсивное выполнение смешанного обхода ===}

Procedure r_Inorder(t: TreePtr);

begin

if t = nil then

begin writeln('Дерево пусто'); exit; end;

if t^.left <> nil then R_inorder (t^.left);

(*--------------- Обработка данных звена --------------*)

................................

if t^.right <> nil then R_inorder(t^.right);

End;

ВОСХОДЯЩИЙ ОБХОД ( Postorder, r_Postorder ).

Алгоритм восходящего обхода можно представить следующим образом: · 1) Спуститься по левой ветви с запоминанием вершины в сте ке как 1-й вид… · 2) Если стек пуст, то перейти к п.5;

РЕКУРСИВНЫЙ СМЕШАННЫЙ ОБХОД

· 1). Восходящий обход левого поддерева; · 2). Восходящий обход правого поддерева; · 3). Обработка корневой вершины.

ПРОЦЕДУРЫ ОБХОДА ДЕРЕВА, ИСПОЛЬЗУЮЩИЕ СТЕК.

Stack=^Zveno; Zveno = record next: Stack;

ПРОШИВКА БИНАРНЫХ ДЕРЕВЬЕВ.

Рассматривая бинарное дерево, легко обнаружить, что в нем имеются много указателей типа NIL. Действительно в дереве с N вершинами имеется ( N+1 )… Поскольку после прошивания дерева поля left и right могут характеризовать либо… Таким образом, прошитые деревья быстрее обходятся и не требуют для этого дополнительной памяти (стек), однако требуют…

Рис. 6.27.

В программном примере 6.14 приведена функция ( Inson ) для определения сына (преемника) данной вершины.

{ === Програмнный пример 6.14 ====}

(*------ Функция, находящая преемника данной вершины X ----*)

(*-------- в соответствии со смешанным обходом ------------*)

Funtion Inson (x: TreePtr):TreePtr;

begin

Inson:=x^.right;

if not (x^.rf) then exit; { Ветвь левая ?}

while Insonon^.lf do { связь не нить }

Inson:=Inson^.left; { перейти по левой ветви }

end; { Inson }

В программном примере 6.15 приведена функция (Int) для определения отца (предка) данной вершины.

{ === Програмнный пример 6.15 ====}

(*---------- Функция, выдающая предшественника узла ------*)

(*------- в соответствии со смеш1анным обходом ------------*)

Function Inp (x:TreePtr):TreePtr;

begin

Inp:=x^.left;

if not (x^.lf) then exit;

while Inp^.rf do Inp:=Inp^.right; { связка не нить }

end;

В программном примере 6.16 приведена функция, реализующая алгоритм включения записи в прошитое дерево ( leftIn ). Этот алгоритм вставляет вершину P в качестве левого поддерева заданной вершины X в случае, если вершина X не имеет левого поддерева. В противном случае новая вершина вставляется между вершиной X и вершиной X^.left. При этой операции поддерживается правильная структура прошивки дерева, соответствующая смешанному обходу.

{ === Програмнный пример 6.16 ====}

(*- Вставка p слева от x или между x и его левой вершиной -*)

Procedure LeftIn (x,p: TreePtr);

Var

q: TreePtr;

begin

(*--------------- Установка указателя ------------------*)

p^.left:=x^.left; p^.lf:=x^.lf; x^.left:=p;

x^.lf:=TRUE; p^.right:=x; p^.rf:=FALSE;

if p^.lf then

(*-------- Переустановка связи с предшественником --------*)

begin q:=TreePtr(Inp(p)); q^.right:=p; q^.rf:=FALSE;

end; end; { LeftIn }

Для примера рассмотрим прошивку дерева приведенного на рис.6.20. при нисходящем обходе.

Машинное представление дерева при нисходящем обходе с прошивкой приведено на рис.6.28.

Рис. 6.28. Машинное связное представление исходного дерева, представленного на рис.6.20 при нисходящем обходе с прошивкой

Трассировка нисходящего обхода с прошивкой приведена в табл.6.3.

Рассмотрим на примере того же дерева прошивку при смешанном обходе. Машинное представление дерева при смешанном обходе с прошивкой приведено на рис.6.28.

@ указателя	Узел	Обработка узла	Выходная строка
PT:=H	H
LPH	A	A	A
LPA	B	B	AB
LPB	C	C	ABC
-LPC
-RPC	D	D	ABCD
LPD	E	E	ABCDE
LPE	F	F	ABCDEF
-LPF
-RPF	G	G	ABCDEFG
-LPG
-RPG	H		Конец алгоритма

Таблица 6.3

Рис. 6.29. Машинное связное представление дерева при смешанном обходе с прошивкой

Трассировка смешанного обхода с прошивкой приведена в табл.6.4.

@ указателя	Узел	Обработка узла	Выходная строка
P:=PT	H
LPH	A
LPA	B
LPB	C
-LPC	C	C	C
-RPC	B	B	CB
-RPB	A	A	CBA
RPA	D
LPD	E
LPE	F
-LPF	F	F	CBAF
-RPF	E	E	CBAFE
-RPE	D	D	CBAFED
RPD	G
-LPG	G	G	CBAFEDG
-RPG	H		Конец алгоритма

Таблица 6.4.

 

Приложения деревьев.

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

Деревья Хаффмена (деревья минимального кодирования)

Каждый символ тремя битами, получим строку :010 100 010 000 000 111 010. А В А С С D А 7*3=21 всего 21 бит - неэффективно 2) Сделаем иначе: предположим, что каждому… Тогда кодировка требует лишь 14 бит. 3) Выберем коды, которые минимизируют длину сообщения по частоте вхождений…

Рис.6.30 Дерево Хаффмена

Обычно коды создаются на основе частоты во всем множестве сообщений, а не только в одном.

Деревья при работе с арифметическими выражениями

МАНИПУЛИРОВАНИЕ АРИФМЕТИЧЕСКИМИ ВЫРАЖЕНИЯМИ.

Дано выражение а*(-b)+с/d

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

Рис.6.31 Представление выражения в виде дерева

Рис. 6.32 Представление выражения в виде бинарного дерева.

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

· (-) - операция унарного минуса;

· () - операция возведения в степень;

· (+) - операция сложения;

· (*) - операция умножения;

· (/) - операция деления.

· (Е) - указательная переменная, адресующая корень дерева, каждая вершина которого состоит из левого указателя (LPТR), правого указателя (RPTR) и информационного поля TYPE.

LPTR

DATA

RPTR

Для неконцевой вершины поле TYPE задает арифметическую операцию, связанную с этой вершиной. Значения поля TYPE вершин +,-,*, /, (-) и равны 1, 2, 3, 4, 5, 6 соответственно.

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

Рис.6.33 Таблица символов

Процедура вычислений:

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

Ниже приводится программа, вычисляющая арифметическое выражение.

Формирование таблиц символов.

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

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

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

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

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

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

Вершины бинарного дерева таблицы символов имеют формат:

LPTR

SYMBOLS

INFO

RPTR

· SYMBOLS - поле символьной строки, задающей идентификатор или имя переменной ( для обеспечения фиксированной длины описания вершин здесь можно хранить не саму строку, а лишь ее описатель );

· INFO - некоторое множество полей, содержащих дополнительно информацию об этом идентификаторе, например его тип данных.

Новая вершина создается путем исполнения оператора P при этом ее адрес запоминается в переменной P.

Еще предлагается, что перед любым исполнением программы ведения таблицы символов на некотором чистом уровне блочной структуры уже имеется соответствующая головная вершина дерева, в поле SYMBOLS в которое занесено значение, лексикографически большее, чем любой допустимый идентификатор. Эта вершина адресуется указателем HEAD[n], где n означает номер уровня блочной структуры. Т.е. предполагается, что при входе в блок осуществляется обращение к основной переменной, управляющей созданием головных вершин деревьев.

Операции включения записи в таблицу и операция поиска в таблице содержат значительное количество одинаковых действий ( например, просмотр ), поэтому рассмотрим только алгоритм TABLE, а различать включение или поиск по переменной FLAG. Если FLAG - истинно - то включение глобальной переменной, если - ложно - поиск. DATA - содержит имя идентификатора и дополнительную информацию для него.

Если включение новой записи было выполнено успешно, то FLAG сохраняет свое первоначальное значение противоположное начальному, что указывает на ошибку, означающую, что искомый идентификатор уже присутствует в таблице данного уровня и выполняемый алгоритм завершается. Если FLAG = ложь, то надо выполнить операцию поиска записи. В этом случае переменная NAME содержит имя идентификатора, который необходимо найти, а значение переменной. При успешном поиске переменная DATA устанавливается на поле INFO соответствующее записи таблицы символов. FLAG сохраняет свое значение и осуществляет возврат к вызванной программе. При неудаче операции поиска, FLAG меняет свое значение и выходит из алгоритма. В этом случае основная программа должна осуществлять поиск записи в таблице, более низких уровней. Деревья с головными вершинами HEAD[n-1], HEAD[n-2] b т.д.

АЛГОТИТМ TABLE.

В этом случае, если требовалось найти запись, то выдается сообщение об ошибке, в противном случае создается новая вершина, в нее заносится нужная… ОПИСАНИЕ ПРОГРАММЫ: Последовательность решения задачи:

Рис. 6.34.

Результат выражения = 14.000

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

ОПРЕДЕЛЕНИЯ.

Одним из методов, улучшающих время поиска в бинарном дереве является создание сбалансированных деревьев обладающих минимальным временем поиска. Одно из определений сбалансированности было дано Адельсоном-Вельским и… Дерево является СБАЛАНСИРОВАННЫМ тогда и только тогда, когда для каждого узла высота его двух поддеревьев различается…

ОПЕРАЦИЯ ВСТАВКИ ВЕРШИНЫ В СБАЛАНСИРОВАННОЕ ДЕРЕВО.

Алгоритм включения и балансировки полностью определяется способом хранения информации о сбалансированности дерева. Определение типа узла имеет… TYPE ref=^node; { указатель } node=record

ПРИНЦИП РАБОТЫ АЛГОРИТМА.

Сбалансированность теперь восстанавливается с помощью более сложного двукратного поворота налево и направо (LR); результатом является дерево (e).…

Рис. 6.35 Последовательное включение узлов в сбалансированное дерево.

АЛГОРИТМ Insert_&_Balanse включения узла в сбалансированное дерево.

Дано: сбалансированное бинарное дерево с корнем ROOT.

Поля: LPTR, RPTR, KEY (ключ), BAL (показатель сбалансированности), DATA (информация).

Заданы переменные: ключ - х, информация - INF.

Алгоритм вставляет в дерево новый элемент, сохраняя сбалансированность дерева. Если элемент уже присутствует в дереве, то выводится соответствующее сообщение.

Переменная h используется как флаг, указывающий на то, что было произведено включение элемента. P - текущий указатель при перемещении по дереву, p1 и p2 - вспомогательные указатели. Count - счетчик вставленных элементов.

_Начало . Insert_&_Balanse:

1. Поиск места для вставки:

_Если . x < KEY(p)

_то .: _если . p=nil

_то .: ВСТАВИТЬ_ЭЛЕМЕНТ и перейти к п. 3;

_иначе .: p=LPTR(p) и перейти к п. 1;

повторный вызов Insert_&_Balanse;

_Если . x > KEY(p)

_то .: _если . p=nil

_то .: ВСТАВИТЬ_ЭЛЕМЕНТ и перейти к п. 5;

_иначе .: p=RPTR(p) и перейти к п. 1;

повторный вызов Insert_&_Balanse;

2. Совпадение:

Напечатать "Элемент уже вставлен" и _конец ..

3. Изменение показателей сбалансированности:

(производилась вставка в левое поддерево)

_если . BAL(p)=1 _то .:

BAL(p)=0; h=false; { перевеш.-> сбалансир.}

перейти к п. 7

_если . BAL(p)=0 _то .

BAL(p)=-1; { перевеш.-> критическ.}

перейти к п. 7

4. Балансировка при возрастании левого поддерева:

_если . p=ROOT _то . ROOT=LPTR(p);

{ перенос корневой вершины }

p1=LPTR(); { вводим дополнительный указатель }

_если . BAL(p1)=-1

_то .:

{ однокр. LL-поворот }

LPTR(p)=RPTR(p1); RPTR(p1)=p;

BAL(p)=0; p=p1;

перейти к п. 7

_иначе .:

{ двукратн. LR-поворот }

_если . p1=ROOT

_то . ROOT=RPTR(p1); { перенос корневой вершины }

p2:=RPTR(p1); RPTR(p1)=LPTR(p2);

LPTR(p1)=p1; LPTR(p)=RPTR(p2);

RPTR(p2)=p;

(изменение показателей сбалансированности )

_если . BAL(p2)=-1 _то . BAL(p)=1 _иначе . BAL(p)=0;

_если . BAL(p2)=1 _то . BAL(p1)=-1 _иначе . BAL(p1)=0;

p=p2;

BAL(p)=0; h=false;

перейти к п. 7;

5. Изменение показателей сбалансированности:

(производилась вставка в правое поддерево)

_если . BAL(p)=-1 _то .:

BAL(p)=0; h=false; { перевеш.-> сбалансир.}

перейти к п. 7

_если . BAL(p)=0 _то

BAL(p)=1; { перевеш.-> критическ.}

перейти к п. 7

6. Балансировка при возрастании правого поддерева:

_если . p=ROOT _то . ROOT=RPTR(p); { перенос корневой вершины }

p1=RPTR(p); { вводим дополнительный указатель }

_если . BAL(p1)=1

_то .:

{ однокр. RR-поворот }

RPTR(p)=LPTR(p1); LPTR(p1)=p;

BAL(p)=0; p=p1;

перейти к п. 7

_иначе .:

{ двукратн. LR-поворот }

_если . p1=ROOT

_то . ROOT=LPTR(p1); { перенос корневой вершины }

p2:=LPTR(p1); LPTR(p1)=RPTR(p2);

RPTR(p1)=p1; RPTR(p)=LPTR(p2);

LPTR(p2)=p;

(изменение показателей сбалансированности )

_если . BAL(p2)=1 _то . BAL(p)=-1 _иначе . BAL(p)=0;

_если . BAL(p2)=-1 _то . BAL(p1)=1 _иначе . BAL(p1)=0;

p=p2;

BAL(p)=0; h=false;

7. Выход.

(Т.к. процедура осуществляет рекурсивный вызов самой

себя в п.3, то здесь производится возврат в место

предыдущего вызова. Последний выход осуществляется

в вызывающую программу).

_Конец . Insert_&_Balanse.

8. Алгоритм процедуры ВСТАВИТЬ_ЭЛЕМЕНТ:

_Начало .:

LPTR(p)=nil; RPT(p)=nil; BAL=0; { обнуление указателей }

DATA=INF; KEY=x; { занесение информации }

h=true; { установка флага вставки элемента }

_если . count=0 { это первый элемент ? }

_то . ROOT=p;

count=count+1;

_Конец ..

Описание работы:

· П.1 - осуществляется поиск места для вставки элемента. Производится последовательный рекурсивный вызов процедурой самой себя. При нахождении места для вставки к дереву добавляется новый элемент с помощью процедуры ВСТАВИТЬ_ЭЛЕМЕНТ.

· П.2 - Если такой элемент уже существует в дереве, то выводится сообщение об этом и выполнение процедуры завершается.

· П.3 (П.5) - производит изменение показателей сбалансированности после включения нового элемента в левое (правое для П.5) поддерево.

· П.4 (П.6) - производит балансировку дерева путем перестановки указателей - т.е. LL- и LR-повороты (RR- и RL-повороты в П.6)

· П.7 - с помощью рекурсивных вызовов в стеке запоминается весь путь до места создания новой вершины. В П.7 производится обратный обход дерева, корректировка всех изменившихся показателей сбалансированности (в П. 3 и 5) и при необходимости балансировка. Это позволяет производить правильную балансировку, даже если критическая вершина находится далеко то места вставки.

ТЕКСТ ПРОЦЕДУРЫ Insert_&_Balanse.

Процедура выполняет действия по вставка элемента в бинарное дерево с последующей балансировкой в соответствии с приведенным выше алгоритмом.

{=====Программный пример 6.18=========}

Procedure Insert_&_Balanse (x:integer; var p,root:ref;

var h:boolean);

{ x=KEY, p=p, root=ROOT, h=h }

var p1,p2:ref; {h=false}

Begin

if p=nil

then Create(x,p,h) {слова нет в дереве,включить его}

else if x=p^.key then

begin gotoXY(35,3); write('Ключ найден!');

readln; exit; end;

if x < p^.key then

begin Insert_&_Balanse(x,p^.left,root,h);

if h then {выросла левая ветвь}

case p^.bal of

1: begin p^.bal:=0; h:=false; end;

0: p^.bal:=-1;

-1: begin {балансировка}

if p=root then root:=p^.left;

p1:=p^.left; {смена указателя на вершину}

if p1^.bal=-1 then

begin {однократный LL-поворот}

p^.left:=p1^.right;

p1^.right:=p;

p^.bal:=0; p:=p1;

end

else begin {2-кратный LR-поворот}

if p1=root then root:=p1^.right; p2:=p1^.right;

p1^.right:=p2^.left; p2^.left:=p1;

p^.left:=p2^.right; p2^.right:=p;

if p2^.bal=-1 then p^.bal:=+1 else p^.bal:=0;

if p2^.bal=+1 then p1^.bal:=-1 else p1^.bal:=0;

p:=p2;

end; p^.bal:=0; h:=false;

end; end;{case}

end { h then}

else if x > p^.key then begin

Insert_&_Balanse(x,p^.right,root,h);

if h then {выросла правая ветвь}

case p^.bal of

-1: begin p^.bal:=0; h:=false; end;

0: p^.bal:=+1;

1: begin {балансировка}

if p=root then root:=p^.right;

p1:=p^.right; {смена указателя на вершину}

if p1^.BAL=+1 then

begin {однократный RR-поворот}

p^.right:=p1^.left; p1^.left:=p; p^.BAL:=0; p:=p1; end

else begin {2-кратный RL-поворот}

if p1=root then root:=p1^.left;

p2:=p1^.left; p1^.left:=p2^.right; p2^.right:=p1;

p^.right:=p2^.left; p2^.left:=p;

if p2^.BAL=+1 then p^.BAL:=-1 else p^.BAL:=0;

if p2^.BAL=-1 then p1^.BAL:=+1 else p1^.BAL:=0;

p:=p2; end;

p^.BAL:=0; h:=false;

end; { begin 3 }

end;{ case }

end; {then }

End {Search};

ТЕКСТ ПРОЦЕДУРЫ ДОБАВЛЕНИЯ ЭЛЕМЕНТА.

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

Procedure Create (x:integer; var p:ref; var h:boolean);

{ создание нового элемента }

Begin

NEW(p); h:=true; with p^ do

begin key:=x; left:=nil; right:=nil; BAL:=0; end;

if count=0 then root:=p; count:=count+1; End;

ОПЕРАЦИЯ УДАЛЕНИЯ ИЗ СБАЛАНСИРОВАННОГО ДЕРЕВА.

В результате удаления какого-либо узла могут возникнуть ситуации аналогичные тем, что возникают при добавлении элемента: · 1. Вершина была лево- или правоперевешивающей, а теперь стала… · 2. Вершина была сбалансированной, а стала лево- или правоперевешивающей.

ПРИМЕР УДАЛЕНИЯ РАЗЛИЧНЫХ УЗЛОВ ИЗ СБАЛАНСИРОВАННОГО ДЕРЕВА.

Узел, который необходимо удалить, обозначен двойной рамкой. Если задано сбалансированное дерево (рис.6.35. a), то последовательное удаление узлов с ключами 4,8,6,5,2,1 и 7 дает деревья (рис.6.35 b...h).

Удаление ключа 4 само по себе просто, т.к. он представляет собой терминальный узел. Однако при этом появляется несбалансированность в узле 3. Его балансировка требует однократного левого поворота налево. Балансировка вновь становится необходимой после удаления узла 6. На этот раз правое поддерево корня балансируется однократным поворотом направо.

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

И четвертый случай: двукратный поворот налево и направо вызывается удалением узла 7, который прежде заменяется самым правым элементом левого поддерева, т.е. узлом с ключом 3.

Рис.6.36 а..h Удаление узлов из сбалансированого дерева.

Удаление элемента из сбалансированного дерева удобнее разбить на 4 отдельных процедуры:

· 1. Delete - осуществляет рекурсивный поиск по дереву удаляемого элемента, вызывает процедуры удаления и балансировки.

· 2. Del - осуществляет собственно удаление элемента и вызов при необходимости процедуры балансировки.

· 3. Balance_L и Balance_R - производят балансировку и коррекцию показателей сбалансированности после удаления элемента из левого (правого) поддерева.

АЛГОРИТМ ПРОЦЕДУРЫ Delete.

Задан: ключ - х, информация - INF. Алгоритм находит удаляемый элемент и вызывает процедуры удаления и последующей… Переменная h используется как флаг, указывающий на то, что было произведено удаление элемента. P - текущий указатель…

АЛГОРИТМ ПРОЦЕДУРЫ Del.

Алгоритм производит удаление этого элемента, с сохранением связей с нижележащими элементами, и вызов процедуры балансировки. Используется вспомогательный указатель q, описанный в процедуре Delete. _Начало . Del.

АЛГОРИТМ ПРОЦЕДУРЫ Balance_L.

Задан: указатель p на место удаленного элемента. Алгоритм производит балансировку бинарного дерева и корректировку показателей… P1 и P2 - вспомогательные указатели, b1 и b2 - вспомогательные показатели сбалансированности.

АЛГОРИТМ ПРОЦЕДУРЫ Balance_R.

Алгоритм, входные данные и вспомогательные переменные аналогичны алгоритму Balance_L, изменены на противоположные только условия выбора и… _Начало . Balance_R: 1. Корректировка показателей сбалансированности:

ПОИСК ЭЛЕМЕНТА.

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

АЛГОРИТМ Search.

Алгоритм производит рекурсивный обход сбалансированного дерева и находит элемент с заданным ключом, либо сообщает об отсутствии такого элемента. 1. Поиск элемента: _Если . x < key(p)

ТЕКСТ ПРОЦЕДУРЫ Search.

Procedure Search (x:integer; var p:ref); begin if x > p^.key then

ОПИСАНИЕ ПРОГРАММЫ РАБОТЫ СО СБАЛАНСИРОВАННЫМИ ДЕРЕВЬЯМИ.

В процессе работы пользователя с программой MAVERIC выводит подсказку в нижней части экрана. Подсказка содержит коды клавиш,определяющих режим… 2. Процедура CREATE. Создает новый узел дерева,в том числе и корень; записывает ключ дерева и обнуляет указатели узла на его ветви.…

Л И Т Е Р А Т У Р А