47855

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

Конспект

Информатика, кибернетика и программирование

Вырожденные простейшие структуры данных называются также типами данных. Любая структура на абстрактном уровне может быть представлена в виде двойки DR где D – конечное множество элементов которые могут быть типами данных либо структурами данных а R – множество отношений свойства которого определяют различные типы структур данных на абстрактном уровне. СД типа массив. Массив – последовательность элементов одного типа называемого базовым.

Русский

2013-12-03

734.5 KB

20 чел.

Понятие о структуре данного.

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

Структура данного (СД) – общее свойство информационного объекта с которым взаимодействует та или иная программа. Это общее свойство характеризуется:

  1.  множеством допустимых значений данной структуры;
  2.  набором допустимых операций;
  3.  характером организованности.

Вырожденные (простейшие) структуры данных называются также типами данных.

Различают следующие уровни описания данного:

  1.  абстрактный (математический) уровень;
  2.  логический уровень;
  3.  физический уровень.

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

Любая структура на абстрактном уровне может быть представлена в виде двойки <D,R>, где D – конечное множество элементов, которые могут быть типами данных, либо структурами данных, а R – множество отношений, свойства которого определяют различные типы структур данных на абстрактном уровне.

Основные виды (типы) структур данных:

  1.  Множество – конечная совокупность элементов, у которой R=.
  2.  Последовательность – абстрактная структура, у которой множество R состоит из одного отношения линейного порядка (т. е. для каждого элемента, кроме первого и последнего, имеются предыдущий и последующий элементы).
  3.  Матрица – структура, у которой множество R состоит из двух отношений линейного порядка.
  4.  Дерево – множество R состоит из одного отношения иерархического порядка.
  5.  Граф – множество R состоит из одного отношения бинарного порядка.
  6.  Гиперграф – множество R состоит из двух и более отношений различного порядка.


Классификация СД в программах пользователя и в памяти ЭВМ

булевый

массив

таблица

деревья

целый

запись

стек

бинарные деревья

вещественный

рекурсивные типы

очередь

граф

символьный

множество

список

дек

указательный тип

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

Примеры СД:

Оперативная память представляет собой массив.

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

СД типа массив.

Массив – последовательность элементов одного типа, называемого базовым. На математическом языке массив – это функция с ограниченной областью определения. Структура массивов однородна. Для выделения отдельной компоненты массива используется индекс. Индекс – это значение специального типа, определенного как тип индекса данного массива. Поэтому на логическом уровне СД типа массив можно записать следующим образом:

type A = array [T1] of T2,

где Т1 – базовый тип массива, Т2 – тип индекса.

Если  DT1 – множество значений элементов типа Т1, DТ2 – множество значений элементов типа Т2, то А: DT1  DТ2 (отображение).

Кардинальное число Car(T) структуры типа Т – это множество значений, которое может принимать данная структура типа Т. Кардинальное число характеризует объем памяти, необходимый данной структуре. Для массива A: Car(A) = [Car(T2)] Car(T1).

Набор допустимых операций для СД типа массив:

  1.  Операция доступа (доступ к элементам массива – прямой; от размера структуры операция не зависит).
  2.  Операция присваивания.
  3.  Операция инициализации (определение начальных условий).

На физическом уровне СД типа массив представляет собой непрерывный участок памяти элементов одинакового объема. Участок памяти, необходимый для одного элемента называется слотом.

Var B: A {определяем переменную В как переменную типа массив А}

p  i  g, где p – индекс первого элемента массива, g – индекс последнего элемента массива, i – индекс рассматриваемого элемента.

Учитывая введенные обозначения, формула для вычисления размера слота одномерного массива выглядит следующим образом:

Adr(B[i]) = Adr(B[p]) + (i-p)S = Adr(B[p]) – p S + i S,

где S – количество слов, которое необходимо для одного элемента (зависит от типа элемента), Adr(B[p]) – p S является константой, а i S – переменная.

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

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

Var A: array [-5 .. 4] of Char

дескриптор будет выглядеть таким образом:

V

A

Adr (A[-5])

-5

4

Char

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

СД типа запись (прямое декартово произведение).

Запись – последовательность элементов, которые в общем случае могут быть одного типа. На логическом уровне СД типа запись можно записать следующим образом:

type Т = Record

S1: T1;

S2: T2;

……..

Sn: Tn;

End;

Здесь: Ti изменяется при i = 1, 2, …, n; S1, …, Sn – идентификаторы полей; Т1, …, Tn – типы данных. Если Ti также является в свою очередь записью, то Si – иерархическая запись.

Если  DT1 – множество значений элементов типа Т1, DТ2 – множество значений элементов типа Т2, … , DТn – множество значений элементов типа Тn, то DT – множество значений элементов типа Т будет определяться с помощью прямого декартова произведения:  DT = DT1  DT2  DТn. Другими словами, множество допустимых значений СД типа запись:

Допустимые операции для СД типа запись аналогичны операциям для СД типа массив.

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

Вообще, смещение – это адрес компоненты (поля) ri относительно начального адреса записи r. Смещение вычисляется следующим образом:

ki = S1 + S2 + … + Si-1,   i=1,2, …,n

где Si – размер слота каждого элемента записи.

Дескриптор СД типа запись, в отличие от дескриптора СД типа массив, зависит от количества элементов записи.

СД типа таблица.

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

Классификация СД типа таблица:

СД типа таблица

неупорядоченная таблица

упорядоченная таблица

хеш-таблица

как отображение на массив

как отображение на список

Если один элемент d i , то кортеж – это <d 1, d 2, …, d n>, причем D Ti  d i. Множество значений элементов типа Т (множество допустимых значений СД типа таблица) будет определяться с помощью прямого декартова произведения:

DT = DT1  DT2  DТn, причем D Ti  <d 1, d 2, …, d n>.

Сам же элемент таблицы можно представить в виде двойки <K, V>, где К – ключ, а V – тело элемента. В качестве ключа может быть разное число полей, которые определяют этот элемент. Ключ используется для операции доступа к элементу, так как каждый из ключей уникален для данного элемента. Таким образом, таблица является совокупностью двоек <K, V>.

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

Type Element = record

Key: integer;

{описание остальных полей}

end;

При реализации таблицы как отображения на массив ее описание выглядит так:

Tabl = array [0 .. N] of Element

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

Перед тем как определить операции, которые можно выполнять над таблицей рассмотрим классификацию операций:

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

Операции над таблицей:

  1.  Операция инициализации (конструктор).
  2.  Операция включения элемента в таблицу (модификатор).
  3.  Операция исключения элемента из таблицы (модификатор).
  4.  Операции-предикаты:

а) таблица пуста / таблица не пуста (наблюдатель)

б) таблица переполнена / таблица не переполнена (наблюдатель).

  1.  Чтение элемента по ключу (наблюдатель).

Временная сложность алгоритмов.

Временная сложность (ВС) – зависимость времени выполнения алгоритма от количества обрабатываемых входных данных. Здесь представляет интерес среднее и худшее время выполнения алгоритма. ВС можно установить с различной точностью. Наиболее точной оценкой является аналитическое выражение для функции:  t=t(N),  где t – время, N – количество входных данных (размерность). Данная функция называется функцией временной сложности (ФВС).

Например: t = 5N2 + 32N + 1. Такая оценка может быть сделана только для конкретной реализации алгоритма и на практике обычно не требуется. Часто бывает достаточно определить лишь порядок функции временной сложности t(N).

Две функции f1(N) и f2(N)одного порядка, если

Иначе это записывается в виде:  f1(N)=О(f2(N))  (Читается " О большое ").

Примеры определения порядка ВС для некоторых алгоритмов:

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

ФВС для алгоритма линейного поиска: t л. п. = k1  N = O(N). Действительно, для отыскания ключа в худшем случае придется просмотреть все элементы массива. При этом время проверки каждого элемента одинаково и не зависит от конкретной вычислительной системы.

Оценим среднее время алгоритма, при этом будем исходить из следующего: пусть P– вероятность того, что будет осуществляться поиск элемента с ключом ki; при этом предположим, что  , т.е. ключ со значением ki не будет отсутствовать (в таблице обязательно есть элемент, поиск которого осуществляется). Среднее время (), как следует из алгоритма, пропорционально среднему числу операций сравнения () и равно ~=. Если ключи имеют одинаковую вероятность P1=P2=...PN=P, а также учитывая, что, NP=1, P=1/N, тогда  ,

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

Рассмотрим упорядоченную таблицу, у которой элементы упорядочены по частоте обращений (по вероятности). Если имеем такую таблицу, то время – худшее:  = О(N).

Распределение осуществляется по закону Зипфа: Pi = c / i,  i = 1, 2, … , N, тогда ~=,

причем ,   (N  )

,  ln N – постоянная Эйлера.

Исходя из этого получили: с = 1 / ln N.

  1.  Алгоритм бинарного (двоичного) поиска. В словесной форме алгоритм двоичного поиска можно записать следующим образом:

