Двухсвязные списки и кольца

ДВУХСВЯЗНЫЙ СПИСОК (КОЛЬЦО)

- модель представления знаний, представляющая собой набор записей (RECORD), каждая из которых содержит ссылки (указатели) на последующий и предыдущий элементы той же структуры. Такая организация структуры обеспечивает возможность просмотра списка в двух направлениях.

Голова – начало списка чаще является не указателем, а «фиктивной» записью, которая содержит в качестве полей ссылку на первый и на последний элементы

ОПИСАНИЕ НА ЯЗЫКЕ ПАСКАЛЬ

TYPE RING =^ NODE; {тип указателя на элементы кольца}   NODE = RECORD DATA: INTEGER; AFT, PRE: RING END; {тип элементов кольца: данное – integer,aft - указатель на следующий элемент, pre – на предыдущий} VAR HEAD: RING; {голова - указатель на первый (фиктивный) элемент кольца}

Таким образом, определено кольцо из целых чисел.

ПРОЦЕДУРА СОЗДАНИЯ ПУСТОГО КОЛЬЦА

PROCEDURE NEWRING (VAR HEAD: RING); {создает новое кольцо – фикивную запись} BEGIN NEW(HEAD); HEAD^.AFT:=HEAD; HEAD^.PRE:=HEAD; END;

Таким образом, пустое кольцо представляет собой «закольцованную» саму на себя фиктивную запись HEAD.

ПРОЦЕДУРА ВЫВОДА ЭЛЕМЕНТОВ КОЛЬЦА НА ЭКРАН

PROCEDURE PRINTRING(HEAD:RING); VAR P: RING; {указатель-счетчик} BEGIN P:=HEAD^.AFT; {начальное значение счетчика – элемент, следующий за головой} WHILE P<>HEAD DO {пока не конец списка, т.е. счетчик, двигаясь по кругу не наткнулся на head} BEGIN WRITE(P^.DATA:6); {вывод содержимого элемента кольца} P:=P^.AFT {переход к следующему элементу кольца} END; WRITELN; END;

ФУНКЦИЯ ДОБАВЛЕНИЯ ЭЛЕМЕНТА В УПОРЯДОЧЕННОЕ КОЛЬЦО

FUNCTION INSERTRING(VAR HEAD: RING; X: INTEGER): RING; VAR P,PP:RING; {указатель на новый эл-т и счетчик-указатель} BEGIN PP:=HEAD^.AFT; WHILE (PP^.DATA<X) AND (PP<>HEAD) DO PP:=PP^.AFT; {продвигаемся по списку пока не достигнем конца или не найдем элемент со значением, большим x } NEW(P); {резервируем в куче память для нового элемента} P^.DATA:=X; {заносим значение поля data – число x } P^.AFT:=PP; {следующий за новым – тот, перед которым вставляем} P^.PRE:=PP^.PRE; {предыдущий у нового – тот, который перед вставляем} PP^.PRE^.AFT:=P; {эл-т перед pp должен ссылаться на p как на след. эл-т} PP^.PRE:=P; {предыдущий у pp – новый} INSERTRING:=P {результат – ссылка на новый эл-т} END;

Выше реализована функция добавления перед элементом, который ищется как превосходящий по значению вставляемый элемент. Если больший элемент не найден, то автоматически элемент вставляется перед HEAD, т.е. в конец списка, при этом упорядоченность не нарушается.

ПРИМЕР ПРОГРАММЫ, РАБОТАЮЩЕЙ С КОЛЬЦОМ

VARPP: POINTER; X: INTEGER; {укзатель и целое число} BEGIN MARK(PP); {запомнить начало кучи} NEWRING(HEAD); {создать пустое кольцо} WRITE('NNEW='); READLN(X); {ввести первое число} WHILE (X<>0) DO {построение кольца продолжается до ввода 0} BEGIN INSERTRING(HEAD,X); {добавить новый эл-т в упорядоченное кольцо} WRITE('NNEW='); READLN(X) {ввод очередного значения} END; PRINTRING(HEAD); {распечатать кольцо} RELEASE(PP) {очистить кучу от запомненной позиции до конца} END.