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

Содержание:

 

Введение 3

1. Информация и данные 4

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

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

     3.1 Линейные и нелинейные...…………………………………………….....8

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

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

     3.4 Сетевые структуры данных...………………………………..…………13

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

Заключение 15

ПРАКТИЧЕСКАЯ ЧАСТЬ 

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

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

 

Введение.

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

 

Цель курсовой работы: рассмотреть основные структуры данных.

 Задачи курсовой работы:

1. Рассмотреть, что такое информация и данные, чем они различаются.
2. Рассмотреть такие понятия, как «тип данных», «структура     данных», «модель данных» и «база данных». 
3. Рассмотреть классификацию структур данных.
4. Рассмотреть характеристики основных типовых структур.

 

1. Информация и данные

 

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

Виды форм представления  информации:

1. По способу отображения: символьная (знаки, цифры, буквы); графическая (изображения); текстовая (набор букв, цифр) и звуковая.
2. По месту появления: внутренняя (выходная) и внешняя (входная).
3. По стабильности: постоянная и переменная.
4. По стадии обработки: первичная и вторичная.¹

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

 

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

 

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

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

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

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

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

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

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

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

Базовые структуры данных, статические, полустатические и динамические характерны для оперативной памяти и часто называются оперативными структурами. Файловые структуры соответствуют структурам данных для внешней памяти.

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

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

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

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

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

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

                                  

 

 

 

 

 

 

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

 

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

 

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

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

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

2) структуры с произвольным размещением элементов.

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

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

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

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

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

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

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

 

 

 

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

 

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

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

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

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

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

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

- указатель списка с адресом первого элемента;

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