ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 8

Тема: «Линейный двунаправленный список»

Цель: научиться создавать и просматривать линейный двунаправленный список, добавлять элементы в список, удалять элементы из списка, выполнять поиск по списку.

Ход работы

Теоретические обоснования

Двусвязный список - это структура данных, которая состоит из узлов, которые хранят полезные данные, указатели на предыдущий узел и следующий узел.

Для реализации списка нам понадобится структура узел

struct list

{

int value;

list *next;

list *prev;

};

Указатель prev хранит адрес предыдущего узла, если его нет (значит, это первый узел) то переменная равна NULL. Аналогично, указатель next хранит адрес следующего узла. Структура "Двусвязный Список" будет хранить указатель head, ссылающийся на первый элемент, и указатель tail, ссылающийся на последний элемент

В случае, когда в списке нет элементов, оба они равны нулю.

list *head=NULL;

list *tail=NULL;

Пустой список

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

Список из одного элемента

Создадим список:

int i,a,b,n;

cout<<"Введите количество элементов ";

cin>>n;

cout<<endl<<"Введите диапазон ";

cin>>a>>b;

cout<<endl;

srand(time(NULL));

for(i=1; i<=n; i++)

{

//Выделение памяти под новый элемент структуры

list *tmp=new list;

//Указываем, что изначально по следующему адресу пусто

tmp->next=NULL;

//Записываем значение в структуру

tmp->value=rand()*(b-a)/32500+a;

if (head!=NULL) //Если список не пуст

{

//Указываем адрес на предыдущий элемент в соотв. поле

tmp->prev=tail;

tail->next=tmp; //Указываем адрес следующего за хвостом элемента

tail=tmp; //Меняем адрес хвоста

}

else //Если список пустой

{

tmp->prev=NULL; //Предыдущий элемент указывает в пустоту

head=tail=tmp; //Голова=Хвост=тот элемент, что сейчас добавили

}

}

Просмотрим список сначала, т.е. с головы:

tmp=head; //Временно указываем на адрес первого элемента

while (tmp!=NULL) //Пока не встретим пустое значение

{

//Выводим каждое считанное значение на экран

cout<<tmp->value<<" ";

//Смена адреса на адрес следующего элемента

tmp=tmp->next;

}

cout<<"\n";

Просмотрим список в обратном порядке, т.е. с хвоста:

list *tmp=tail; //Временный указатель на адрес последнего элемента

while (tmp!=NULL) //Пока не встретится пустое значение

{

cout<<tmp->value<<" "; //Выводить значение на экран

//Указываем, что нужен адрес предыдущего элемента

tmp=tmp->prev;

}

cout<<"\n";

Удалим список:

while (tmp!=NULL)

{

tmp = head->next;

delete tmp;

head = tmp;

}

Вставка нового элемента в начало списка:

Вставка спереди очень похожа на вставку в односвязный список. Сначала создаётся новый элемент и задается ему значение:

list *tmp1=new list;

cout<<"Введите новое значение: "; cin>>tmp1->value;

cout<<endl;

Так как он стал первым, то указатель next ссылается на старую голову списка, а предыдущего элемента нет. Теперь, если в списке уже был головной элемент, то его указатель prev должен ссылаться на вновь созданный элемент:

tmp1->prev=NULL;

tmp1->next=head;

head->prev = tmp;

head=tmp1; // перекинем указатель head на вновь созданный элемент

Создали новый элемент и задали ему значение

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

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

//создаем указатель на элемент, следующий за первым

tmp=head->next;

delete head; //удаляем первый элемент списка

head=tmp; //делаем первым элементом списка (т.е. головой) элемент, который следовал за первым элементом

head->prev=NULL; // указатель на предыдущий элемент для первого элемента равен нулю

Удаление последнего элемента:

tmp=tail; //создаем указатель на последний элемент списка

tail=tail->prev; //перекидываем указатель хвоста на предыдущий элемент

tail->next=NULL; //указатель на следующий элемент для хвоста равен нулю

delete tmp; //удаляем последний элемент

Вставка элемента внутрь списка:

//вставить новый элемент после третьего элемента

tmp1=head; //Временно указываем на адрес первого элемента

i=1; //переменная для подсчета номера элемента списка

while (tmp1!=NULL && i<3) //Пока не встретим пустое значение и элемент списка не будет третьим

{

tmp1=tmp1->next; //Смена адреса на адрес следующего элемента

i++;

}

//после выполнения цикла в tmp1 хранится третий элемент

tmp2=tmp1->next; //запоминаем четвертый элемент

list *tmp3=new list; //создаем новый элемент

tmp3->value=9000; //присвоим ему значение

//связываем третий элемент с новым и новый элемент с четвертым

tmp1->next=tmp3;

tmp3->prev=tmp1;

tmp2->prev=tmp3;

tmp3->next=tmp2;

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

Задание 1. Создать список, просмотреть его с начала, просмотреть список с конца, удалить первый, удалить второй элемент списка, удалить последний элемент списка, вставить новый в начало списка, в конец списка, после 3-го элемента, удалить списки из памяти.

Выполнение задания 1.

#include <iostream.h>

#include <iomanip.h>

#include <ctime>

struct list

{

int value;

list *next;

list *prev;

};

