Основные структуры данных (характеристика и классификация)

Тема: Основные структуры данных (характеристика и классификация)

Раздел: Бесплатные рефераты по информатике

Тип: Курсовая работа | Размер: 103.57K | Скачано: 359 | Добавлен 09.10.11 в 14:31 | Рейтинг: 0 | Еще Курсовые работы

Вуз: ВЗФЭИ

Год и город: Пенза 2010

Оглавление

Введение 3

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

Введение 4

1.1. Общая характеристика данных 5

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

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

Заключение 16

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

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

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

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

 

Введение

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

В данной работе рассматривается: общая характеристика данных, понятия «тип данных», «структура данных».  Приводится классификация структур данных, обширная информация о физическом и логическом представлении структур данных всех классов памяти ЭВМ: простых, статических и др., а также,  информация о возможных операциях над всеми перечисленными структурами. Теоретическая часть была выполнена в программе MS Word 2010.

Для практической части – задача, вариант №6 «ООО Снежок», которая решена при помощи программы  MS Excel 2003.

 

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

Введение

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

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

• списковые

• древовидные или иерархические

• сетевые

• табличные

 

1.1. Общая характеристика данных

Данные – это материальные объекты произвольной формы, выступающие в качестве средства представления информации. Преобразование и обработка данных позволяют извлечь информацию, т.е. знание о том или ином предмете, процессе, явлении [4, С.21]. Другими словами данные - диалектическая составная часть информации. Они представляют собой зарегистрированные сигналы. В соответствии с методом регистрации данные могут храниться и переноситься на носителях различных видов, например: на бумаге, дисках (CD-ROM) и т.д.

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

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

* сбор данных ­­– накопление информации с целью обеспечения достаточной полноты для принятия решений;

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

* фильтрация данных – отсеивание «лишних» данных, в которых нет необходимости для принятия решений;

* сортировка данных – упорядочение данных по заданному признаку с целью удобства использования; повышает доступность информации;

* архивация данных – организация хранения данных в удобной и легкодоступной форме;

* защита данных – комплекс мер, направленных на предотвращение утраты, воспроизведения и модификации данных;

* транспортировка данных – прием и передача (доставка и поставка) данных между удаленными участниками информационного процесса;

* преобразование данных – перевод данных из одной формы в другую или из одной структуры в другую.

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

 

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

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

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

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

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

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

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

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

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

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

Информация по каждому типу однозначно определяет:

1) структуру хранения данных указанного типа, т.е. выделение памяти и представление данных в ней, с одной стороны, и интерпретирование двоичного представления, с другой;

2) множество допустимых значений, которые может иметь тот или иной объект описываемого типа;

3) множество допустимых операций, которые применимы к объекту описываемого типа.

 

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

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

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

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

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

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

К линейным структурам данных относятся ПСД и простые списки, называемые также строками, или строчными структурами. ПСД реализуют естественное отношение порядка на множестве данных в среде хранения. Если этот естественный порядок в ПСД совпадает с логическим отношением порядка на множестве элементов данных (чаще всего, когда у элементов данных выделяются ключевые атрибуты, он устанавливается в соответствии со значениями ключа), то такие разновидности ПСД называются упорядоченными (сортированными), в противном случае – неупорядоченными.

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

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

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

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

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

• стек – последовательность, в которой доступ на чтение и запись разрешен только к последнему моменту [6];
• очередь – последовательность элементов, в которой разрешено добавление в конец, а удаление - только из начала [6];
• дек – двусторонняя очередь, структура, позволяющая добавлять и извлекать элементы как в начале, так и в конце последовательности данных [5].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сетевые структуры данных

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

 

Заключение

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

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

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

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

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

 

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

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

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

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

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

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

СТАВКИ ЕСН

Фонд, в который производится отчисление	Ставка, %
ТФОМС	2,00
Федеральный бюджет	20,00
ФСС	3,20
ФФОМС	0,80
Итого	26,00

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

Табельный номер	ФИО сотрудника	Начислено за месяц, руб.	Федеральный бюджет, руб.	ФСС, руб.	ФФОМС, руб.	ТФОМС, руб.	Итого, руб.
001	Иванов И.И.	15 600,00
002	Сидоров А.А.	12 300,00
003	Матвеев К.К.	9 560,00
004	Сорокин М.М.	4 620,00
005	Петров С.С.	7 280,00

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

ООО «Снежок» Расчетный период с по __.__. 0__ __.__.20__         ВЕДОМОСТЬ РАСЧЕТА ЕСН Табельный номер ФИО сотрудника Федеральный бюджет, руб. ФФС, руб. ФФОМС, руб. ТФОМС, руб. Итого, руб. 001 Иванов И.И.           002 Сидоров А.А.           003 Матвеев К.К.           004 Сорокин М.М.           005 Петров С.С.           ВСЕГО ПО ВЕДОМОСТИ

Рис. 3. Ведомость расчета ЕСН

 

2.2. Описание алгоритма решения задачи смотрите в файе

 

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

1. Безрядина Г.П., Дулькин В.Н, Коноплева И.А. и др. Информатика: Методические указания по выполнению курсовой работы для самостоятельной работы студентов II курса (первое высшее образование). – М.: Вузовский учебник, 2006. – 60с.
2. Далека В.Д., Деревянко А.С., Кравец О.Г., Тимановская Л.Е. Модели и структуры данных: Учеб. пособие. – Харьков: ХГПУ, 2000. – 241с.
3. Информатика в экономике: Учеб. пособие / Под ред. проф. Б.Е. Одинцова, проф. А.Н. Романова. – М.: Вузовский учебник, 2008. – 478 с.
4. Экономическая информатика: Учебник / Под ред. В.П. Косарева. - 2-е изд., перераб. и доп. - М.: Финансы и статистика, 2005. - 592 с.
5. Лудов И.Ю. Методическое пособие по предмету: «Практикум на ЭВМ», раздел «Введение в структуры данных». – http://imcs.dvgu.ru/works/data/course/6411/struct.pdf

---

Понравилось? Нажмите на кнопочку ниже. Вам не сложно, а нам приятно).

---

Чтобы скачать бесплатно Курсовые работы на максимальной скорости, зарегистрируйтесь или авторизуйтесь на сайте.

Важно! Все представленные Курсовые работы для бесплатного скачивания предназначены для составления плана или основы собственных научных трудов.

---

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

Добавить работу

---

Если Курсовая работа, по Вашему мнению, плохого качества, или эту работу Вы уже встречали, сообщите об этом нам.

---

Добавление отзыва к работе

Добавить отзыв могут только зарегистрированные пользователи.

---

Похожие работы

• Основные структуры данных
• Основные структуры данных
• Линейные и нелинейные структуры данных