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

Большинство современных языков программирования может реализовывать технологию «структурного программирования». В них применяется структурирование логики программы и используемых ею данных.

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

 

Структура данных – это форма хранения и представления информации.

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

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

1. Линейные

a. Массив

b. Список

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

d. Стек

e. Очередь

f. Хэш-таблица

2. Иерархические

a. Двоичные деревья

b. N-арные деревья

c. Иерархический список

3. Сетевые

a. Простой граф

b. Ориентированный граф

4. Табличные

a. Таблица реляционной базы данных

b. Двумерный массив

5. Файлы

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

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

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

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

Линейный массив.
Адрес (элемент(index)) = размер_ячейки * index.

Список – это динамическая линейная структура данных, в которой каждый элемент ссылается

a) только на предыдущий (однонаправленный линейный список),

b) либо на предыдущий и следующий за ним (двунаправленный линейный список).

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

Список.

Двунаправленный список.

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

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

Стек – это динамическая линейная структура данных, для которой определены всего две операции: добавление элемента в конец и удаление последнего элемента. Еще говорят, что стек реализует очередь LIFO (Last in, First Out) – последним пришел, первым вышел. Например, при выполнении программы, компьютер в случае необходимости вызвать некоторую функцию или метод сначала заносит указатель на место ее вызова в стек. Этот подход обеспечивает корректный возврат после завершения метода к инструкции, следующей после точки вызова. Такая структура данных

называется стеком вызовов подпрограмм.

Стек.

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

Очередь.

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

⇐ Предыдущая123456Следующая ⇒

Поделиться:

Популярное:

1. I. Какое из данных утверждений выражает основную идею текста?
2. I. КЛАССИФИКАЦИЯ ПО ИСПОЛЬЗОВАНИЮ.
3. I. Классификация установок, по Узнадзе.
4. I.9. Структура киноповествования
5. IDEF1X - методология моделирования данных, основанная на семантике, т.е. на трактовке данных в контексте их взаимосвязи с другими данными.
6. II КЛАССИФИКАЦИЯ И МАРКИРОВКА ЧУГУНОВ
7. II. Особенности технологии баз и банков данных.
8. II. СПОСОБЫ И ПРИЗНАКИ ИЗМЕНЕНИЯ МАРКИРОВОЧНЫХ ДАННЫХ
9. III. Классификация мебельных тканей.
10. III. Структура и правила внесения записей
11. III.6. Набор химических структурных формул.
12. IV. Классификация по скорости развития