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

Содержание

Введение…………………………………………………………………………..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. Задачи, которые решаются с помощью компьютера, редко выражаются на языке битов. Как правило, данные имеют форму чисел, литер, текстов, символов и более сложных структур типа последовательностей, списков и деревьев.

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

 

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

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

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

 


 

 

 

 

 

 

 

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

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

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

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

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

Например7:

 – матрица;

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

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

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


 

 

 

 

 

 

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

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

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

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


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

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


 

 

 

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

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

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

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

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

 


 

 

 

 

 

 

 

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

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

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

 


 

 

 

 

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

 

 


 

 

 

 

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

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

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

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

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

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

 

 

 

 

 

 


 

 

 

 

 

 

 

 

 

 

Рисунок 9 – Многосвязный список (сплетение)

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

 

 

 

 

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

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

 

Рассмотрим следующую  задачу:

На предприятии ООО «Сириус» производится расчет заработной платы сотрудников Центра информационных технологий (ЦИТ) за текущий месяц по повременной форме тарифной системы оплаты труда. По условиям заключенных договоров всем сотрудникам начисляются ежемесячные премии. Данные для выполнения расчетов представлены в таблицах 1, 2 и 3.

Для решения задачи необходимо следующее.

1. Построить таблицы по  данным, приведенным в таблицах 1, 2 и 3.

2. Организовать межтабличные  связи с использованием функций  ВПР или ПРОСМОТР для автоматического  формирования заработной платы  сотрудников.

3. Сформировать и заполнить  ведомость начисления заработной  платы сотрудников ЦИТ ООО  «Сириус» за текущий месяц  (таблица 3).

4. Результаты расчетов размеров оплаты труда сотрудников ЦИТ представить в графическом виде.

 

Таблица 1. − Часовые тарифные ставки сотрудников ЦИТ

Должность

Часовая тарифная ставка, руб.

Премия, %

IT-менеджер

548,56

30

Системный администратор

521,66

25

Инженер-программист

480,32

22

Администратор баз данных

457,25

20

Программист группы 1С

496,48

25

Техник-программист

321,39

18


 

Таблица 2. − Отработанное время сотрудников в текущем  месяце

Должность

ФИО сотрудника

Отработанное время, час

IT-менеджер

Савельев А.Г.

200

Системный администратор

Коробейник В.А.

212

Инженер-программист

Волкова Н.А.

180

Администратор баз данных

Хохлова О.А.

150

Программист группы 1С

Быкова М.Н.

190

Техник-программист

Чигин Е.В.

140


 

Таблица 3. − Ведомость  начисления заработной платы сотрудникам  ЦИТ за текущий месяц

№ п/п

ФИО

Должность

Часовая тарифная ставка, руб.

Отработанное время, час.

Премия, руб.

Заработная плата, руб.

1

Савельев А.Г.

          

2

Коробейник В.А.

          

3

Волкова Н.А.

          

4

Хохлова О.А.

          

5

Быкова М.Н.

          

6

Чигин Е.В.

          

Фонд оплаты труда, руб.

  

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

 

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

 

Условно-постоянной информацией (справочной) служат следующие реквизиты: данные справочника должностей, часовой  тарифной ставке и проценте премии.

В результате следует получить ведомость со следующими реквизитами: №, ФИО, должность, часовая тарифная ставка, руб., отработанное время, премия, заработная плата по каждому сотруднику и по всем сотрудникам в целом.

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

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

 

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

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

 

Информационная модель, отражающая взаимосвязь исходных и результирующих документов, приведена на рис. 1.

                                                 1                                                             2


 

 

 

 

 

 

 

                          3                                                                                                   4

 

 

Рис. 1. Информационная модель взаимосвязи исходных и результирующих данных

1 – Часовые тарифные  ставки сотрудников ЦИТ, 2 – Отработанное  время сотрудников в текущем  месяце, 3 – Ведомость начисления  заработной платы сотрудникам  ЦИТ за текущий месяц, 4 – диаграмма

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

 

Описание алгоритма решения  задачи:

1. Запустить табличный  процессор MS Exсel.

2. Создать книгу с именем  «ООО Сириус».

3. Лист 1 переименовать в  лист с названием Часовые тарифные ставки сотрудников ЦИТ.

4. На рабочем листе Часовые тарифные ставки сотрудников ЦИТ создать таблицу.

5. Заполнить таблицу исходными  данными (Таблица 1).

 

            

