Удаление элемента из списка.

При удалении элемента из списка необходимо различать три случая:

1. Удаление элемента из начала списка.

2. Удаление элемента из середины списка.

3. Удаление из конца списка.

Удаление элемента из начала списка.

Двусвязный список

Каждый элемент в списке с двойной связью имеет указатель на следующий элемент списка и указатель на предыдущий элемент списка. Рис. иллюстрирует характер связей в таком списке. Список, который вместо одной имеет две связи, отличается двумя основными преимуществами. Во-первых, список может читаться в обоих направлениях. Это не только упрощает сортировку списка, но также позволяет пользователям базы данных просматривать данные в обоих направлениях. Во-вторых, и прямая и обратная связь позволяют прочитать список полностью и поэтому при нарушении одной из связей список может быть восстановлен по другой связи. Это свойство имеет смысл использовать при отказах оборудования, приводящих к нарушению списка.

Рис.. Список с двойной связью: 1 - информационные поля; 2 - связь с нулевым значением.
Для списка с двойной связью предусматриваются три основные операции: вставка нового первого элемента, вставка нового среднего элемента и вставка нового последнего элемента. Эти операции проиллюстрированы на рис..
Список с двойной связью строится подобно списку с одной связью, причем в записи должно быть предусмотрено место для двух указателей. Для примера со списком почтовых корреспонденций запись адреса можно модифицировать следующим образом:

type

AddrPointer = ^address;

address = record

name : string[30];

street: string[40];

city: string[20];

state: string[2];

zip: string[9];

next: AddrPointer; { указатель на следующую запись }

prior: AddrPointer; { указатель на предыдущую запись }

end;

DataItem = address;

DataArray = array [1..100] of AddrPointer;

1 Inserling a New First Element
4 becomes
6 Inserling a New Middle Element
4 becomes
7 Inserling a New Last Element
4 becomes

Рис.. Вставка элемента в список с двойной связью: 1 - вставка нового первого элемента; 2 - новый элемент; 3 - указатель с нулевым значением; 4 - левый список преобразуется в правый; 5 - информационные поля; 6 - вставка нового среднего элемента; 7 - вставка нового последнего элемента.

Ниже приводится функция, которая позволяет строить список с двойной связью для записей адресов:

{добавление элементов в список с двойной связью }

procedure DL_Store(i: AddrPointer);

begin

if last=nil then { первый элемент списка }

begin

last:=i;

start:=i;

i^.next:=nil;

i^.prior:=nil;

end

else

begin

last^.next:=i;

i^.next:=nil;

i^.prior:=last;

last:=i;

end;

end; { конец функции добавления в список с двойной связью }

Эта функция помещает каждый новый элемент в конец списка. Следует иметь в виду, что перед первым обращением к функции переменные "start" и "last" должны устанавливаться в нулевое значение.
В ходе построения списка с двойной связью каждый новый элемент может /как и для списка с одной связью/ устанавливаться не в конец, а в соответствующее место, обеспечивая упорядочность элементов в списке.

При поиске конкретного элемента списка, как и для списка с одиночной связью, делается последовательный проход по цепочке связей пока не будет найден требуемый элемент

.
При удалении элемента из списка возникает одна из трех ситуаций: удаление первого элемента, удаление среднего элемента и удаление последнего элемента. Рис. иллюстрирует изменение связей для этих случаев.

1 Deleting the First Item
3 becomes
6 Deleting a Middle Item
3 becomes
7 Deleting the Last Item
3 becomes

Рис.. Удаление элемента из списка с двойной связью: 1 - удаление первого элемента; 2 - информационные поля; 3 - левый список преобразуется в правый; 4 - удаленный элемент; 5 - указа- тель с нулевым значением; 6 - удаление среднего элемента; 7 удаление последнего элемента.

Ниже приводится функция, которая выполняет удаление элемента типа "address" из списка с двойной связью:

{ удаление элемента из списка с двойной связью }

function DL_Delete(start: AddrPointer;

             key: string[80]): AddrPointer;

var

temp, temp2: AddrPointer;

done: boolean;

begin

if start^.name=key then begin { первый элемент списка}

DL_Delete:=start^.next;

if temp^.next <> nil then

begin

temp := start^.next;

temp^.prior := nil;

end;

dispose(start);

end else

begin

done := FALSE;

temp := start^.next;

temp2 := start;

while (temp<>nil) and (not done) do

begin

if temp^.name=key then

begin

   temp^.next:=temp^.next;

if temp^.next<>nil then

   temp^.next^.prior:=temp2;

done:=TRUE;

dispose(temp);

end else

begin

temp2:=temp;

temp:=temp^.next;

end;

end;

DL_Delete:=start; { начало не изменяется }

