Работа с двунаправленным списком
Двунаправленный список представлен на рис. 27. Пример 107 даёт представление о работе с двунаправленным списком.
Рис. 27. Двунаправленный список
Пример 107. Создать двунаправленный список, выполнить удаление элемента с заданным номером, добавление элемента с заданным номером, печать полученных списков.
#include <iostream.h>
struct point //описание структуры
{
int key; //ключевое поле
point* pred,*next; //адресные поля
};
point*make_list()
{
int n;
cout<<«n-?»;cin>>n;
point *p,*r,*beg;
p=new (point); //создать первый элемент
beg=p; /*запомнить адрес в переменную beg, в которой хранится начало списка*/
cout<<«key-?»;cin>>p->key; /*заполнить ключевое поле*/
p->pred=0; p->next=0; //запомнить адресные поля
for(int i=1;i<n;i++) /*добавить элементы в конец списка*/
{
r=new(point); //новый элемент
cout<<«key-?»;cin>>r->key; //адресное поле
p->next=r; //связать начало списка с r
r->pred=p; //связать r с началом списка
r->next=0; /*обнулить последнее адресное поле*/
p=r; /*передвинуть p на последний элемент списка*/
}
return beg; //вернуть первый элемент списка
}
void print_list(point *beg)
{
if (beg==0) //если список пустой
{
cout<<«The list is empty\n»;
return;
}
point*p=beg;
while(p) //пока не конец списка
{
cout<<p->key<<«\t»;
p=p->next; //перейти на следующий
}
cout<<«\n»;
}
point* del_point(point*beg, int k)
{
point *p=beg;
if(k==0) //удалить первый элемент
{
beg=beg->next; /*переставить начало списка на следующий элемент*/
if(beg==0)return 0; /*если в списке только один элемент*/
beg->pred=0; /*обнулить адрес предыдущего элемента */
delete p; //удалить первый
return beg; //вернуть начало списка
}
//если удаляется элемент из середины списка
for(int i=0;i<k-1&&p!=0;i++,p=p->next); /*пройти по списку либо до элемента с предыдущим номером, либо до конца списка*/
if(p==0||p->next==0)return beg; //если в списке нет элемента с номером k
point*r=p->next; //встать на удаляемый элемент
p->next=r->next; //изменить ссылку
delete r; //удалить r
r=p->next; //встать на следующий
if(r!=0)r->pred=p; /*если r существует, то связать элементы*/
return beg; //вернуть начало списка
}
point* add_point(point *beg,int k)
{
point *p;
p=new(point); /*создать новый элемент и заполнить ключевое поле*/
cout<<«key-?»;cin>>p->key;
if(k==0) //если добавляется первый элемент
{
p->next=beg; //добавить перед beg
p->pred=0; //обнулить адрес предыдущего
beg->pred=p; //связать список с добавленным элементом
beg=p; //запомнить первый элемент в beg
return beg; //вернуть начало списка
}
point*r=beg; //встать на начало списка
for(int i=0;i<k-1&&r->next!=0;i++,r=r->next); /*пройти по списку либо до конца списка, либо до элемента с номером k-1*/
p->next=r->next; //связать р с концом списка
if (r->next!=0) r->next->pred=p; /*если элемент не последний, то связать конец списка с р*/
p->pred=r; //связать р и r
r->next=p;
return beg; //вернуть начало списка
}
void main()
{
point*beg;
int i,k;
do
{
cout<<«1.Make list\n»;
cout<<«2.Print list\n»;
cout<<«3.Add point\n»;
cout<<«4.Del point\n»;
cout<<«5.Exit\n»;
cin>>i;
switch(i)
{
case 1:
{beg=make_list();break;}
case 2:
{print_list(beg);break;}
case 3:
{
cout<<«\nk-?»;cin>>k;
beg=add_point(beg,k);
break;
}
case 4:
{
cout<<«\nk-?»;cin>>k;
beg=del_point(beg,k);
break;
}
}
}
while(i!=5);
}
4.11. Ввод-вывод в C++