Программирование на языке C


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


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

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

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.




Начало  Назад  Вперед



Книжный магазин