1. Определить середину массива.

2. Если ключ, находящийся в середине массива, совпадает с искомым, поиск завершен.

3. Если ключ из середины массива больше искомого, применить двоичный поиск к первой половине массива.

4. Если ключ из середины массива меньше искомого, двоичный поиск необходимо применить ко второй половине массива.

5. Пункт 1-4 повторять, пока размер области поиска не уменьшается до нуля. Если это произойдет, то ключа в массиве нет.

ФВС для алгоритма бинарного поиска: t б. п. = O(log 2 N). Это объясняется тем, что на каждом шаге поиска вдвое уменьшается область поиска. До того, как она станет равной одному элементу, произойдет не более log 2 N таких уменьшений, т.е. выполняется не более log 2 N шагов алгоритма.

Изобразим графически функции ВС для линейного и двоичного поиска. Из графика видно, что для малых N нужно использовать линейный поиск, а для больших N — двоичный поиск. Nкр находятся в пределах 10 .. 1000 в зависимости от характеристик используемого оборудования.

СД типа хеш-таблица.

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

Операция включения элемента в таблицу.

Перед включением элемента в таблицу определяют его адрес с помощью хеш-функции: A = h(K), где K – ключ, а А – адрес элемента таблицы, причем  0 А  N-1, т.е. хеш-функция – отображение множества ключей на множество адресов.

A = K mod N = (C1  k + C2) mod N, где N – количество адресов в таблице.

“Хорошая” хеш-функция – это функция, которая быстро вычисляется и минимизирует количество коллизий. Коллизия – это ситуация, когда для разных ключей адрес один и тот же, т.е. h(ki) = h(kj), где i  j. Минимизации можно добиться, если равномерно распределить элементы по адресному полю таблицы.

После вычисления адреса элемента таблицы есть две возможности размещения элемента:

  1.  поместить этот элемент по адресу, если адрес свободен;
  2.  если вычисленный адрес занят, то повторить хеширование, т.е. совершить рехеширование по следующей формуле: A1 = (A+C) mod N.

Таким образом, алгоритм включения элемента в таблицу будет иметь следующий вид:

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

Чтобы процесс размещения элементов был равномерным, адресное поле таблицы делается больше множества ключей на 10-15%.

Операция исключения элемента из таблицы:

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

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

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

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

Если даны элементы а1, а2 ,…, аn, то сортировка означает перестановку этих элементов в массив ак1, ак2,…,акn где при заданной функции упорядочения f справедливы отношения  fк1)fк2)fкn). Обычно функция упорядочения f не вычисляется по какому-то специальному правилу, а является ключом элемента.

Метод сортировки называется устойчивым, если относительный порядок элементов с одинаковыми ключами не меняется при сортировке; неустойчивым – в противном случае.

Методы сортировки, в зависимости от лежащего в их основе приема, можно разбить на три базовых класса:

  1.  сортировка вставками;
  2.  сортировка выбором;
  3.  сортировка обменом.

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

Рассмотрим улучшенные методы сортировок:

1) Сортировка Шелла. – это улучшенный метод сортировки включениями. Был предложен Д.Л. Шеллом в 1959 г. Рассмотрим этот метод на примере.

Пример:

Первичный массив

ключей

X1

25

X2

57

X3

82

X4

63

X5

90

X6

75

X7

80

Просмотр 1

Шаг 5

Проходов 5

25

57

82

63

90

75

80

Просмотр 2

Шаг 3

Проходов 3

25

57

82

63

90

75

80

Просмотр 3

Шаг 1

Проходов 1

25

57

75

63

90

82

80

Отсортированный массив ключей

25

57

63

75

80

82

90

При первом просмотре группируются и сортируются элементы, отстоящие друг от друга на 5 позиций: (Х16), (Х2,Х7), (Х3), (Х4), (Х5); при втором проходе — элементы, отстоящие друг от друга на три позиции: (Х14,Х7), (Х2,Х5), (Х3,Х6); при третьем — на 1 позицию.

Поскольку первый в сортировке Шелла используемый шаг является большим, отдельные подмассивы достаточно малы по отношению к исходным. Таким образом, сортировка включением над этими подмассивами работает достаточно быстро – О(N2) (эффективно при малом N). Сортировка каждого подмассива приводит к тому, что весь массив становиться ближе к отсортированному виду, что также делает эффективным использование сортировки включением. Так как массив становится более упорядоченным, то О(N) < порядок ФBC < О(N2).

Если некоторый массив частично отсортирован с использованием шага k, а затем сортируется частично с использованием шага j, то данный массив остается частично отсортированным по шагу k, т.е. последующие частичные сортировки не нарушают результата предыдущих сортировок.

В случае правильного выбора шагов порядок ФВС будет выглядеть как О(N1.2). Д. Кнут предложил выбирать шаги из следующего ряда: 1, 4, 13, 40, 121, … , а вычислять их по следующей формуле: hk–1 = 3 hk +1;  ht = 1;  t = [log 3 N] – 1 (количество просмотров), где N – размерность исходного массива. Т.е. элементы должны быть взаимно простыми числами. Исходя из этого порядок сортировки может быть аппроксимирован величиной О(N(log 2 N)).

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

Пример:

k1

30

k2

10

k3

40

k4

20

k5

15

k6

17

k7

45

k8

60

10

20

15

45

10

15

10

10 – элемент MaxInt.

k1(N-1) – количество просмотров;  log 2 N – высота бинарного дерева.

Мы проходим от корня к листу по тому пути, по которому шел минимальный элемент (шаг 2). Затем осуществляем модификацию бинарного дерева. Общее количество модификаций:  k2log 2 N  (N-1).

Алгоритм быстрой сортировки выбором:

  1.  Сравниваем пары соседних ключей и запоминаем значение меньшего ключа из каждой пары.
  2.  Выполняем п.1 по отношению к значениям, полученным на предыдущем шаге. Так повторяем, пока не определим наименьший ключ и не построим бинарное дерево.
  3.  Вносим значение корня, найденное в п.2, в массив упорядоченных ключей.
  4.  Проходим от корня к листу дерева, следуя по пути, отмеченному минимальным ключом, и заменяем значение в листе на наибольшее целое число.
  5.  Проходим от листа к корню, по пути обновляя значения в узлах дерева, и определяем новый минимальный элемент.
  6.  Повторяем пп.3-6, пока минимальным элементом не будет MaxInt.

Анализ быстрой сортировки выбором.

k1(N-1)+ k2log 2 N(N-1) = О(N  log 2 N)  (ФВС = порядок)

2) Быстрая обменная сортировка (сортировка Хоара)  лучший из известных до сего времени метод сортировки массивов. Он обладает столь блестящими характеристиками, что его изобретатель Ч. Хоар окрестил его быстрой сортировкой. Быстрая сортировка основана на том факте, что для достижения наибольшей эффективности желательно производить обмены элементов на больших расстояниях.

Алгоритм быстрой обменной сортировки:

  1.  Выбираем первый ключ в таблице в качестве разделителя.
  2.  Располагаем ключи меньшие разделителя до него, а большие – после.
  3.  Если число ключей до разделителя больше 1, то применяем алгоритм в целом.
  4.  Если число ключей после разделителя больше 1, то применяем алгоритм в целом. Конец алгоритма.

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

П.2 выполняется следующим образом: просматриваем массив от краев к центру и меняем местами ключи, нарушающие порядок.

30

10

40

20

15

17

45

60

30

 (  10

17

20

15

40

45

60  )

……………………………………………………………………….

(  10

17

20

15  )

30

(  40

45

60  )

……………………………………………………………………….

Анализ сортировки Хоара.

  •  Количество элементов N = 2m , m = log 2 N, где N – количество элементов.
  •  Будем считать, что разделитель попадает в середину массива.

Подсчитаем количество сравнений:

Если воспользоваться алгоритмом на упорядоченную таблицу, то порядок будет O(N2).

Для определения разделителя имеются разные алгоритмы.

Классификация задач по временной сложности.

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

По временной сложности все задачи классифицируются следующим образом:

1 класс. Задачи класса Р – это задачи, для которых известен алгоритм и временная сложность оценивается полиномиальной функцией f(N) = a kN + a k-1N 2 +…+a 0N k+1. Алгоритмы таких задач называют также “хорошими” алгоритмами. Этих алгоритмов мало, они образуют небольшой по мощности класс. Легко реализуются. Функция временной сложности для таких алгоритмов имеет вид O(Nk).

2 класс. Задачи класса Е – это задачи, для которых алгоритм известен, но сложность таких алгоритмов O(f N), где f – константа. Задачи такого класса – это задачи построения всех подмножеств некоторого множества, задачи построения всех полных подграфов графа. При небольших N экспоненциальный алгоритм может работать быстрее полиномиального.

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

N

2

3

5

10

20

50

100

1000

1000N2

4 мкс

10 мкс

25 мкс

100 мкс

400 мкс

