Файл: Способы организации данных: пользовательский тип данных - структура ( Понятие о программировании и структурировании данных).pdf

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

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

Можно показать много случаев, где у информации видно явную структуру.[20]

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

В широком смысле рассматриваемого понятия, структуру имеет всякое живое существо.

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

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

Стоит отметить, что структурированные данные имеют свою специфическую форму текстов, чисел и могут в себе содержать более сложные структуры (рисунок 1):

Рис. 1. Пример древоподобной структуры

Стоит отметить, что с понятием структуры данных в программировании тесно связан термин «тип данных». Виды применяемых данных при написании программ показаны на рисунке 2:[10]

Рис. 2. Типы данных

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

Стоит отметить, что много средств, для описания почти всех ЯП, есть возможность ссылаться в поэлементном варианте, пользуясь только названием [4].

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

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

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

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

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

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

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

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

Другой важнейший признак, по которому можно структурировать данных – характер упорядоченности для её элементов. [12]

По данному также структуры делятся на: (рисунок 3):

Рис. 3. Категории структур

По качестве и характеру связей между элементами структур их можно разделять на следующие типы (рисунок 4):

Рис. 4. Классификация структур по характеру связей

В зависимости от указанной выше характеристики для взаимного расположения всех структуры в оперативной памяти, все современные структуры данных, которые называются линейными, еще можно разделить на несколько категорий [16]:

– векторы;

– массивы;

– стеки;

– строки;

– очереди.

Типичным примером нелинейной структуры являются многофайловые списки, графы, деревья. [3]

В современных ЯП очень тесно связывается определение "структуры " с термином "формат данных".

1.3. Характеристика структурных форматов данных

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

В ЯП иногда применяются простые структуры, описывающиеся с применением таких базовых типов [6].

К таким типам можно отнести (рисунок 5):

Рис. 5. Простые структуры данных

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

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

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

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

К ним можно отнести:

– массивы;

– структуры;

– множества.

Рассмотрим некоторые с перечисленных структур.

Вектор (или одномерный массив) – это структура данных, которая располагает конкретной численностью элементов базового формата данных [3].

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

Такой номер называют индексом.

Обращение к элементу можно реализовать по имени, номеру элемента массива.

Под массивом понимается специальная структура данных, характеризующаяся: [6]

– фиксированным перечнем элементов;

– каждый из компонентов имеет уникальный набор значений индексов;

– общее количество всех рассмотренных индексов описывает размерность массива;

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

2. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ

2.1. Принцип обработки динамических структур

Часто в больших программных проектах надо применять данные, в которых размер и структура должны меняться непосредственно при процессе работы.

Все динамические массивы выделяют память под свои компоненты только в процессе их обработки.

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

– ссылок;

– поля данных.

Ссылка (или указатель) – это адрес других узлов такого же типа, с которыми этот узел логически связан. [9]

В языке программирования С++ для организации ссылок применяется переменная-указатели.

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

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

Достоинство применения ссылок состоит в следующем:

– возможность обеспечения изменчивости информации;

– размер структур ограничен только доступным объёмом оперативной ПК;

– при рассмотрении иных логических последовательностей для компонентов динамической структуры не нужно переместить всю информацию в оперативной памяти, а возможно только выполнить перенаправление указателей на нее. [18]

Также, вместе с рассмотренным фактом, ссылки имеют также некоторые недостатки:

– работа с указателями выполняется разработчиками, которые имеют более высокую квалификацию;

– на поля ссылок будет расходоваться также некоторый объем дополнительной памяти;

– выполнение непосредственного доступа к элементам структур во времени может быть не эффективным.

Динамический список – упорядоченная совокупность, которая состоит из некоторого количества элементов (не обязательно постоянного), с которыми применяются операции по добавлению и удалению узлов в список (рисунок 6)[2].

Рис. 6. Схема динамического списка

Каждый элемент списка содержит ссылку на следующий элемент за ним. У последнего элемента списка поле ссылки содержит указатель NULL.

Чтоб не потерять список, надо где-то (в основном, в переменной) хранить адрес первого его узла – его называют «головой» списка.

Стоит отметить, что в программе надо объявлять 2 новых формата данных, к примеру, узел Node и указатель PNode.

Узел представляется структурой, которая содержит сразу три поля:

– строку;

– целое число;

– указатель на аналогичный узел.

Ниже, на рисунке 7 приведена классическая структура односвязного списка. В структуре, которая рассмотрена ниже, поле inf реализуется как информационное поле или данные, а next – это указатель на следующий узел структуры.

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

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

Рис. 7. Структура линейного односвязного списка

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

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

Для выполнения доступа к списку применяется не одна переменная-указатель, а сразу две – ссылка на первый элемент списка (к примеру, Head) и на последний элемент – Tail.

Стоит заметить, что эту возможность может обеспечить только 2-связный список, в котором использованы 2 указателя: [14]

– на предыдущий элемент;

– на следующий элемент.

В крайних элементах расмотренных списков соответствующие указатели могут содержать значения nil (рисунок 8).[1]

Рис.8. Схема 2-связного списка

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

Указанное применение 2-х указателей для узлов значительно усложняет архитектуру списка, приводит также к разным дополнительным объемам памяти, обеспечивает выполнение всех команд, операций с обрабатываемой списочной структурой. [7]

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

При непосредственной работе с списочной структурой односвязного типа указатели последнего элемента часто указывают на первый элемент списка (рисунок 9). [11]

Рис.9. Описание циклических списков

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