Уважаемый посетитель сайта! На нашем сайте вы можете скачать без регистрации книги, тесты, курсовые работы, рефераты, дипломы бесплатно!

Авторизация на сайте

Забыли пароль?
Регистрация нового пользователя

Наименование предмета

Яндекс.Метрика
Введение 3
ТЕОРЕТИЧЕСКАЯ ЧАСТЬ 4
1. Информация и данные 4
2. Классификация структур данных 5
3. Основные структуры данных 8
Простые структуры данных 8
Статические структуры данных 11
Полустатические структуры данных 15
Динамические структуры данных 18
Нелинейные структуры данных 21
Заключение 24
ПРАКТИЧЕСКАЯ ЧАСТЬ 25
Общая характеристика задачи 25
Описание алгоритма решения задачи 27
Список использованной литературы 33







Введение
Веками человечество накапливало знания, навыки работы, сведения об окружающем нас мире, т.е. собирало информацию. Вначале информация передавалась из поколения в поколение в виде преданий и устных расска-зов. Возникновение и развитие книжного дела позволило передавать и хранить информацию в более надежном письменном виде. Открытия в об-ласти электричества привели к появлению телеграфа, телефона, радио, те-левидения — средств, позволяющих оперативно передавать и накапливать информацию. Развитие прогресса обусловило резкий рост информации, в связи, с чем вопрос о её сохранении и переработке становился год от года острее. С появлением вычислительной техники значительно упростились способы хранения, а главное, обработки информации. Развитие вычисли-тельной техники на базе микропроцессоров приводит к совершенствова-нию компьютеров и программного обеспечения. Появляются программы, способные обработать большие потоки информации. С помощью таких программ создаются информационные системы. Целью любой информа-ционной системы является обработка данных об объектах и явлениях ре-ального мира и предоставление нужной человеку информации о них.
В данной работе рассматривается что такое информация и данные, чем они различаются; как информация переходит в структурированные данные. Рассматриваются такие понятия, как «тип данных», «структура данных», «модель данных» и «база данных». В основной части работы приводится классификация структур данных, обширная информация о фи-зическом и логическом представлении структур данных всех классов памя-ти ЭВМ: простых, статических, полустатических, динамических и нелиней-ных; а также, информация о возможных операциях над всеми перечислен-ными структурами.
В практической части работы я показала на примере ООО «Снежок» как производится расчет отчислений по каждому сотруднику предприятия и представила все в графическом виде.
ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
Информация и данные
В информатике различают два понятия «данные» и «информация». Данные представляют собой информацию, находящуюся в формализован-ном виде и предназначенную для обработки техническими системами. Под информацией понимается совокупность представляющих интерес фактов, событий, явлений, которые необходимо зарегистрировать и обработать. Информация в отличие от данных – это то, что нам интересно, что можно хранить, накапливать, применять и передавать. Данные только хранятся, а не используются. Но как только данные начинают использоваться, то они преобразуются в информацию. В процессе обработки информация изменя-ется по структуре и форме. Признаками структуры является взаимосвязь элементов информации. Структура информации классифицируется на формальную и содержательную. Формальная структура информации ори-ентирована на форму представления информации, а содержательная – на содержание.
Виды форм представления информации:
1. По способу отображения: символьная (знаки, цифры, буквы); графи-ческая (изображения); текстовая (набор букв, цифр) и звуковая.
2. По месту появления: внутренняя (выходная) и внешняя (входная)
3. По стабильности: постоянная и переменная
4. По стадии обработки: первичная и вторичная.
Теперь можно дать более конкретное определение данных на машин-ном уровне представления информации. Независимо от содержания и сложности любые данные в памяти ЭВМ представляются последователь-ностью двоичных разрядов, или битов, а их значениями являются соответ-ствующие двоичные числа. Для человека описывать и исследовать сколь-ко-нибудь сложные данные в терминах последовательностей битов весьма неудобно. Более крупные и содержательные, нежели бит, "строительные блоки" для организации произвольных данных получаются на основе по-нятия "структуры данного".
Классификация структур данных
Структуры данных служат материалами, из которых строятся про-граммы. Как правило, данные имеют форму чисел, букв, текстов, символов и более сложных структур типа последовательностей, списков и деревьев.
Для точного описания абстрактных структур данных и алгоритмов программ используются такие системы формальных обозначений, называ-емые языками программирования, в которых смысл всякого предложения определится точно и однозначно. Среди средств, представляемых почти всеми языками программирования, имеется возможность ссылаться на элемент данных, пользуясь присвоенным ему именем. Выбор правильного представления данных служит ключом к удачному программированию и может в большей степени сказываться на производительности программы, чем детали используемого алгоритма. Вряд ли когда-нибудь появится об-щая теория выбора структур данных.
Под структурой данных в общем случае понимают множество эле-ментов данных и множество связей между ними. Такое определение охва-тывает все возможные подходы к структуризации данных, но в каждой конкретной задаче используются те или иные его аспекты. Поэтому вво-дится дополнительная классификация структур данных, направления ко-торой соответствуют различным аспектам их рассмотрения. Прежде чем приступать к изучению конкретных структур данных, дадим их общую классификацию по нескольким признакам.
Физическая структура данных отражает способ физического пред-ставления данных в памяти машины и называется еще структурой хране-ния, внутренней структурой или структурой памяти.
Рассмотрение структуры данных без учета её представления в машин-ной памяти называется абстрактной или логической структурой. В об-щем случае между логической и соответствующей ей физической структу-рами существует различие, степень которого зависит от самой структуры и особенностей той среды, в которой она должна быть отражена. Вследствие этого различия существуют процедуры, осуществляющие отображение ло-гической структуры в физическую и наоборот. Эти процедуры обеспечи-вают доступ к физическим структурам и выполнение над ними различных операций.
Различаются простые (базовые, примитивные) структуры (типы) дан-ных и интегрированные (структурированные, композитные, сложные). Простыми называются такие структуры данных, которые не могут быть расчленены на составные части, большие, чем биты. Интегрированными называются такие структуры данных, составными частями которых явля-ются другие структуры данных - простые или в свою очередь интегриро-ванные. Интегрированные структуры данных конструируются програм-мистом с использованием средств интеграции данных, предоставляемых языками программирования.
В зависимости от отсутствия или наличия явно заданных связей между элементами данных следует различать несвязные структуры (векторы, массивы, строки, стеки, очереди) и связные структуры (связные списки).
Весьма важный признак структуры данных - её изменчивость - изме-нение числа элементов или связей между элементами структуры. По при-знаку изменчивости различают структуры статические, полустатиче-ские и динамические. Классификация структур данных по признаку из-менчивости приведена на рис. 1.

