while (r != NULL) // Пока не дошли до последнего
//элемента списка
{cout << r -> inf << " "; // Вывод информации из поля inf
//адрес которого находится в указателе r. r = r -> next; // Переход к следующему элементу списка.
//Для этого из поля next текущего элемента списка
//в указатель r пересылаем адрес на следующий элемент.
}getch();
cout << "\n\nУдалить узел cо значением k= "; cin >> a;
r = fr;
if (r -> inf == a)
{ cout << "\nудаляется головной узел списка\n";
fr = fr -> next; // В указатель на первый элемент пересылаем // адрес второго элемента списка.
delete r;
}
else
{ while ((r -> inf != a) && ( r != NULL)) // Поиск элемента,
{ // который надо удалить.
rp = r; // Запоминаем адрес пройденного элемента. r = r -> next; } // Переходим на новый элемент.
if (r -> inf == a) // Проверяем, найден элемент или нет.
{ cout << " Удаляется узел со значением= " << r -> inf << "\n\n";
rp -> next = r -> next; // Поле указателя удаляемого элемента
//пересылаем в поле указателя элемента, который
//расположен перед удаляемым.
delete r;
cout << "\tСписок после удаления элемента: \n\n"; r = fr;
24
while (r != NULL) // Пока не дошли до последнего элемента
//списка
{cout << r -> inf << " "; // Вывод значения текущего
//элемента списка
r = r -> next; // Переход к следующему элементу списка.
//Для этого из поля next текущего элемента списка
}// в указатель r пересылаем адрес на следующий
//элемент.
}
else
cout << "\n" << "Узел со значением " << a << " не найден "; getch(); }
// Вставка нового элемента в список.
cout << "\n\nВставить в список элемент со значением b= ";
cin >> b;
cout << "\n\nЗа элементом со значением n = "; cin >> a;
r = fr;
while ((r -> inf != a) && (r != NULL)) r = r -> next;
if (r -> inf == a)
{
rp = new node; // Выделяем память под новый элемент. rp -> inf = b; // Заполняем поле inf нового элемента.
rp -> next = r -> next; // К новому элементу присоединяем // правую часть списка.
r -> next = rp; // К левой части списка присоединяем // новый элемент списка.
cout << "Cписок после вставки элемента со значением: " << b << "\n";
r = fr;
25
while (r != NULL)
{
cout << r -> inf << " "; r = r -> next;
}
}
else
cout << "\nЭлемент списка со значением " << a << " не найден ";
// Вставка в список нового головного элемента.
cout << "\n\nВведи значение для нового головного элемента n
= ";
cin >> a;
rp = new node; // Выделяем память под новый элемент. rp -> inf = a; // Заполняем поле inf нового элемента.
rp -> next = fr; // Новый элемент делаем первым. fr = rp; // В указатель на первый элемент списка
// пересылаем адрес нового элемента. cout << "\nСписок с новым головным элементом:\n";
r = fr;
while (r != NULL)
{ cout << r -> inf << " "; r = r -> next; }
getch(); }
26
Лабораторная работа №4 Двусвязные линейные списки
Цель работы – овладеть практическими навыками работы с двусвязными линейными списками. Научиться формировать списки, освоить технику программирования операций над списками.
Задания:
1. Изучить:
а) способы формирования списка; б) операции над списками: удалить элемент из списка,
добавить элемент в список, найти элемент в списке; в) способы вывода списка.
2.Разработать алгоритм решения задачи.
3.Составить программу решения задачи.
4.Отладить программу.
Контрольные вопросы :
Все вопросы в данном пункте рассматриваются для списка, элементами которого являются следующие объекты:
struct zvn { int inf; zvn *lf, *rt;}
1.Как определить объект для списка, элементами которого являются числа.
2.Как определить объект для списка, элементами которого являются слова.
3.Как определить объект для списка, элементами которого являются указатели.
4.Определены переменные: zvn *fst = NULL, *en = NULL, *r. Указатели fst, en, r – соответственно для адреса пер-
27
вого, последнего элемента списка и промежуточных значений адресов переменных типа zvn. Сформирован список, с элементами типа zvn. Напишите коды перебора элементов списка.
5.Перечислите информацию, которая необходима для того, чтобы удалить из списка со значением, равным некоторому числу k.
6.Перечислите информацию, которая необходима для того, чтобы в список добавить элемент со значением равным некоторому числу k.
7.Определены переменные: zvn *fst = NULL, *en=NULL, *r. Сформирован список. Пусть в указателе en находится адрес последнего элемента списка. Напишите коды присоединение нового элемента типа zvn к списку.
8.В указателе r находится адрес некоторого элемента списка. Напишите код вывода элемента списка, который является пятым относительно данного. Циклы не использовать. Ответ должен состоять из одной директивы.
9.В указателе r находится адрес некоторого элемента списка. Напишите код вывода элемента списка, относительно которого данный элемент является пятым. Циклы не использовать. Ответ должен состоять из одной директивы.
10.Определены переменные: zvn *fst = NULL, *en=NULL, *r. Объясните код r -> lf.
11.Определены переменные: zvn *fst = NULL, *en=NULL, *r. Объясните код r -> inf.
12.Определены переменные: zvn *fst = NULL, *en=NULL, *r. Объясните код r = r -> lf.
13.Определены переменные: zvn *fst = NULL, *en=NULL, *r. Объясните код r ->lf->lf->lf-> lf-> inf.
14.Определены переменные: zvn *fst = NULL, *en=NULL, *r. Объясните код r -> rt -> rt -> rt -> rt -> inf.
15.Перечислите информацию, которая необходима для того, чтобы удалить из списка головной (первый) элемент списка.
28