int main()

{

system("chcp 1251>nul");

//инициализация списка

list *head=NULL;

list *tail=NULL;

//создание списка

int i,a,b,n;

cout<<"Введите количество элементов ";

cin>>n;

cout<<"Введите диапазон ";

cin>>a>>b;

cout<<endl;

srand(time(NULL));

for(i=1; i<=n; i++)

{

list *tmp=new list; //Выделение памяти под новый элемент структуры

tmp->next=NULL; //Указываем, что изначально по следующему адресу пусто

tmp->value=rand()*(b-a)/32500+a; //Записываем значение в структуру

if (head!=NULL) //Если список не пуст

{

tmp->prev=tail; //Указываем адрес на предыдущий элемент в соотв. поле

tail->next=tmp; //Указываем адрес следующего за хвостом элемента

tail=tmp; //Меняем адрес хвоста

}

else //Если список пустой

{

tmp->prev=NULL; //Предыдущий элемент указывает в пустоту

head=tail=tmp; //Голова=Хвост=тот элемент, что сейчас добавили

}

}

//вывод списка в обратном порядке

cout<<"Список в обратном порядке: \n";

list *tmp=tail;

//Временный указатель на адрес последнего элемента

while (tmp!=NULL) //Пока не встретится пустое значение

{

cout<<tmp->value<<" "; //Выводить значение на экран

tmp=tmp->prev; //Указываем, что нужен адрес предыдущего элемента

}

cout<<"\n";

//вывод списка с начала

cout<<"Список с начала:"<<endl;

tmp=head; //Временно указываем на адрес первого элемента

while (tmp!=NULL) //Пока не встретим пустое значение

{

cout<<tmp->value<<" "; //Выводим каждое считанное значение на экран

tmp=tmp->next; //Смена адреса на адрес следующего элемента

}

cout<<"\n";

//удаление первого элемента списка

tmp=head->next;

delete head;

head=tmp;

head->prev=NULL;

//удаление последнего элемента списка

tmp=tail;

tail=tail->prev;

tail->next=NULL;

delete tmp;

//вставка в начало списка

list *tmp1=new list;

cout<<"Введите новое значение для головы "; cin>>tmp1->value;

cout<<endl;

tmp1->prev=NULL;

tmp1->next=head;

head=tmp1;

//вставка в конец списка

list *tmp2=new list;

cout<<"Введите новое значение для хвоста "; cin>>tmp2->value;

cout<<endl;

tail->next=tmp2;

tmp2->next=NULL;

tail=tmp2;

//вывод списка с начала

cout<<"Список с начала:"<<endl;

tmp=head; //Временно указываем на адрес первого элемента

while (tmp!=NULL) //Пока не встретим пустое значение

{

cout<<tmp->value<<" "; //Выводим каждое считанное значение на экран

tmp=tmp->next; //Смена адреса на адрес следующего элемента

}

cout<<"\n";

//вставить новый элемент после третьего элемента

tmp1=head; //Временно указываем на адрес первого элемента

i=1; //переменная для подсчета номера элемента списка

while (tmp1!=NULL && i<3) //Пока не встретим пустое значение и элемент списка не будет третьим

{

tmp1=tmp1->next; //Смена адреса на адрес следующего элемента

i++;

}

//после выполнения цикла в tmp1 хранится третий элемент

tmp2=tmp1->next; //запоминаем четвертый элемент

list *tmp3=new list; //создаем новый элемент

tmp3->value=9000; //присвоим ему значение

//связываем третий элемент с новым и новый элемент с четвертым

tmp1->next=tmp3;

tmp3->prev=tmp1;

tmp2->prev=tmp3;

tmp3->next=tmp2;

//удалить второй элемент списка

tmp1=head; //Временно указываем на адрес первого элемента

i=1; //переменная для подсчета номера элемента списка

while (tmp1!=NULL && i<2) //Пока не встретим пустое значение и элемент списка не будет вторым

{

tmp1=tmp1->next; //Смена адреса на адрес следующего элемента

i++;

}

//после выполнения цикла в tmp1 хранится второй элемент

tmp2=tmp1->next; //запоминаем третий элемент

//связываем первый и третий элемент

head->next=tmp2;

tmp2->prev=head;

delete tmp1;

cout<<"\n";

//вывод списка с начала

cout<<"Список с начала:"<<endl;

tmp=head; //Временно указываем на адрес первого элемента

while (tmp!=NULL) //Пока не встретим пустое значение

{

cout<<tmp->value<<" "; //Выводим каждое считанное значение на экран

tmp=tmp->next; //Смена адреса на адрес следующего элемента

}

cout<<"\n";

//удаление списка из памяти

while (tmp!=NULL)

{

tmp = head->next;

delete tmp;

head = tmp;

}

system("pause");

return 0;

}

Решить самостоятельно:

Написать программу, которая создает, просматривает список и решает следующие задачи:

Найти максимальный элемент в списке. Удалить его из списка, затем добавить его в середину списка.

Найти среднее значение в списке. Удалить из списка первый и последний элементы списка, если они меньше, чем среднее значение.

Найти произведение всех ненулевых значений в списке. Вставить его в середину списка.

Найти количество отрицательных элементов списка. Добавить его после последнего отрицательного элемента списка.