Рис. 1. Классификация структур данных
Базовые структуры данных, статические, полустатические и динамиче-ские характерны для оперативной памяти и часто называются оператив-ными структурами. Файловые структуры соответствуют структурам данных для внешней памяти.
Второй важный признак структуры данных - характер упорядоченно-сти её элементов. По этому признаку структуры можно делить на линей-ные и нелинейные структуры. В зависимости от характера взаимного расположения элементов в памяти, линейные структуры можно разделить на структуры с последовательным распределением элементов в памяти (векторы, строки, массивы, стеки, очереди) и структуры с произвольным связным распределением элементов в памяти (односвязные, двусвязные списки). Пример нелинейных структур - многосвязные списки, деревья, графы.
В языках программирования понятие "структуры данных" тесно свя-зано с понятием "типы данных". Любые данные, т.е. константы, перемен-ные, значения функций или выражения, характеризуются своими типами.
Информация по каждому типу однозначно определяет:
1) структуру хранения данных указанного типа, т.е. выделение памяти и представление данных в ней, с одной стороны, и интерпретирование двоичного представления, с другой;
2) множество допустимых значений, которые может иметь тот или иной объект описываемого типа;
3) множество допустимых операций, которые применимы к объекту описываемого типа.




Основные структуры данных
Простые структуры данных
Простые структуры данных называют также примитивными или ба-зовыми структурами. Эти структуры служат основой для построения бо-лее сложных структур. В языках программирования простые структуры описываются простыми (базовыми) типами. К таким типам относятся: чис-ловые, битовые, логические, символьные, перечисляемые, интервальные и указатели. В дальнейшем изложении мы будем ориентироваться на язык PASCAL. Структура простых типов PASCAL приведена на рис 2.1 (через запятую указан размер памяти в байтах, требуемый для размещения дан-ных соответствующего типа). В других языках программирования набор простых типов может несколько отличаться от указанного.

