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

Содержание

Введение…………………………………………………………………………..2

1. Теоретическая часть………………………………………………………..…3

1.1. Основные понятия структуры данных……………………………...…....…3

1.2. Классификация структуры…………………………………………………..6

1.3. Линейные и нелинейные структуры данных…………………………….…7

1.3.1. Линейные структуры  данных…………………………………………...…7

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

2. Практическая часть………………………………………………………..….13

2.1. Постановка задачи…………………………………………………………..13

2.2. Условие задачи, цель  решения задачи…………………………………..…14

2.3. Компьютерная модель  решения задачи………………………………...…16

2.3.1. Информационная модель  решения задачи………………………………16

2.3.2. Аналитическая модель  решения задачи………………………………....16

2.4. Анализ полученных  результатов………………………………………..…21

Заключение……………………………………………………………………….22

Список использованной литературы…………………………………………...23

Приложения……………………………………………………………………...24

 

 

Введение

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

     В данной  работе рассматривается: информация и данные, чем они различаются; как информация  переходит в структурированные данные. Рассматриваются такие понятия, как «тип данных» и «структура данных».  Приводится классификация структур данных, обширная информация о линейных и нелинейных структурах данных.

Практическая часть курсовой работы состоит из построения  и  анализа компьютерной модели решения задачи варианта 11.

 

1. Теоретическая часть

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

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

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

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

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

Рисунок 1 – Уровни представления  структуры данных

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

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

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

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

 

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

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

По признаку изменчивости различают структуры базовые, статические, полу статические, динамические и файловые⁴. Классификация структур данных (СД) по признаку изменчивости приведена в приложении 1. Базовые структуры данных, статические, полустатические и динамические характерны для оперативной памяти и часто называются оперативными структурами. Файловые структуры соответствуют структурам данных для внешней памяти.

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

Массив - последовательность элементов одного типа, называемого базовым.

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

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

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

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

 

3. Линейные и нелинейные данные

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

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

 

 

 

 

 

 

 

 

Рисунок 2 - Линейные и нелинейные структуры данных

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

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

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

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

Например⁷:

 – матрица;

B = (9, 3, 6, 5) – вектор;

Z = {7, 6, 0, 2, 3} – множество элементов;

Строчные структуры - одномерные, динамически изменяемые структуры данных, различающиеся способами включения и исключения элементов (рисунок 3).

 

 

 

 

 

 

Рисунок 3 – Строчные структуры  данных

Стек - это последовательность, в которой включение и исключение элемента осуществляется с одной стороны последовательности.

Известные примеры стека  – винтовочные патронный магазин, железнодорожный разъезд для  сортировки вагонов.

Очередь — последовательность, в которую включают элементы с одной стороны, а исключают — с другой (рисунок 4). Структура функционирует по принципу FIFO (первым пришел - первым обслуживается).

Рисунок 4 – Схема доступа  к элементам очереди

Дек — линейная структура (последовательность), в которой операции включения и исключения элементов могут выполняться как с одного, так и с другого конца последовательности (рисунок 5).

 

 

 

Рисунок 5 – Схема доступа  к элементам дека

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

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

Нелинейные структуры данных - это СД, у которых связи между элементами зависят от выполнения определенного условия. Примеры нелинейных структур — деревья, графы, многосвязные списки.

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

 

 

 

 

 

 

 

 

Рисунок 6 – Древовидная  структура (дерево)

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

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

 

 

 

 

 

Рисунок 7 – Бинарное дерево

 

 

 

 

 

 

Рисунок 8 – Примеры графовых структур

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

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