Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
ДВУХСВЯЗНЫЙ СПИСОК (КОЛЬЦО)
- модель представления знаний, представляющая собой набор записей (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, т.е. в конец списка, при этом упорядоченность не нарушается.
ПРИМЕР ПРОГРАММЫ, РАБОТАЮЩЕЙ С КОЛЬЦОМ
Дата публикования: 2015-02-22; Прочитано: 464 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!