Информатика и технология программирования

       

Структуры данных " в узком смысле"


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

Структуры данных этого типа строятся на основе трех основных базовых структур данных :



- массивов (массивы указателей) (см.5.2.) ;



- списков (см.5.3.) ;



- деревьев (см.5.5.).

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

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

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

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



- выбор (поиск) по логическому номеру ;



- добавление последним ;



- включение по логическому номеру ;



- удаление по логическому номеру ;



- " быстрый" (двоичный) поиск в упорядоченной структуре данных ;



- включение с сохранением упорядоченности ;



- сортировка неупорядоченной структуры данных .

И, наконец , последняя характеристика HYPERLINK "bk51.htm" \l "def1" 08d0c9ea79f9bace118c8200aa004ba90b02000000090000000303000000000000c000000000000046000009000000626b35312e68746d00ffffadde00000000000000000000000000000000000000001600000010000000030062006b00350031002e00680074006d000500000064006500660031000000 структуры данных. В зависимости от способа хранения элементов различают:

- структуры данных, хранящие сами элементы данных;



- структуры данных, хранящие указатели на элементы данных. В этом случае сами элементы данных полностью независимы от структуры. Такой способ организации данных часто называют КОЛЛЕКЦИЕЙ. В этом случае допускается, что структура данных может хранить как указатели на элементы данных одного типа, так и на элементы данных различных (произвольных) типов (указатели типа void* ).





Содержание раздела