2.5 мс

10 мс

1 с

100N3

1 мкс

3 мкс

18.5 мкс

100 мкс

800 мкс

13 мс

100 мс

100 с

2N

4 мс

8 мс

30 мс

1 мкс

1 мс

10 сут.

Миллиарды лет

16 мс

250 мс

30 с

Миллиарды лет

СД типа стек.

Стек – это последовательность, в которой включение и исключение элемента осуществляется с одной стороны последовательности (вершины стека). Так же осуществляется и операция доступа. Структура функционирует по принципу LIFO (последний пришедший обслуживается первым). Условные обозначения стека:

При реализации стека рассматриваются стек как отображение на массив и стек как отображение на список.

Совокупность операций, определяющих структуру типа стек:

  1.  Операция инициализации.
  2.  Операция включения элемента в стек.
  3.  Операция исключения элемента из стека.
  4.  Операция проверки: стек пуст / стек не пуст.
  5.  Операция проверки: стек переполнен / стек не переполнен (данная операция характерна для стека как отображения на массив).
  6.  Операция чтения элемента (доступ к элементу).

Все операции не зависят от размерности стека, т.е. порядок временной сложности – О(1).

Имеется две модификации стека:

  1.  Указатель находится на вершине стека, показывая на первый пустой элемент.
  2.  

Указатель указывает на первый заполненный элемент.

Стек в последовательной памяти (схема на физическом уровне):

Дескриптор:

Условные обозначения

Название стека

Нижний адрес стека

Верхний адрес стека

Адрес указателя

Описание элемента

Применение стека:

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

Алгоритм сортировки Хоара (стек используется для хранения границ сортируемой области в таблице):

  1.  Включить в стек начало и конец сортируемой таблицы.
  2.  Исключить из стека адрес конца сортируемой области (В). Если стек пуст, то сортировка окончена.
  3.  Исключить из стека адрес начала сортируемой области (А).
  4.  Выбираем ключ-разделитель в сортируемой области (при этом используем тот или иной алгоритм).
  5.  Размещаем меньшие ключи до разделителя, а большие – после него. Адрес разделителя – С.
  6.  Если А < (С-1), то записываем в стек адрес А и (С-1).
  7.  Если (С+1) < В, то записываем в стек начало (С+1) и конец сортируемой области В и переходим к п.2.
  8.  Стек используется при разработке компиляторов.

Например, вычисление арифметических выражений. Имеем некоторое выражение: (А+В)С. Это выражение в инфиксной записи. Необходимо перевести его в постфикс (польскую запись): А В + С . С помощью стека выражение вычисляется за один проход.

Пример:  Имеем выражение (5 + 3) 7 + 2 4. Преобразуем его к виду 5 3 + 7 2 4 +

<    > - стек. Заносим в стек цифры и когда появляется операция, то выполняем ее над занесенными в стек элементами: <   > < 5 > < 5 3 > < 8 > < 8 7 >

  1.  Cтеки оказали влияние и на архитектуру ЭВМ, послужили основой для стековых машин. В такой ЭВМ аккумулятор выполнен в виде стека, позволяющего расширить спектр безадресных команд.
  2.  д, т.е. команд, не требующих явных заданий адресов операндов. Следствием использования стека является увеличение скорости обработки.

СД типа очередь.

Очередь – последовательность, в которую включают элементы с одной стороны, а исключают – с другой. Структура функционирует по принципу FIFO (поступивший первым обслуживается первым). Условные обозначения очереди:

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

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

  1.  Операция инициализации.
  2.  Операция включения элемента в очередь.
  3.  Операция исключения элемента из очереди.
  4.  Операция проверки: очередь пуста / очередь не пуста.
  5.  Операция проверки: очередь переполнена / очередь не переполнена.

В последовательной памяти очередь имеет следующий вид:

Здесь: Uk 1 – указатель на “голову” (начало) очереди, Uk 2 – указатель на “хвост” (конец) очереди.

Чтобы избежать переполнения, рациональней использовать кольцевую очередь. При этом Uk 1 > Uk 2 или Uk 2 > Uk 1. В случае же если очередь не кольцевая, то всегда Uk 2 > Uk 1. Если очередь пуста или переполнена, то Uk 1 = Uk 2.

Пусть n – текущее состояние очереди, а N – количество элементов в очереди, тогда имеем условие 0  n  N и значение n может являться условием проверки состояния очереди. Операция включения возможна, если n < N, а операция исключения, если n > 0. В случае кольцевой очереди при операции модуля указатели будут меняться следующим образом: Uk 1 = Uk 1 mod N + 1,   Uk 2 = Uk 2 mod N + 1.

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

Дескриптор:

Условные обозначения

Название очереди

Нижний адрес очереди

Верхний адрес очереди

Указатель начала очереди

Указатель конца очереди

Свойства элементов очереди

Применение очереди:

Очередь используется при передаче данных из оперативной во вторичную память (при этом происходит процедура буферизации: накапливается блок и передается во вторичную память). Наличие буфера обеспечивает независимость взаимодействия процессов между производителем и потребителем (ранжирование задач пользователя). Задачи разделяются по приоритетам: 1) задачи, решаемые в режиме реального времени (высший приоритет) (очередь 1); 2) задачи, решаемые в режиме разделения времени (очередь 2); задачи, решаемые в пакетном режиме (фоновые задачи) (очередь 3). Очереди выполняются последовательно.

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

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

  1.  Определенно неизвестно, сколько элементов будет иметь данная структура, т.е. нельзя сделать оценку.
  2.  Если мы рассматриваем некую последовательность элементов в последовательной памяти x1, x2, …, xn и необходимо включить какой-либо новый элемент x в эту последовательность, то мы должны осуществить массовую операцию сдвига всех элементов, находящихся за тем элементом последовательности, после которого мы хотим включить новый элемент. После вставим этот новый элемент x на освободившееся место. Таким образом, здесь проявляется свойство физической смежности.

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

СД типа линейный односвязный список.

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

Связный список

линейный

нелинейный

односвязный

двухсвязный

двухсвязный

многосвязный

циклический

нециклический

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

Операции, определяющие структуру типа линейный односвязный список:

  1.  Инициализация.
  2.  Включить элемент за рабочий указатель списка.
  3.  Исключить элемент, находящийся за рабочим указателем списка.
  4.  Передвинуть рабочий указатель на один шаг.
  5.  Проверка: список пуст / список не пуст.
  6.  Поместить рабочий указатель в начало списка (производная операция).
  7.  Поместить рабочий указатель в конец списка (производная операция).
  8.  Сделать список пустым.

При инициализации списка эффективно использовать реализацию следующей структуры:

Реализацию списка можно осуществить с помощью отображения на массив.

Рассмотрим операции включения и исключения элементов в общем случае. Введем следующие обозначения полей: Data – поле, куда записываются данные; Link – поле, где находится указатель на следующий элемент списка; Start – указатель на начало списка; Free – указатель указывающий на первый элемент свободного (рабочего) списка.

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

Операции включения и исключения от размерности списка не зависят.

Включение элемента в список:

  1.  Pntr = Free;
  2.  Free – Link(Pntr);
  3.  Data(Pntr) = { };
  4.  Link(Pntr) – Link(Ptr) {формируем указатель в новом элементе};
  5.  Link(Pntr) = Pntr {модификация указателя}.

Реализация списка в последовательной памяти.

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

Например:

D:

1

2

A

3

C

4

B

…...

N-1

N

L:

1

2

4

3

0

4

3

…...

N-1

N

D – массив, используемый для записи элементов, L – массив, используемый для записи указателей, 0 – указатель конца списка.

D:

1

2

3

4

…...

N-1

N

L:

1

1

2

3

3

4

4

5

…...

N-1

N

N

2

Будем считать, что: [1] будет указывать на первый элемент функционального списка, [2] – на первый элемент свободного списка.

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

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

СД типа указатель.

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

Type <тип указателя> = ^ <тип указываемого объекта> 

(этот тип разрешает использовать базовый тип перед описанием)

Type PtrType = ^BaseType;

BaseType = record

x, y: real;

end;

Var  A: PtrType; {А – переменная статического типа, значением которой являются адреса расположения в памяти конкретных значений заданного типа}

B: BaseType;

C: ^PtrType;

Переменной А можно присвоить адрес какой-либо переменной, для чего используем унарную операцию взятия указателя: А = @ В.

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

Операции над указательным типом:

  1.  Операция сравнения на равенство: = (равенство, если совпадают адреса сегмента и смещения).
  2.  Операция сравнения на неравенство: <>.
  3.  Операция доступа: B. x = B. X + 3. Доступ с помощью разыменования: A^. X=A^. X+3. Краткая операция разыменования: С^^. x.

Среди всех возможных указателей выделяется один специальный указатель, который никуда не указывает. Т.е. в памяти выделяется один адрес, в который не записывается ни одна переменная. На это место в памяти и ссылается такой пустой или “нулевой” указатель, который обозначается nil. Указатель nil считается константой, совместимой с любым ссылочным типом, т.е. это значение можно присваивать любому указательному типу.

