- •А.Н. Горитов
- •Учебное пособие
- •Учебное пособие
- •Введение
- •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.3 Массивы
Массив – агрегат данных, простейшая оперативная статическая структура. Можно также считать его регулярной структурой: все его компоненты одного типа, называемого базовым типом. Массив – структура с так называемым случайным или произвольным доступом: все его компоненты могут выбираться произвольно и являются одинаково доступными.
Для обозначения отдельной компоненты к имени массива добавляется так называемый индекс, позволяющий выбрать компоненту. Индекс должен иметь значение типа, определенного как тип индексов массива.
Индекс массива – это имя его компоненты. Он должен быть скалярного типа (т.е. неструктурированного, на котором определено отношение порядка).
Индексы могут вычисляться и результат определяет выбираемую компоненту. Значит, вместо индексной константы можно использовать индексное выражение. (Что приводит к самым частым ошибкам).
Если базовый тип массива так же, как и тип индекса упорядоченный, то на таком регулярном типе имеется естественное отношение порядка.
Представление массивов в памяти ЭВМ
Физически массив представляет собой в машинной памяти последовательность одинаковых по длине участков – полей или слотов, каждый из которых предназначен для хранения одного элемента массива. Слот может быть размером в 1 байт – минимальная адресуемая ячейка памяти – или соответствовать целой группе последовательных ячеек памяти. Если слот состоит из нескольких ячеек, то его адресом считают адрес самой левой ячейки, т.е. байта. Известна также должна быть длина слота.
Если массив одномерный (вектор), то переход от его логической структуры к физической несложен.
Для массивов большей размерности нужно преобразование логической структуры массива на линейную память или так называемая линеаризация. Таким образом физическая структура любого массива аналогична физической структуре вектора.
Например, 2-мерный массив
b11 b12 b13
b21 b22 b23
можно распределять в памяти по строкам
b11 b12 b13 b21 b22 b23 или по столбцам
b11 b21 b12 b22 b13 b23 или по спирали (редко)
b11 b12 b13 b23 b22 b21 Преобразование логической структуры массива в физическую осуществляется с помощью подходящей функции упорядочения. Аргументом этой функции является набор (упорядоченный) индексов элемента, а значением – номер соответствующего слота в физической структуре.
2.4 Строки
Строки играют важную роль в современных языках программирования и информационных системах.
Строка – конечная, линейно упорядоченная последовательность простых данных символьного типа, рассматриваемая как единое целое.
В общем случае строка в процессе выполнения операций над ней может изменяться как по составу входящих в неё символов, так и по их количеству, т.е. по длине строки. Поэтому логическая структура строки в простейшем случае – это вектор с переменной длиной.
Доступ может осуществляться, в принципе, не только к отдельному элементу, но и к цепочке символов, в том числе и ко всей строке в целом.
В Турбо Паскале представление строк следующее. Длина строкового типа в байтах равна его максимальной длине + 1. Первый байт содержит текущую длину строки, следующие – символы строки. Байт длины и символы представлены беззнаковыми значениями. Максимальная длина строки 255 символов + байт длины (string[255]).