Лекция № 9

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

План лекции

1. Двунаправленный список. Создание и просмотр.

2. Работа со списками

1. Двунаправленный список. Создание и просмотр

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

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

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;

}

2. Работа со списками

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

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

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. Дайте понятие двунаправленного списка.

2. Что такое заголовок списка?

3. Как создать пустой двунаправленный список?

4. Как обратиться к следующему, предыдущему элементу списка?

5. Как перейти к следующему, предыдущему элементу списка?

6. Как создать и удалить список?

7. Как просмотреть список с начала и с конца?

8. Как вывести элементы списка на экран?

9. Как выполнить поиск в списке?

10. Как удалить элемент из начала списка, из конца списка?

11. Как вставить элемент в начало списка, в конец списка?