- •А.Н. Горитов
- •Учебное пособие
- •Учебное пособие
- •Введение
- •1 Введение в предмет
- •1.1 Непрерывная и дискретная информация
- •1.2 Данные и эвм
- •1.3 Объекты предметной области
- •1.4 Представление информации об объектах
- •1.5 Абстрактные алфавиты. Кодирование
- •2 Основные типы и структуры данных эвм
- •2.1 Архитектурные особенности эвм, наиболее существенные для представления данных
- •2.2 Основные понятия о типах и структурах данных
- •2.3 Массивы
- •2.4 Строки
- •2.5 Записи
- •2.6 Записи с вариантами
- •2.7 Множества
- •3 Последовательный файл
- •3.1 Основные свойства последовательных файлов
- •3.2 Сортировка последовательных файлов
- •4 Полустатические структуры
- •4.1 Стек, очередь и дек как полустатические структуры
- •4.2 Представление полустатических структур с помощью массивов
- •5 Линейные динамические структуры
- •5.1 Основные свойства динамических структур
- •5.2 Реализация связного списка массивом
- •5.3 Кольцевой связный список
- •5.4 Линейный двусвязный список
- •6 Представление динамических структур с помощью указателей
- •6.1 Указатели
- •6.2 Представление стека
- •6.3 Представление очереди
- •6.4 Ведение динамических списков с помощью указателей
- •6.5 Алгоритм составления кольцевого двусвязного списка
- •7 Древовидные структуры данных
- •7.1 Основные понятия и определения
- •7.2 Представление деревьев в эвм
- •7.3 Основные операции с бинарными деревьями
- •7.4 Сильно ветвящиеся деревья
- •8 Алгоритмы на графах
- •8.1 Машинное представление графов
- •8.2 Поиск в глубину в графе
- •8.3 Поиск в ширину в графе
- •8.4 Стягивающие деревья (каркасы)
- •8.5 Отыскание фундаментального множества циклов в графе
- •8.6 Эйлеровы пути в графе
- •8.7 Алгоритмы с возвратом
- •8.8 Нахождение кратчайших путей в графе
- •8.9 Кратчайшие пути от фиксированной вершины
- •8.10 Алгоритм Дейкстры
- •8.11 Пути в бесконтурном графе
- •Литература
2 Основные типы и структуры данных эвм
2.1 Архитектурные особенности эвм, наиболее существенные для представления данных
Минимальной адресуемой единицей памяти является байт. Передача информации в ЭВМ производится побайтно или группами байтов – блоками. Каждый байт в памяти ЭВМ имеет свой порядковый номер, который называется адресом.
Однако байт – сравнительно мелкая единица памяти (256, если без знака). Поэтому для представления и обработки данных обычно используются поля данных. Поле данных – это последовательность нескольких смежных байтов. Количество байтов называется длиной поля, а адрес самого левого байта поля – адресом поля. Байты нумеруются слева направо, начиная с нуля. Различают поля фиксированной и переменной длины.
Минимальным полем фиксированной длины является полуслово. Оно состоит из двух последовательных байтов (16 бит, пронумерованных слева направо от 0 до 15). Два полуслова образуют слово – 4 последовательных байта (или 32 бита, пронумерованных слева направо от 0 до 31). Слово – важнейший архитектурный признак ЭВМ. Это поле, которое, как правило, может обработать 1 команда ЭВМ. 2 слова образуют двойное слово (64 бита, пронумерованных слева направо от 0 до 63).
2.2 Основные понятия о типах и структурах данных
Вычислительный процесс на ЭВМ реализуется с помощью программы и данных, которые она использует или формирует. Сама программа – тоже совокупность данных. Поэтому можно считать, что любая информация, с которой может работать ЭВМ, описывается данными.
На машинном уровне представления информации независимо от содержания и сложности. Любое данное в ЭВМ выражается последовательностью двоичных разрядов (битов), а его значением может служить двоичное число. Однако для человека такое слабоструктурированное описание в виде двоичных разрядов весьма неудобно. Нужны более крупные и содержательные "строительные блоки", чем бит.
Такие блоки можно получить на основе понятия "тип данного". Тип данного определяется множеством значений данного и набором операций, которые можно выполнять над этими значениями. Базовые типы данных определяют архитектуру ЭВМ.
Команды современных ЭВМ обеспечивают, как правило, обработку следующих типов данных: целые числа INTEGER
вещественные числа REAL символьные данные CHARACTER логические BOOLEAN
адреса (целые числа) POINTER (указательный тип) Тип INTEGER – конечное множество целых чисел, причем, наибольшее по модулю целое число определяется конкретной ЭВМ.
О 1
15
Целая часть числа
-32768 .. 32767
Знак
Тип REAL
О 1
|
Характеристика |
Мантисса |
Знак мантиссы
2.9*10-39 .. 1.7*10+38
Тип CHARACTER – предназначен для хранения одного символа - буквы, знака или кода. Символы хранятся в виде числовых значений соответствующей кодовой таблицы. В памяти ЭВМ для хранения символа выделяется 1 байт. Этого достаточно для представления 256 различных символов.
Тип BOOLEAN – для запоминания логического значения достаточно 1 бита. Но для убыстрения доступа к нему целесообразно использовать минимально адресуемый элемент памяти – байт, хотя такое представление и избыточно.
Тип POINTER – представляет множество указателей или адресов данных. Данное типа POINTER указывает на некоторое другое данное или группу данных. Присваивая указателю то или другое значение, можно через этот указатель получить доступ к желаемым данным.
Среди множества значений данных типа POINTER имеется одно специальное значение, которое говорит о том, что данный указатель никуда не указывает, т.е. является нулевым или пустым указателем. В Паскале таким значением является символ Nil (ничего), в памяти он обычно представлен числом 0. Операции над указателем сводятся к присваиванию ему значения другого указателя или адреса области памяти, занимаемой другим данным. Например, в Паскале есть функция ADDR, аргументом которой является имя некоторой переменной, а значением – её адрес, который обычно присваивается указателю. (Богатые средства для работы с указателями имеются в языке Си.)
Вообще указатели играют важную роль при создании и обработке связных структур.
В памяти для хранения указателя выделяется область, равная максимальной длине адреса в соответствующей вычислительной системе.
Мы рассмотрели типы данных, которые обычно называются простыми (скалярными) типами данных. Действия над ними выполняются аппаратно командами. Для них характерна простота организации (неструктурированность).
Назовем структурой данных совокупность элементов данных, между которыми существуют некоторые отношения, причем элементами данных могут быть простые данные и структуры данных. Структуру данных S можно определить как
S = (D, R), где D – множество элементов данных; R – множество отношений между ними.
Для получения структур необходима возможность создания новых типов данных на основе простых типов. Современные языки программирования (Паскаль, Ада) представляют такую возможность, т.к. в них имеются методы определения новых типов.
Так, данные простых типов могут объединяться в агрегаты. Агрегат – (коллекция), совокупность значений компонент, принадлежащих к определенным ранее типам. Такие составные типы уже можно считать структурированными.
Типы компонент могут быть, в свою очередь, составными. Можно построить целую иерархию структур, но конечные компоненты структуры должны быть простыми.
Система нотаций алгоритмического языка должна допускать описание как простых, так и структурированных типов.
Самый простой метод описания простого типа – перечисление всех значений этого типа. Например, тип фигура (если в задаче речь идет о плоских геометрических фигурах) может иметь значения, которые задаются идентификаторами прямоугольник, квадрат, эллипс, круг.
Кроме типов, создаваемых программистом, обязательно должны быть стандартные типы (предопределенные). Они обычно включают числа и логические переменные.
Если значения некоторого типа упорядочены, то он называется упорядоченным или скалярным. В Паскале предполагается, что все неструктурированные типы упорядочены. Если они явно перечисляются, то считается, что они упорядочены в порядке перечисления.
Применяя эти правила, можно описывать простые типы и строить из них структурированные типы любой степени сложности. Однако на практике недостаточно иметь только один общий метод объединения типов компонент в структуру. С практической точки зрения универсальный язык должен располагать несколькими методами структурирования. Мы рассмотрим эти методы применительно к Паскалю.
Прежде чем познакомиться с конкретными структурами, приведем их классификацию по некоторым признакам.
1.По наличию явно заданных связей между элементами данных:
а)несвязные структуры:
векторы,
массивы,
строки,
стеки,
очереди;
б)связные структуры:
♦ связные списки
2.По признаку изменчивости структуры (т.е. изменения числа элементов и (или) связей между ними:
а) статические;
б)полустатические;
в) динамические.
3.По характеру упорядоченности элементов структуры:
а)линейно-упорядоченные (линейные);
б) нелинейные.
4.По характеру взаимного расположения элементов в памяти:
а)с последовательным распределением:
векторы,
массивы,
строки,
стеки,
очереди;
б)с произвольным связанным распределением:
односвязные списки,
двусвязные списки,
циклически связанные списки,
ассоциативные списки. Для нелинейных структур – многосвязные списки, древовидные структуры и графовые структуры общего
вида.
Данные различных типов вводятся в программу для того, чтобы их использовать в каких-либо вычислениях. Следовательно, нужно иметь кроме различных типов данных и некоторое множество операций над ними. Вместе с типами данных любой язык программирования задает и некоторое множество операций (простых, стандартных – атомарных), и методы структурирования, которые позволяют описывать сложные действия в терминах простых операций.
Важнейшие операции:
сравнение (проверка равенства и порядка в следовании упорядоченных типов);
присваивание (команда "установка равенства");
преобразование (отображение одних типов в другие). Первые две операции определены для большинства типов данных, третья особенно важна для составных
типов.
Составные значения строятся из значений компонент с помощью так называемых конструкторов, а значения компонент извлекаются с помощью так называемых селекторов. Таким образом конструкторы и селекторы – это операции преобразования, отображающие типы компонент в составные типы и наоборот. Каждому методу структурирования соответствует своя пара конструкторов и селекторов, обозначения которых четко различаются.
Следует различать:
а)логическую (абстрактную) структуру;
б) физическую (конкретную) структуру. Первая составляется и записывается в программе без учета её представления в машинной памяти. Вторая
отражает способ физического представления данных в памяти ЭВМ. В общем случае между логической и физической структурой существует различие, степень которого зависит от самой структуры и особенностей физической среды, в которую она должна быть отражена.
Например, с точки зрения пользователя Паскаля двумерный массив – это прямоугольная таблица, содержащая определенное число строк и столбцов. В машинной же памяти этот массив представляется линейной последовательностью ячеек, причем элементы массива упорядочены по строкам.
Вследствие различия между логической и физической структурами в ЭВМ должны существовать процедуры, осуществляющие отображение логической структуры в физическую и наоборот. Эти процедуры также обеспечивают доступ к физическим структурам и выполнение над ними различных операций. Эти операции можно рассматривать применительно как к логическим, так и к физическим структурам данных. Например, доступ к элементу массива на логическом уровне осуществляется указанием номеров строки и столбца, на пересечении которых в прямоугольной таблице находится данный элемент. На физическом же уровне доступ к элементу массива осуществляется с помощью функции адресации, которая при известном начальном адресе массива в машинной памяти преобразует номера строки и столбца в адрес соответствующего элемента памяти.
Таким образом каждую структуру данных можно характеризовать её логическим и физическим представлением, а также совокупностью операций на этих двух уровнях представления. Возможна ситуация, когда логические структуры в разных языках совпадают, а физические – различны (массивы в Фортране и Паскале).
При изучении физической структуры должна учитываться проблема распределения и управления памятью ЭВМ. Пока будем считать (для простоты), что объем машинной памяти для любой физической структуры может быть неограничен, а память ЭВМ – непрерывной последовательностью ячеек (байтов, слов и т.д.), характерной для организации основной памяти.
Структуры данных, характерные для основной памяти ЭВМ, будем называть оперативными структурами. Для структур, организуемых во внешней памяти, существуют свои особенности, т.к. внешняя память имеет, как правило, блочный характер.
Рассмотрим теперь оперативные структуры данных, следуя линии классификации по признаку изменчивости как наиболее важному, т.е. начнем со статических структур. При этом будем рассматривать не только логическую, но и физическую структуру, а также типичные операции над логическими, а иногда и физическими структурами.