Рис. 2. Структура простых типов PASCAL
Числовые типы
Целые типы. С помощью целых чисел может быть представлено ко-личество объектов, являющихся дискретными по своей природе (т.е. счет-ное число объектов).
Вещественные типы. В отличии от порядковых типов (все целые, символьный, логический), значения которых всегда сопоставляются с ря-дом целых чисел и, следовательно, представляются в памяти машины аб-солютно точно, значение вещественных типов определяет число лишь с не-которой конечной точностью, зависящей от внутреннего формата веще-ственного числа.
Битовые типы
В ряде задач может потребоваться работа с отдельными двоичными разрядами данных. Чаще всего такие задачи возникают в системном про-граммировании, когда, например, отдельный разряд связан с состоянием отдельного аппаратного переключателя или отдельной шины передачи данных и т.п. Данные такого типа представляются в виде набора битов, упакованных в байты или слова, и не связанных друг с другом. Операции над такими данными обеспечивают доступ к выбранному биту данного.
Логические типы
Значениями логического типа BOOLEAN может быть одна из предва-рительно объявленных констант false (ложь) или true (истина). Данные ло-гического типа занимают один байт памяти. При этом значению false соот-ветствует нулевое значение байта, а значению true соответствует любое ненулевое значение байта. Над логическими типами возможны операции булевой алгебры - НЕ (not), ИЛИ (or), И (and), исключающее ИЛИ (xor) - последняя реализована для логического типа не во всех языках. В этих операциях операнды логического типа рассматриваются как единое целое - вне зависимости от битового состава их внутреннего представления. Ре-зультаты логического типа получаются при сравнении данных любых ти-пов.
Символьный тип
Значением символьного типа char являются символы из некоторого предопределенного множества. В большинстве современных персональ-ных ЭВМ этим множеством является ASCII (American Standard Code for Information Intechange - американский стандартный код для обмена ин-формацией). Это множество состоит из 256 разных символов, упорядочен-ных определенным образом и содержит символы заглавных и строчных букв, цифр и других символов, включая специальные управляющие сим-волы. Допускается некоторые отклонения от стандарта ASCII, в частности, при наличии соответствующей системной поддержки это множество может содержать буквы русского алфавита. Значение символьного типа char за-нимает в памяти 1 байт. Код от 0 до 255 в этом байте задает один из 256 возможных символов ASCII таблицы.
Перечислимый тип
Перечислимый тип представляет собой упорядоченный тип данных, определяемый программистом, т.е. программист перечисляет все значения, которые может принимать переменная этого типа. Значения являются не-повторяющимися в пределах программы идентификаторами, количество которых не может быть больше 256.
Интервальный тип
Один из способов образования новых типов из уже существующих - ограничение допустимого диапазона значений некоторого стандартного скалярного типа или рамок описанного перечислимого типа. Определяется заданием минимального и максимального значений диапазона. При этом изменяется диапазон допустимых значений по отношению к базовому ти-пу, но представление в памяти полностью соответствует базовому типу.
Указатели
Тип указателя представляет собой адрес ячейки памяти. При про-граммировании на низком уровне - в машинных кодах, на языке Ассем-блера и на языке C, который специально ориентирован на системных про-граммистов, работа с адресами составляет значительную часть программ-ных кодов. При решении прикладных задач с использованием языков вы-сокого уровня наиболее частые случаи, когда программисту могут пона-добиться указатели:
1) При необходимости представить одни и те же физические данные, как данные разной логической структуры.
2) При работе с динамическими структурами данных.
Статические структуры данных
Статические структуры относятся к разряду непримитивных структур, которые представляют собой структурированное множество примитивных, базовых, структур. Например, вектор может быть представлен упорядо-ченным множеством чисел. Поскольку по определению статические струк-туры отличаются отсутствием изменчивости, память для них выделяется автоматически - как правило, на этапе компиляции или при выполнении - в момент активизации того программного блока, в котором они описаны. Выделение памяти на этапе компиляции является столь удобным свойством статических структур, что в ряде задач программисты используют их для представления объектов, обладающих изменчивостью. Например, когда размер массива неизвестен заранее, для него резервируется максимально возможный размер.
Статические структуры в языках программирования связаны со структурированными типами. Структурированные типы в языках про-граммирования являются теми средствами интеграции, которые позволяют строить структуры данных сколь угодно большой сложности. К таким ти-пам относятся: массивы, записи (в некоторых языках - структуры) и мно-жества (этот тип реализован не во всех языках).
Векторы
Вектор (одномерный массив) - структура данных с фиксированным числом элементов одного и того же типа. Каждый элемент вектора имеет уникальный в рамках заданного вектора номер. Обращение к элементу вектора выполняется по имени вектора и номеру требуемого элемента.
Массивы
Логическая структура.
Массив - такая структура данных, которая характеризуется: фиксиро-ванным набором элементов одного и того же типа; каждый элемент имеет уникальный набор значений индексов; количество индексов определяют мерность массива (два индекса - двумерный массив, три индекса - трех-мерный массив, один индекс - одномерный массив или вектор); обращение к элементу массива выполняется по имени массива и значениям индексов для данного элемента. Другими словами, массив - это вектор, каждый эле-мент которого - вектор.
Физическая структура - это размещение элементов массива в памяти ЭВМ. Для случая двумерного массива, состоящего из (k1-n1+1) строк и (k2-n2+1) столбцов физическая структура представлена на рис. 3.

