Программирование на языке С
Страница 70. Организация двусвязных списков

2.1.4. Организация двусвязных списков

Связанное хранение линейного списка называется списком с двумя связями или двусвязным списком, если каждый элемент хранения имеет два компонента указателя (ссылки на предыдущий и последующий элементы линейного списка).

В программе двусвязный список можно реализовать с помощью описаний:

 typedef struct ndd
 { float val; /* значение элемента */
 struct ndd * n; /* указатель на следующий элемент */
 struct ndd * m; /* указатель на предыдующий элемент */
 } NDD;
 NDD * dl, * p, * r;

Вставка нового узла со значением new за элементом, определяемым указателем p, осуществляется при помощи операторов:

 r=malloc(NDD);
 r->val=new;
 r->n=p->n;
 (p->n)->m=r;
 p->=r;

Удаление элемента, следующего за узлом, на который указывает p

 p->n=r;
 p->n=(p->n)->n;
 ( (p->n)->n )->m=p;
 free(r);

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

Пусть на входе задана последовательность целых чисел B1,B2,...,Bn из интервала от 1 до 9999, и пусть Fi (1<9999) последовательность, получаемая упорядочиванием элементов списка по возрастанию. Составить процедуру для формирования Fn в связанном хранении и возвращения указателя на его начало.

При решении задачи в каждый момент времени имеем упорядоченный список Fi и при вводе элемента Bi+1 вставляем его в нужное место списка Fi, получая упорядоченный список Fi+1. Здесь возможны три варианта: в списке нет элементов; число вставляется в начало списка; число вставляется в конец списка. Чтобы унифицировать все возможные варианты, начальный список организуем как связанный список из двух элементов <0,1000>.

Рассмотрим программу решения поставленной задачи, в которой указатели dl, r, p, v имеют следующее значение: dl указывает начало списка; p, v - два соседних узла; r фиксирует узел, содержащий очередное введенное значение in.

 #include
 #include
 typedef struct str1
 { float val;
 struct str1 *n; } ND;
 main()
 { ND *arrange(void);
 ND *p;
 p=arrange();
 while(p!=NULL)
 {
 printf("\n %f ",p->val);
 p=p->n;
 }
 }
 ND *arrange() /* формирование упорядоченного списка */
 { ND *dl, *r, *p, *v;
 float in=1;
 char *is;
 dl=malloc(sizeof(ND));
 dl->val=0; /* первый элемент */
 dl->n=r=malloc(sizeof(ND));
 r->val=10000; r->n=NULL; /* последний элемент */
 while(1)
 {
 scanf(" %s",is);
 if(* is=='q') break;
 in=atof(is);
 r=malloc(sizeof(ND));
 r->val=in;
 p=dl;
 v=p->n;
 while(v->valn;
 }
 r->n=v;
 p->n=r;
 }
 return(dl);
 }