Динамические структуры: списки, деревья - раздел Транспорт, От автора Примеры Программ, Использующих Динамические Массивы, Приведенные В Предыдущей...
Примеры программ, использующих динамические массивы, приведенные в предыдущей главе, все еще были плохими. Для того чтобы использовать динамические массивы таким образом, мы должны заранее знать размеры этих массивов. В реальных же задачах зачастую объем обрабатываемых данных заранее не известен. В этом случае удобно использовать динамические структуры данных, простейшей из которых является список. Список называется динамической структурой не только потому, что он размещается в динамической памяти, но, главным образом, потому, что его размер может меняться в процессе выполнения программы. Список не является объектом языка Паскаль и вообще никак не связан с конкретным языком программирования. Сама идея списка заключается в следующем: список есть совокупность однотипных элементов, элементы размещаются в памяти произвольным образом, но в каждом из элементов хранится адрес следующего элемента. Таким образом, для обработки списка достаточно знать один-единственный адрес - адрес первого элемента списка. Чтобы обозначить последний элемент, в нем в качестве адреса следующего элемента хранят константу Nil. Схематично список можно изобразить так:
Каждый элемент такого списка можно рассматривать как совокупность двух полей - поля данных, в котором содержится хранимая в списке информация (любого типа), и адресного поля, в котором записан адрес следующего элемента. Такой список называют односвязным, поскольку между парой элементов есть только одна связь. В некоторых случаях удобнее использовать двусвязный список, в каждом элементе которого хранятся адреса предыдущего и последующего элементов:
Деревом называют совокупность элементов, каждый из которых связан с одним элементом-предком и с несколькими элементами-потомками. Простейшее дерево, когда число потомков не превышает двух, называется бинарным. Бинарное дерево можно схематично изобразить в виде:
Каждый элемент бинарного дерева содержит поле данных и 3 (или 2) адресных поля. Рассмотрим теперь реализацию динамических структур в Паскаль-программе. Поскольку элементы будут размещаться в динамической памяти, переменные такого типа в программе не нужны, а нужны лишь указатели на них, следовательно, достаточно описать тип элемента в операторе Type. В качестве типа элемента можно, очевидно, использовать только запись. Опишем сначала элемент односвязного списка:
B r... Теперь мы можем присвоить переменным их значения...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Динамические структуры: списки, деревья
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
От автора
Первое издание этой книги вышло в свет в 1997 году и довольно быстро стало библиографической редкостью. Автор несколько неожиданно для себя обнаружил, что книга пользуется черезвычайно высоким спро
Символьный тип данных
Для хранения символьной информации в Паскале предусмотрен специальный тип данных Char. Допустимы переменные, нетипизированные и типизированные константы такого типа. Данные типа
Caseвыражение Of
список значений : оператор/блок
..................................
список значений: оператор/блок
Процедуры и функции. Сфера действия описаний
В языке Паскаль (как вы уже поняли из предыдущего материала) существуют понятия процедуры и функции. Процедуры и функции можно определить как замкнут
Открытые массивы и нетипизированные параметры
Из предыдущего раздела мы узнали, что параметры подпрограмм описываются как [Var] имя : имя типа , это правда, но не вся правда - существует еще два
Множества
Понятие множества в Паскале очень близко к математическому определению: множество - это совокупность однотипных неиндексированных объектов. Множества
Графические средства языка Паскаль
Монитор персонального компьютера может работать в двух режимах - текстовом и графическом. Все, что мы делали до сих пор, мы делали в текстовом режиме. Текстовый экран содержит 2000 знако
Особенности вещественных вычислений
В отличие от целочисленных выражений, которые всегда вычисляются точно, вещественные выражения дают приближенный результат и вещественные переменные содержат приближенные значения. Это обстоятельст
Case тип Of
константа 1 : (описание поля);
константа 2 : (описание поля);
.....................
Модуль Crt
Crt - еще один стандартный модуль Паскаля, в котором содержатся разнообразные средства консольного ввода-вывода (то есть ввода с клавиатуры и вывода на текстовый экран). Процедуры
Var TextAttr : Byte
В ней содержится текущий цвет фона и цвет символов, используемые при выводе на экран процедурами Write иWriteLn. Изменив эту переменную, вы задаете новый
Другие средства обработки файлов и модуль DOS
Для того чтобы определить, есть ли на диске файл с заданным именем, удобно использовать уже известную нам стандартную функцию IOResult , которая возвращает ноль при успешном завершении последней оп
Type SearchRec=Record
Fill : Array[1..21] of Byte;
Attr : Byte;
Time : LongInt;
Size : LongInt;
Name : Stri
Процедурные типы
Язык Паскаль позволяет использовать в программе данные типа “процедура” или типа “функция”. Такие данные можно передавать как аргументы подпрограмм, можно описывать и использовать массивы процедур
Указатели и динамическая память
Указателями называются переменные и константы, значениями которых являются адреса. Различаются два вида указателей - обобщенные указатели и
Открытые строки
Открытыми строками, или длинными строками, или C-строками, называются символьные последовательности длиной до 65535 символов, ограниченные справа нуль-символ
Обработка программных прерываний
Программное прерывание - это ситуация, возникающая, когда дальнейшее выполнение программы невозможно. Например, деление на ноль, переполнение, ошибка Range check error, обращение по неверному адрес
Объекты
Объектом в языке Паскаль называется совокупность данных и подпрограмм, обрабатывающих эти данные. Программирование с использованием объектов называется объектно-о
Type имя типа=Object
описание полей описание методов End;
Поля объектов описываются так же, как поля записей, а описание метода - это заголовок процедуры или функции. Сами методы распол
Рекурсия и динамическое программирование
В этом и всех последующих разделах речь пойдет уже не о языке программирования Паскаль, а о задачах, которые вы можете решать с помощью этого языка, о наиболее интересных и полезных алгоритмах и пр
Рекурсия и стек отложенных заданий
Рекурсивные алгоритмы далеко не всегда неэффективны, как можно подумать, прочитав предыдущий раздел. Во многих задачах рекурсивные процедуры и функции очень полезны, кроме того, они исключительно п
Стеки и очереди
Значение стека как структуры данных в программировании не исчерпывается лишь стеком отложенных заданий. В этом разделе мы решим с помощью стека задачу о вычислении значения арифметического выражени
Комбинаторные алгоритмы
В этом разделе мы рассмотрим три наиболее важные задачи комбинаторики: нахождение всех подмножеств множества из n элементов; нахождение всех выборок по m элементов из n элементов и нахождение всех
Бинарные деревья
В этом разделе мы рассмотрим различные алгоритмы обхода бинарного дерева. К алгоритмам создания бинарного дерева мы обратимся несколько позже, а пока будем считать, что дере
Алгоритмы сортировки
В этом разделе мы рассмотрим различные алгоритмы решения задачи сортировки. Задача сортировки ставится следующим образом: дана последовательность записей R1,R
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов