Необходимым условием хранения информации в памяти компьютера является возможность преобразования этой самой информации в подходящую для компьютера форму. В том случае, если это условие выполняется, следует определить структуру, пригодную именно для наличествующей информации, ту, которая предоставит требующийся набор возможностей работы с ней.
Кольцевой список
Здесь под структурой понимается способ представления информации, посредством которого совокупность отдельно взятых элементов образует нечто единое, обусловленное их взаимосвязью друг с другом. Скомпонованные по каким-либо правилам и логически связанные межу собой, данные могут весьма эффективно обрабатываться, так как общая для них структура предоставляет набор возможностей управления ими – одно из того за счет чего достигаются высокие результаты в решениях тех или иных задач.
Но не каждый объект представляем в произвольной форме, а возможно и вовсе для него имеется лишь один единственный метод интерпретации, следовательно, несомненным плюсом для программиста будет знание всех существующих структур данных. Таким образом, часто приходиться делать выбор между различными методами хранения информации, и от такого выбора зависит работоспособность продукта.
Говоря о не вычислительной технике, можно показать ни один случай, где у информации видна явная структура. Наглядным примером служат книги самого разного содержания. Они разбиты на страницы, параграфы и главы, имеют, как правило, оглавление, то есть интерфейс пользования ими. В широком смысле, структурой обладает всякое живое существо, без нее органика навряд-ли смогла бы существовать.
Вполне вероятно, читателю приходилось сталкиваться со структурами данных непосредственно в информатике, например, с теми, что встроены в язык программирования. Часто они именуются типами данных. К таковым относятся: массивы, числа, строки, файлы и т. д.
Методы хранения информации, называемые «простыми», т. е. неделимыми на составные части, предпочтительнее изучать вместе с конкретным языком программирования, либо же глубоко углубляться в суть их работы. Поэтому здесь будут рассмотрены лишь «интегрированные» структуры, те которые состоят из простых, а именно: массивы, списки, деревья и графы.
Массивы.
Массив – это структура данных с фиксированным и упорядоченным набором однотипных элементов (компонентов). Доступ к какому-либо из элементов массива осуществляется по имени и номеру (индексу) этого элемента. Количество индексов определяет размерность массива. Так, например, чаще всего встречаются одномерные (вектора) и двумерные (матрицы) массивы.
Первые имеют один индекс, вторые – два. Пусть одномерный массив называется A, тогда для получения доступа к его i-ому элементу потребуется указать название массива и номер требуемого элемента: A[i]. Когда A – матрица, то она представляема в виде таблицы, доступ к элементам которой осуществляется по имени массива, а также номерам строки и столбца, на пересечении которых расположен элемент: A, где i – номер строки, j – номер столбца.
В разных языках программирования работа с массивами может в чем-то различаться, но основные принципы, как правило, везде одни. В языке Pascal, обращение к одномерному и двумерному массиву происходит точно так, как это показано выше, а, например, в C++ двумерный массив следует указывать так: A[i][j]. Элементы массива нумеруются поочередно. На то, с какого значения начинается нумерация, влияет язык программирования. Чаще всего этим значением является 0 или 1.
Массивы, описанного типа называются статическими, но существуют также массивы по определенным признакам отличные от них: динамические и гетерогенные. Динамичность первых характеризуется непостоянностью размера, т. е. по мере выполнения программы размер динамического массива может изменяться. Такая функция делает работу с данными более гибкой, но при этом приходится жертвовать быстродействием, да и сам процесс усложняется.
Обязательный критерий статического массива, как было сказано, это однородность данных, единовременно хранящихся в нем. Когда же данное условие не выполняется, то массив является гетерогенным. Его использование обусловлено недостатками, которые имеются в предыдущем виде, но оно оправданно во многих случаях.
Таким образом, даже если Вы определились со структурой, и в качестве нее выбрали массив, то этого все же недостаточно. Ведь массив это только общее обозначение, род для некоторого числа возможных реализаций. Поэтому необходимо определиться с конкретным способом представления, с наиболее подходящим массивом.
Списки.
Список – абстрактный тип данных, реализующий упорядоченный набор значений. Списки отличаются от массивов тем, что доступ к их элементам осуществляется последовательно, в то время как массивы – структура данных произвольного доступа. Данный абстрактный тип имеет несколько реализаций в виде структур данных. Некоторые из них будут рассмотрены здесь.
Список (связный список) – это структура данных, представляющая собой конечное множество упорядоченных элементов, связанных друг с другом посредствам указателей. Каждый элемент структуры содержит поле с какой-либо информацией, а также указатель на следующий элемент. В отличие от массива, к элементам списка нет произвольного доступа.
Односвязный списокВ односвязном списке, приведенным выше, начальным элементом является Head list (голова списка [произвольное наименование]), а все остальное называется хвостом. Хвост списка составляют элементы, разделенные на две части: информационную (поле info) и указательную (поле next). В последнем элементе вместо указателя, содержится признак конца списка – nil.
Односвязный список не слишком удобен, т. к. из одной точки есть возможность попасть лишь в следующую точку, двигаясь тем самым в конец. Когда кроме указателя на следующий элемент есть указатель и на предыдущий, то такой список называется двусвязным.
Двусвязный список
Возможность двигаться как вперед, так и назад полезна для выполнения некоторых операций, но дополнительные указатели требуют задействования большего количества памяти, чем таковой необходимо в эквивалентном односвязном списке.
Для двух видов списков описанных выше существует подвид, называемый кольцевым списком. Сделать из односвязного списка кольцевой можно добавив всего лишь один указатель в последний элемент, так чтобы он ссылался на первый. А для двусвязного потребуется два указателя: на первый и последний элементы.
Кольцевой список
Помимо рассмотренных видов списочных структур есть и другие способы организации данных по типу «список», но они, как правило, во многом схожи с разобранными, поэтому здесь они будут опущены.
Кроме различия по связям, списки делятся по методам работы с данными. О некоторых таких методах сказано далее.
Стек.
Стек
Стек характерен тем, что получить доступ к его элементом можно лишь с одного конца, называемого вершиной стека, иначе говоря: стек – структура данных, функционирующая по принципу LIFO (last in - first out, «последним пришёл - первым вышел»). Изобразить эту структуру данных лучше в виде вертикального списка, например, стопки каких-либо вещей, где чтобы воспользоваться одной из них нужно поднять все те вещи, что лежат выше нее, а положить предмет можно лишь на вверх стопки.
В показанном односвязном списке операции над элементами происходят строго с одного конца: для включения нужного элемента в пятую по счету ячейку необходимо исключить тот элемент, который занимает эту позицию. Если бы было, например 6 элементов, а вставить конкретный элемент требовалось также в пятую ячейку, то исключить бы пришлось уже два элемента.
Очередь.
Структура данных «Очередь» использует принцип организации FIFO (First In, First Out - «первым пришёл - первым вышел»). В некотором смысле такой метод более справедлив, чем тот, по которому функционирует стек, ведь простое правило, лежащее в основе привычных очередей в различные магазины, больницы считается вполне справедливым, а именно оно является базисом этой структуры. Пусть данное наблюдение будет примером. Строго говоря, очередь – это список, добавление элементов в который допустимо, лишь в его конец, а их извлечение производиться с другой стороны, называемой началом списка.
Очередь
Дек
Дек (deque - double ended queue, «двухсторонняя очередь») – стек с двумя концами. Действительно, несмотря конкретный перевод, дек можно определять не только как двухстороннюю очередь, но и как стек, имеющий два конца. Это означает, что данный вид списка позволяет добавлять элементы в начало и в конец, и то же самое справедливо для операции извлечения.
Дек
Эта структура одновременно работает по двум способам организации данных: FIFO и LIFO. Поэтому ее допустимо отнести к отдельной программной единице, полученной в результате суммирования двух предыдущих видов списка.
Графы.
Раздел дискретной математики, занимающийся изучением графов, называется теорией графов. В теории графов подробно рассматриваются известные понятия, свойства, способы представления и области применения этих математических объектов. Нас же интересует, лишь те ее аспекты, которые важны в программировании.
Граф – совокупность точек, соединенных линиями. Точки называются вершинами (узлами), а линии – ребрами (дугами).
Как показано на рисунке различают два основных вида графов: ориентированные и неориентированные. В первых ребра являются направленными, т. е. существует только одно доступное направление между двумя связными вершинами, например из вершины 1 можно пройти в вершину 2, но не наоборот. В неориентированном связном графе из каждой вершины можно пройти в каждую и обратно. Частный случай двух этих видов – смешанный граф. Он характерен наличием как ориентированных, так и неориентированных ребер.
Степень входа вершины – количество входящих в нее ребер, степень выхода – количество исходящих ребер.
Ребра графа необязательно должны быть прямыми, а вершины обозначаться именно цифрами, так как показано на рисунке. К тому же встречаются такие графы, ребрам которых поставлено в соответствие конкретное значение, они именуются взвешенными графами, а это значение – весом ребра. Когда у ребра оба конца совпадают, т. е. ребро выходит из вершины F и входит в нее, то такое ребро называется петлей.
Графы широко используются в структурах, созданных человеком, например в компьютерных и транспортных сетях, web-технологиях. Специальные способы представления позволяют использовать граф в информатике (в вычислительных машинах). Самые известные из них: «Матрица смежности», «Матрица инцидентности», «Список смежности», «Список рёбер». Два первых, как понятно из названия, для репрезентации графа используют матрицу, а два последних – список.
Деревья.
Неупорядоченное дерево
Дерево как математический объект это абстракция из соименных единиц, встречающихся в природе. Схожесть структуры естественных деревьев с графами определенного вида говорит о допущении установления аналогии между ними. А именно со связанными и вместе с этим ациклическими (не имеющими циклов) графами. Последние по своему строению действительно напоминают деревья, но в чем то и имеются различия, например, принято изображать математические деревья с корнем расположенным вверху, т. е. все ветви «растут» сверху вниз. Известно же, что в природе это совсем не так.
Поскольку дерево это по своей сути граф, у него с последним многие определения совпадают, либо интуитивно схожи. Так корневой узел (вершина 6) в структуре дерева – это единственная вершина (узел), характерная отсутствием предков, т. е. такая, что на нее не ссылается ни какая другая вершина, а из самого корневого узла можно дойти до любой из имеющихся вершин дерева, что следует из свойства связности данной структуры. Узлы, не ссылающиеся ни на какие другие узлы, иначе говоря, ни имеющие потомков называются листьями (2, 3, 9), либо терминальными узлами. Элементы, расположенные между корневым узлом и листьями – промежуточные узлы (1, 1, 7, 8). Каждый узел дерева имеет только одного предка, или если он корневой, то не имеет ни одного.
Поддерево – часть дерева, включающая некоторый корневой узел и все его узлы-потомки. Так, например, на рисунке одно из поддеревьев включает корень 8 и элементы 2, 1, 9.
С деревом можно выполнять многие операции, например, находить элементы, удалять элементы и поддеревья, вставлять поддеревья, находить корневые узлы для некоторых вершин и др. Одной из важнейших операций является обход дерева. Выделяются несколько методов обхода. Наиболее популярные из них: симметричный, прямой и обратный обход. При прямом обходе узлы-предки посещаются прежде своих потомков, а в обратном обходе, соответственно, обратная ситуация. В симметричном обходе поочередно просматриваются поддеревья главного дерева.
Представление данных в рассмотренной структуре выгодно в случае наличия у информации явной иерархии. Например, работа с данными о биологических родах и видах, служебных должностях, географических объектах и т. п. требует иерархически выраженной структуры, такой как математические деревья.
ТИПЫ И СТРУКТУРЫ ДАННЫХ
Методические указания по дисциплине «Алгоритмы и структуры данных»
Составитель О.Л. Чагаева
Подготовлены кафедрой «Программные средства и системы» ФУО УрФУ
Введение
В окружающем нас мире находится огромное разнообразие предметов, объектов, явлений, процессов, отображаемых посредством информации.
Каждая представляемая информацией сущность (объект, явление) имеет ряд характерных для нее свойств (черт, признаков, параметров, характеристик, моментов). Например, свойствами материала являются его вес, габариты, сорт, цена, номенклатурный номер и др. Свойствами-признаками, характеризующими такую сущность, как организация-покупатель, являются наименование, ведомственная принадлежность, адрес, номер расчетного счета в Госбанке и др.
Свойства физической сущности отображаются с помощью переменных величин, являющихся элементарными единицами информации и называемых реквизитами.
Реквизит - это логически неделимый элемент любой сложной информационной совокупности, соотносимый с определенным свойством отображаемого информацией объекта или процесса.
В обрабатываемой информации реквизиты представляются как бы «атомами», из которых компонуются все остальные, более сложные по структуре образования информации. И наоборот, единицы информации любой сложности можно последовательным разложением на составляющие компоненты в конечном итоге расчленить до таких составляющих - переменных величин, которые не поддаются дальнейшему логическому разбиению. Такие элементарные компоненты и будут реквизитами.
Другими часто встречающимися в литературе синонимами реквизита являются элемент, поле, терм, признак иатрибут .
У каждого реквизита есть имя. При алгоритмизации и программировании с целью компактного написания чаще всего применяют сокращенные имена-идентификаторы, причем конкретные реализации обычно ограничивают их длину, алфавит и сферу действия. В ряде случаев допускается также употребление синонимов наименований реквизита, в том числе таких полных наименований, которые используются только во внешних документах, например, в качестве заголовков граф отчетов.
Каждому реквизиту присуще некоторое конечное множество значений в зависимости от характеристики того свойства объекта (явления), которое информационно отображает данный реквизит. Это множество, именуемое классом значений, одно, например, для параметра «температура больного» и другое - для признака «пол больного».
Значение реквизита, таким образом, есть в каждый заданный момент времени одна из позиций класса значений данного реквизита, отображающая, как предполагается, соответствующее состояние (из множества состояний) того свойства объекта (явления), которое характеризует реквизит. Так, текущим значением реквизита «температура больного» может быть 37,4°, а реквизита «пол больного» - «мужской». Другими словами, значение реквизита используется для представления значения соответствующего свойства сущности.
Существует ряд типов реквизитов в зависимости от видов значений, которые они могут иметь. Наиболее распространенными типами реквизитов, однако, являются числовой и текстовой .
Реквизиты числового типа характеризуют количественные свойства сущностей, полученные в результате подсчета натуральных единиц, измерения, взвешивания, вычисления на основе других количественно-суммовых данных и т. п. Поэтому значениями таких реквизитов служат числа со всеми свойственными им чертами и атрибутами.
В конкретных представлениях фигурирует несколько типов числовых величин в зависимости от класса чисел, системы счисления, фиксации десятичной запятой, упаковки и других; накладываются ограничения на диапазон чисел, форматы их представления на вводевыводе и различных носителях даже в рамках одной реализации. Поскольку все реквизиты числового типа активно используются в различных арифметических операциях, а большинство из них вообще создается в результате осуществления таких операций, указанные отличия и ограничения следует постоянно иметь в виду, так же как и необходимость соответствующего аппарата преобразования.
Реквизиты текстового типа выражают, как правило, качественные свойства сущностей и характеризуют обстоятельства, при которых имел место изучаемый процесс и были получены те или
иные числовые значения. Поэтому такие реквизиты называются признаками.
Значениями признаков являются последовательности символов (букв, цифр, различных знаков и специальных обозначений), называемые строками, или текстом.
Полный набор всевозможных попарно различимых символов данной информационной системы составляет ее алфавит, зависящий от характера задач, применяемых технических средств обработки данных и других факторов. Причем на различных стадиях обработки и даже в рамках одной вычислительной системы возможно применение различных алфавитов.
Размер алфавита (число разнообразных символов, которые могут быть в одном разряде величины) и его состав (набор) имеют прямое отношение к решению следующих проблем:
кодирования и дешифровки,
компактной записи значений единиц информации,
эффективного хранения данных, ускорения их поиска, передачи, ввода в вычислительные машины,
получения от машин информации в наиболее удобной для потребления форме,
снижения затрат на всевозможные перезаписи.
Поэтому выбору алфавита придается немаловажное значение.
Для использования информации, в алгоритмизации и программировании очень большое значение уделяется таким понятиям, как тип и структура данного.
1. ТИПЫ ДАННЫХ
Вычислительный процесс на ЭВМ реализуется, как известно, с помощью программ и данных. Сама программа тоже относится к данным. Поэтому можно сказать, что данные описывают любую информацию, с которой может работать ЭВМ. При этом под информацией понимаются любые факты и знания об объектах реального мира, процессах и отношениях и связях между ними. Все данные характеризуются рядом атрибутов (признаков, реквизитов), в том числе значением.
Кроме значения, к таким признакам относится понятие «тип данного». Тип данного определяется множеством значений данного и набором операций, которые можно выполнять над этими значениями в соответствии с их известными свойствами. Следовательно, тип данного определяет те операции, которые допустимы над соответствующим значением.
В языках программирования обычно используются такие распространенные типы данных, как целые, вещественные, символьные, битовые, указатели и пр.
2. СТРУКТУРЫ ДАННЫХ
Особенностью данного того или иного типа является простота организации (неструктурированность).
Структура данных – это совокупность элементов данных, между которыми существуют некоторые отношения, причем элементами данных могут быть как простые данные (скаляры), так и структуры данных.
Таким образом, структуру можно определить следующим образом: S = (D, R), где D - множество элементов данных, R – множество отношений между элементами данных.
Все связи одного элемента данных с другими образуют элемент отношений, ассоциированный с соответствующим элементом данных.
Графическое изображение структуры должно отражать ее элементы данных и связи (отношения между ними), поэтому структуру удобно изображать в виде графа. При этом вершины графа можно интерпретировать как элементы данных, а отношениям между элементами данных соответствуют ориентированные дуги или неориентированное ребра (рис. 1).
Таким образом описанную и представленную структуру данных называют абстрактной или логической, так как она рассматривается без учета ее представления в машинной памяти. Но любая структура данных должна быть представлена в машинной памяти. Такая структура данных называется физической структурой, структурой хранения, внутренней структурой или структурой памяти.
Рис 1. Неориентированный (а) и ориентированный (б) граф
Таким образом, физическая структура данных отражает способ представления данных в машинной памяти.
В общем случае между логической и соответствующей ей физической структурой существует различие, степень которого зависит от самой структуры и особенностей той физической среды, в которой она должна быть отражена.
Например, с точки зрения языков программирования двумерный массив представляет собой прямоугольную таблицу, а в памяти – это линейная последовательность ячеек, в каждой из которых хранится значение одного из элементов массива, причем элементы массива упорядочены по строкам (или столбцам).
Разумеется, между логической и физической структурой должен существовать механизм, позволяющий отобразить логическую структуру в физическую.
Таким образом, каждую структуру данных можно характеризовать ее логическим (абстрактным) и физическим (конкретным) представлением, а также совокупностью операций на этих двух уровнях представления структуры (рис. 2).
Операции над логической структурой
Логическая структура данных
Операции над физической структурой
Физическая структура данных
Рис. 2. Отображение между логическим и физическим представлением структуры данных
2.1. Классификация структур данных
В зависимости от отсутствия или наличия явно заданных связей между элементами данных следует различать несвязанные структуры (векторы, массивы, строки, стеки, очереди) и связные структуры (связные списки).
Важные признак структуры – ее изменчивость – изменение числа элементов и/или связей между элементами структуры. Значение элемента данных не имеется в виду, так как в этом случае это свойство было бы характерно для всех структур данных за исключением, может быть, констант и данных, хранящихся в ПЗУ. По признаку изменчивости различают статические, полустатические и динамические структуры.
Важный признак структуры данных – характер упорядоченности ее элементов. По этому признаку структуры можно делить на линейно-упорядоченные, или линейные, и нелинейные.
В зависимости от характера взаимного расположения элементов в памяти линейные структуры можно разделить на структуры с последовательным распределением их элементов в памяти (векторы, строки, массивы, стеки, очереди) и структуры с произвольным связным распределением элементов в памяти (односвязные, двусвязные, циклически связанные, ассоциативные списки). Примером нелинейных структур являются многосвязные списки, древовидные структуры и графовые структуры общего вида.
2.2. Простейшие статические структуры
К простейшим структурам данных обычно относят векторы, массивы, записи, таблицы. Они характеризуются следующими свойствами:
постоянство структуры в течение всего времени ее существования;
смежность элементов и непрерывность области памяти, отводимой сразу для всех элементов структуры;простота и постоянство отношений между элементами
структуры, позволяющие исключить информацию об этих отношениях из области памяти, выделенной для элементов структуры, и хранить ее, например, в компактной форме в дескрипторах.
В силу этих свойств векторы, массивы, записи и таблицы принято считать статическими структурами.
2.2.1. Вектор
Вектор – это конечное упорядоченное множество простых данных или скаляров, одного и того же типа. С геометрической точки зрения вектор задает точку в многомерном пространстве, координатами которой служат значения элементов вектора.
Элементы вектора находятся друг с другом в единственно возможном отношении – отношении непосредственного следования. Строгая последовательность элементов вектора позволяет
пронумеровать их последовательными целыми числами – индексами. Логическая структура вектора полностью описывается числом и типом его элементов. Например, int array – целочисленный массив, состоящий из 10 элементов.
Важнейшая операция над вектором – доступ к его элементам. Как только организован доступ к элементу, над ним может быть выполнена любая операция, имеющая смысл для выбранного типа данных.
На логическом уровне для доступа к элементу вектора достаточно указать имя вектора и значение индекса соответствующего элемента. Например: array + array.
Физическая структура вектора – это последовательность одинаковых по длине участков памяти, называемых полями или слотами, каждый из которых предназначен для хранения одного элемента вектора. Поле может иметь размер минимально адресуемой ячейки памяти или соответствовать целой группе последовательных ячеек памяти.
Нередко физической структуре ставится в соответствие дескриптор или заголовок, который содержит информацию о данной физической структуре. Дескриптор необходим, например, в том случае, когда граничные размеры вектора становятся известны только на этапе выполнения программы.
Дескриптор тоже хранится в машинной памяти и представляет собой структуру, называемую записью. Для вектора дескриптор обычно хранит его имя, размер, значения граничных индексов, тип элемента, размер поля или слота, адрес первого элемента вектора (поля, хранящего этот элемент).
2.2.2. Массив
Массивом называется такой вектор, каждый элемент которого - вектор. В свою очередь, элементы вектора, являющегося элементом массива, также могут быть векторами. Процесс перехода от элемента к элементу этого элемента и так далее рано или поздно должен завершиться скаляром некоторого типа данных, причем этому типу должны соответствовать все скалярные элементы массива (рис. 3).
Рис. 3. Вид многомерного массива
На рис.3 представлен вид многомерного массива: в каждом узле решетки находится элемент массива. Таким образом, размерность его равна (3,3,2).
Как и для вектора, важнейшей элементарной операцией для массива является доступ к его элементу. На уровне логической структуры она осуществляется при помощи имени массива и упорядоченного набора индексов, однозначно идентифицирующих элемент массива. Например: array[i][j].
В отличие от вектора, для массива общего вида преобразование логической структуры в физическую имеет более сложный вид. Это преобразование выполняется путем процесса линеаризации, в ходе которого многомерная логическая структура массива отображается в одномерную физическую структуру. Эта физическая структура представляет собой линейно упорядоченную последовательность элементов массива. Таким образом, физическая структура многомерного массива аналогична физической структуре вектора.
Несмотря на это, дескриптор многомерного массива отличается от дескриптора вектора. Например, в нем должна хранится информация о размерности массива, способе упорядочения элементов (по строкам или столбцам).
2.2.3. Запись
Запись – это конечное упорядоченное множество элементов, содержащее в общем случае данные различных типов.
Элементы записи часто называют полями. Запись – это обобщенное понятие вектора, при котором не требуется однотипность или
Понятие структуры данных является настолько фундаментальным, что для него сложно подобрать простое определение. Задача упрощается, если попробовать сформулировать это понятие по отношению к типам данным и переменным. Как известно, программа представляет собой единство алгоритма (процедур, функций) и обрабатываемых ими данных. Данные, в свою очередь, определяются базовыми и производными типами данных -"идеальными" представлениями переменных фиксированной размерности с наборами известных операций над ними и их компонентами. Переменные -это именованные области памяти, в которые "отображаются" сконструированные типы данных.
В программе всегда можно выделить группы косвенно связанных (по использованию данных в одних и тех же процедурах и функциях) и непосредственно связанных (по наличию взаимосвязей через указатели) переменных. Их в первом приближении и можно считать структурами данных.
Различаются ПРОСТЫЕ (базовые, примитивные) структуры (типы) данных и ИНТЕГРИРОВАННЫЕ (структурированные, композитные, сложные). Простыми называются такие структуры данных, которые не могут быть расчленены на составные части, большие, чем биты. С точки зрения физической структуры важным является то обстоятельство, что в данной машинной архитектуре, в данной системе программирования мы всегда можем заранее сказать, каков будет размер данного простого типа и какова структура его размещения в памяти. С логической точки зрения простые данные являются неделимыми единицами. Интегрированными называются такие структуры данных, составными частями которых являются другие структуры данных - простые или в свою очередь интегрированные. Интегрированные структуры данных конструируются программистом с использованием средств интеграции данных, предоставляемых языками программирования.
В зависимости от отсутствия или наличия явно заданных связей между элементами данных следует различать НЕСВЯЗНЫЕ структуры (векторы, массивы, строки, стеки, очереди) и СВЯЗНЫЕ структуры (связные списки).
Весьма важный признак структуры данных - ее изменчивость - изменение числа элементов и (или) связей между элементами структуры. В определении изменчивости структуры не отражен факт изменения значений элементов данных, поскольку в этом случае все структуры данных имели бы свойство изменчивости. По признаку изменчивости различают структуры СТАТИЧЕСКИЕ, ПОЛУСТАТИЧЕСКИЕ, ДИНАМИЧЕСКИЕ. Классификация структур данных по признаку изменчивости приведена на рис. 1.1. Базовые структуры данных, статические, полустатические и динамические характерны для оперативной памяти и часто называются оперативными структурами. Файловые структуры соответствуют структурам данных для внешней памяти.
Рис. 1.1. Классификация структур данных
Важный признак структуры данных - характер упорядоченности ее элементов. По этому признаку структуры можно делить на ЛИНЕЙНЫЕ И НЕЛИНЕЙНЫЕ структуры.
В зависимости от характера взаимного расположения элементов в памяти линейные структуры можно разделить на структуры с ПОСЛЕДОВАТЕЛЬНЫМ распределением элементов в памяти (векторы, строки, массивы, стеки, очереди) и структуры с ПРОИЗВОЛЬНЫМ СВЯЗНЫМ распределением элементов в памяти (односвязные, двусвязные списки). Пример нелинейных структур - многосвязные списки, деревья, графы.
В языках программирования понятие "структуры данных" тесно связано с понятием "типы данных". Любые данные, т.е. константы, переменные, значения функций или выражения, характеризуются своими типами.
Информация по каждому типу однозначно определяет:
· 1) структуру хранения данных указанного типа, т.е. выделение памяти и представление данных в ней, с одной стороны, и интерпретирование двоичного представления, с другой;
· 2) множество допустимых значений, которые может иметь тот или иной объект описываемого типа;
· 3) множество допустимых операций, которые применимы к объекту описываемого типа.
СТРУКТУРА ДАННЫХ - совокупность физически (типы данных) и логически (алгоритм, функции) взаимосвязанных переменных и их значений.
Заметим, что понятие структуры данных имеет отношение не только к переменным, которые ее составляют, но и к алгоритмам (функциям), которые не только логически связывают переменные между собой, но и определяют внутренние значения, которые также должны быть свойственны этой структуре данных. Например, последовательность положительных значений, размещенная в массиве и имеющая переменную размерность (структура данных), может иметь нулевой ограничитель. Все операции по формированию и проверке этого ограничителя реализуются функциями. Таким образом, можно сказать, что значительная часть структуры данных "зашита" в алгоритмах ее обработки.
Известный нам способ определения переменных через типы данных характеризуется тем, что, во-первых, количество переменных в программе фиксировано, а во-вторых, размерность их не может быть изменена во время работы программы. Если взаимосвязи между этими переменными имеют более-менее постоянный характер, то такие структуры данных можно назвать статическими.
СТАТИЧЕСКАЯ СТРУКТУРА ДАННЫХ - совокупность фиксированного количества переменных постоянной размерности с неизменным характером связей между ними
И наоборот, если один из параметров структуры данных -количество переменных, их размерность или взаимосвязи между ними меняются во время работы программы, то такие структуры данных называются динамическими.
ДИНАМИЧЕСКАЯ СТРУКТУРА ДАННЫХ - совокупность переменных, количество, размерность или характер взаимосвязей между которыми меняется во время работы программ.
Динамические структуры данных базируются на двух элементах языка программирования:
· динамических переменных, количество которых может меняться и в конечном счете определяется самой программой. Кроме того, возможность создания динамических массивов позволяет говорить о данных переменной размерности;
· указателях, которые обеспечивают непосредственную взаимосвязь данных и возможность изменения этих связей.
Таким образом, близко к истине и такое определение: динамические структуры данных -это динамические переменные и массивы, связанные указателями.
Говоря о структурах данных, нельзя забывать, что обычные переменные размещаются в оперативной памяти (внутренней памяти компьютера). Поэтому обычно и структуры данных имеют отношение к памяти. Однако существует еще и внешняя память, которая в языке доступна опосредованно через операторы (Паскаль) или функции (Си), работающие с файлами. В режиме двоичного файла произвольного доступа любой файл представляет собой аналог неограниченной прямо адресуемой области памяти, то есть с точки зрения программы выглядит так же, как обычная память. Естественно, что программа может копировать переменные из памяти в произвольное место файла и обратно, а значит и организовывать в файле любые (в том числе и динамические) структуры данных.
Структура данных - это исполнитель, который организует работу с данными, включая их хранение, добавление и удаление, модификацию, поиск и т.д. Структура данных поддерживает определенный порядок доступа к ним. Структуру данных можно рассматривать как своего рода склад или библиотеку. При описании структуры данных нужно перечислить набор действий, которые возможны для нее, и четко описать результат каждого действия. Будем называть такие действия предписаниями. С программной точки зрения, системе предписаний структуры данных соответствует набор функций, которые работают над общими переменными.
Структуры данных удобнее всего реализовывать в объектно-ориентированных языках. В них структуре данных соответствует класс, сами данные хранятся в переменных-членах класса (или доступ к данным осуществляется через переменные-члены), системе предписаний соответствует набор методов класса. Как правило, в объектно-ориентированных языках структуры данных реализуются в виде библиотеки стандартных классов: это так называемые контейнерные классы языка C++, входящие в стандартную библиотеку классов STL, или классы, реализующие различные структуры данных из библиотеки Java Developer Kit языка Java.
Тем не менее, структуры данных столь же успешно можно реализовывать и в традиционных языках программирования, таких как Фортран или Си. При этом следует придерживаться объектно-ориентированного стиля программирования: четко выделить набор функций, которые осуществляют работу со структурой данных, и ограничить доступ к данным только этим набором функций. Сами данные реализуются как статические (не глобальные) переменные. При программировании на языке Си структуре данных соответствуют два файла с исходными текстами:
1. заголовочный, или h-файл, который описывает интерфейс структуры данных, т.е. набор прототипов функций, соответствующий системе предписаний структуры данных;
2. файл реализации, или Си-файл, в котором определяются статические переменные, осуществляющие хранение и доступ к данным, а также реализуются функции, соответствующие системе предписаний структуры данных
Структура данных обычно реализуется на основе более простой базовой структуры, ранее уже реализованной, или на основе массива и набора простых переменных. Следует четко различать описание структуры данных с логической точки зрения и описание ее реализации. Различных реализаций может быть много, с логической же точки зрения (т.е. с точки зрения внешнего пользователя) все они эквивалентны и различаются, возможно, лишь скоростью выполнения предписаний.
Необходимым условием построения алгоритма является формализация данных , т.е. приведение информации к некоторой информационной модели (см. “Информационные модели ”), уже описанной и исследованной. Когда такая модель найдена, говорят, что определена абстрактная структура данных .
Абстрактная структура данных описывает признаки и свойства объекта, взаимосвязь между элементами объекта, а также возможные операции над данным объектом или классом объектов.
Одной из задач информатики является нахождение форм представления информации, удобных для компьютерной обработки. Информатика как точная наука работает с формальными (описанными математически строго) объектами. Такими объектами - базовыми абстрактными структурами данных , используемыми в информатике, являются:
· целые числа;
· вещественные числа;
· символы;
· логические значения.
Для компьютерной обработки этих объектов в языках программирования существуют соответствующие типы данных (см. “Типы данных ”). Базовые объекты можно объединять в более сложные структуры, добавляя операции уже над структурой в целом и правила доступа к отдельным элементам этой абстрактной структуры данных.
К таким абстрактным структурам данных относятся:
· векторы (конечные массивы);
· таблицы (матрицы), а в общем случае - многомерные массивы;
· динамические структуры:
Последовательности символов, чисел;
Очереди;
Деревья;
Удачный выбор структуры данных часто является залогом создания эффективного алгоритма и программы, его реализующей: используя аналогию структур данных и реальных объектов, можно находить эффективные решения задач.
Заметим, что перечисленные структуры существуют независимо от их реализации при программировании. С этими структурами данных работали и в XVIII, и в XIX веках, когда еще не придумали вычислительную машину. Мы можем разрабатывать алгоритм в терминах абстрактной структуры данных, но для реализации алгоритма в конкретном языке программирования необходимо найти способ ее представления в терминах типов данных и операторов , поддерживаемых данным языком программирования (см. “Операторы языка программирования ”). Для компьютерного представления абстрактных структур используются структуры данных ,которые представляют собой набор переменных, возможно различных типов данных, объединенных определенным образом. Для конструирования таких структур, как вектор, таблица, строка, последовательность, в большинстве языков программирования присутствуют стандартные типы данных : одномерный массив, двухмерный массив, строка, файл (реже список) соответственно. Организацию остальных структур данных, в первую очередь динамических структур , размер которых меняется во время выполнения программы, программисту приходится осуществлять самостоятельно, используя базовые типы данных. Рассмотрим такие структуры подробнее.
Списки
Линейный список - последовательность линейно связанных элементов, для которых разрешены операции добавления элементов в произвольное место списка и удаление любого элемента. Линейный список однозначно задается указателем на начало списка. Типовыми операциями над списками являются: обход списка, поиск заданного элемента, вставка элемента сразу после или перед определенным элементом, удаление заданного элемента, объединение двух списков в один, разбиение одного списка на два и более списков и т.п.
В линейном списке для каждого элемента, кроме первого , есть предыдущий элемент; для каждого элемента, кроме последнего , есть следующий элемент. Таким образом, все элементы списка упорядочены. Однако обработка линейного односвязного списка не всегда удобна, т.к. отсутствует возможность движения в противоположную сторону - от конца списка к началу. В линейном списке можно обойти все элементы, только двигаясь последовательно от текущего элемента к следующему, начиная с первого, прямой доступ к i -му по счету элементу невозможен.
Пример 1. Порядок следования записей фамилий читателей в компьютере библиотекаря определяет отношение “предыдущий–следующий”. Как правило, сами записи имеют дополнительное свойство - они упорядочены по алфавиту. Над этим списком реализованы операции добавления нового читателя и, при необходимости, удаления старого. Если к тому же ведутся записи выданных каждому читателю книг, то каждую такую запись удобно представлять опять же с помощью списка выданных книг.
Кольцевые списки - такая же структура, как и линейный список, но имеющая дополнительную связь между последним и первым элементом, то есть следующим за последним элементом является первый элемент.
В кольцевом списке в отличие от линейного все элементы равноправны (поскольку для каждого элемента определены и предыдущий, и следующий элементы). Выделение “первого” и “последнего” элементов в кольцевом списке весьма условно, так как собственно структура списка не имеет явно выделенных элементов !
Пример 2. Во многих играх дети используют считалочки, чтобы выбрать ведущего, разделиться на команды и т.п. Как правило, считалочки длинные, и дети (сами того не зная) организуют кольцевой список. Отношение “предыдущий–следующий” определяется тем, в какую сторону ведущий считает. Типичная операция в такой структуре - удаление элемента из списка с сохранением его кольцевой структуры.
Линейные списки, в которых операции вставки, удаления и доступа к значениями элементов выполняются только с крайними элементами (первым или последним), получили специальные названия.
Стек - частный случай линейного односвязного списка, для которого определены две операции: добавление элемента в вершину стека (перед первым элементом) и удаление элемента из вершины стека (удаление первого элемента).
Пример 3. Рассмотрим задачу определения сбалансированности скобок различных видов в арифметическом выражении. Например, требуется проанализировать, сбалансированы ли скобки в выражении, содержащем круглые и квадратные скобки: ? Для решения этой задачи будем использовать динамическую структуру данных стек . Приведем алгоритм решения этой задачи по шагам. Будем использовать следующие обозначения:
i - номер анализируемого символа;
n - количество символов в выражении.
1. i = 0.
2. i = i + 1.
3. Если i n , то переход на п. (4), иначе если стек пуст, то выдаем сообщение “скобки сбалансированы”, в противном случае выдаем сообщение “скобки не сбалансированы ”. Конец алгоритма.
4. Если i -й символ отличен от символов скобок, то переход на п. (2).
5. Если i -й символ равен “(” или “[”, то помещаем его в стек, переход на п. (2).
6. Если i -й символ равен “)”, то проверяем вершину стека: если в вершине стека находится “(”, то извлекаем ее из стека; переход на п. (2), иначе выдаем сообщение “скобки не сбалансированы ”. Конец алгоритма.
7. Если i -й символ равен “]”, то проверяем вершину стека: если в вершине стека находится “[”, то извлекаем ее из стека; переход на п. (2), иначе выдаем сообщение “скобки не сбалансированы ”. Конец алгоритма.
Очередь - частный случай линейного односвязного списка, для которого разрешены только две операции: добавление элемента в конец (хвост) очереди и удаление элемента из начала (головы) очереди.
Понятие очереди действительно очень близко к бытовому термину “очередь”. Очередь покупателей в магазине хорошо описывается в терминах этой структуры данных.
Деревья
Дерево - это совокупность элементов, называемых узлами , в которой выделен один элемент (корень ), а остальные элементы разбиты на непересекающиеся множества (поддеревья), каждое из которых является деревом, при этом корень каждого поддерева является потомком корня дерева, т.е. все элементы связаны между собой отношением (предок–потомок). В результате образуется иерархическая структура узлов. Узлы, которые не имеют ни одного потомка, называются листьями . Над деревом определены следующие операции: добавление элемента в дерево, удаление элемента из дерева, обход дерева, поиск элемента в дереве.
Пример 4. Дерево является наиболее удобной структурой данных для представления генеалогического дерева, с помощью которого можно решать задачи определения степени родства между двумя людьми.
Используются деревья и для определения выигрышной стратегии в играх (см. статью “Игры. Выигрышные стратегии ”), и для построения различных информационных моделей (см. “Информационные модели ”).
Особенно важную роль в информатике играют так называемые бинарные деревья .
Двоичное (бинарное) дерево - частный случай дерева, в котором каждый узел может иметь не более двух потомков, являющихся корнями левого и правого поддерева.
Если дополнительно для узлов дерева выполняется условие, что все значения элементов левого поддерева меньше значения корня дерева, а все значения элементов правого поддерева больше значения корня, то такое дерево называется деревом бинарного поиска и предназначено для быстрого поиска элементов. Алгоритм поиска в таком дереве работает так: искомое значение сравнивается со значением корня дерева, и в зависимости от результата сравнения поиск либо заканчивается, либо продолжается только в левом или только в правом поддереве соответственно. Общее количество операций сравнения не будет превосходить так называемую высоту дерева - максимальное количество элементов на пути от корня дерева к одному из листьев. Так, высота изображенного на рисунке дерева равна 4.
Графы
Граф - это множество элементов, называемых вершинами графа вместе с набором отношений между этими вершинами, называемых ребрами графа. Графической интерпретацией этой структуры данных является множество точек, соответствующих вершинам, некоторые пары из которых соединены линиями или стрелками, которые соответствуют ребрам. В последнем случае граф называется ориентированным (см. также статьи “Графические модели ” и “Табличные модели ”).
В силу того, что с помощью графов можно описывать объекты произвольной структуры, графы являются основным средством для описания структур сложных объектов и функционирования систем. Например, для описания вычислительной сети, транспортной системы, иерархической структуры (дерево является одной из разновидностей графа). Блок-схемы алгоритмов (см. “Способы записи алгоритмов ”) также представляют собой графы.
Если каждому ребру к тому же приписано некоторое число (вес ), то такой граф называют взвешенным . Например, при описании с помощью графа системы дорог России важным является длина дороги (вес ребра графа), соединяющей те или иные населенные пункты (вершины графа). При этом на рисунке длины соответствующих ребер не обязаны соответствовать приписанным им весам, в отличие от карты дорог.
Пример 5. В терминах взвешенного графа удобно решать следующую задачу. Правительство России составляет план строительства современных автомагистралей, соединяющих города, население которых превышает миллион человек. Какие именно дороги следует построить, чтобы из любого такого города можно было добраться в любой другой по новым автомагистралям, а общая длина дорог была бы минимальной?
Эта задача в теории графов имеет простое и точное решение. Мы можем начать планирование сети дорог, начиная с любого города, например, Санкт-Петербурга. Соединим его с ближайшим городом-миллионником. Далее на каждом шаге к имеющейся сети добавляется кратчайшая дорога, которой можно соединить город, еще не присоединенный к сети, с одним из городов, уже включенных в сеть. Количество дорог будет, таким образом, на единицу меньше, чем число городов.
Абстрактную структуру данных - граф - в программе можно представить несколькими способами, т.е. используя разные типы данных. Например, граф можно описывать с помощью списка ребер, задавая каждое ребро парой вершин и, при необходимости, весом. Наибольшее распространение получило табличное хранение графа (см. “Табличные модели ”), называемое также матрицей смежности , т.е. двухмерного массива, скажем, A , где для невзвешенного графа (или 1), если ребро между вершинами i и j существует, и (или 0) в противном случае. Для взвешенного графа A [i ][j ] равно весу соответствующего ребра, а отсутствие ребра в ряде задач удобно обозначать бесконечностью. Для неориентированных графов матрица смежности всегда симметрична относительно главной диагонали (i = j ). C помощью матрицы смежности легко проверить, существует ли в графе ребро, соединяющее вершину i с вершиной j . Основной же ее недостаток заключается в том, что матрица смежности требует, чтобы объем памяти был достаточен для хранения N 2 значений для графа, содержащего N вершин, даже если ребер в графе существенно меньше, чем N 2 .
При объяснении понятия структуры данных можно воспользоваться следующей иллюстрацией.
При решении любой задачи возникает необходимость работы с данными и выполнения операций над ними. Набор этих операций для каждой задачи, вообще говоря, свой. Однако, если некоторый набор операций часто используется при решении различных задач, то полезно придумать способ организации данных, позволяющий выполнять именно эти операции как можно эффективнее. После того, как такой способ придуман, при решении конкретной задачи можно считать, что у нас в наличии имеется “черный ящик” (его мы и будем называть структурой данных), про который известно, что в нем хранятся данные некоторого рода, и который умеет выполнять некоторые операции над этими данными. Это позволяет отвлечься от деталей и сосредоточиться на характерных особенностях задачи. Внутри (т.е. в компьютере) этот “черный ящик” может быть реализован различным образом, при этом следует стремиться к как можно более эффективной (быстрой и экономично расходующей память) реализации.
Государственный образовательный стандарт предусматривает изучение различных структур данных как в базовом курсе основной школы, так и в старших классах. В курсе программирования основной школы в Примерной программе упоминаются в качестве обрабатываемых объектов цепочки символов (строки), числа, списки, деревья, графы. Однако в практических работах из данных сложной структуры упоминается только массив (см. статью “Операции с массивами ”). В основной школе остальные структуры, видимо, имеет смысл изучать в первую очередь при построении графических и других моделей (см. раздел IV энциклопедии).
Примерная программа для профильной школы предполагает работу с числами, матрицами, строками, списками, деревьями. В качестве простой иллюстрации работы со списками можно выбрать организацию стека с помощью одномерного массива и целочисленной переменной, указывающей на вершину стека (“дно” стека при этом всегда находится в первом элементе массива). Помимо приведенной в статье задачи проверки скобок на сбалансированность, можно изучить работу стекового калькулятора на примере алгоритма перевода арифметического выражения в обратную польскую запись (постфиксную запись) из привычной нам инфиксной записи и дальнейшее вычисление значения арифметического выражения.
Бинарное дерево также легко представить в памяти компьютера с помощью одномерного массива, при этом в первом элементе массива будет храниться корень дерева, а потомки узла дерева, хранящегося в i -м элементе массива, будут располагаться в 2i -м и (2i + 1)-м элементах соответственно. Если потомок у узла отсутствует, то соответствующий элемент будет равен, например, 0. Рекурсивная процедура обхода дерева t и печати его элементов в этом случае будет выглядеть так:
procedure order(i:integer);
if t[i] <> 0 then
О реализации списков и массивов с помощью динамических переменных можно прочитать, например, в классической книге Н.Вирта “Алгоритмы и структуры данных”.
В программу для профильной школы включены и алгоритмы на графах. В частности, упоминается поиск кратчайшего пути в графе. Для невзвешенного графа решать эту задачу можно, например, с использованием алгоритма “поиска в ширину”, когда сначала помечаются вершины графа, соединенные ребром с исходной вершиной, затем все вершины, соединенные с помеченными, и т.д. Для взвешенного графа чаще всего используют алгоритм Дийкстры (см., например, статью Е.В. Андреевой “Олимпиады по информатике. Пути к вершине”, “Информатика” № 8/2002). Знание таких алгоритмов необходимо для успешного решения олимпиадных задач по информатике. Так, на IV федеральном окружном этапе Всероссийской олимпиады по информатике 2007 г. предлагалась задача “Окопы и траншеи”, решение которой как раз и сводилось к поиску кратчайшего пути во взвешенном графе.
Первоначально процесс программирования предусматривал запись программистом всех алгоритмов непосредственно на машинном языке. Такой подход усугублял и без того трудную задачу разработки алгоритмов и слишком часто приводил к ошибкам, которые необходимо было обнаружить и исправить [процесс, известный как отладка] до того, как работу можно было считать законченной.
Первым шагом на пути к облегчению задачи программирования был отказ от использования цифр для записи команд и операндов непосредственно в той форме, в которой они используются в машине. С этой целью при разработке программ стали широко применять мнемоническую запись различных команд вместо их шестнадцатеричного представления. Например, вместо цифрового кода команды загрузки регистра программист мог теперь написать LOD, а вместо кода команды копирования содержимого регистра в память мог использовать мнемоническое обозначение STO. Для записи операндов были разработаны правила, в соответствии с которыми программист мог присваивать некоторым областям памяти описательные имена [их часто называют идентификаторами] и использовать их при записи команд программы вместо адресов соответствующих ячеек памяти. Такие идентификаторы обычно называют переменными. Это подчеркивает, что, изменяя значение, размещенное в данном участке памяти, мы изменяем значение, связанное с идентификатором, присвоенным этому участку по ходу выполнения программы.
При объявлении в программе переменной обычно одновременно определяют и их тип. Тип данных определяет как интерпретацию конкретных данных, так и операции, которые можно с ними выполнять. К типам данных относятся Integer [целый], Real [действительный], Character [символьный] и Boolean [логический].
Тип Integer используется для обозначения числовых данных, являющихся целыми числами. В памяти они чаще всего представляются в двоичном дополнительном коде. С данными типа Integer можно выполнять обычные арифметические операции и операции сравнения.
Тип Real предназначен для представления числовых данных, которые могут содержать нецелые величины. В памяти они обычно хранятся как двоичные числа с плавающей точкой. Операции, которые можно выполнять с данными Real, аналогичны операциям, выполняемым с данными типа Integer. Однако, что манипуляции, которые следует выполнить, чтобы сложить два элемента данных типа Real, отличаются от манипуляций, необходимых для выполнения действий с переменными типа Integer.
Тип Character используется для данных, состоящих из символов, которые хранятся в памяти в виде кодов ASCII или UNICODE. Данные этого типа можно сравнивать друг с другом [определять, какой из двух символов предшествует другому в алфавитном порядке]; проверять, является ли одна строка символов другой, а также объединять две строки в одну, более длинную строку, дописывая одну из них после другой [операция конкатенации].
Boolean относится к данным, которые могут принимать только два значения True [истина] и False [ложь]. Примером таких данных может служить результат операции сравнения двух чисел. Операции с данными типа Boolean включает проверку, является ли текущее значение переменной True или False.
Основная память машины организована в виде отдельных ячеек с последовательно увеличивающимися адресами. Однако часто эти ячейки используются как основа для реализации иных способов размещения данных. Например, текст обычно рассматривается как длинная строка символов, тогда как информация о продажах может рассматриваться как прямоугольная таблица с числовыми значениями, каждое из которых представляет число сделок, заключенных определенным работником в определенный день. Задача состоит в том, чтобы предоставить пользователю средства, позволяющие оперировать подобными абстрактными структурами, вместо того чтобы вникать в детали истинной организации данных в основной памяти машины. Для правильного использования компьютера необходимо хорошо знать структурные взаимосвязи между данными, основные методы представления структур внутри компьютера, а также методы работы с ними. Для связей между данными в компьютере используются следующие информационные структуры: массив, запись, список, дерево, стек, очередь.
Массивы
Массив - это структура, содержащая в себе несколько однотипных элементов. Для упорядочивания элементов массива используются индексы. Индексы записываются в скобках после имени массива. Массив с одним индексом называется одномерным, с двумя - двумерным и т.д.
Запись
Запись - это структура, состоящая из элементов не обязательно одного типа. Отдельные элементы записи называют полями. Поле в свою очередь тоже может быть записью.
record Student (
FirstName,
LastName,
Group
)
Списки
Список - это множество записей, каждая из которых содержит специальное поле - указатель . Указатель связывает запись с какой-либо другой записью или содержит значений Null, которое говорит о том, что значение указателя не определено.
Записи в односвязном списке имеют по одному указателю, при этом они связанны в цепочку:
Стрелка на рисунке говорит о содержимом указателя, а слово Data обозначает совокупностей полей, в которых хранятся данные. Список можно организовать с помощью двумерного массива, все элементы которого с первым индексом, равным 0, предназначены для хранения данных, а элементы с первым индексом, равным 1, являются указателями.
В данном списке записи, содержащие буквы английского алфавита, выстроены в алфавитном порядке. Первая запись в списке содержит символ "A", вторая - "B" и т.д.
Для работы со списком нужно уметь выполнять три основных операции:
Pass() - обход или перемещение вдоль списка;
Add() - добавление новой записи в список;
Delete() - удаление записи из списка.
Кроме операций для работы со списком нужны еще две переменные:
переменная Head, в которой хранится информация о первой записи в списке
переменная Current, которая указывает на текущую запись в списке
В таблице сведены описания некоторых операций над списком, пример реализации которого приведен выше.
| Название операции | Псевдокод |
| Перейти вдоль списка на один шаг |
function Pass(Current) { |
|
function Add(Current, New) { |
|
| Добавить в список запись, на которую указывает переменная New |
function Delete(Current) { |
Записи в двусвязном списке связаны между собой в цепочку, но при этом имеют два поля-указателя. Одно из них указывает на предыдущий элемент в списке, другое - на следующий элемент. Такая структура позволяет перемещаться по списку в двух направлениях: вперед и назад.
Кольцевым называется список, последняя запись которого указывает на первую. В этих списках отсутствует запись с пустым указателем.
Дерево - это разветвленный список, каждая запись которого может содержать несколько указателей. Записи, входящие в дерево, называются узлами. Узлы, у которых все указатели пустые, называются листьями. Верхний начальный узел дерева называется корневым узлом. Во многих задачах достаточно использовать двоичные [бинарные] деревья, узлы которых имеют не более двух указателей.
Пример. Требуется вычислить математическое выражение (3+7)*(2/(3-1)). Представим это выражение в виде дерева:
Каждый узел этого дерева представляет собой запись следующего вида:
record Node (
Operation
Number
LeftPointer
RightPointer
)
Листья дерева содержат числа, остальные узлы - символы операций.
Реализовав описанное дерево на двумерном массиве, мы получим следующую картину:
Для вычисления значения дерева нужно вычислить значения правого и левого поддеревьев, а потом над ними выполнить результирующую операцию. Псевдокод алгоритма решающего поставленную задачу будет иметь вид:
function Calculate (Current) {
if (M=Null) then
Result:= M;
else {
R1:=Calculate(M);
R2:=Calculate(M);
Result:=R1(M)R2;
}
return (Result);
}
Стек - это структура данных, организованная по принципу "последним пришел - первым ушел" . Доступ к данным, хранящимся в стеке, осуществляется через вершину. Данные помещаются в стек последовательно Элемент, помещенный в стек самым первым, оказывается на дне и для того чтобы его извлечь из стека, необходимо сначала извлечь все данные, которые были помещены в стек позже.
При работе со стеком возможны две аварийные ситуации: попытка прочитать данные из пустого стека; попытка занести в стек элемент, когда количество элементов в стеке достигло максимально допустимого количества.
Очередь - это структура данных, организованная по принципу "первым пришел - первым ушел" . В очереди переменное количество данных. При постановке в очередь данные добавляются в хвост, при извлечении берутся из головы.
Хеш-таблица
Хеширование - это метод, обеспечивающий прямой доступ к записям без использования каких-либо дополнительных структур. Процесс можно кратко описать следующим образом. Пространство, где хранятся данные, делится на несколько сегментов. Записи распределяются по этим сегментам согласно некоторому алгоритму, называемому алгоритмом хеширования, преобразующему значение поля ключа в номер сегмента. Каждая запись хранится в сегменте, определяемом этим процессом. Следовательно, запись можно извлечь, применив алгоритм хеширования к значению ее поля ключа и считав записи соответствующего сегмента. Структура данных, сконструированная таким способом, называется хеш-таблицей.
Например, если необходимо организовать хеш-таблицу для хранения прописных букв английского алфавита, то в качестве ключей можно выбрать ASCII-коды символов, а алгоритм хеширования будет отрезать младшие пять битов и формировать на их основе индекс элемента массива для хранения символа:
В общем случае, алгоритм хеширования должен по значению ключа производить значение индекса в границах массива и равномерно распределять ключи по элементам массива. Невыполнение последнего требования приводит к возникновению ситуаций, когда несколько записей попадает в один и тот же сегмент. Данные ситуации называются коллизиями.