Рис. 3. Физическая структура двумерного массива из (k1-n1+1) строк и (k2-n2+1) столбцов
Многомерные массивы хранятся в непрерывной области памяти. Размер слота определяется базовым типом элемента массива. Количество элементов массива и размер слота определяют размер памяти для хране-ния массива. Принцип распределения элементов массива в памяти опреде-лен языком программирования. Так в FORTRAN элементы распределяют-ся по столбцам - так, что быстрее меняется левые индексы, в PASCAL - по строкам - изменение индексов выполняется в направлении справа налево.
Специальные массивы. На практике встречаются массивы, которые в силу определенных причин могут записываться в память не полностью, а частично. Это особенно актуально для массивов настолько больших раз-меров, что для их хранения в полном объёме памяти может быть недоста-точно. К таким массивам относятся симметричные и разреженные мас-сивы.
Симметричные массивы. Двумерный массив, в котором количество строк равно количеству столбцов называется квадратной матрицей. Квад-ратная матрица, у которой элементы, расположенные симметрично отно-сительно главной диагонали, попарно равны друг другу, называется сим-метричной.
Разреженные массивы. Разреженный массив - массив, большинство элементов которого равны между собой, так что хранить в памяти доста-точно лишь небольшое число значений отличных от основного (фонового) значения остальных элементов. Различают два типа разреженных масси-вов:
1) массивы, в которых местоположения элементов со значениями от-личными от фонового, могут быть математически описаны;
2) массивы со случайным расположением элементов.
Множества
Логическая структура: Множество - такая структура, которая пред-ставляет собой набор неповторяющихся данных одного и того же типа. Множество может принимать все значения базового типа. Базовый тип не должен превышать 256 возможных значений. Поэтому базовым типом множества могут быть byte, char и производные от них типы.
Физическая структура: Множество в памяти хранится как массив би-тов, в котором каждый бит указывает является ли элемент принадлежащим объявленному множеству или нет. Т.о. максимальное число элементов множества 256, а данные типа множество могут занимать не более 32-ух байт.
Числовые множества. Стандартный числовой тип, который может быть базовым для формирования множества - тип byte.
Символьные множества. Символьные множества хранятся в памяти также как и числовые множества. Разница лишь в том, что хранятся не числа, а коды ASCII символов.
Множество из элементов перечислимого типа. Множество, базовым типом которого есть перечислимый тип, хранится также, как множество, базовым типом которого является тип byte. Но, в памяти занимает место, которое зависит от количества элементов в перечислимом типе.
Множество от интервального типа. Множество, базовым типом ко-торого есть интервальный тип, хранится также, как множество, базовым типом которого является тип byte. В памяти занимает место, которое зави-сит от количества элементов, входящих в объявленный интервал.
Записи
Запись - конечное упорядоченное множество полей, характеризую-щихся различным типом данных. Полями записи могут быть интегриро-ванные структуры данных - векторы, массивы, другие записи. Записи яв-ляются чрезвычайно удобным средством для представления программных моделей реальных объектов предметной области, как правило, каждый та-кой объект обладает набором свойств, характеризуемых данными различ-ных типов.
Таблицы
Таблица - сложная интегрированная структура. С физической точки зрения таблица представляет собой вектор, элементами которого являются записи. Логической особенностью таблиц является то, что доступ к элемен-там таблицы производится не по номеру (индексу), а по ключу - по значе-нию одного из свойств объекта, описываемого записью-элементом табли-цы. Ключ - это свойство, идентифицирующее данную запись во множестве однотипных записей. Ключ может включаться в состав записи и быть од-ним из её полей, но может и не включаться в запись, а вычисляться по по-ложению записи. Таблица может иметь один или несколько ключей. Ос-новной операцией при работе с таблицами является операция доступа к записи по ключу. Она реализуется процедурой поиска. Поскольку поиск может быть значительно более эффективным в таблицах, упорядоченных по значениям ключей, довольно часто над таблицами необходимо выпол-нять операции сортировки.
Иногда различают таблицы с фиксированной и с переменной длиной записи. Очевидно, что таблицы, объединяющие записи совершенно иден-тичных типов, будут иметь фиксированные длины записей. Таблицы с за-писями переменной длины обрабатываются только последовательно - в порядке возрастания номеров записей.
Полустатические структуры данных
Полустатические структуры данных характеризуются следующими признаками: они имеют переменную длину и простые процедуры её изме-нения; изменение длины структуры происходит в определенных пределах, не превышая какого-то максимального (предельного) значения.
Если полустатическую структуру рассматривать на логическом уровне, то о ней можно сказать, что это последовательность данных, свя-занная отношениями линейного списка. Доступ к элементу может осу-ществляться по его порядковому номеру. Физическое представление полу-статических структур данных в памяти это обычно последовательность слотов в памяти, где каждый следующий элемент расположен в памяти в следующем слоте (т.е. вектор). Физическое представление может иметь также вид однонаправленного связного списка (цепочки), где каждый сле-дующий элемент адресуется указателем находящемся в текущем элементе.
Стеки
Стек - такой последовательный список с переменной длиной, включе-ние и исключение элементов из которого выполняются только с одной сто-роны списка, называемого вершиной стека. Применяются и другие назва-ния стека - магазин и очередь, функционирующая по принципу LIFO (Last - In - First- Out - "последним пришёл - первым вышел").
Основные операции над стеком - включение нового и исключение эле-мента из стека. Полезными могут быть также вспомогательные операции: определение текущего числа элементов в стеке и очистка стека. Некоторые авторы рассматривают также операции включения/исключения элементов для середины стека, однако структура, для которой возможны такие опе-рации, не соответствует стеку по определению.
Для наглядности рассмотрим небольшой пример, демонстрирующий принцип включения элементов в стек и исключения элементов из стека. На рис. 4.1 (а, б ,с) изображены состояния стека:
а) пустого;
б, в, г) после последовательного включения в него элементов с именами 'A', 'B', 'C';
д, е) после последовательного удаления из стека элементов 'C' и 'B';
ж) после включения в стек элемента 'D'.

