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