Понятие типов и структур данных

Общее понятие структуры данных, классификация

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

Данные определяются, как базовые и производные модели данных, то есть представляют собой «идеальные» представления переменных фиксированной размерности с набором известных операций над ними и их компонентами. Переменными называют области памяти с присвоенными именами, в которые записываются сконструированные типы данных.

Типы данных из программ:

• косвенно связанные переменные, в зависимости от применения данных в одинаковых процедурах и функциях;
• непосредственно связанные переменные, исходя из взаимосвязей через указатели.

Структуры данных бывают:

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

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

Конструкцией интегрированных структур занимаются программисты. В процессе инженеры применяют средства интеграции данных, предоставляемые языками программирования. В языках программирования тесно связаны определения «структуры данных» и «типы данных». Какие-либо данные, включая константы, переменные, значения функций или выражения, характеризуются конкретными типами. Данная информация определяет такие условия, как:

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

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

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

• фиксированное количество переменных в программе;
• стабильность размерности этих переменных в процессе функционирования программы.

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

В режиме двоичного файла произвольного доступа какой-либо файл является аналогом неограниченной прямо адресуемой области памяти, то есть, с точки зрения программы, имеет вид стандартной памяти. Таким образом, программа может копировать переменные из памяти в произвольное место файла и в обратном направлении. В результате в файле формируются любые (в том числе и динамические) структуры данных.

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

• хранение;
• добавление;
• удаление;
• модификацию;
• поиск.

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

Удобство реализации структуры данных заключается в использовании объектно-ориентированных языков. В этом случае структуре присваивается класс, а непосредственно сама информация записывается в переменных-членах класса, либо обеспечивается доступ к ней с помощью переменных-членов, системе предписаний соответствует набор методов класса.

Обычно, в объектно-ориентированных языках структуры данных реализуются, как библиотека стандартных классов: это так называемые контейнерные классы языка C++, входящие в стандартную библиотеку классов STL, или классы, реализующие различные структуры данных из библиотеки Java Developer Kit языка Java.

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

• четкое выделение комплекса опций, осуществляющих работу со структурой;
• ограничение доступа к информации лишь с помощью этого набора опций.

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

• заголовочный, или h-файл, описывающий интерфейс структуры данных, то есть комплекс прототипов функций, который соответствует системе предписаний структуры данных;
• файл реализации, или Си-файл, определяющий статические переменные, которые отвечают за хранение и доступ к данным, а также реализуются функции, соответствующие системе предписаний структуры данных.

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

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

Простые структуры данных

Данные структуры являются примитивными или базовыми. Их применяют в качестве основы, чтобы построить более сложные структуры. На языке программирования они описаны с помощью простых или базовых типов, а именно:

• числовые;
• битовые;
• логические;
• символьные;
• перечисляемые;
• интервальные;
• указатели.

Структуру простых типов целесообразно рассмотреть на языке PASCAL и его реализации в среде MS DOS. В случае других языков набор простых типов может в некоторой степени отличаться. Размер памяти под информацию определенного типа определяется языком программирования и способом реализации в рамках одного языка.

Какие бывают типы в программировании, описание с примерами

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

• несвязанными – в том случае, когда связи между данными структуре слабые (например, вектор, массив, строки, стеки);
• связанные – при наличии связей между данными (например, связанные списки).

Структура может характеризоваться разной изменчивостью по времени или в процессе реализации программы. При этом меняется число компонентов и/или связей между структурными элементами. Это один из наиболее важных признаков структуры данных. Классификация структур в зависимости от изменчивости:

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

Базовые структуры данных, статические, полустатические и динамические характерны для оперативной памяти и, как правило, носят название «оперативные структуры». Файловые структуры соответствуют структурам данных для внешней памяти.

По характеру упорядоченности структурных компонентов выделяют следующие типы:

• линейные – в виде векторов, массивов. стеков, деков, записей;
• нелинейные – представлены многосвязными списками, древовидными структурами, графами.

Группировка по особенностям взаимного размещения компонентов в памяти линейной структуры включает следующие виды:

• с последовательным распределением элементов в памяти (к примеру, векторы, строки, массивы, стеки, очереди);
• с произвольным связным распределением компонентов в памяти (например, односвязные и двусвязные списки).

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

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

При постоянном характере взаимосвязи переменных структуры данных называют статическими. При обратной ситуации структуры относятся к динамическому типу.

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

Ряд языков программирования, в том числе PL/1, ALGOL-60, подразумевает возможность для размещения статических структур в памяти на стадии реализации по явному требованию программиста. При этом объем резервируемой памяти остается стабильным до момента удаления структуры. Выделение памяти при компиляции представляет собой удобное свойство статических структур, что позволяет решать программистам задачи по представлению изменчивых объектов. Например, при неизвестном размере массива под него определяется максимально допустимый размер.

Каждая структура характеризуется:

• логическим представлением;
• физическим представлением.

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

Дескриптор применим в ситуации, когда граничные значения индексов компонентов массива неизвестны на стадии компиляции и, следовательно, выделение памяти для массива может быть выполнено только на этапе выполнения программы (как в языке PL/1, ALGOL-60).

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

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

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

• массивы;
• записи;
• множества.

Полустатические структуры данных

Признаки полустатической структуры:

• переменная длина, простота ее изменения;
• наличие определенных пределов, в которых изменяется длина структуры, исключается превышение некоего максимального или предельного значения.

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

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

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

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

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

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

• отсутствие физической смежности компонентов в памяти;
• изменчивость и непредсказуемость размера при обработке структуры.

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

• информационное поле или поле данных;
• поле связок с одним или несколькими указателями.

Преимущества связного отображения данных:

• обеспечение существенной изменчивости структур;
• ограничение размера только по доступному объему машинной памяти;
• допустимо лишь корректировать указатели при необходимости изменить логическую последовательность компонентов.

Недостатки связной структуры:

• высокие требования к квалификации программиста;
• расход дополнительной памяти на поля связок;
• менее эффективный по времени доступ к компонентам структуры.

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

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

Реализация одних структур на базе других

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

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

В процессе учитывают изначально данную базовую структуру или уже реализованную ранее. Реализация включает:

• идеи, объясняющие способы хранения структурных компонентов в базовой структуре, содержащие описание используемых дополнительных переменных;
• комплекс подпрограмм, способных моделировать какие-либо предписания реализуемой структуры с помощью предписаний базовой структуры.

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

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

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

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

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