Рис. 4. Включение и исключение элементов из стека
Как видно из рис. 4, стек можно представить, например, в виде стопки книг (элементов), лежащей на столе. Присвоим каждой книге свое назва-ние, например A,B,C,D... Тогда в момент времени, когда на столе книг нет, про стек аналогично можно сказать, что он пуст, т.е. не содержит ни одно-го элемента. Если же мы начнем последовательно класть книги одну на другую, то получим стопку книг (допустим, из n книг), или получим стек, в котором содержится n элементов, причем вершиной его будет являться элемент n+1. Удаление элементов из стека осуществляется аналогичным образом т. е. удаляется последовательно по одному элементу, начиная с вершины, или по одной книге из стопки.
Очереди FIFO
Очередью FIFO (First - In - First- Out - "первым пришел - первым вы-шел") называется такой последовательный список с переменной длиной, в котором включение элементов выполняется только с одной стороны списка (эту сторону часто называют концом или хвостом очереди), а исключение - с другой стороны (называемой началом или головой очереди).
Основные операции над очередью - те же, что и над стеком - включе-ние, исключение, определение размера, очистка, неразрушающее чтение.
Деки
Дек - особый вид очереди. Дек (от англ. deq - double ended queue, т.е очередь с двумя концами) - это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любо-го из двух концов списка. Частный случай дека - дек с ограниченным вхо-дом и дек с ограниченным выходом. Логическая и физическая структуры дека аналогичны логической и физической структуре кольцевой FIFO-очереди. Однако, применительно к деку целесообразно говорить не о начале и конце, а о левом и правом конце.
Операции над деком: включение элемента справа, слева; исключение элемента справа, слева; определение размера; очистка.
Строки
Строка - это линейно упорядоченная последовательность символов, принадлежащих конечному множеству символов, называемому алфавитом. Строки обладают следующими важными свойствами: их длина, как прави-ло, переменна, хотя алфавит фиксирован; обычно обращение к символам строки идёт с какого-нибудь одного конца последовательности, т.е важна упорядоченность этой последовательности, а не её индексация; в связи с этим свойством строки часто называют также цепочками; чаще всего целью доступа к строке является не отдельный её элемент (хотя это тоже не ис-ключается), а некоторая цепочка символов в строке.
Говоря о строках, обычно имеют в виду текстовые строки - строки, со-стоящие из символов, входящих в алфавит какого-либо выбранного языка, цифр, знаков препинания и других служебных символов.
Базовыми операциями над строками являются: определение длины строки; присваивание строк; конкатенация (сцепление) строк; выделение подстроки; поиск вхождения.
Операция определения длины строки имеет вид функции, возвращае-мое значение которой - целое число - текущее число символов в строке. Операция присваивания имеет тот же смысл, что и для других типов дан-ных.
Динамические структуры данных
Динамические структуры по определению характеризуются отсутстви-ем физической смежности элементов структуры в памяти непостоянством и непредсказуемостью размера (числа элементов) структуры в процессе её обработки. Для установления связи между элементами динамической структуры используются указатели, через которые устанавливаются явные связи между элементами. Такое представление данных в памяти называется связным. Элемент динамической структуры состоит из двух полей:
1. информационного поля или поля данных, в котором содержатся те данные, ради которых и создается структура; в общем случае информационное поле само является интегрированной структу-рой - вектором, массивом, записью и т.п.;
2. поле связок, в котором содержатся один или несколько указате-лей, связывающий данный элемент с другими элементами струк-туры;
Когда связное представление данных используется для решения при-кладной задачи, для конечного пользователя "видимым" делается только содержимое информационного поля, а поле связок используется только программистом-разработчиком.
Достоинства связного представления данных: в возможности обеспе-чения значительной изменчивости структур; размер структуры ограничи-вается только доступным объёмом машинной памяти; при изменении логи-ческой последовательности элементов структуры требуется не перемеще-ние данных в памяти, а только коррекция указателей.
Вместе с тем связное представление не лишено и недостатков: работа с указателями требует, как правило, более высокой квалификации от про-граммиста; на поля связок расходуется дополнительная память; доступ к элементам связной структуры может быть менее эффективным по времени.
Последний недостаток является наиболее серьёзным и именно им ограничивается применимость связного представления данных.
183
Связные линейные списки.
Списком называется упорядоченное множество, состоящее из пере-менного числа элементов, к которым применимы операции включения, ис-ключения. Список, отражающий отношения соседства между элементами, называется линейным. Если ограничения на длину списка не допускаются, то список представляется в памяти в виде связной структуры. Линейные связные списки являются простейшими динамическими структурами дан-ных. Графически связи в списках удобно изображать с помощью стрелок.
На рис. 5.1 приведена структура односвязного списка. На нем поле INF - информационное поле, данные, NEXT - указатель на следующий элемент списка. Каждый список должен иметь особый элемент, называе-мый указателем начала списка, который по формату отличен от остальных элементов. В поле указателя последнего элемента списка находится специ-альный признак nil, свидетельствующий о конце списка.

