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

СТРУКТУРЫ ДАННЫХ

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

Графическое представление элемента структуры данных.

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

S:=(D,R)

Где S - структура данных, D - данные и R - отношения.

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

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

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

 

Классификация структур данных. Векторы и массивы как статистические структуры.

 

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

Структуры данных классифицируются:

1. По связанности данных в структуре:

- если данные в структуре связаны очень слабо, то такие структуры называются несвязанными (вектор, массив, строки, стеки)

- если данные в структуре связаны, то такие структуры называются связанными (связанные списки)

2. По изменчивости структуры во времени или в процессе выполнения программы:

- статические структуры - структуры, неменяющиеся до конца выполнения программы (записи, массивы, строки, вектора)

- полустатические структуры (стеки, деки, очереди)

- динамические структуры - происходит полное изменение при выполнении программы

3. По упорядоченности структуры:

- линейные (вектора, массивы, стеки, деки, записи)

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

Наиболее важной характеристикой является изменчивость структуры во времени.

Статические структуры данных

Векторы

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

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

Пример:

var

M1: Array [1..100] of integer;

M2: Array [1..10] of real;

Вектор состоит из совершенно однотипных данных и количество их строго определено.

Массивы

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

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