Введение            3

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

     Введение            4

     1.1 Понятие информации и данных        5

     1.2. Характеристики основных типовых  структур     7

     1.2.1 Линейные и нелинейные        7

     1.2.2 Списковые структуры данных       8

     1.2.3 Древовидные (иерархические) структуры данных    10

     1.2.4 Табличные структуры данных       12

     Заключение           13

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

     2.1 Общая характеристика задачи        14

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

     Список  литературы          20 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение

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

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

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

    Характеристика  ПК использованного для выполнения работы: монитор Samsung LCD 22”, 1680 x 1050; системный блок DNS Prestige [0116439]; ОС: Windows XP; клавиатура A4 KL-50; мышь Gigabyte; принтер Panasonik KX-MB1900.  
 
 
 
 

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

Введение

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

    Структура данных поддерживает определённый порядок  доступа к ним. Понятие структуры данных можно определить, как совокупность внешних связей между элементами данных, которые на принятом уровне рассмотрения можно считать неделимыми, элементарными.[3, С. 89]

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

1. списковые;
2. древовидные или иерархические;
3. табличные.

    1.1 Понятие информации и данных

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

    Сказанное выше позволяет провести более четкое различие между терминами «информация» и «данные».

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

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

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

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

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

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

    1.2. Характеристики основных типовых структур

    1.2.1 Линейные и нелинейные

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

    Структуры данных также можно разделить на два больших класса по признаку физического размещения в памяти:

1. физически последовательные структуры, или просто последовательные структуры данных (ПДС);
2. структуры с произвольным размещением элементов.

    Среди структур данных с произвольным размещением элементов, прежде всего, выделяются списковые структуры данных (ССД), или просто списки. К линейным структурам данных относятся ПДС и простые списки, они также называются строками, или строчными структурами. [1, С. 123]

    ПДС реализуют естественное отношение порядка на множестве данных в среде хранения: «следующий» означает расположенный в памяти непосредственно вслед за предыдущим. Если этот естественный порядок совпадает с логическим отношением порядка на множестве элементов данных (чаще всего, когда у элементов данных выделяются ключевые атрибуты, он устанавливается в соответствии со значениями ключа), то такие разновидности ПДС называют упорядоченными (сортированными), если не совпадает – неупорядоченными. Служебная информация для описания ПДС обычно содержит сведения о количестве элементов множества данных, размерах (длине) элементов, о расположении ключа или ключей (если элементами являются записи) и их размерах, адресе первого элемента множества данных, и другие. [5, С. 67]

    В зависимости от разнообразия длин данных и способа указания длины записи ПДС подразделяются на следующие разновидности:

1. ПДС с фиксированной длиной элементов;
2. ПДС с элементами переменной длины;
3. ПДС с элементами неопределённой длины.

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

    Особая  разновидность ПДС – очереди. В них для пользователя (при  обращении к ПДС за данными или при добавлении новых данных) доступен только первый или (и) последний элемент данных. Вся остальная служебная информация скрыта от него и доступна только управляющей очередями программе. Разновидности очередей определяются конкретным вариантом доступного для поступления и доступного для обработки элемента. Наиболее распространены следующие разновидности очередей:

1. магазин или стек – соответствует принципу «первый вошёл, последний вышел»;
2. очередь (т.е. очередь в узком смысле в отличие от всей совокупности этого подкласса ПДС), соответствует принципу «первый вошёл, первый вышел»;
3. дек – двусторонняя очередь, структура, позволяющая добавлять и извлекать элементы, как в начале, так и в конце последовательности данных. [2, С. 143]

    1.2.2 Списковые структуры данных

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

    Элементы  ССД могут быть двух типов: простые, логически не делимые (их называют подсписками) или сложные – совокупность простых и сложных меньшого объёма. В простые ССД (строки или цепи) входят только простые элементы. В сложные ССД входят и простые, и сложные элементы.

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

    Возможно  совместное и раздельное размещение в памяти собственной и ассоциативной информации.

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

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