Рис. 5.1. Структура односвязного списка
Но, обработка односвязного списка не всегда удобна, так как отсут-ствует возможность продвижения в противоположную сторону. Такую возможность обеспечивает двухсвязный список, каждый элемент которого содержит два указателя: на следующий и предыдущий элементы списка. Структура линейного двухсвязного списка приведена на рис. 5.2, где поле NEXT - указатель на следующий элемент, поле PREV - указатель на предыдущий элемент. В крайних элементах соответствующие указатели должны содержать nil, как и показано на рис. 5.2.
Для удобства обработки списка добавляют еще один особый элемент - указатель конца списка. Наличие двух указателей в каждом элементе усложняет список и приводит к дополнительным затратам памяти, но в то же время обеспечивает более эффективное выполнение некоторых опера-ций над списком.

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

Рис. 5.3. Структура кольцевого двухсвязного списка
Линейные списки находят широкое применение в приложениях, где непредсказуемы требования на размер памяти, необходимой для хранения данных; большое число сложных операций над данными, особенно вклю-чений и исключений. На базе линейных списков могут строится стеки, оче-реди и деки. Представление очереди с помощью линейного списка позво-ляет достаточно просто обеспечить любые желаемые дисциплины обслу-живания очереди. Особенно это удобно, когда число элементов в очереди трудно предсказуемо.
Нелинейные разветвленные списки
Нелинейным разветвленным списком является список, элементами ко-торого могут быть тоже списки. Если один из указателей каждого элемента списка задает порядок обратный к порядку, устанавливаемому другим указателем, то такой двусвязный список будет линейным. Если же один из указателей задает порядок произвольного вида, не являющийся обратным по отношению к порядку, устанавливаемому другим указателем, то такой список будет нелинейным.
В обработке нелинейный список определяется как любая последова-тельность атомов и списков (подсписков), где в качестве атома берется лю-бой объект, который при обработке отличается от списка тем, что он структурно неделим.
Нелинейные структуры данных
Графы
Граф - это сложная нелинейная многосвязная динамическая структура, отображающая свойства и связи сложного объекта.
Многосвязная структура обладает следующими свойствами: на каж-дый элемент (узел, вершину) может быть произвольное количество ссылок; каждый элемент может иметь связь с любым количеством других элемен-тов; каждая связка (ребро, дуга) может иметь направление и вес.
В узлах графа содержится информация об элементах объекта. Связи между узлами задаются ребрами графа. Ребра графа могут иметь направ-ленность, показываемую стрелками, тогда они называются ориентиро-ванными, ребра без стрелок - неориентированные.
Граф, все связи которого ориентированные, называется ориентиро-ванным графом или орграфом; граф со всеми неориентированными свя-зями - неориентированным графом; граф со связями обоих типов - сме-шанным графом. Примеры изображений графов даны на рис. 6.
а). ((A,B),(B,A)) б). (< A,B >,< B,A >).