Статические и динамические переменные.

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

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

Рассмотрим распределение памяти:

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

Образование и уничтожение динамических переменных.

Основные действия над динамическими переменными – создание и уничтожение – реализуются стандартными процедурами New и Dispose.

New (<имя ссылки>): point; - процедура предназначена для создания динамических переменных определенного типа (другими словами, для отведения памяти в куче для хранения значений динамической переменной).

Dispose (<имя ссылки>): point; - процедура используется для освобождения памяти, отведенной с помощью процедуры New.

MaxAvail: longint; - функция возвращает максимальный размер (в байтах) непрерывного свободного участка кучи. Применение данной процедуры необходимо для контроля динамической памяти при реализации операции включения.

Например:  if MaxAvail > SizeOf (BaseType) then {генерируем объект}

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

MemAvail: longint; - функция возвращает общее количество свободной памяти.

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

СД типа циклический линейный список.

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

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

СД типа двусвязный линейный список.

В списке такого типа указатель можно перемещать как в одну, так и в другую сторону.

Дескриптор данной структуры состоит из трех полей указательного типа:

Допустимые операции:

  1.  инициализация;
  2.  сделать список пустым:
  3.  проверка: список пуст / список не пуст;
  4.  установить указатель в конец списка / начало списка (две отдельные процедуры);
  5.  передвинуть указатель вперед / назад на один шаг;
  6.  включить элемент в список до указателя / после указателя;
  7.  исключить элемент из списка до указателя / после указателя.

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

  1.  список пуст;
  2.  включение элемента в середину списка;
  3.  включение элемента в список в качестве первого.

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

 

СД типа дек.

Дек – линейная структура (последовательность) в которой операции включения и исключения элементов могут выполняться как с одного, так и с другого конца последовательности.

Допустимые операции:

  1.  инициализация;
  2.  проверка: дек пуст / дек не пуст;
  3.  включение элемента в начало / конец дека;
  4.  исключение элемента из начала / конца дека.

Многосвязные списки.

В общем случае число указателей может быть произвольным. В результате такого обобщения мы получаем многосвязный список. Рассмотрим несколько примеров таких списков.

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

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

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

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

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

СРЕДСТВА ОБЪЕКТНО-ОРИЕНТИРОВАННОГО ПРОГРАММИРОВАНИЯ.

Вообще существует несколько стилей программирования: структурное, логическое, функциональное, объектное.

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

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

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

Объекты и свойства инкапсуляции.

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

Type Point = Object

x, y: integer; {координаты точки}

v: boolean; {видимость точки}

end;

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

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

  1.  операция инициализации точки (установка значений координат);
  2.  операция включения точки;
  3.  операция выключенияточки;
  4.  операция перемещения точки;
  5.  получение текущей координаты X точки;
  6.  получение текущей координаты Y точки.

Подпрограммы, определенные в объектовом типе, называются методами объекта. Вообще, объектовый тип на языке Turbo Pascal имеет следующий вид:

Type <имя объекта> = Object

<поля данных>

<заголовки методов>

end;

Технически в языке Turbo Pascal определение подпрограмм в объектовых типах делается следующим образом: непосредственно в объектовом типе задаются только заголовки подпрограмм-методов, а полные их описания должны быть заданы отдельно, причем имя подпрограммы-метода формируется из имени объектового типа-“хозяина”, символа “точка” и имени подпрограммы, например:

Type Point =Object

x, y: integer;

v: boolean;

Procedure Init (a, b: integer);

Procedure SwitchOn;

Procedure SwitchOff;

Procedure Move (dx, dy: integer);

Function GetX: integer;

Function GetY: integer;

End;

Procedure Point.Init (a, b: integer);

begin

x:=a;  y:=b;

v:=false;

end;

Procedure Point.SwitchOn;

begin

v:=true;

PutPixel (x, y, GetColor);

end;

……………………..

Procedure Point.GetY;

begin

GetY:=y;

end;

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

Var ObPoint: Point; {определяем экземпляр объекта}

begin

ObPoint.Init (30, 40); {выполнили инициализацию экземпляра}

…………………….

Для объектовых типов допускается использование оператора присоединения. Например, для вышеописанного примера:

with ObPoint do 

begin

Init (30, 40);

………..….

end;

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

Замечания:

  1.  Не рекомендуется обращаться к полям данных объекта непосредственно. Это считается отступлением от объектно-ориентированного стиля, согласно которому все действия с объектом осуществляются только посредством его методов.
  2.  На первый взгляд, объектовый тип похож на модуль. Однако в языке Turbo Pascal модуль рассматривается как часть программы, оформленная в виде отдельно хранящейся и раздельно компилируемой конструкции; нельзя, например, определить переменную модульного типа. В отличие от этого, определив некоторый объектовый тип, можно создавать произвольное число переменных этого типа.
  3.  Объект может содержать несколько десятков методов, но в результирующий код попадут только те методы, которые используются в данной программе пользователя.

Наследование и переопределение.

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

Type Circle = Object (Point)

Radius: integer;

end;

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

Var ObCircle: Circle;

begin

ObCircle.Init (30, 40);

…………………….

Таким образом, наследование на языке Turbo Pascal может быть описано таким образом:

Type <имя нового объекта> = Object (имя объекта-родителя)

< новые поля данных>

<новые методы потомка>

end;

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

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

Type Circle =Object (Point)

Radius: integer;

Procedure Init (a, b, R: integer);

Procedure SwitchOn;

Procedure SwitchOff;

Procedure Move (dx, dy: integer);

Function GetR: integer;

End;

Procedure Circle.Init (a, b, R: integer);

begin

Point.Init (a, b);

Radius:=R;

end;

…………………………..

Procedure Circle.SwitchOn;

begin

v:=true;

Graph.Circle (x, y, R);

end;

…………………………

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

<родитель>::=<наследник>

При этом копируются только те поля, которые являются общими для обоих типов.

Как правило, основная часть работы по написанию объектно-ориентированных программ состоит в построении иерархии объектов.

Полиморфизм. Виртуальные методы.

Имеем описания двух объектовых типов:

Type Point =Object

x, y: integer;

v: boolean;

Procedure Init (a, b: integer);

Procedure SwitchOn;

Procedure SwitchOff;

Procedure Move (dx, dy: integer);

Function GetX: integer;

Function GetY: integer;

End;

Type Circle =Object (Point)

Radius: integer;

Procedure Init (a, b, R: integer);

Procedure SwitchOn;

Procedure SwitchOff;

Procedure Move (dx, dy: integer);

Function GetR: integer;

End;

Алгоритм метода Move похож для обоих типов, поэтому определим его для объектового типа Point, а тип-потомок Circle унаследует его без переопределения:

Procedure Move (dx, dy: integer);

begin

SwitchOff;

x:=x+dx;  y:=y+dy;

SwitchOn;

end;

Имеем экземпляры двух объектов рассматриваемых типов:

Var ObPoint: Point;

ObCircle: Circle;

В случае такого описания объектовых типов при выполнении следующих двух сообщений: ObPoint.Move (20, 30); ObCircle.Move (10, 15); возникает коллизия. Причиной ее является то, что унаследованный метод Move жестко связан с методом Point, поэтому метод Move всегда будет вызывать метод Point.SwitchOff. Связь этих методов является статической, т.к. она была определена при компиляции. Таким образом, при выполнении сообщения ObCircle.Move (10, 15); на экране также будет перемещаться точка, а не круг.

Таким образом, если мы имеем один метод для различных объектов, то необходимо разорвать статическую связь, а также обеспечить возможность для Move подключать либо метод Point.SwitchOff, либо метод Circle.SwitchOff в зависимости от того, какой объект вызывает Move. Такой механизм называется динамическим или поздним связыванием и достигается с помощью применения виртуальных методов.

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

Type Point =Object

…………………….

Constructor Init (a, b: integer);

Procedure SwitchOn; virtual;

Procedure SwitchOff; virtual;

Procedure Move (dx, dy: integer);

…………………….

End;

Type Circle =Object (Point)

…………………….

Constructor Init (a, b, R: integer);

Procedure SwitchOn; virtual;

Procedure SwitchOff; virtual;

…………………….

End;

