Размещено на http://www.allbest.ru/

Федеральное государственное образовательное бюджетное учреждение

высшего профессионального образования

"Финансовый университет при Правительстве Российской Федерации"

Курсовая работа

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

Выполнила:

Студентка Бычевская С.Б.

Группа 1Б-ЭФ108

Научный руководитель:

Дудихин В.В.

Москва 2013

Содержание

Введение

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

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

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

1.3 Линейные и нелинейные данные

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

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

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

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

2.1.1 Цель решения задачи

2.1.2 Условие задачи

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

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

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

2.2.3 Технология решения задачи

2.3 Результаты компьютерного эксперимента и их анализ

2.3.1 Результаты компьютерного эксперимента

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

Заключение

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

Приложения

данные информация линейный компьютерный

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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) каждая связка (ребро, дуга) может иметь направление и вес.

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

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

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

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

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

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

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

2.1.1 Цель решения задачи

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

2.1.2 Условие задачи

Входной оперативной информацией служит ведомость платежей по кредиту клиента банка "Акцепт+", содержащая следующие реквизиты (условная форма):

1) годовая процентная ставка;

2) срок выдачи кредита;

3) сумма кредита;

4) номер платежа;

5) дата платежа;

6) текущий остаток по кредиту; сумма процентов;

7) погашение основного долга;

8) платеж по кредиту.

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

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

Ведомость платежей по кредиту клиента К.В. Рыбиной банка "Акцепт +" за 2010 г.

Рисунок 10 - Экранная форма входной информации

В результате следует получить ведомость со следующими реквизитами:

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

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

Рисунок 10 - Экранная форма c результатами решения задачи

Кроме того, информацию, находящуюся в таблицах для анализа, необходимо представить в виде диаграммы. В процессе решения задачи, необходимо использовать функции: СУММ(), ОКРУГЛ() и ЕСЛИ().

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

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

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



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

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

Для получения ведомости "Ведомости платежей по кредиту клиента К.В. Рыбиной банка "Акцепт+" с итоговыми данными, необходимо рассчитать следующие показатели:

– текущий остаток по кредиту;

– сумму процентов;

– погашение основного долга;

– платеж по кредиту;

– итого по сумме процентов;

– итого по погашению основного долга;

– итого по платежу по кредиту.

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

где Ot - текущий остаток по кредиту, Sk - сумма кредита, Pd - погашение основного долга, сумма процентов, St% - годовая процентная ставка, срок выдачи кредита, Pl - платеж по кредиту.

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

2.2.3 Технология решения задачи

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

1. Вызвать Excel;

2. Переименовать "Лист1" в "Ведомость", дважды нажав левым курсором мыши по ярлыку или, нажав правым курсором мыши и выбрав "Переименовать" (рисунок 12).

Рисунок 12 - Изменение имени листа документа Excel

3. Ввести заголовок таблицы. Зная, что будущая таблица имеет 6 столбцов, выделить ячейки A1чF1 и нажать на кнопку "Объединить ячейки"и в полученной области ввести заголовок "Ведомость платежей по кредиту клиента К.В. Рыбиной банка "Акцепт +" за 2010 г.".

4. Ввести имена ячеек в таблицу, представленные на рисунке 13.

Рисунок 13 - Имена ячеек заполняемой таблицы

5. Заполнить таблицу известными данными. По условию задачи известны значения: годовой процентной ставки, срока кредита и суммы кредита, они соответственно равны: 12%, 12 месяцев, 250 000. Значения ячейки "Номер платежа" соответствуют числам от 1 до 12, поскольку по условию задачи, срок кредита - 12 месяцев. Значения ячейки "Дата платежа" соответствуют названию месяца и года.