Рис.6. Граф неориентированный (а) и ориентированный (б).
Для ориентированного графа число ребер, входящих в узел, называ-ется полустепенью захода узла, выходящих из узла - полустепенью исхода. Количество входящих и выходящих ребер может быть любым, в том числе и нулевым. Граф без ребер является нуль-графом. Если ребрам графа со-ответствуют некоторые значения, то граф и ребра называются взвешенны-ми. Мультиграфом называется граф, имеющий параллельные (соединяю-щие одни и те же вершины) ребра, в противном случае граф называется простым.
Путь в графе - это последовательность узлов, связанных ребрами; элементарным называется путь, в котором все ребра различны, простым называется путь, в котором все вершины различны. Путь от узла к самому себе называется циклом, а граф, содержащий такие пути - циклическим.
Два узла графа смежны, если существует путь от одного из них до другого. Узел называется инцидентным к ребру, если он является его вер-шиной, т.е. ребро направлено к этому узлу.
Логически структура-граф может быть представлена матрицей смеж-ности или матрицей инцидентности.
Деревья
Дерево - это граф, который характеризуется следующими свойствами:
1. Существует единственный элемент (узел или вершина), на кото-рый не ссылается никакой другой элемент - и который называет-ся корнем (рис. 7; 8 - A, G, M - корни).
2. Начиная с корня и следуя по определенной цепочке указателей, содержащихся в элементах, можно осуществить доступ к любо-му элементу структуры.
3. На каждый элемент, кроме корня, имеется единственная ссылка, т.е. каждый элемент адресуется единственным указателем.