В этом случае, при выполнении цепочки вызовов ObPoint.Move (20, 30); ObCircle.Move (10, 15); один и тот же метод Move будет работать по-разному в зависимости от того, какой объект этот метод вызывает. Такое свойство называется полиморфизмом.

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

  1.  Если родительский тип объекта описывает метод как виртуальный, то все его производные типы, которые реализуют метод с тем же именем, тоже описываются как виртуальные (т.е. нельзя виртуальный метод заменять статическим).
  2.  Если переопределяется реализация виртуального метода, то заголовок заново определяемого виртуального метода в производном типе или объекте не может быть изменен.
  3.  В описании объекта должен обязательно описываться специальный метод (обычно это метод, выполняемый первым – метод инициализации). Слово Procedure, при этом, заменяется ключевым словом Constructor. Это особый вид процедуры, определяющий установочную функцию для механизма виртуальных методов. Суть механизма виртуальных методов состоит в том, что каждый объектный тип (но не экземпляр) имеет свою таблицу виртуальных методов ,которая содержит размер объекта и адреса кодов виртуальных методов. При вызове виртуального метода каким-либо экземпляром местонахождение кода определяется по таблице. Конструктор же определяет связь между экземпляром объекта и таблицей виртуальных методов. Конструкторы могут быть только статическими, хотя внутри его могут быть использованы виртуальные методы.

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

Динамические объекты. Деструкторы.

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

Var <имя ссылки на объект>^. <тип объекта>

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

Var ObCirclePtr: ^Circle;

begin

New (ObCirclePtr);

ObCirclePtr^.Init (20, 30, 10);

………………………

В целях большей наглядности Turbo Pascal допускает совмещение порождения объекта и его инициализации конструктором в одном вызове New:

New (ObCirclePtr, Init (20, 30, 10));

Освобождение динамической памяти, выделенной объекту, реализуется стандартной процедурой Dispose: Dispose (<имя ссылки на объект>);

Необходимо учесть, что если поля данных объекта были динамическими и для них выделялась дополнительная память, то их надо освободить до уничтожения самого объекта. Для этих целей или для других завершающих действий перед уничтожением вводится специальный вид метода – деструктор. Он объявляется среди прочих методов с помощью замены ключевого слова Procedure на служебное слово Destructor. Функции деструктора по сути противоположны функциям конструктора. Действие завершается ключевым словом Done. Деструкторы могут наследоваться, при этом желательно делать их виртуальными, чтобы выполнялся тот деструктор, который соответствует именно этому типу объекта.

Имеется также расширенная возможность использования процедуры уничтожения: Dispose (<имя ссылки на объект>, <имя деструктора>); При этом вначале выполняется деструктор, а затем объект уничтожается.

Если объект содержит виртуальные методы, то деструктор осуществляет поиск размера объекта, т.е. того участка памяти, который нужно уничтожить. Чтобы выполнение уничтожения было корректным, используют пустой блок: Begin   End;

Обработка ошибок при работе с динамическими объектами.

HeapError – системная переменная, имеющая указательный тип pointer. Она указывает на функцию:

HeapError := @HeapFunc;

Function HeapFunc (Size: word): integer;

Данная функция вызывается каждый раз, когда работают процедуры генерирования динамического объекта, и когда не может быть выполнен запрос на распределение объекта. Здесь Size указывает на то, какой блок памяти не может разместиться в динамической памяти. В качестве результата функция возвращает значения 0, 1 или 2. Если функция возвращает значение 0, то осуществляется аварийный останов. Если значение 1, то при выполнении процедуры New (P) ссылка на объект принимает значение константы. Если значение 2, то вызов повторяется.

{$F+}

Function HeapFunc (Size: word): integer;

begin

HeapFunc:=1;

end;

{$F-}

New (P);

if  P = nil then <обработка исключительной ситуации>

else <нормальный ход программы>

Таким образом, если мы имеем расширенные процедуры генерирования объекта (New (<>,<>)), необходимо учитывать следующее: когда начинает выполняться тело конструктора, то при выполнении алгоритма может потребоваться дополнительная память. В этом случае мы должны сделать откат, т.е. отменить все проделанные распределения в конструкторе и, в завершение, освободить экземпляр типа объекта. Ссылка должна получить значение константы. Для выполнения отката используется стандартная процедура Fail, располагающаяся в конструкторе. Вызов этой процедуры освобождает динамический экземпляр, который был размещен в памяти до входа в конструктор, и возвращает в ссылке значение nil.

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

Модули, экспортирующие объекты.

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

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

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

СД типа дерево.

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

  1.  Имеется один специально обозначенный узел, называемый корнем данного дерева.
  2.  Остальные узлы (исключая корень) содержатся в m>=0 попарно не пересекающихся множествах Т1, Т2, …, Тm, каждое из которых в свою очередь является деревом. Деревья Т1, Т2, …, Тm называются поддеревьями данного корня.

Рассмотрим один из способов изображения структуры дерева:

Если подмножества Т1, Т2, …, Тm упорядочены, то дерево называют упорядоченным. Если два дерева считаются равными и тогда, когда они отличаются порядком, то такие деревья называются ориентированными деревьями. Конечное множество непересекающихся деревьев называется лесом.

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

Количество подмножеств для данного узла называется степенью узла. Если такое количество равно нулю, то узел является листом. Максимальная степень узла в дереве – степень дерева. Уровень узла – длина пути от корня до рассматриваемого узла. Максимальный уровень дерева – высота дерева.

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

Представление деревьев в связной памяти ЭВМ.

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

Алгоритмы прохождения деревьев в глубину и в ширину.

Алгоритм прохождения дерева в глубину:

<пустой стек S>;

<пройти корень и включить его в стек S>;

while <стек S не пуст> do

begin  {пусть P – узел, находящийся в вершине стека S}

if <не все сыновья узла Р пройдены>

then <пройти старшего сына и включить его в стек S>

else begin

<исключить из вершины стека узел Р>;

if <не все братья вершины Р пройдены>

then <пройти старшего брата и включить его в стек S>

end;

end;

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

A,  B, C, D, E,    F, G, H, I, J,    K.

Алгоритм прохождения дерева в ширину:

<взять две очереди О1 и О2>;

<поместить корень в очередь О1>;

while <О1 или О2 не пуста> do 

if <О1 не пуста> then {Р – узел, находящийся в голове очереди О1}

begin

<исключить узел из очереди О1 и пройти его>;

<поместить все узлы, относящиеся к братьям этого узла Р в очередь О2>;

end

else <O1=O2; O2=> и повторяем цикл.

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

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

  1.  изображаем корень дерева;
  2.  по вертикали изображаем старшего сына этого корня;
  3.  по горизонтали вправо от этого узла представляем всех его братьев;
  4.  пп. 1, 2, 3 повторяем для всех его узлов.

Теорема. Число бинарных деревьев с n вершинами можно выразить формулой: . Например, для n=3 имеем

Проиллюстрируем этот пример графически:

Представление бинарных деревьев в связной памяти.

Прошитые деревья

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

Если мы воспользуемся прошитым бинарным деревом, то вид узла для него будет таким:

Один из возможных способов прошивки бинарного дерева заключается в том, что для каждого узла, не имеющего левого поддерева, запоминается ссылка на непосредственного предшественника, а для каждого узла, не имеющего правого поддерева ,запоминается ссылка на его непосредственного преемника. Предшественников и преемников для узла определяют исходя из списка, который получается при прохождении рассматриваемого бинарного дерева в симметричном порядке. Для того, чтобы отличать ссылку на левого или правого сына (такие ссылки называют структурными связями) от ссылки на предшественника или преемника узла (такие ссылки называют “нитями”), используются индикаторные поля LP и RP.

Пример. Рассмотрим бинарное дерево:

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

Формирование бинарного дерева.

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

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

  1.  взять один узел в качестве корня;
  2.  построить левое поддерево с количеством узлов n l = [n / 2] тем же способом;
  3.  построить правое поддерево с количеством узлов n r = nn l – 1 тем же способом.

Описание узла дерева на языке Turbo Pascal выглядит таким образом:

Type ElPtr = ^Element

Element = record

Data: integer;

L_Son, R_Son: ElPtr;

end;

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

Function Tree (n: integer): ElPtr;

var nl, nr, x: integer;

NewElement: ElPtr;

begin

if n=0 then Tree:=nil

else begin

nl:=n div 2;

nr:=n – nl – 1;

read (x); New (NewElement);

with NewElement do begin

Data:=x;

L_Son:=Tree (nl);

R_Son:=Tree )nr);

end;

Tree:=NewElement;

end;

end;

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

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

В односвязном списке невозможно использовать бинарные методы, они могут использоваться только в последовательной памяти. Однако, если использовать бинарные деревья, то в такой связной структуре можно получить алгоритм поиска со сложностью O(log 2 N). Такое дерево реализуется следующим образом: для любого узла дерева с ключом Ti все ключи в левом поддереве должны быть меньше Ti, а в правом – больше Ti. В дереве поиска можно найти место каждого ключа, двигаясь, начиная от корня и переходя на левое или правое поддерево, в зависимости от значения его ключа. Из n элементов можно организовать бинарное дерево (идеально сбалансированное) с высотой не более чем log 2 N, которое определяет количество операций сравнения при поиске.

Function Search (x: integer; t: ElPtr): ElPtr;

{поле Data заменим на поле Key}

var f: boolean;

begin

f:=false;

while (t<>nil) and not f do

if x=t^. key then f:=true

else if x>t^. key then t:=t^. R_Son else t:=t^. L_Son;