Рис. 5. − Расположение таблицы  Часовые тарифные ставки сотрудников  ЦИТ

6. Лист 2 переименовать в  лист с названием Отработанное время сотрудников в текущем месяце.

7. На рабочем столе Отработанное время сотрудников в текущем месяце создать таблицу и заполнить её исходными данными (таблица 2).

 

                      

Рис. 6. − Расположение таблицы  Отработанное время сотрудников  в текущем месяце

 

8. Лист 3 переименовать в  лист с названием Расчёт заработной платы сотрудников ЦИТ.

9. На рабочем листе Расчёт заработной платы сотрудников ЦИТ. создать таблицу, и заполнить её исходными данными (таблица 3).

 

               

Рис. 7. − Расположение таблицы  Расчёт заработной платы 

сотрудников ЦИТ

 

10. Заполнить графу Должность таблицы «Расчёт заработной платы сотрудников ЦИТ» следующим образом:

Занести в ячейку С2 формулу:

=ВПР('Часовые тарифные ставки'!A2;'Часовые тарифные

ставки'!A1:C7;1;1).

 

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

11. Заполнить графу Часовая тарифная ставка таблицы «Расчёт заработной платы сотрудников ЦИТ» следующим образом:

Занести в ячейку D2 формулу:

=ПРОСМОТР('Часовые тарифные ставки'!B1;'Часовые тарифные

ставки'!B1:B7;'Часовые тарифные ставки'!B2:B7).

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

12. Заполнить графу Отработанное время таблицы «Расчёт заработной платы сотрудников ЦИТ» следующим образом:

Занести в ячейку E2 формулу:

=ПРОСМОТР('Отработанное время сотрудников'!C5;'Отработанное

время сотрудников'!C1:C7;'Отработанное время сотрудников'!C2).

 

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

13. Заполнить графу Премия таблицы «Расчёт заработной платы сотрудников ЦИТ» следующим образом:

Занести в ячейку F2 формулу:

=ПРОСМОТР('Часовые тарифные ставки'!C1;'Часовые тарифные

ставки'!C1:C7;'Часовые тарифные ставки'!C2).

 

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

14. Рассчитать графу Заработная плата таблицы «Расчёт заработной платы сотрудников ЦИТ» следующим образом:

Занести в ячейку G2 формулу:

=D2*E2+D2*E2*F2/100

 

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

15. Рассчитать Фонд оплаты труда таблицы «Расчёт заработной платы сотрудников ЦИТ» следующим образом:

Занести в ячейку G8 формулу:

=СУММ(G2:G7)

 

      

Рис. 8. − Расчёт заработной платы сотрудников ЦИТ ООО  «Сириус» за текущий месяц

 

16. Результаты расчетов размеров оплаты труда сотрудников ЦИТ представлена в графическом виде.

 

              

Рис. 9. − Графическое представление  результатов вычисления

 

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

 

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

 

Данная работа скачена  с сайта http://www.vzfeiinfo.ru ID работы: 42719

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

 

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

Список используемой литературы

 

  1.  «Информатика» КайминВ. А. Учебник. М.: ИНФРА-М, 2000г.232 с.
  2. «Информатика, общий курс» под ред. Колесникова В.И. Наука-Пресс. Москва, 2007г. – 315с.
  3. Модели и структуры данных: учебное пособие/ В. Д. Далека, А. С. Деревянко, О. Г. Кравец, Л. Е. Тимановская. - Харьков: ХГПУ, 2000г. - 241с.
  4. Структуры и алгоритмы обработки данных:  учебноепособие/Ключарев А. А., Матьяш В. А., Щекин С. В.- СПбГУАП.СПб., 2003г. - 172 с.
  5. Алгоритмы и структуры данных: учебное пособие/ Л. Г. Гагарина, В. Д. Колдаев. – М.: Финансы и статистика; ИНФРА-М, 2009г. – 304с.

 

 

 

 

 

 

 

 

 

1[1, c. 36]

2[5, c. 10]

3[5, c. 11]

4[5, c. 12]

5[2, c. 152]

6[5, c. 14]

7[5, c. 15]

8[5, c. 17]

9[5, c. 18]

10[5, c. 18]

11[4, предисловие]

 


Линейные и нелинейные структуры данных 📙 Курсовая → 🆔 116910

Линейные и нелинейные структуры данных 📙 Курсовая → 🆔 116910