рис. 7. Дерево рис. 8. Лес
Название "дерево" проистекает из логической эквивалентности древо-видной структуры абстрактному дереву в теории графов. Линия связи между парой узлов дерева называется обычно ветвью. Те узлы, которые не ссылаются ни на какие другие узлы дерева, называются листьями или терминальными вершинами (рис. 7; 8 - b, k, l, h - листья). Узел, не являю-щийся листом или корнем, считается промежуточным или узлом ветвле-ния (нетерминальной или внутренней вершиной).
Деревья нужны для описания любой структуры с иерархией. Тради-ционные примеры таких структур: генеалогические деревья, десятичная классификация книг в библиотеках, иерархия должностей в организации и т. д.
Ориентированное дерево - это такой ациклический орграф (ориенти-рованный граф), у которого одна вершина, называемая корнем, имеет по-лустепень захода, равную 0, а остальные - полустепени захода, равные 1. Ориентированное дерево должно иметь по крайней мере одну вершину. Изолированная вершина также представляет собой ориентированное дере-во.
Вершина ориентированного дерева, полустепень исхода которой рав-на нулю, называется концевой (висячей) вершиной или листом; все остальные вершины дерева называют вершинами ветвления. Длина пути от корня до некоторой вершины называется уровнем (номером яруса) этой вершины. Уровень корня ориентированного дерева равен нулю, а уровень любой другой вершины равен расстоянию (т.е. модулю разности номеров уровней вершин) между этой вершиной и корнем. Ориентированное дере-во является ациклическим графом, все пути в нем элементарны.




Тэги: основные структуры данных, информация и данные, классификация структур данных, статические структуры данных, динамические структуры данных, нелинейные структуры данных



x

Уважаемый посетитель сайта!

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

В целях борьбы с ботами каждая работа заархивирована в rar архив. Пароль к архиву указан ниже. Благодарим за понимание.

Пароль к архиву: 4Q3514

Я согласен с условиями использования сайта