Search:=t;

end;

Если получим, что значение функции = nil, то ключа со значением x в дереве не найдено.

Function Search (x: integer; t: ElPtr): ElPtr;

begin

S^.key:=x;

while t^.key<>x do

if x > t^.key then then t:=t^. R_Son else t:=t^. L_Son;

Search:=t;

end;

Операция включения в СД типа бинарное дерево.

Рассмотрим случай постоянно растущего, но никогда не убывающего дерева. Хорошим примером этого является построение частотного словаря. В этой задаче задана последовательность слов и нужно установить число появления каждого слова. Это означает, что, начиная с пустого дерева, каждое слово, встречающееся в тексте, ищется в нем. Если это слово найдено, то счетчик появления данного слова увеличивается; если же слово не найдено, то в дерево включается новое слово со значением счетчика = 1.

Type ElPtr = ^Element

Element = record

Key: integer;

n: integer;

L_Son, R_Son: ElPtr;

end;

Procedure Put (x: integer; var t: ElPtr);

begin

if t=nil then begin

New(t);

with t^  do begin

key:=x;  n:=1;  L_Son:=nil;  R_Son:=nil;

end;

end

else if x> t^.key then Put(x, t^.R_Son)

else if x<t^.key then Put(x, t^.L_Son)

else t^.n:=t^.n+1;

end;

Хотя задача этого алгоритма – поиск с включением, но его можно использовать и для сортировки, т.к. он напоминает сортировку с включением. А так как вместо массива используется дерево, то пропадает необходимость перемещения элементов выше места включения. Для того, чтобы сортировка этого алгоритма была устойчивой, алгоритм должен выполняться одинаково как при t^.key=x, так и при t^.key>x.

Анализ алгоритма поиска. Если дерево вырождается в последовательность то сложность в таком случае O(N) (в худшем случае). В лучшем же случае, если дерево сбалансировано, то сложность будет O(log 2 N). Таким образом, имеем:

O(N) ПФВС  O(log 2 N).

Если считать, что вероятность появления любой структуры дерева одинакова, и ключи появляются с одинаковой вероятностью, то .

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

Операция исключения из бинарного дерева.

При удалении узла дерево должно оставаться упорядоченным относительно ключа:

а) удаляется лист;

б) удаляется узел с одним потомком (потомок слева или справа);

в) удаляется узел с двумя потомками, но в левом потомке нет правого поддерева;

г) общий случай.

Рассмотрим случай б):

if g^.L_Son=nil then begin

g:=t;

t:=t^.R_Son;

dispose(g);

end;

if g^.R_Son=nil then begin

g:=t;

t:=t^.L_Son;

dispose(g);

end;

Случай а) является частным случаем этого алгоритма.

Случай в):  r указывает на элемент, не имеющий правого поддерева.

g:=t;

g^.key:=r^.key;

g:=r;

r:=r^.L_Son;

dispose(g);

Случай г):

Procedure Get (x: integer; var t: ElPtr);

var g: ElPtr;

begin

if t=nil then {обработка исключительной ситуации, когда элемента с заданным ключом в дереве нет}

else if x>t^.key then Get(x, t^.R_Son)

else if x<t^.key then Get(x, t^.L_Son)

else begin

g:=t;

if g^.L_Son=nil then t:=g^.R_Son

else if g^.R_Son=nil then t:=g^.R_Son

else D(g^.L_Son); {найти r)

dispose(g);

end;

end;

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

При представлении дерева в прямоугольной памяти одно из полей R_Son или L_Son удаляется, т.к. необходимость в нем отпадает. Потомок может размещаться рядом, т.е. в непосредственной близости. Чтобы узнать, есть ли потомок, вводится булево поле L или R. Пусть, например, отсутствует левый потомок. Введем следующие переменные:

index = 0..max;

type Element = record

R_Son: index;

Data: BaseType;

L: boolean;

end;

var Tree = array [index] of Element;

a

b

c

f

g

d

e

h

T

F

T

F

F

1

2

3

4

5

6

7

8

Применение бинарных деревьев.

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

ассмотрим пример: 3 (x – 2) + 4.

Если же осуществить просмотр дерева в обратном порядке (левое поддерево, правое поддерево, корень), то получим обратную польскую запись.

  1.  Классическая программа из класса интеллектуальных: построение деревьев решений. В этом случае не листовые (внутренние) узлы содержат предикаты – вопросы, ответы на которые могут принимать значения “да” или “нет”. На уровне листьев находятся объекты (альтернативы, с помощью которых распознаются программы). Пользователь получает вопросы, начиная с корня, и, в зависимости от ответа, спускается либо на левое поддерево, либо на правое. Таким образом, он выходит на тот объект, который соответствует совокупности ответов на вопрос.
  2.  Применение практических задач.

СД типа граф.

Граф – двойка G = (X, U), где X – множество элементов (вершин, узлов), а U представляет собой бинарное отношение на множестве X (U  XX). Если |X| = n (конечно), то граф является конечным. Элементы U называют либо дугами, либо ребрами.

Если (Xi, Xj) – упорядоченная пара, то такой граф называется ориентированным (орграфом), а элементы U называются дугами. Если (Xi, Xj) = (Xj, Xi), то граф – неориентированный (неорграф), а элементы U называются ребрами.

F: U  R – если задана такая функция, то граф является взвешенным, где R – множество вещественных чисел, т.е. отображение дуги на число.

Вообще:  U  X  X.

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

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

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

Представление графа в памяти ЭВМ.

  1.  Графический способ представления (если граф небольшой).
  2.  Использование матриц. Матрица легко описывается и при анализе характеристик графа можно использовать алгоритмы линейной алгебры. Также используется представление графа в связной памяти, в том случае, если большее количество элементов в матрице равно нулю (матрица не заполнена).

Числовыми характеристиками графа являются: количество узлов, количество дуг, ранг графа. Ранг графа: R(G) = |X| - K, где К – количество компонентов связности графа в случае, если но не связан.

Рассмотрим матрицу смежности. Пусть задан граф G = (X, U), |X| = n. Имеем матрицу А размерности n  n, которая называется матрицей смежности, если элементы ее определяются следующим образом:

Рассмотрим применение матричной алгебры для определения характеристик графа. Выражение a i k  a k j означает, что между узлами i и j есть две дуги, проходящие через узел k, если значение выражения равно True.

Выражение  означает, что всегда имеется путь между этими узлами длиною 2 (два), если выражение истинно.

А  А = А(2) – логические операции заменяются арифметическими. Тогда каждый элемент a i j будет давать информацию о том, есть ли путь из i в j (i, j = 1, 2,…,n).

Выражение А(n) = А(n – 1)  А означает, есть ли путь длиной n между различными узлами i. По диагонали будет характеристика, есть ли циклы (контура) в матрице.

Р = А А(2) А(n) =  - матрица связности. Определяется, существует ли какой-либо путь между узлами i и j. Алгоритм вычисления данного выражения:

  1.  Р = А;
  2.  повторить 3, 4 (k=1, 2,…, n);
  3.  повторить 4 для i=1, 2, …,n;
  4.  повторить Рi j = Рi j V i k  Рk j), j=1, 2,…, n.

В связной памяти наиболее часто представление графа осуществляется с помощью структур смежности. Для каждой вершины множества X задается множество М(X i) соответственно вех его последователей (если это орграф) или соседей (для неорграфа). Таким образом, структура смежности графа G будет представлять собой список таких множеств: < М(X 1), М(X 2),…, М(X n)> для всех его вершин.

Рассмотрим пример (узлы обозначаем в виде цифр: 1, 2,…, n):

Структуру смежности можно реализовать массивом из n линейно связанных списков:

Представление графа может оказать влияние на эффективность алгоритма. Часто запись алгоритмов на графах задается в терминах вершин и дуг, независимо от представления графа. Например, алгоритм определения количества последователей вершин: (X)   Xi, S – количество дуг.

= 0;

 x  X выполнить:

начало

С(x)=0;

 t  M(x) выполнить: C(x) = C(x) + 1;

= S + C(x);

конец;

Алгоритмы прохождения графа.

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

Имеем граф G = (X, U), X = {x1, x2,…, xn}. Каждое прохождение можно рассматривать как определенную последовательность. Максимальное число прохождений (перестановок) – n!.

Алгоритм прохождения графа в глубину:

  1.  

Определим списки смежности для каждой вершины графа G:

1: 2,  3, 5 2: 1,  3,  4 3: 1, 2,   4,    5   4: 2, 3   5: 1,3

t: 1, 2, 3, 4, 5

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

Для каждого выбора начальной вершины в связном графе может быть получено единственное прохождение. Если граф представляет собой объединение компонент:  и  | x i | = n i , то количество прохождений такого несвязного графа: 1  n 2    n р ( i = 1, 2,…, p).

