Файл: Контрольная работа на тему Классификация структур данных по учебной дисциплине Алгоритмизация и программирование.docx

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

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

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

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

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

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

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

– звенья связи элементов, для простого элемента это звено содержит адреса

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

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

– указатель строки, который содержит адрес указателя начала кольца;

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

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

---

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

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

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

по уровням иерархии следующим образом:

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

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

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

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

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

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

---

своей левой ветви элементы с меньшим, чем у него, значением ключа, а на правой ветви – элементы с большим или равным значением ключа.

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

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

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

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

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

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

• 
  вектора описания записей;
  

• 
  вектора описания ключей;
  
• 
  матрицы значений ключей.
  

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

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

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

---

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

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

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

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

Недостатком иерархических структур является относительная трудоемкость записи адреса элемента данных и сложность упорядочения. Часто методы упорядочения в таких структурах основывают на предварительной индексации

---

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

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

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

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

1. 
   Гуда А.Н., Бутакова М.А., Нечитайло Н.М., Чернов А.В. Информатика. Общий курс: Учебник / Под ред. академика РАН В.И. Колесникова. – М.: Издательско-торговая корпорация «Дашков и К»; Ростов н/Д: Наука-Пресс, 2007 г. – 400 с.
   
2. 
   «Информатика. Терминологический словарь». Всероссийский НИИ комплексной информации по стандартизации и качеству; Москва, 2008 г. – 350 с.
   
3. 
   «Информатика, общий курс» под ред. Колесникова В.И. Наука-Пресс. Москва, 2007 г. – 315 с.
   
4. 
   Каймин В.А. Информатика: Учебник. – М.: ИНФРА-М, 2007 г. – 232 с.
   
5. 
   Когаловский М.Р. «Энциклопедия технологий баз данных» Финансы и статистика; Москва, 2008 г. – 195 с.
   
6. 
   Модели и структуры данных В.Д. Далека, А.С. Деревянко, О.Г. Кравец, Л.Е. Тимановская. Учебное пособие. Харьков: ХГПУ, 2009 г. – 241 с.
   
7. 
   Соболь Б.В., Галин А.Б., Панов Ю.В., Рашидова Е.В., Садовой Н.Н. «Информатика»; Ростов н/Д: Феникс, 2008 г. – 145 с.
   
8. 
   Советов Б.Я. Информационные технологии. Учебник для студентов вузов. 2006 г. – 263 с.
   
9. 
   Уоллес Вонг. Основы программирования для «чайников». ДИАЛЕКТИКА. Москва – Санкт-Петербург – Киев. 2007 г. – 335 с.
   

---