Односвязный список

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

Ключевое понятие списка – голова – указатель на первый элемент списка

(обычно обозначается HEAD). В некоторых задачах используется также

указатель на последний элемент списка – LAST.

ОПИСАНИЕ ЭЛЕМЕНТОВ СПИСКА НА ЯЗЫКЕ ПАСКАЛЬ

TYPE LIST =^ NODE; {тип указателя на элементы списка} NODE = RECORD DATA: INTEGER; NEXT: LIST END; {тип элементов списка: данное – integer и next - указатель на следующий элемент} VAR HEAD: LIST; {голова - указатель на первый элемент списка} LAST: LIST; {хвост - указатель на последний элемент списка}

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

ПРОЦЕДУРА СОЗДАНИЯ СПИСКА

PROCEDURE NEWLIST (VAR HEAD: LIST); {создает новый пустой список} BEGIN HEAD:= NIL; END;

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

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

ПРОЦЕДУРА ДОБАВЛЕНИЯ ЭЛЕМЕНТА В ГОЛОВУ СПИСКА

PROCEDURE ADDHEADLIST(VAR HEAD: LIST; X: INTEGER); VAR P: LIST; {указатель на новый элемент} BEGIN NEW(P); {резервируем в куче память для нового элемента} P^.DATA:=X; {заносим значение поля data – число x } P^.NEXT:=HEAD; {следующим в списке будет тот элемент, который сейчас находится в голове; заносим его адрес в next } HEAD:=P {теперь головой становится новый элемент} END;

ФУНКЦИЯ ВЫЧИСЛЕНИЯ СУММЫ ЭЛЕМЕНТОВ СПИСКА

FUNCTION SUM(HEAD: LIST):INTEGER; VAR P: LIST; {указатель-счетчик} S:INTEGER; {накопитель суммы} BEGIN S:=0; {начальное значение суммы - 0} P:=HEAD; {начальное значение счетчика - голова} WHILE P<>NIL DO {пока не конец списка} BEGIN S:=S+P^.DATA; {добавляем содержимое элемента списка к сумме} P:=P^.NEXT {переход к следующему элементу списка} END; SUM:=S; END;

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

VAR X:INTEGER; BEGIN NEWLIST(HEAD); {создаем новый пустой список} WRITE('NEW='); READLN(X); {вводим элемент для добавления в список} WHILE (X<>0) DO {пока не введен ноль} BEGIN ADDHEADLIST(HEAD,X); {добавляем введенное значение в список} WRITE('NEW='); READLN(X) {вводим элемент для добавления в список} END; PRINTLIST(HEAD); {распечатаем построенный список} WRITELN(SUM(HEAD)); {выведем сумму элементов построенного списка} END.