Структуры данных. Элементарные данные.

Структуры данных. Элементарные данные.

 

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

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

 

 

Линейные структуры данных. Массив.

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

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

Следующее объявление задаёт имя для массива, тип для индекса и тип элементов массива:

array[тип индекса] ofтип элемента;

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

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

var

vector: array[1..100] of integer;

matrix: array[1..100, 1..100] of integer;

cube: array[1..100, 1..100, 1..100] of integer;

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

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

Cube [0,0,10]:= 25;

Matrix [10,30]:= Cube [0,0,10] + 1;

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

 

Циклический однонаправленный список. Способы реализации и основные операции.

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

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

Понятие «первого» элемента здесь достаточно условно и не всегда требуется. Хотя иногда бывает полезно выделить некоторых элемент как «первый» путём установки на него специального указателя. Это требуется, например, для предотвращения «зацикливания» при просмотре списка.

Основные операции:

- вставка элемента

- просмотр

- поиск

- удаление элемента

 

Обходы деревьев.

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

- в прямом порядке

- в обратном порядке

- в симметричном порядке

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

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

2. если дерево состоит из одной вершины, то в список обхода записывается эта вершина

3. ели дерево – дерево с корнем n и поддеревьями t1, t2, y3 то:

- при прохождении в прямом порядке сначала посещается корень n, затем в прямом порядке вершины поддерева tk

- при прохождении в обратном порядке сначала посещаются в обратном порядке посещаются вершины поддерева t1, далее последовательно в обратном порядке посещаются вершины поддеревьев t2…tk. Последним посещается корень n

- при прохождении в симметричном порядке сначала посещаются в симметричном порядке вершины поддерева t1, далее корень n, затем последовательно в симметричном порядке вершины поддеревьев t2…tk

 

 

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

Случайные деревья поиска представляют собой упорядоченные бинарные деревья поиска, при создании которых элементы (их ключи) вставляются в случайном порядке.
При создании таких деревьев используется тот же алгоритм, что и при добавлении вершины в бинарное дерево поиска. Будет ли созданное дерево случайным или нет, зависит от того, в каком порядке поступают элементы для добавления. Примеры различных деревьев, создаваемых при различном порядке поступления элементов, приведены ниже.
При поступлении элементов в случайном порядке получаем дерево с минимальной высотой h (рис. 32, а), а соответственно минимизируется время поиска элемента в таком дереве, которое пропорционально O(log n). При поступлении элементов в упорядоченном виде (рис. 32, 6) или в несколько необычном порядке (рис. 32, в) происходит построение вырожденных деревьев поиска (оно вырождено в линейный список), что нисколько не сокращает время поиска, которое составляет O(n).
2.3.4.3. Оптимальные деревья поиска
В двоичном дереве поиск одних элементов может происходить чаще, чем других, т. е. существуют вероятности рА поиска А..-го элемента и для различных элементов эти вероятности неодинаковы. Можно сразу предположить, что поиск в дереве в среднем будет более быстрым, если те элементы, которые ищут чаще, будут находиться ближе к корню дерева.
Пусть даны 2п+1 вероятностей р1, р2, р„, q< q> q где р,.- вероятность того, что аргументом поиска является К,.; q,. - вероятность того, что аргумент поиска лежит между К,. и К,. ~, q< - вероятность того, что аргумент поиска меньше, чем К,; q„- вероятность того, что аргумент поиска больше, чем К„.
г
Дерево поиска называется оптимальным, если его цена минимальна или, другими словами, оптимальное бинарное дерево поиска - это бинарное дерево поиска, построенное в расчете на обеспечение максимальной производительности при заданном распределении вероятностей поиска требуемых данных.
Существует подход построения оптимальных деревьев поиска, при котором элементы вставляются в порядке уменьшения частот, что дает в среднем неплохие деревья поиска. Однако этот подход может дать вырожденное дерево поиска (см. 2.3.4.2), которое будет далеко от оптимального.
Еще один подход состоит в выборе корня 1 таким образом, чтобы максимальная сумма вероятностей для вершин левого поддерева или правого поддерева была настолько мала, насколько это возможно. Такой подход также может оказаться плохим в случае выбора в качестве корня элемента с малым значением рА.
30. Сбалансированные по высоте деревья поиска. Способы реализации и основные операции

Как уже говорилось ранее (см. 2.3.4.2), в худшем случае (дерево вырождено в линейный список) хранение данных в упорядоченном бинарном дереве никакого выигрыша в сложности операций (поиск/добавление/удаление) по сравнению с массивом или линейным списком не дает. В лучшем случае (дерево сбалансировано) для всех операций получается логарифмическая сложность, что гораздо лучше.
Идеально сСбалансированным называется дерево, у которого для каждой вершины выполняется требование: число вершин в левом и правом поддеревьях различается не более чем на 1. Однако идеальную сбалансированность довольно трудно поддерживать. В некоторых случаях при добавлении/удалении может потребоваться значительная перестройка дерева, не гарантирующая логарифмической сложности. Поэтому в 1962 году два советских математика Г М. Адельсон-Вельский и Е. М. Ландис ввели менее строгое определение сбалансированности и доказали, что при таком определении можно написать программы добавления/ удаления, имеющие логарифмическую сложность и сохраняющие дерево сбалансированным.
Дерево считается сбалансированным по АВЛ (в дальнейшем просто «сбалансированным»), если для каждой вершины выполняется требование: высота левого и правого поддеревьев различаются не более, чем на 1. Не всякое сбалансированное дерево идеально сбалансировано, но всякое идеально сбалансированное дерево сбалансировано.
При операциях добавления и удаления может произойти нарушение сбалансированности дерева. В этом случае потребуются некоторые преобразования, не нарушающие упорядоченности дерева и способствующие лучшей сбалансированности.

Структуры данных. Элементарные данные.

 

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

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