6. Вычислить и заполнить данными ячейку "Погашение основного долга", для этого нужно воспользоваться формулой (3) и округлить значения до целого, используя функцию ОКРУГЛ(): поставить курсор мыши в ячейку E6 и ввести: =ОКРУГЛ(C4/C3;0). Поскольку ежемесячное погашение кредита осуществляется равными (аннуитетными) платежами, то значения ячеек E6чE16будут равными 20 833 руб. Значение ячейки E17 будет иметь другое значение:=ЕСЛИ(СУММ(E7:E17)+E7=C4;0;E7+C18) для того, чтобы итоговая сумма погашения основного долга равнялась сумме выданного кредита. Функция ЕСЛИ() в данном случае используется для отражения остатков по платежу в последнем платеже.

7. Вычислить и заполнить данными ячейку "Текущий остаток по кредиту", для этого необходимо воспользоваться формулой (1): поставить курсор мыши в ячейку С7 и ввести: =C5-E7, а вот значение ячейки C8 уже будет иметь значение: =C7-E8, ячейки С9: =C8-E9, и т.д.

8. Вычислить и заполнить данными ячейку "Сумма процентов", для этого необходимо воспользоваться формулой (2)и округлить значения до целого, используя функцию ОКРУГЛ(): поставить курсор мыши в ячейку D7 и ввести: =ОКРУГЛ(C7*1%;0), аналогично с этим рассчитываются значения других ячеек D8чD18.

9. Вычислить и заполнить данными ячейку "Платеж по кредиту", для этого необходимо воспользоваться формулой (4): поставить курсор мыши в ячейку F7 и ввести: =D7+E7, аналогично с этим рассчитываются значения других ячеек F8чF18.

10. После того, как найдены все значения, необходимо найти итоговые значения ячеек "Сумма процентов", "Погашение основного долга" и "Платеж по кредиту". Для этого необходимо воспользоваться функцией СУММ(). Для ячейки D19: =СУММ(D7:D18), для ячейки E19:=СУММ(E7:E18), для ячейки F19:=СУММ(F7:F18).

11. Для того чтобы таблица смотрелась законченной и выразительной, ее необходимо отформатировать, для этого выделим ячейки A3чF19, щелкним по ней правой кнопкой мыши и в контекстном меню выберем "Формат ячеек". В появившемся окне, зайдем на вкладку "Граница" и нажмем на кнопки "Внешние" и "Внутренние" (рисунок 14).

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

Рисунок 14 - Форматирование границ таблицы

12. Наглядно представим результаты расчетов, создав диаграмму по данным таблицы. Для этого необходимо зайти в Вставка/Гистограмма и выбрать понравившейся тип гистограммы (рисунок 15).

Рисунок 15 - Создание диаграммы

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

На рисунке 16 изображена итоговая таблица, в ячейках которой отображены формулы вместо значений.

Рисунок 16 - Итоговая таблица с формулами вместо значений

2.3 Результаты компьютерного эксперимента и их анализ

2.3.1 Результаты компьютерного эксперимента

Для тестирования правильности решения задачи изменим входные данные (рисунок 17), а затем рассчитаем результаты (рисунок 18).

Рисунок 17 - Измененные входные данные задачи



Рисунок 18 - Результаты решения задачи с измененными входными данными

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

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

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

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

Заключение

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

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

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

1. "Информатика" Каймин В.А. Учебник. М.: ИНФРА-М, 2000 г. 232 с.

2. "Информатика, общий курс" под ред. Колесникова В.И. Наука-Пресс. Москва, 2007 г. - 315 с.

3. Модели и структуры данных: учебное пособие / В.Д. Далека, А.С. Деревянко, О.Г. Кравец, Л.Е. Тимановская. - Харьков: ХГПУ, 2000 г. - 241 с.

4. Структуры и алгоритмы обработки данных: учебное пособие / Ключарев А.А., Матьяш В.А., Щекин С.В. - СПбГУАП. СПб., 2003 г. - 172 с.

5. Алгоритмы и структуры данных: учебное пособие / Л.Г. Гагарина, В.Д. Колдаев. - М.: Финансы и статистика; ИНФРА-М, 2009 г. - 304 с.

Приложения

Приложение 1

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

Приложение 2

Решение задачи с помощью программы Excel 2010

Приложение 3

Гистограмма платежей по кредиту по месяцам

Размещено на Allbest.ru

...