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

метки: Структура, Данные, Элемент, Канонический, Информация, Следовать, Хранение, Служебный

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

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

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

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

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

Область применения баз данных

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

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

• табличные

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

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

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

1.3Характеристики основных типовых структур, Линейные и нелинейные

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

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

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

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

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

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

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

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

Архитектура серверов корпоративных баз данных

... В данном реферате будут рассмотрены особенности архитектуры RISC процессоров фирм DEC, Hewlett-Packard и Bull и особенности построения на их основе многопроцессорных SMP серверов и кластерных ... систем. 1. Системы управления базами данных и серверы баз данных Одним из наиболее распространенных классов прикладных систем ...

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

магазин или стек – соответствует принципу «первый вошёл, последний вышел»;

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

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

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

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

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

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

Возможно совместное и раздельное размещение в памяти собственной и ассоциативной информации (см. Рисунок 2 и Рисунок 3):

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

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

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

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