Пусть граф G = (X, U) задан структурой смежности < М(x 1), М(x 2),…, М(x n)>. Определим Num(x) как массив для регистрации посещений вершин (Num(x)=1, если вершина не посещалась; Num(x)=0, если вершина посещалась). Тогда алгоритм прохождения графа в глубину будет выглядеть так:

 x  X выполнить Num(x)=1;

 x  X выполнить: если Num(x)=1, то D(x);

Процедура D(x);

начало

R(V);

Num(V)=0;

 t  M(V) выполнить: если Num(t)=1, то D(t);

конец;

Алгоритм прохождения графа в ширину:

Определим списки смежности для каждой вершины графа G:

1: 2, 3, 5 2: 1,  3,  4 3: 1, 2, 4, 5   4: 2, 3  5: 1,3

t: 1, 2, 3, 4, 5 (для выбранной вершины переписываем весь список смежности).

Выберем начальную вершину н. Первые элементы искомой перестановки t являются элементами смежного списка вершины н, т.е. M(н). Обозначим список смежности следующим образом: M(н) = {(w1, xн), (w2, xн),…,(wk, xн)}. Следующими элементами перестановки будут те элементы их M(w1), которые отсутствуют в формируемой перестановке t. Затем, берем все элементы из M(w2), и т.д. обход прекращается, когда все вершины, достижимые из н, будут содержаться в t (wi  X, i=1, 2,…, k).

Топологическая сортировка.

Топологическая сортировка (ТС) вершин орграфа G заключается в присвоении его вершинам чисел 1, 2,…, | x |, причем должно выполняться следующее условие для орграфов: если имеется дуга (xi, xj), то > i ( j).

Рассмотрим случай для ацикличного графа:

  1.  

Топологическая сортировка может быть использована:

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

Рассмотрим алгоритм топологической сортировки. Идея его заключается в том, что осуществляется поиск такой вершины, из которой не выходит ни одна дуга. Такой вершине присваивается | x |. Затем эту вершину выбрасывают вместе с дугами и опять осуществляют поиск на | x | - 1, …

Введем массив LABEL размерностью | x |. Он будет обладать следующими свойствами: если вершина не выброшена, то значение LABEL(x)=0; если есть дуга (xi, xj), то LABEL(j) > LABEL(i).

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

 x  X выполнить: (Num(x)=1; LABEL(x)=0;)

= | x | + 1;

 x  X выполнить: если Num(x)=1, то DM(x);

Процедура DM(v);

начало

Num(V)=0;

 t  M(V) выполнить: если Num(t)=1, то DM(t);

конец;

= C  1;

LABEL(V) = C;

ОРГАНИЗАЦИЯ ДАННЫХ ВО ВНЕШНЕЙ ПАМЯТИ.

Типы и характеристики устройств внешней памяти.

Все рассмотренные ранее СД относятся к оперативным структурам, т.к. их формирование и обработка происходит в основной памяти. В современных вычислительных системах существует иерархия уровней памяти. Сюда входят: регистры процессора, сверхоперативная память (КЭШ-память), основная память, вторичная память и архивная память.

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

Основными характеристиками устройств внешней памяти являются:

  1.  емкость;
  2.  время доступа;
  3.  скорость передачи данных;
  4.  форма доступа;
  5.  экономическая характеристика (стоимость хранения в расчете на одну единицу данных).

Время доступа – длительность интервала времени от момента инициирования операции ввода / вывода, до начала передачи данных. Скорость передачи данных измеряется числом единиц данных, передаваемых между устройствами внешней и основной памяти (1 бод = 1 символ / 1 c). Форма доступа – порядок, в котором можно записывать или читать из устройства внешней памяти. Доступ может быть последовательным, прямым, и т.д. При прямом доступе время доступа не зависит от размерности структуры.

Накопители на магнитных дисках.

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

Рассмотрим структуру диска:

Корневой каталог содержит: имя файла, номер первого кластера. Кластер – минимальная порция информации, включающая несколько сегментов.

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

Файл на физическом уровне – наименованная область памяти на внешнем носителе (динамическая последовательность кластеров). Файл на логическом уровне – линейная динамическая структура.

СД типа последовательный файл.

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

Основные операции над СД типа последовательный файл:

  1.  инициализация;
  2.  обработка данных без их изменения;
  3.  модификация файла.

Инициализация файла:

  1.  присвоить файлу имя;
  2.  открытие нового файла (формируется буфер, и указатель принимает значение 0);
  3.  подготовка данных;
  4.  запись компоненты (указатель перемещается на 1);
  5.  закрытие файла (формируется маркер конца файла).

Обработка данных:

  1.  задание имени файла;
  2.  открыть сформированный файл (с помощью процедуры Reset);
  3.  прочитать данные, сделать обработку;
  4.  закрыть файл.

Модификация файла (добавление новых компонент, изменение существующих компонент):

  1.  присвоить имя;
  2.  открыть файл;
  3.  установить указатель на следующую после последней записи компоненту (использовать для этого процедуру  Seek (<файловая переменная>, FileSize(<файловая переменная>)));
  4.  подготовка данных;
  5.  запись;
  6.  закрыть файл.

СД типа файл прямого доступа.

Файл прямого доступа используется, если есть ограничение на время доступа к информации.

Основные операции над СД типа последовательный файл:

  1.  инициализация;
  2.  обработка данных;
  3.  модификация..

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

Обработка данных:

  1.  присвоить файлу имя;
  2.  открыть сформированный файл;
  3.  запросить ключ;
  4.  установить указатель с использованием информации о нахождении ключа;
  5.  прочитать;
  6.  закрыть файл.

Модификация (изменение записи):

  1.  присвоить имя;
  2.  открыть сформированный файл, запросить ключ;
  3.  подвести указатель к нужной записи;
  4.  обработать компоненту;
  5.  опять подвести указатель к нужной компоненте;
  6.  записать;
  7.  закрыть файл.

В более сложном случае:

  1.  С помощью какого-либо алгоритма обработать ключ, вытекающий из какой-либо предметной области и вычислить адрес. Алгоритм определения места ключа в файле осуществляет отображение шифров на адреса. Это отображение 1:1. Сложность состоит в определении функции отображения Ф(к).

Пример: Имеем g=6, n=13, где g – номер класса (g=1, 2,…, 10), n – номер по списку в журнале (n=1, 2,…,25). K = 100g + n (n = k – 100g)

Ak = A0 + 25(g – 1) + n – 1 = A0 + 25g – 25 + n – 1 = A0 + 25g – 26 + k – 100g =  A0 – 75g – 26 + k = A0 – 75[k/100] – 26 + k = Ф(k) – функция отображения.

  1.  Если функцию отображения Ф(k) найти не удается, то нужно провести индексирование. Функция Ф(k) строится с помощью таблицы.

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

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

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

СД типа индексно-последовательный файл.

  1.  

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

  1.  
  2.  
  3.  
  4.  

 

  1.  
  2.  
  3.  
  4.  

Отображение идет в отношении n:1 (множество ключей отображается на 1 блок).

Упорядоченный файл делится на блоки. Блок содержит определенное число записей (обычно одинаковое  количество). На каждый блок в справочнике заводится одна статья, состоящая из указателя и ключа. Каждая статья содержит адрес первой записи, а поле ключа – значение последней записи. Поиск записи с нужным значением осуществляется в два этапа:

  1.  Просматривается справочник и определяется блок, к которому должна принадлежать искомая запись (при этом последовательно просматривается индекс-таблица, пока не будет найден первый ключ, не превышающий заданный). Т.к. справочник упорядочен, то можно использовать ускоренные методы поиска.
  2.  На втором этапе производится обращение к найденному блоку, где осуществляется последовательный поиск нужной записи (линейный или бинарный). Если известно, что количество записей N, то t(N) ~ (N/+ n) = 0, где n – искомое количество записей. – N/n2 + 1 = 0   n =.

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

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

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

Например, количество записей в файле равно приблизительно 1 млн.

Число уровней

Размер блока

Занимаемая справочником память

Среднее число обращений

0

0

0

500000 (n/2)

1

1000

1000

2

10000

150

3

33000

63

4

66000

40

5

100000

30

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

СД типа хеш-файл.

Осуществляется отображение n:1. Хеширование является реализацией вышерассмотренной идеи. Хеширование задается функцией:

Function h (key.Tk): 0..N;

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

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

= k mod N – функция хеширования (N – простое число)

[k mod (10000/100)]

h(k) = B + m[k mod (10 n/10 l)], где B и m – константы, n > l.

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

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

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

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

Рассмотрим алгоритм слияния (x, y, z – ключи в файлах):

Имеем: x1  x2  xn (1 файл);  y1  y2  ym (2 файл); z1  z2  zn+m (3 файл).

  1.  i=1, j=1, k=1;
  2.  найти наименьшее;

если x i < y j, то идти к п.3 иначе к п.5;

  1.  вывести x i ; z k  x i ; i=i+1; k=k+1;

если i  n, то идти к п.2;

  1.  вывести y jy m , т.е.  z k … z n+m  y j … y m ;

