Работа с двунаправленным списком

Рис. 6 Двунаправленный список

Пример 3.

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

#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);

}