Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Использование указателей. Списки





Список представляет собой совокупность динамических объектов одного типа, упорядоченных с помощью ссылок.

Объекты называются элементами списка. Элементом списка обычно является запись, которая содержит, по крайней мере, два поля (рис. 2.13):

- информационное;

 
 

- указатель.

 
 

Сам список представляется в виде рис. 2.14.

Каждый элемент списка имеет указатель на соседа. У последнего элемента указатель – Nil. Элементы списка и указатели описываются так:

 

Type

Указатель = ^Эл_Списка; {Опережающее описание }

{допускается только в этом случае }

Эл_Списка = Record

Инф_поле: Тип_Инф_поля;

Поле_указателя: Указатель; {Этот тип уже определен выше}

End;

Тип информационного элемента - любой (скалярный, строка, массив и т. д.).

 

Пример. Тype

Ptr = ^El;

El = Record

Buk: Char;

Ukaz: Ptr;

End;

Var

tUk, PrUk, NUk, q: Ptr; {Указатели на элемент списка}

ElSp: El; { Элемент списка (запись типа El) }

С помощью списков достаточно просто представляются очереди.

 

Очередь – это понятие, которое широко используется в вычислительной технике. Список позволяет моделировать операции добавления элементов в очередь и выборки из нее.

Основные операции над списками:

1) переход от одного элемента к другому (следующему);

2) включение нового элемента в список;

3) удаление элемента из списка.

 

1) Первая операция выполняется просто: значению переменной-указателю, которая сейчас указывает на некоторый элемент, необходимо присвоить значение, находящееся в поле указателя этого элемента (см. рис. 2.15):

tUk: = tUk^.Ukaz

 
 

В результате tUk станет ссылкой на следующий элемент или Nil, если элемент последний.

 

2) Удаление элемента из списка выполняется наиболее просто, если имеется ссылка (указатель) на элемент, предшествующий удаляемому. При этом сначала переносятся ссылки, а потом удаляется элемент (освобождается занимаемая им динамическая память). Ссылка на удаляемый элемент не должна теряться, пока он не будет уничтожен или включен в другой список, иначе из него получится " мусор".

Процесс удаления элемента, расположенного в списке после элемента, на который указывает ссылка PrUk, иллюстрируется рис. 2.16, а фрагмент соответствующей программы может иметь вид, приведенный далее.

 

 
 

{Запомним указатель на удаляемый элемент}

tUk: = PrUk^.Ukaz;

{Полю указателя элемента, стоящего перед удаляемым, присвоим}

{ значение поля указателя удаляемого элемента }

PrUk^.Ukaz: = PrUk^.Ukaz^.Ukaz;

 

На этом удаление элемента из списка закончено: связь этого элемента с предыдущим разорвана. Но элемент продолжает занимать память и для его физического удаления нужно выполнить процедуру:

Dispose (tUk); {Физически удалили элемент }

Если нет необходимости освобождать память, то иногда полезно записать в поле указателя удаленного элемента Nil:

tUk^.Ukaz: = Nil.

 

 
 

3) Включение в список элемента, на который имеется указатель NUk, после элемента, на который имеется указатель PrUk, иллюстрирует рис. 2.17. Для выполнения этой операции нужно задать ссылку из вставляемого элемента на следующий (она равна ссылке из предыдущего элемента на следующий – см. рис. 2.17, а), а затем – изменить ссылку из предыдущего элемента на вставляемый (см. рис. 2.17, б). Существующая связь разрывается последней, чтобы не потерять элемент.

 

Фрагмент программы будет иметь вид

New(NUk); {Создали вставляемый элемент}

Readln(NUk^.Buk);

Nuk^.Ukaz: =PrUk^.Ukaz; {Ссылка из вставляемого на следующий}

PrUk^.Ukaz: = Nuk; {Ссылка из предыдущего на вставляемый}


 







Дата добавления: 2014-12-06; просмотров: 643. Нарушение авторских прав; Мы поможем в написании вашей работы!




Практические расчеты на срез и смятие При изучении темы обратите внимание на основные расчетные предпосылки и условности расчета...


Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...


Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...


Вычисление основной дактилоскопической формулы Вычислением основной дактоформулы обычно занимается следователь. Для этого все десять пальцев разбиваются на пять пар...

Эффективность управления. Общие понятия о сущности и критериях эффективности. Эффективность управления – это экономическая категория, отражающая вклад управленческой деятельности в конечный результат работы организации...

Мотивационная сфера личности, ее структура. Потребности и мотивы. Потребности и мотивы, их роль в организации деятельности...

Классификация ИС по признаку структурированности задач Так как основное назначение ИС – автоматизировать информационные процессы для решения определенных задач, то одна из основных классификаций – это классификация ИС по степени структурированности задач...

Предпосылки, условия и движущие силы психического развития Предпосылки –это факторы. Факторы психического развития –это ведущие детерминанты развития чел. К ним относят: среду...

Анализ микросреды предприятия Анализ микросреды направлен на анализ состояния тех со­ставляющих внешней среды, с которыми предприятие нахо­дится в непосредственном взаимодействии...

Типы конфликтных личностей (Дж. Скотт) Дж. Г. Скотт опирается на типологию Р. М. Брансом, но дополняет её. Они убеждены в своей абсолютной правоте и хотят, чтобы...

Studopedia.info - Студопедия - 2014-2025 год . (0.009 сек.) русская версия | украинская версия