Создание двунаправленного списка

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

struct point {

char *key;//адресное поле – динамическая строка

point *next;//указатель на следующий элемент

point *pred;//указатель на предыдущий элемент

};

point* make_point(){

//создание одного элемента

point*p=new(point);

p->next=0;p->pred=0;//обнуляем указатели

char s[50];

cout<<"\nEnter string:";

cin>>s;

p->key=new char[strlen(s)+1];

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

strcpy(p->key,s);

return p;

}

point*make_list(int n) {

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

point *p,*beg;

beg=make_point();//создаем первый элемент

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

p=make_point();//создаем один элемент

//добавление элемента в начало списка

p->next=beg;//связываем р с первым элементом

beg->pred=p;//связываем первый элемент с p

beg=p;// p становится первым элементом списка

}

return beg;

}

Фрагменты программ, выполняющих различные действия с двусвязным списком:

void exam1(list2 *p) {

/*Просмотр циклического (возможно пустого) списка без

заглавного звена*/

list2 *ph; //в направлении от начала к концу списка

if ( p = = NULL ) return;

ph = p;

do { . . .

p = p -> next; }

while ( p != ph );

//Просмотр продолжается пока текущий указатель

// p не равен указателю на начало списка - ph

}

. . .

void exam2( list2 *p) {

/*Просмотр циклического (возможно пустого) списка с за

главным звеном*/

list2 *pr; //в направлении от конца списка к началу

if ( p –> next = = p ) return;

pr = p -> pred; /*Текущий указатель pr получил значение

ссылки на последний элемент списка*/

while (pr != p)

/*Просмотр продолжается пока текущий указатель pr не

равен указателю на заглавное звено списка – p*/

{ . . . pr = pr -> pred; }

. . .

x = new list2;

/*Включение нового элемента (в список с заглавным

звеном) перед элементом, на который ссылается p*/

x -> pred = p -> pred;

x -> next = p;

p -> pred -> next = x;

p -> pred = x;

. . .

p -> pred -> next = p -> next;

/*Исключение из списка с заглавным звеном элемента, на

который ссылается указатель p*/

p -> next -> pred = p -> pred;

delete p;

}