if not done then WriteLn('not found');

 end;

end; { конец функции удаления элемента из списка с двойной связью }

Этой функции передается на один указатель меньше, чем для соответствующей функции при использовании списка с одной связью. /Удаленный элемент уже имеет указатель на предыдущий элемент и указатель на следующий элемент/. Поскольку первый элемент в списке может измениться, функция возвращает указатель на начало списка.

Порядок выполнения работы

1. Открыть проект Delphi Stuctures.

2. На главной форме в главное меню проекта добавить пункт «Лабораторная работа №5», при выборе которого должно появляться окно модуля «DinamicStuct». Для этого модуль DinamicStuct с формой добавить в проект.

3. Установить на форму модуля DinamicStuct компоненты, обеспечивающие ввод исходных данных и вывод результатов работы программы в соответствии с вашим вариантом задания (табл. 5.1), а также управляющую кнопку для запуска программного кода при нажатии на кнопку (событие onClic) в работающей программе. Для ввода и вывода в этих задачах использовать компоненты класса Tmemo.

4. В обработчике события onClic управляющей кнопки написать программный код, моделирующий работу структуры данных динамического характера, соответствующей заданию вашего варианта.

5. отладить приложение на тестовых примерах и продемонстрировать работу смоделированной структуры данных преподавателю.

6. Составить отчет о выполненной лабораторной работе, в который должны войти:

а) задание, в соответствии с вариантом;

б) блок-схема решения задачи;

в) программа решения задачи;

г) распечатка формы с демонстрацией работы смоделированной структуры данных.

7. Защитить работу преподавателю.

Таблица 5.1

№ вар.	Содержание задания
1.	Организовать программно линейный односвязный список следующей структуры: Опишите в программе запись, в поле bukv которой заносится буква. Порождая записи, поместить их в стек, а затем «вытолкнуть» их из списка, получив буквы в порядке, обратном исходному. Проверьте работу примера для исходного набора букв: const A: array [1 .. 9] of char =(‘A’, ’P’, ‘Y’, ‘T’, ‘K’, ‘Y’, ’P’, ‘T’, ‘C’).
2.	С помощью стека, организованного в соответствии со структурой вар. 1 организовать получение палиндрома, в котором вторая половина является зеркальным отражение первой без последнего символа. Первую половину вводить с клавиатуры. Например:
3.	Программно организазать очередь в виде однонаправленого списка из элементов типа rec: Type ptr =^ rec; rec = record      key : integer;        s : ptr;           end; var t : rec; Заполняются ссылки на первое ипоследнее звенья списка. Во входном файле задана последовательность из равного количества положительных и отрицательных целых чисел, за которой следует нуль. Ввести эти числа и вывести их, чередуя положитедльные числа (на нечетных местах) с отрицательными ( на четных), причем исходный взаимный порядок как среди положительных, так и среди отрицательных чисел должен быть сохранен.
4.	Многочлен P(х) = anxn + an-1xn-1 +… + a1x + a0 с целыми коэффициентами можно представить в виде списка, элементы которого расположены по убыванию степеней одночленов: Описать на Object Pascal тип данных, соответствующий такому представлению многочленов, и определить следующие функции и процедуры для работы с этими списками-многочленами: а) логическую функцию Equal(p,q), проверяющую на равенство многочлены p и q; б) функцию Value(p,x), вычисляющую значение p в точке x; в) процедуру Dif(p,q), которая строит многочлен p-производную многочлена q; г) процедуру Addit(p,q,r), которая строит многочлен p-сумму многочленов q и r.
5.	Кольцевым списком называется однонаправленный список, в последнем звене которого вместо Nil указывается ссылка на первое звено: Пусть L - кольцевой список с элементами типа Type prt =^ rec                                                                                  rec = record;                                                                                                  key : integer;                                                                                         s : ptr;                                                                                            end; а E - переменная типа rec.   Описать и отладить: а) процедуру, которая строит кольцевой список L и выводит в компонент класса TstringGrid таблицу: t1 t2  … tn-1 tn t2 t3  … tn t1 t3 t4  … t1 t2 -- - - - - - - - - - tn t1  … tn-2 tn-1     б) процедуру, которая строит линейный список L и функцию, которая удаляет из непустого списка L последний элемент. в) процедуру, которая строит двусвязный список L и функцию, которая добавляет в конец списка L новый элемент.

Контрольные вопросы

1 Определения типизированного и обобщенного указателя.

2 Что такое линейный цепной список, и алгоритмы основных операций при работе с ним.

3 Принцип работы кольцевого списка.

4 Организация стека на базе линейного и кольцевого списка.

5 Организация очереди на базе линейного и кольцевого списка.

Лабораторная работа № 6

(8 часов)