- •4. Динамические структуры
- •4.1. Данные динамической структуры
- •4.2. Линейные связанные структуры данных
- •5.3.1. Создание лс.
- •5.3.2. Вывод списка
- •5.3.2. Удаление элемента из списка.
- •5.3.2. Вставка в отсортированный список.
- •5.3.3. Слияние двух отсортированных списков в третий отсортированный список.
- •5.4. Линейный двусвязный список.
- •5.4.1. Создание 2-связного списка.
- •5.4.2. Удаление в 2-связном списке.
- •5.4.2. Вставка заданного элемента в отсортированный 2-связный список.
- •5.5. Стек.
- •5.6. Пример вычисления арифметического выражения с помощью стеков.
4. Динамические структуры
В вычислительной машине программы обычно оперируют с таблицами информации. В большинстве случаев это не просто аморфные массы числовых величин: в таблицах присутствуют важные структурные отношения между элементами данных. В простейшей форме таблица может быть линейным списком элементов. Тогда присущие ей структурные свойства содержат в себе ответы на такие вопросы, как: "Какой элемент является первым в списке? какой — последним? какой элемент предшествует данному или следует за данным?" Можно много говорить о структуре даже в этом совершенно очевидном случае.
В более сложных ситуациях таблица может быть двумерным массивом (т. е. матрицей, имеющей структуру строк и столбцов), либо может быть n-мерным массивом при весьма больших значениях n, либо она может иметь структуру дерева, представляющего отношения иерархии или ветвления, либо это может быть сложная многосвязная структура с огромным множеством взаимных соединений, такая, например, которую можно найти в человеческом мозгу. Чтобы правильно использовать машину, важно добиться хорошего понимания структурных отношений, существующих между данными, способов представления таких структур в машине и методов работы с ними.
В настоящей главе кратко рассматриваются наиболее важные факты, касающиеся информационных структур:
- статические и динамические свойства разного рода структур;
- средства распределения памяти и представления структурных данных;
- эффективные алгоритмы для создания, изменения, разрушения структурной информации и доступа к ней.
Структуры будут нас интересовать не только с точки зрения внешнего, но и их внутреннего представления в машине. Мы увидим, что нет ничего мистического или трудного в методах работы со сложными структурами; эти методы являются важной частью репертуара каждого программиста, и он легко может ими воспользоваться, программируя на различных языках. Обычно в данных присутствует значительно больше структурной информации, чем мы хотим непосредственно представить в машине. Можно себе представить, что такая структурная информация была бы уместна в некоторых машинных приложениях, но, очевидно, нам никогда не придется в каждой из ситуаций хранить о структуре все, что существует. Из сказанного ясно, что в каждом конкретном случае мы должны решить, насколько подробно в наших данных должна быть представлена структура и как организовать доступ к любой части информации. Чтобы принять такое решение, необходимо знать, какие операции будут выполняться с данными. Вот почему в этой главе в связи с каждой задачей мы будем рассматривать не только структуру данных, но и класс операций, которые выполняются с этими данными; разработка машинного представления в равной мере определяется требуемыми функциями от данных и присущими им свойствами. Вообще в задачах прием проектирования такое выделение "функции" наравне с "формой" является основополагающим.
4.1. Данные динамической структуры
Между объектами реального мира, поведение которых моделируют программы, существуют разнообразные, постоянно меняющиеся связи. Одни объекты могут исчезнуть, другие — появиться. Так, люди рождаются и умирают, порывают с кем-то из старых друзей и заводят новых. Ясно, что, если в программе мы хотим моделировать группы с переменным числом объектов, связи между которыми подвержены изменениям, нужны языковые средства для установления, изменения и разрыва связей между отдельными объектами, а также для порождения и уничтожения объектов. Для этой цели в Паскале
Табл. 5.1. Работа со статическими и несвязанными динамическими данными.
| ||
Структура данных |
Обычные переменные |
Динамические переменные |
1. Простая переменная |
Var x :Char; y: Integer; Begin x := ’*’; y := 3; End. |
Var px :^Char; py :^Integer; Begin New(px); New(py); px^ := ‘*’; py^ := 3; …… Dispose(px); Dispose(py); End. |
2. Массив |
Var x :Array[1..3]Of Byte; i :Byte; Begin For i:=1 to 3 Do Read(x[i]); …… End; |
Var px :^Array[1..3]Of Byte; i :Byte; Begin New(px); For i:=1 to 3 Do Read(px^[i]); …… Dispose(px); End; |
3. Запись |
Var x :Record a :Char; b :Byte; End; Begin x .a := ‘*’; x .b := 3; …… End.
|
Var px :^Record a :Char; b :Byte; End; Begin New(px); px^ .a := ‘*’; px^ .b := 3; …… Dispose(px); End.
|
динамические переменные и указатели. Классификация данных динамической структуры показана на рис.4.1.
Несвязанные динамические данные классифицируются точно также, как и статические и работа с ними выполняется аналогично. Динамические свойства несвязанных динамических данных выражаются только в том, что они могут «появляться» и «исчезать» во время работы программы. Отличия использования таких данных заключаются в двух аспектах:
в разделе Var объявляется не переменная требуемого типа, а указатель на этот тип;
перед использованием необходимо вызвать процедуру New, а после использования – процедуру Dispose.
В качестве примера приведена таблица 5.1. сравнения работы с аналогичными статическими и несвязанными динамическими данными.
Программированию с использованием несвязанных данных посвящена многочисленная учебная литература (например, по языкам высокого уровня), поэтому основное внимание в дальнейшем будет уделено связанным динамическим данным. Связанные динамические данные характеризуются высокой гибкостью создания структур данных различной конфигурации. Это достигается благодаря возможности выделять и освобождать память под элементы в любой момент времени работы программы и возможности установить связь между любыми двумя элементами с помощью указателей.