конец алгоритма.

  1.  вывести y j ; z k  y j ; k=k+1; j=j+1;

если j  m, то идти к п.2;

  1.  вывести x ix n , т.е.  z k … z n+m  x i … x n ;

конец алгоритма.

Алгоритм прямого слияния.

Этот алгоритм является одним из простейших.

Серия – упорядоченная последовательность. Серия может быть различной длины.

Алгоритм:

  1.  Последовательность а разбивается на две половины b и c. Затем осуществляется слияние частей b и c, при этом серия размерностью 1 становится серией размерностью 2.
  2.  Полученная последовательность снова обрабатывается последовательностью 1 и 2. Получается серия размерностью 4.
  3.  Повторяем шаги, получая серии 8, … до тех пор, пока не будет упорядочена вся последовательность.

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

a = {50, 3, 7, 60, 80, 90, 13, 15}

Поскольку на каждом проходе размерность серии удваивается, то сортировка заканчивается, когда p  n, где р – размер серии, а n – размер исходного файла.

Количество проходов: k = [log 2 n]. По определению при каждом проходе все множество из n элементов копируется ровно 1 раз, следовательно общее число пересылок М = n[log 2 n]. Число сравнений С еще меньше, чем М, т.к. при копировании остатка последовательности сравнения не производятся. Поскольку сортировка слиянием использует ВЗУ, то временные затраты на операцию пересылки на несколько порядков превышают временные затраты на операции сравнения.

Улучшение характеристик сортировки можно обеспечить увеличением файлов на фазе разделения и фазе слияния. Обозначим количество файлов – N. Тогда слияние r серий при 1 проходе дает r/N – количество серий, а на k-том проходе r/Nk. Тогда количество проходов будет k = [log N n], а количество пересылок М = n[log N n].

Например, при N=4:

38

80

  •  1

10

70

  •  2

100

200

  •  3

50

60

  •  4

38

38

38

10

10

50

100

200

50

60

Вообще можно считать, что имеется N/2 входов и столько же выходов, и они меняются местами после каждого отдельного прохода.

Многофазная сортировка.

В основе данной сортировки лежит отказ от жесткого понятия прохода и разделения файлов на две категории. Рассмотрим этот метод сортировки на примере:

f1

f2

f3

L

13

8

0

L=6

0

1

0

1

5

0

8

L=5

1

1

1

2

0

5

3

L=4

2

2

1

3

3

2

0

L=3

3

3

2

5

1

0

2

L=2

4

5

3

8

0

1

1

L=1

5

8

5

13

1

0

0

L=0

6

13

8

21

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

f1

f2

f3

f4

f5

f6

L

16

15

14

12

8

0

L=5

0

1

0

0

0

0

1

8

7

6

4

0

8

L=4

1

1

1

1

1

1

5

4

3

2

0

4

4

L=3

2

2

2

2

2

1

9

2

1

0

2

2

2

L=2

3

4

4

4

3

2

17

1

0

1

1

1

1

L=1

4

8

8

7

6

4

33

0

1

0

0

0

0

L=0

5

16

15

14

12

8

65

;

;

;

;

.

Подставляя вместо , получаем

(для i 4);

Такие числа называются числами Фибоначчи четвертого порядка. В общем случае числа Фибоначчи порядка р определяются следующим образом:

(для i > p); .

Заметим, что обычные числа Фибоначчи – числа первого порядка.

Теперь уже ясно, что исходные числа серий для идеальной многофазной сортировки с N последовательностями (файлами) представляют собой последовательность чисел Фибоначчи порядка N – 2. Отсюда следует, что метод применим для лишь входов, сумма серий на которых есть сумма N – 1 таких чисел Фибоначчи. В том случае, когда сумма серий отличается от идеальной суммы, то вводим фиктивную серию.

Сущность базы данных.

Системы управления базами данных.

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

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

Для создания и доступа к базам данных необходимо определить системные программные компоненты. Комплекс, состоящий из технических средств и системных программных компонентов, которые обеспечивают использование и обслуживание баз данных, называют системой управления баз данных (СУБд). Обычно сюда не входят прикладные программы, что обеспечивает независимость баз данных от программ пользователя.

Общая структура СУБД.

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

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

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

Реляционная модель СУБД.

В основе реляционной модели лежит математическое понятие отношения. Пусть заданы множества Di , i = 1, 2,…,n  и определим декартово произведение этих множеств: = D1  D2  Dn. Множества эти не обязательно разные. D также будет являться множеством, элементами которого являются последовательности = <d1, d2,…,dn>, di  D, d = 1, 2,…,n. D – домен различного характера и размерности:

D1 = {Иванов, Сидоров, …}; D2 = {1967, 1970, …}, …

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

Отношение можно представить в виде символьной строки (название и имена атрибутов): R(A1, A2,…,AN). Например: Студент (личный номер, Ф.И.О., факультет, группа). Таблица тогда имеет вид:

Студент.

Личный номер

Ф.И.О.

Факультет

Группа

Как правило, один или несколько атрибутов используют в качестве ключа, относительно которого осуществляют сортировки.

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

Преподаватель (личный номер, Ф,И,О,, зарплата);

Квалификация (личный номер, ВУЗ, ученая степень, дисциплина);

Семейное положение (личный номер, адрес, …).

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

Язык реляционной алгебры.

Для манипулирования данными в реляционной СУБД используется язык реляционной алгебры. Элементами являются отношения, и в результате операций снова получаются отношения. Т.к. отношения являются множествами, то имеют место основные операции над множествами: объединение, пересечение, разность, декартово произведение; а также специфические операции: проекция, соединение, выбора. Если отношения имеют одинаковые атрибуты, то они называются совместимыми.

Операцией объединения над отношениями R1 и R2 называют отношения, в которых кортежи отношения являются элементами R1 и R2. Например:

R1(A, B) = {(a1, b1), (a2, b2)};  R2(A, B) = {(a1, b1), (a3, b3)};

R = R1  R2 = {(a1, b1), (a2, b2), (a3, b3)}.

Операция пересечения: R = R1  R2 = {(a1, b1)}.

Разность: R = R1 \ R2 = {(a2, b2)} (есть в R1, но нет в R2).

Декартово произведение (меняется степень отношения):

R = R1  R2 = {(a1, b1, a1, b1), (a1, b1, a3, b3), (a2, b2, a1, b1), (a2, b2, a3, b3)}.

Рассмотренные операции могут быть определены на произвольное число отношений.

Операция проекция (унарная операция) – позволяет из заданного отношения R получить отношение /, в котором множество атрибутов является подмножеством атрибутов отношения R: R / = П R(А), где А – подмножество атрибутов исходного отношения.

Студент (личный номер, Ф.И.О., группа, В.М., ин. яз., СД, МК);

Высшая математика (личный номер, Ф.И.О., группа, В.М.).

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

Пример.

Студент.

Личный номер

Ф.И.О.

Факультет

Курс

Группа

87

Иванов

ФСУ

2

33

81

Сидоров

СТФ

3

43

Спорт.

Личный номер

Ф.И.О.

Вид спорта

Участие в соревнованиях

81

Сидоров

Плавание

Да

87

Иванов

Бег

Нет

Медосмотр.

Личный номер

Дата осмотра

81

11.12.97

87

01.10.97

Получаем:

Ф.И.О.

Факультет

Вид спорта

Дата осмотра

Сидоров

СТФ

Плавание

11.12.97

Иванов

ФСУ

Бег

01.10.97

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


 

А также другие работы, которые могут Вас заинтересовать

49387. Проектирование линейной автоматической системы управления 1.07 MB
  Цель работы: для заданного объекта регулирования требуется спроектировать АСР с заданным типом регулятора (ПИ-регулятор). Процесс проектирования состоит из следующих этапов: Анализ объекта регулирования. Определение оптимальных настроек ПИ-регулятора. Анализ функционирования АСР с оптимальными настройками.
49389. Расчет снижения налогов для нормализации заработной платы 944 KB
  Анализ объекта управления. Синтез типовой системы управления. Синтез нетиповой системы управления.
49390. Масс-спектрометрия и ее использование 3.71 MB
  История массспектрометрии ведётся с основополагающих опытов Джона Томсона в начале XX века. Существенное отличие массспектрометрии от других аналитических физикохимических методов состоит в том что оптические рентгеновские и некоторые другие методы детектируют излучение или поглощение энергии молекулами или атомами а массспектрометрия непосредственно детектирует сами частицы вещества. Массспектрометрия в широком смысле это наука получения и интерпретации массспектров которые в свою...
49391. Прибор для исследования оптических приборов 5.26 MB
  В курсовой работе я реализовал все требования в задании, однако посчитал необходимым изображать также мнимые лучи, полученные в результате преломления света в рассеивающих линзах. Эти лучи изображаются, в отличие от «нормальных», пунктирной линией, начинаясь в точке преломления луча, и заканчиваясь в мнимом фокусе изображения.