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

1. Информация  и данные

 

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

Виды  форм представления информации:

1. По способу отображения: символьная (знаки, цифры, буквы); графическая (изображения); текстовая (набор букв, цифр) и звуковая.

2. По  месту появления: внутренняя (выходная) и внешняя (входная)

3.  По  стабильности: постоянная и переменная

4. По  стадии обработки: первичная и  вторичная.

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

 Теперь  можно дать более конкретное  определение данных на машинном  уровне представления информации. Независимо от содержания и  сложности любые данные в памяти  ЭВМ представляются последовательностью  двоичных разрядов, или битов, а их значениями являются соответствующие двоичные числа. Для человека описывать и исследовать сколько-нибудь сложные данные в терминах последовательностей битов весьма неудобно. Более крупные и содержательные, нежели бит, "строительные блоки" для организации произвольных данных получаются на основе понятия "структуры данного". 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

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

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

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

Простые структуры данных называют также  примитивными или базовыми структурами. Эти структуры служат основой  для построения более сложных  структур. В языках программирования простые структуры описываются  простыми (базовыми) типами. К таким типам относятся: числовые, битовые, логические, символьные, перечисляемые, интервальные, указатели. В дальнейшем изложении мы ориентируемся в основном на язык PASCAL и его реализации в среде MS DOS. Структура простых типов PASCAL приведена на рис 1.1. (через запятую указан размер памяти в байтах, требуемый для размещения данных соответствующего типа). В других языках программирования набор простых типов может несколько отличаться от указанного. Размер же памяти, необходимый для данных того или иного типа, может быть разным не только в разных языках программирования, но и в разных реализациях одного и того же языка.  

                               Рис. 1.1. Структура простых типов PASCAL. 

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

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

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

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

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

3. Линейные  структуры

Стек - такой последовательный список с  переменной длиной, включение и исключение элементов из которого выполняются  только с одной стороны списка, называемого вершиной стека. Применяются  и другие названия стека - магазин  и очередь, функционирующая по принципу LIFO (Last - In - First- Out - "последним пришёл - первым вышел").

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

Очередью FIFO (First - In - First- Out - "первым пришел - первым вышел") называется такой последовательный список с переменной длиной, в котором включение элементов выполняется только с одной стороны списка (эту сторону часто называют концом или хвостом очереди), а исключение - с другой стороны (называемой началом или головой очереди).

Основные  операции над очередью - те же, что  и над стеком - включение, исключение, определение размера, очистка, неразрушающее  чтение.

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

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

Базовыми  операциями над строками являются: определение длины строки; присваивание строк; конкатенация (сцепление) строк; выделение подстроки; поиск вхождения.

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

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

4. Нелинейные  структуры данных

Графы

Граф - это сложная нелинейная многосвязная динамическая структура, отображающая свойства и связи сложного объекта.

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

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

Граф, все  связи которого ориентированные, называется ориентированным графом или орграфом; граф со всеми неориентированными связями - неориентированным графом; граф со связями обоих типов - смешанным  графом.

Дерево - это граф, который характеризуется  следующими свойствами:

1. Существует  единственный элемент (узел или  вершина), на который не ссылается  никакой другой элемент - и  который называется корнем  (рис. 7; 8 - A, G, M - корни).

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

3. На  каждый элемент, кроме корня,  имеется единственная ссылка, т.е.  каждый элемент адресуется единственным  указателем.

  

Рис1. Дерево      Рис.2 Лес 

Название "дерево" проистекает из логической эквивалентности древовидной структуры  абстрактному дереву в теории графов. Линия связи между парой узлов  дерева называется обычно ветвью. Те узлы, которые не ссылаются ни на какие  другие узлы дерева, называются листьями или терминальными вершинами (рис. 7; 8 - b, k, l, h - листья). Узел, не являющийся листом или корнем, считается промежуточным  или узлом ветвления (нетерминальной или внутренней вершиной).

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

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