 |
|
|
Архитектура Астрономия Аудит Биология Ботаника Бухгалтерский учёт Войное дело Генетика География Геология Дизайн Искусство История Кино Кулинария Культура Литература Математика Медицина Металлургия Мифология Музыка Психология Религия Спорт Строительство Техника Транспорт Туризм Усадьба Физика Фотография Химия Экология Электричество Электроника Энергетика |
Cвязанные динамические данные
Линейные списки — это данные динамической структуры, которые представляют собой совокупность линейно связанных однородных элементов, и для которых разрешается добавлять элементы между любыми двумя другими, и удалять любой элемент. Очередь — частный случай линейного односвязного списка, для которого разрешены только два действия: добавление элемента в конец (хвост) очереди и удаление элемента из начала (головы) очереди. Стек — частный случай линейного односвязного списка, для которого разрешено добавлять или удалять элементы только с одного конца списка, который называется вершиной (головой) стека. Деревья — это динамические данные иерархической структуры произвольной конфигурации. Элементы дерева называются вершинами (узлами). Организация взаимосвязей в связанных динамических данных Связанные динамические данные характеризуются высокой гибкостью создания структур данных различной конфигурации. Это достигается благодаря возможности выделять и освобождать память под элементы в любой момент времени работы программы и возможности установить связь между любыми двумя элементами с помощью указателей. Для организации связей между элементами динамической структуры данных требуется, чтобы каждый элемент содержал кроме информационных значений как минимум один указатель. Отсюда следует, что в качестве элементов таких структур необходимо использовать записи, которые могут объединять в единое целое разнородные элементы. В простейшем случае элемент динамической структуры данных должен состоять из двух полей: информационного и указательного. Схематично такую структуру данных можно показать следующим образом:
Соответствующие ей объявления будут иметь такой вид: Type TPtr = ^TElem; TElem = record Inf : Real; Link : TPtr end; Правило последовательности описаний в Turbo Pascal требует, чтобы каждый идентификатор был описан, прежде чем он будет использоваться для других объявлений. Однако в приведенном примере, как бы ни располагались описания типов указателя TPtr и элемента TElem, это правило выполнено не будет. Поэтому, для описания типов элементов динамических структур данных сделано исключение. Тип указателя на элемент динамической структуры данных может и должен быть описан перед описанием типа этого элемента. Работа с очередью Для создания очереди и работы с ней необходимо иметь как минимум два указателя: • на начало очереди (возьмем идентификатор BegQ); • на конец очереди (возьмем идентификатор EndQ). Кроме того, для освобождения памяти удаляемых элементов требуется дополнительный временный указатель (возьмем идентификатор Р). Дополнительный указатель также часто используется в других ситуациях для удобства работы с очередью. Создание очереди 1. Исходное состояние:
BegQ:= nil; EndQ:= nil; 2. Выделение памяти под первый элемент очереди:
New(P);
3. Занесение информации в первый элемент
P^.Inf:=3; P^.Link:=nil;
4. Установка указателей BegQ и EndQ на созданный первый элемент:
BegQ:=P; EndQ:=P;
Поиск по сайту: |