• указатель списка с адресом первого элемента;
• звено связи элементов, в которых для простого элемента содержаться адрес следующего элемента списка и адрес значения элемента, а для сложного элемента – адрес следующего элемента списка и адрес первого элемента подсписка.

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

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

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

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

    При каждом просмотре кольца значение N уменьшается на единицу и проверяется условие N=0. Если N≠0,просмотр продолжается; при N=0 просмотр заканчивается. Двунаправленная кольцевая строка отличается от однонаправленной тем, что вместо указателя начала кольца вводятся два указателя со своими константами – это указатель начала прямого направления и указатель начала обратного направления со своими константами чисел просмотра N1 и N2. Кроме того, звенья связи содержат адреса предыдущего и последующего элементов. [1, С. 124] 

    1.2.3 Древовидные (иерархические) структуры данных

    Элементы  древовидных структур данных (ДСД) располагаются  на различных уровнях и соединяются с помощью адресов связи. ДСД  соответствует графу типа «дерево» и представляется набором элементов, распределённых по уровням иерархии следующим образом:

    На  первом уровне расположен только один элемент, который называется корнем дерева; к любому элементу k-го уровня ведёт только один адрес связи; к любому элементу k-го уровня адрес связи идёт только от элемента(k-1)-го уровня.

    Количество  уровней в ДСД называют рангом. Элементы дерева, которые адресуются от общего элемента (k-1)-го уровня, образуют группу. Максимальное число элементов в группе называется порядком дерева. Деревья с порядком больше двух принято называть общими ДСД, а с порядком 2 − двоичными, или бинарными деревьями. Дерево порядка 1 – строчная структура.

    В зависимости от количества элементов  в группе некоторой вершины различают три типа вершин. Если n – порядок дерева, то вершины из n элементов называются полными, вершины, не имеющие группы – концевыми (листьями), а остальные неполными.

    Для ДСД можно определить её двунаправленный  и кольцевоё варианты. Если в однонаправленном варианте некоторая вершина А имеет адрес связи на вершину В, то в двунаправленном дереве дополнительно появится адрес связи от В к А. Если все концевые вершины дерева имеют адрес связи на вершину-корень, то ДСД называется кольцевой.

    Наиболее  распространённым видом ДСД являются бинарные деревья, в которых каждая вершина  k-го уровня содержит два адреса (правый и левый) связи на вершины (k+1)-го уровня и один (обратный) – на вершину  (k-1)-го уровня. Множество вершин, соединённых с данной вершиной через левый адрес связи, образует левую ветвь этой вершины. Аналогично определяется правая ветвь.

    В случае, когда элементы дерева являются записями, наиболее распространённым условием организации бинарных деревьев является упорядоченность. Записям соответствуют ключи с числовыми значениями. Каждый элемент в упорядоченном бинарном дереве (УБД) имеет на своей левой ветви элементы с меньшим, чем у него, значением ключа, а на правой ветви - элементы с большим или равным значением ключа.

    Имеются специальные разновидности бинарных деревьев, у которых размах расстояния Д от корня дерева до концевых вершин сравнительно невелик: подравненные и выровненные (в частном случае – симметричные). Алгоритмы формирования таких деревьев более сложные, чем общий алгоритм формирования УБД.

    Для общих ДСД часто используется разновидность: В-деревья (сбалансированные деревья) со специальным алгоритмом их формирования. В алгоритме формирования УБД дерево растёт вниз и его корень не меняется, а в алгоритме формирования В-дерева оно растёт вверх и его корень может меняться. [5, С. 69] 

    1.2.4 Табличные структуры данных

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

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

    Поиск, аналогично линейной структуре, осуществляется по разделителям. Если элементы таблицы одной длины, структура называется матрицей данных, разделители в ней не требуются. При длине одного элемента - d, зная номер строки  m и номер столбца n, а также строк и столбцов М, N, найдем адрес его начала:

d [N(m - 1) + (n - 1)].

    Таблица может быть и трехмерная, тогда  три числа характеризуют положение элемента и требуются три типа разделителей, а может быть и n-мерная. [4, С. 45] 
 
 
 
 
 
 
 
 
 
 

    Заключение

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

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

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

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

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

     2.1 Общая характеристика задачи

        В бухгалтерии ООО  «Снежок» производится расчет отчислений по каждому сотруднику предприятия:

• в федеральный бюджет,
• фонды обязательного медицинского страхования (ФФОМС - федеральный, ТФОМС - территориальный),
• фонд социального страхования (ФСС).

        Процентные ставки отчислений приведены на рис. 6.1. Данные для расчета отчислений в фонды по каждому сотруднику приведены на рис. 6.2.

1. Построить таблицы по приведенным ниже данным.
2. Выполнить расчет размеров отчислений с заработной платы по каждому сотруднику предприятия, данные расчета занести в таблицу (рис. 6.2) .
3. Организовать межтабличные связи для автоматического формирования ведомости расчета ЕСН (единого социального налога) по предприятию.
4. Сформировать и заполнить ведомость расчета ЕСН (рис. 6.3).
5. Результаты расчета ЕСН по каждому сотруднику за текущий месяц представить в графическом виде.

Рис. 6.1. Процентные ставки отчислений 
 
 
 
 
 

Рис. 6.2. Данные для расчета ЕСН за текущий месяц по каждому сотруднику