Способ представления структурных данных
1. Какие бывают данные и их структуры?
2. Как задаются структуры данных?
… Лучше, чтобы в 100 функциях
использовалась одна структура данных,
чем в 10 функциях — 10 структур
А. Дж. Перлис
Всякая программа, предназначенная для реализации на ЭВМ, представляет собой формальное описание алгоритма решения той или иной задачи. Действия, выполняемые программой в соответствии с этим алгоритмом, направлены на преобразование некоторых объектов, определяющих текущее состояние процесса решения задачи. Такие внутренние объекты программы мы и называем данными. Основная цель любой программы состоит в обработке данных. Данные различных типов хранятся в памяти компьютера и обрабатываются по-разному. Согласно концепции типов данных, каждый тип данных однозначно определяет: множество значений, которые может принимать переменная заданного типа; операции и функции, которые можно применять к этой переменной; внутреннее представление переменной в памяти компьютера. Напомним, что память выделяется не для типа данных, а для размещения переменных или констант определенных типов.
Будем исходить из того представления, что структура данных – программная единица, позволяющая хранить и обрабатывать множество однотипных или логически связанных данных в вычислительной технике (https://ru.wikipedia.org/wiki/Структура_данных). Она формируется с помощью типов данных, ссылок и операций над ними в выбранном языке программирования.
3.1 Классификация структур данных
В языке Си различают следующие категории типов данных : базовые (или простые, основные, стандартные) типы данных и производные (или сложные, составные) типы данных. Основные типы данных представлены на рис. 3.1.
Базовый тип данных не обладает внутренней структурой и представляет собой единое, неделимое целое. В каждый момент времени данные этого типа принимают только одно значение из допустимого диапазона значений (см. табл. 3.1).
Рисунок 3.1 — Основные типы данных, применяемые в программировании
Указание типа данных четко определяет:
- размер памяти, отведенной под данную структуру и способ ее размещения в памяти;
- значения, допустимые для данного типа данных;
- операции, которые возможно над этими данными выполнять.
В си несколько основных базовых типов. Разделим их на две группы — целые и числа с плавающей точкой.
- char — размер 1 байт. Всегда! Это нужно запомнить.
- short — размер 2 байта
- int — размер 4 байта
- long — размер 4 байта
- long long — размер 8 байт.
Здесь следует сделать замечание. Размер переменных в си не определён явно, как размер в байтах. В стандарте только указано, что
char 3.1 — Размер целых чисел в Си
| Тип | Размер,байт | Миним.значение | Максим.значение |
|---|---|---|---|
| unsigned char | 1 | 0 | 255 |
| signed char ( char ) | 1 | -128 | 127 |
| unsigned short | 2 | 0 | 65535 |
| signed short ( short ) | 2 | -32768 | 32767 |
| unsigned int ( unsigned ) | 4 | 0 | 4294967296 |
| signed int ( int ) | 4 | -2147483648 | 2147483647 |
| unsigned long | 4 | 0 | 4294967296 |
| signed long ( long ) | 4 | -2147483648 | 2147483647 |
| unsigned long long | 8 | 0 | 18446744073709551615 |
| signed long long ( long long ) | 8 | -9223372036854775808 | 9223372036854775807 |
Числа с плавающей точкой:
- float — 4 байта,
- long float — 8 байт
- double — 8 байт
- long double — 8 байт.
Таблица 3.2 — Размер типов с плавающей точкой
| Тип | Размер,байт | Количество значащих знаков мантиссы | Миним. значение | Максим. значение |
|---|---|---|---|---|
| float | 4 | 6-7 | 1.175494351 E – 38 | 3.402823466 E + 38 |
| double | 8 | 15-16 | 2.2250738585072014 E – 308 | 1.7976931348623158 E + 308 |
| long double | 10 | — | 3.4 E — 4932 | 3.4 E +4932 |
В стандарте только указано, что float Производные (пользовательские) типы данных и типы класса являются более сложными объектами, которые составляются непосредственно пользователями, а основой или их начинкой являются непосредственно базовые данные. Их представление рассмотрим в следующем разделе.
С понятием типа данных тесно связано понятие структуры данных. Различают физическую и логическую структуры данных. Физическая структура в отличие от логической отражает способ представления данных в памяти компьютера и называется еще внутренней.
По составу различаются простые структуры (типы) данных и интегрированные (сложные) . Простые структуры не могут быть расчленены на составные части, большие, чем биты. С точки зрения физической структуры для простого типа четко определен его размер и способ размещения в памяти компьютера. С точки зрения логической структуры простые структуры являются неделимыми единицами. Интегрированные структуры данных включают в себя другие структуры данных — простые или интегрированные.
Рисунок 3.2 – Классификация структур данных
И наконец, по организации взаимосвязей между элементами сложных структур данных существует следующая классификация:
Таблица реляционной базы данных
Приведенная классификация далеко не полная. Элементами сложных структур данных могут выступать как экземпляры простых, так и экземпляры сложных структур данных, например структура данных лес – это список непересекающихся деревьев.
3.2 Способы представления структур данных
Необходимым условием хранения информации в памяти компьютера является возможность преобразования этой самой информации в подходящую для компьютера форму. В том случае, если это условие выполняется, следует определить структуру, пригодную именно для наличествующей информации, ту, которая предоставит требующийся набор возможностей работы с ней. Под структурой понимается способ представления информации, посредством которого совокупность отдельно взятых элементов образует нечто единое, обусловленное их взаимосвязью друг с другом.
3.2.1 Массивы
Массив – это структура однотипных данных, оптимизированная для операций поиска элемента по его индексу. Однозначное местоположение элемента в памяти обеспечивается именно однотипностью элементов в массиве и определяется произведением его индекса на размер памяти, занимаемой одним элементом.
Рисунок 3.3 – Структура данных «Линейный массив»
Адрес(элемент(index)) = размер_ячейки * index.
Доступ к какому-либо из элементов массива осуществляется по имени и номеру (индексу) этого элемента. Количество индексов определяет размерность массива.
Т.е. массив — это контейнер, в котором можно располагать, извлекать данные (объекты). Давайте рассмотри, как обозначаются одномерные массивы:
Квадратные скобки это обязательный элемент в объявлении массива. В них указывается его размер, т.е. количество элементов, которые в нем содержатся. Кстати, этот параметр является необязательным, т.е. если мы при объявлении массива, сразу его инициализируем, то можно опустить значение в скобках, т.к. наш компилятор сам посчитает количество элементов:
Многомерные массивы так же часто используются, как и одномерные. Вообще, многомерные массивы — это массивы массивов. Т.е. каждый индексный номер содержит массив. Например, int i[2][4] = <<1,2,3,4>, <5,6,7,8>>, где мы создаем двумерный массив размером 2х4, т.е. 2 строчки по 4 элемента каждая.
Массивы, описанного типа называются статическими, но существуют также массивы по определенным признакам отличные от них: динамические и гетерогенные. Динамичность первых характеризуется непостоянностью размера, т. е. по мере выполнения программы размер динамического массива может изменяться. Такая функция делает работу с данными более гибкой, но при этом приходится жертвовать быстродействием, да и сам процесс усложняется. Обязательный критерий статического массива, как было сказано, это однородность данных, единовременно хранящихся в нем. Когда же данное условие не выполняется, то массив является гетерогенным. Его использование обусловлено недостатками, которые имеются в предыдущем виде, но оно оправданно во многих случаях.
3.2.2 Списки
Список – абстрактный тип данных, реализующий упорядоченный набор значений. Списки отличаются от массивов тем, что доступ к их элементам осуществляется последовательно, в то время как массивы – структура данных произвольного доступа. Данный абстрактный тип имеет несколько реализаций в виде структур данных. Некоторые из них будут рассмотрены здесь.
Список – это динамическая линейная структура данных, в которой каждый элемент ссылается либо только на предыдущий – однонаправленный линейный список, либо на предыдущий и следующий за ним – двунаправленный линейный список. Достоинство этой структуры данных, помимо возможности изменять размер, — это простота реализации. Также, благодаря наличию ссылок, каждый элемент в списке, в отличие от массива, может занимать разный объем памяти. Адрес первого элемента в линейном списке однозначно определяется адресом самого списка.
Список.
Двунаправленный список.
Рисунок 3.4 – Структуры данных «Однонаправленный и двунаправленный список»
Связанный список – это вариант обычного линейного списка, оптимизированный для операций добавления и удаления элементов. Оптимизация заключается в том, что элементы связанного списка не обязаны в памяти располагаться друг за другом. Порядок элементов определяется ссылкой на первый элемент (не обязан быть в самом начале выделенной для списка памяти) и последовательностью ссылок на остальные элементы списка.
Рисунок 3.5 – Структура данных «Связанный список»
Список – это последовательность структур, каждая из которых содержит ссылку, связывающую её с другой структурой. Для организации списков используются структуры, состоящие из двух смысловых частей – информационной и дополнительной. Информационная часть содержит подлежащую обработке информацию, в дополнительной находятся указатели на последующую или предыдущую структуру списка:
struct spis *next; >; // Указатель на структуру
Здесь при описании указателя используем ещё не описанный объект struct spis *next , который будет служить ссылкой на последующий элемент списка. Самая последняя структура в списке никуда не указывает, т.е. поле next должно иметь значение NULL. Адрес начала (головы) списка хранится в переменной типа указатель *head. На текущую структуру будет указывать *p.
В двухсвязном списке каждая структура содержит две ссылки: на предыдущую и последующую структуры. Таким образом, по списку можно перемещаться от начала к концу и от конца к началу. Для доступа к началу и концу списка должны быть известны их адреса, которые могут сохраняться в глобальных переменных типа указатель.
3.2.3 Стек
Стек – это динамическая линейная структура данных, представляющая собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).
Часто сравнивают стек со стопкой тарелок. Чтобы достать следующую тарелку, необходимо снять предыдущие. Вершина стека – это вершина стопки тарелок.
Пример задания стека :
Возможны три операции со стеком: добавление элемента (иначе проталкивание, push), удаление элемента (pop) и чтение головного элемента (peek). При проталкивании (push) указывается новый элемент, указывающий на элемент бывший до этого головой. Новый элемент теперь становится головным. При удалении элемента убирается первый, а головным становится тот, на который был указатель у этого объекта (следующий элемент).
Рисунок 3.6 – Структура данных «стек»
Рисунок 3.7 — Последовательное выполнение операций push 3, push 5, push 7, pop, pop, pop
3.2.4 Очередь
О́чередь — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, First In — First Out). Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется.
В некотором смысле такой метод более справедлив, чем тот, по которому функционирует стек, ведь простое правило, лежащее в основе привычных очередей в различные магазины, больницы считается вполне справедливым, а именно оно является базисом этой структуры. Строго говоря, очередь – это список, добавление элементов в который допустимо, лишь в его конец, а их извлечение производиться с другой стороны, называемой началом списка.
Рисунок 3.8 – Структура данных «Очередь»
Очереди очень часто встречаются в реальной жизни, например, около банков или ресторанов быстрого обслуживания. Чтобы представить себе работу очереди, давайте введем две функции: qstore() и qretrieve() (от «store»— «сохранять», «retrieve» — «получать»). Функция qstore() помещает элемент в конец очереди, а функция qretrieve() удаляет элемент из начала очереди и возвращает его значение.
3.2.5 Дек
Дек – структура данных одновременно работает по двум способам организации данных: FIFO и LIFO. Поэтому ее допустимо отнести к отдельной программной единице, полученной в результате суммирования двух предыдущих видов структур данных.
Рисунок 3.9 – Структура данных «дек»
3.2.6 Хэш-таблица
Хеш-табли́ца — это структура данных, реализующая интерфейс ассоциативного массива, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.
Рисунок 3.10 – Структура данных «хэш – таблица»
Хэш-таблица – наиболее сложный из динамических линейных структур данных тип. Хэш-таблица оптимизирована для быстрого поиска элементов за счет вычисления адреса элемента, как значения хэш-функции. Аргументом хэш-функции является некий ассоциированный с элементом ключ, например, его порядковый номер. Чтобы гарантировать уникальные значения хэш-функции для уникальных значений ключа (исключить коллизии) хэш-таблица, помимо хитрых алгоритмов, также щедро использует оперативную память. Применение хэш-таблиц должно быть оправдано и тщательно продумано.
Во многих ситуациях, хэш-таблицы оказаться более эффективным, чем деревья поиска или любой другой структуры таблице. По этой причине, они широко используются во многих видах программного обеспечения, в частности, для ассоциативных массивов, индексация базы данных, кэш-памяти и множеств.
Рисунок 3.11 — Телефонная книга на примере хэш-таблицы
3.2.7 Иерархические структуры данных
Элемент в иерархической структуре данных характеризуется ссылкой на вышестоящий в иерархии элемент (или ссылками на нижестоящие элементы) и (необязательно) порядковым номером в линейной последовательности своего уровня (иерархические списки).
Деревья
Деревья или, в более широком смысле, древовидные структуры данных , представляют собой динамические структуры, отличающиеся от списков тем, что система связей не носит линейного характера, а образует ветви , подобно природному дереву (откуда и произошло название этой структуры данных).
Деревья – динамическая иерархическая структура данных, представленная единственным корневым узлом и его потомками. Максимальное количество потомков каждого узла и определяет размерность дерева. Отдельно выделяют двоичные или бинарные деревья, поскольку они используются в алгоритмах сортировки и поиска: каждый узел двоичного дерева поиска соответствует элементу из некоторого отсортированного набора, все его “левые” потомки – меньшим элементам, а все его “правые” потомки – большим элементам. Каждый узел в дереве однозначно идентифицируется последовательностью неповторяющихся узлов от корня и до него – путем. Длина пути и является уровнем узла в иерархии дерева. Для двоичных или бинарных деревьев выделяют следующие виды рекурсивного обхода всех его элементов (в фигурных скобках указан порядок посещения элементов каждого узла, начиная с корня): прямой или префиксный <узел, левое поддерево, правое поддерево>; обратный или постфиксный <левое поддерево, правое поддерево, узел>; симметричный или инфиксный
<левое поддерево, узел, правое поддерево>.
Пример представления дерева:
Чтобы вывести элементы в порядке их возрастания, дерево поиска следует обойти в симметричном порядке. Чтобы элементы оказались в обратном порядке, в процессе обхода необходимо поменять порядок посещения поддеревьев.
Рисунок 3.12 – Структура данных «дерево»
Иерархический список
Иерархический список – симбиоз линейного списка и дерева. Каждый элемент списка может быть также началом списка следующего подуровня иерархии. Пример иерархического списка – структура интернет форумов: последовательность сообщений образует линейный список, в то время как сообщения, являющиеся ответами на другие сообщения, порождают новые потоки обсуждения.
Рисунок 3.13 – Структура данных «Иерархический список»
Примеры применения структур данных
Пример 3.1. Применения структуры массив. Дан одномерный массив. Необходимо, заполнить одномерный массив, сделать вывод одномерного массива. Определить среднее арифметическое значение элементов массива.
Пример 3.2. Пример создания и просмотра односвязного списка (http://c.guti.ru/dstruktury.asp ).
Пример 3.3. Пример реализации структуры данных «стек».
Источник
