Алгоритм удаления элемента в списке по ключу

Удалить из списка элемент, информационная часть (ключ) которого совпадает со значением, введенным с клавиатуры.

Решение данной задачи проводим в два этапа – поиск и удаление.

Первый этап – поиск

Алгоритм поиска аналогичен просмотру списка с начала. Введем дополнительный указатель и присвоим ему значение NULL: Spis2 *key = NULL. Введем с клавиатуры искомое значение i_p (ключ поиска).

1. Установим текущий указатель на начало списка: t = begin;

2. Начало цикла (выполнять пока t! = NULL).

3. Сравниваем информационную часть текущего элемента с искомым, если они совпадают (t -> info = i_p), то запоминаем адрес найденного элемента: key = t; (если ключ поиска уникален, то завершаем поиск – break).

4. Переставляем текущий указатель на следующий элемент: t = t -> next;

5. Конец цикла.

Выполняем контроль, если key = NULL, т.е. искомый элемент не найден, то сообщаем о неудаче и этап удаления не выполняем (return).

Второй этап – удаление

Если элемент найден (key! = NULL), то выполняем удаление элемента из списка в зависимости от его местонахождения.

1. Если удаляемый элемент находится в начале списка, т.е. key равен begin, то первым элементом списка становится второй элемент:

а) указатель начала списка переставляем на следующий (второй) элемент:

begin = begin -> next;

б) адресу prev присваиваем значение NULL, т.е. теперь предыдущего нет begin -> prev = NULL;

2. Если удаляемый элемент в конце списка, т.е. key равен end, то последним элементом в списке должен стать предпоследний:

а) указатель конца списка переставляем на предыдущий элемент: end = end -> prev;

б) обнуляем адрес next нового последнего элемента

end -> next = NULL;

3. Если удаляемый элемент находится в середине списка, нужно обеспечить связь предыдущего и следующего элементов (см. рис. 4.1):

а) от k-го элемента с адресом key обратимся к предыдущему (k–1)-му элементу, адрес которого key-> prev, и в его поле next [(key-> prev)-> next] запишем адрес (k+1)-го элемента, значение которого key-> next:

( key -> prev ) -> next = key -> next;

б) аналогично, в поле prev (k+1)-го элемента, с адресом key-> next запишем адрес (k–1)-го элемента:

( key -> next ) -> prev = key -> prev;

4. Освобождаем память, занятую удаленным элементом.

Рис. 4.1. Схема удаления внутреннего элемента

Алгоритм освобождения памяти, занятой двунаправленным списком, аналогичен рассмотренному алгоритму для стека (см. л.р. 3).

4.2. Пример выполнения задания

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

4.2.1. Реализация задания в оконном приложении

Вид формы и полученные результаты представлены на рис. 4.2.

Приведем только тексты функций-обработчиков соответствующих кнопок:

...

struct Spis2 {

int info;

Spis2 *next, *prev;

} *begin, *end, *t;

//---------------------------------------------------------------------------

void Create_Spis2(Spis2**, Spis2**, int);

void Add_Spis2(int, Spis2**, Spis2**, int);

void View_Spis2(int, Spis2*);

void Del_All(Spis2**);

Рис. 4.2

//----------------------------- Текст функции-обработчика кнопки Создать ------------

int i, in = StrToInt(Edit1-> Text);

if(begin! = NULL){

ShowMessage(" Освободите Память! " );

return;

}

Create_Spis2(& begin, & end, in);

Memo1-> Lines-> Add(" Начало = " + IntToStr(begin -> info));

//--------------------------- Текст функции-обработчика кнопки Добавить ------------

int i, in = StrToInt(Edit1-> Text), kod = RadioGroup1-> ItemIndex;

String Str[2] = {" в начало ", " в конец " };

Add_Spis2(kod, & begin, & end, in);

if(kod == 0) t = begin;

else t = end;

Memo1-> Lines-> Add(" Добавили " + Str[kod] + IntToStr(t -> info));

//---------------------------- Текст функции-обработчика кнопки Просмотреть -----

if(! begin){

ShowMessage(" Список Пуст! " );

return;

}

if(RadioGroup1-> ItemIndex == 0) {

t = begin;

Form1-> Memo1-> Lines-> Add(" -- С начала --" );

}

else {

t = end;

Form1-> Memo1-> Lines-> Add(" --- С конца --" );

}

View_Spis2(RadioGroup1-> ItemIndex, t);

//----------------------------- Текст функции-обработчика кнопки Очистить ---------

Del_All(& begin);

ShowMessage(" Память освобождена! " );

//---------------------------- Текст функции-обработчика кнопки EXIT -----------------

if(begin! = NULL) Del_All(& begin);

Close();

//------------------- Создание первого элемента -----------------------------

void Create_Spis2(Spis2 **b, Spis2 **e, int in) {

t = new Spis2;

t -> info = in;

t -> next = t -> prev = NULL;

*b = *e = t;

}

//------------------- Добавление элемента в список --------------------------

void Add_Spis2(int kod, Spis2 **b, Spis2 **e, int in) {

t = new Spis2;

t -> info = in;

if(kod == 0){

t -> prev = NULL;

t -> next = *b;

(*b) -> prev = t;

*b = t;

}

else {

t -> next = NULL;

t -> prev = *e;

(*e) -> next = t;

*e = t;

}

//--------------------- Просмотр элементов списка ---------------------------

void View_Spis2(int kod, Spis2 *t) {

while(t! = NULL) {

Form1-> Memo1-> Lines-> Add(t-> info);

// В консольном приложении: cout < < t-> info < < endl;

if(kod == 0) t = t-> next;

else t = t-> prev;

}

4.2.2. Реализация задания в консольном приложении

Декларацию шаблона структуры, декларации прототипов функций пользователя и их тексты смотрите в предыдущем примере, а основная функция может иметь следующий вид:

void main()

{

int i, in, n, kod, kod1;

char Str[2][10] = {" Begin ", " End " };

while(true){

cout < < " \n\tCreat - 1\n\tAdd - 2\n\tView - 3\n\tDel - 4\n\tEXIT - 0: " ;

cin > > kod;

switch(kod) {

case 1: if(begin! = NULL){

cout < < " Clear Memory! " < < endl;

break;

}

cout < < " Begin Info = "; cin > > in;

Create_Spis2(& begin, & end, in);

cout < < " Creat Begin = " < < begin -> info < < endl;

break;

case 2:

cout < < " Info = "; cin > > in;

cout < < " Add Begin - 0, Add End - 1: "; cin > > kod1;

Add_Spis2(kod1, & begin, & end, in);

if(kod1 == 0) t = begin;

else t = end;

cout < < " Add to " < < Str[kod1] < < " " < < t -> info < < endl;

break;

case 3: if(! begin){

cout < < " Stack Pyst! " < < endl;

break;

}

cout< < " View Begin-0, View End-1: ";

cin > > kod1;

if(kod1 == 0) {

t = begin;

cout < < " -- Begin --" < < endl;

}

else {

t = end;

cout < < " --- End --" < < endl;

}

View_Spis2(kod1, t);

break;

case 4:

Del_All(& begin);

cout < < " Memory Free! " < < endl;

break;

case 0: if(begin! = NULL)

Del_All(& begin);

return;

}

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

4.3. Индивидуальные задания

Написать программу по созданию, добавлению (в начало, в конец), просмотру (с начала, с конца) и решению поставленной в лаб.раб.3 задачи для двунаправленных линейных списков.

⇐ Предыдущая 1 2 345 6 7 Следующая ⇒