Организация двусвязных списков
Связанное хранение линейного списка называется списком с двумя связями или двусвязным
списком, если каждый элемент хранения имеет два компонента указателя (ссылки на
предыдущий и последующий элементы линейного списка).
В программе двусвязный список можно реализовать с помощью описаний:
typedef struct ndd
{ float val; /* значение элемента */
struct ndd * n; /* указатель на следующий элемент */
struct ndd * m; /* указатель на предыдующий элемент*/
} NDD;
NDD * dl, * p, * r;
Графическая интерпретация метода связанного хранения списка F=<2,5,7,1> как списка с
двумя связями приведена на рис.20.
Вставка нового узла со значением 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 - на последний элемент списка.
Схема циклического хранение списка F=<2,5,7,1> приведена на рис.21.
При решении конкретных задач могут возникать разные виды связанного хранения.
Пусть на входе задана последовательность целых чисел B1,B2,...,Bn из интервала от 1 до
9999, и пусть Fi (1 по возрастанию. Составить процедуру для формирования 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);
}