Создание прямого односвязного списка

В прямом односвязном линейном списке связь устанавливается от i-го элемента к i+1.

Inf

Link

Inf

Link

Inf

Link

Inf

Link

Inf

Link

Inf

Link

i i+1 i+2

Inf

Link

Inf

Link

Inf

Link

Inf

Link

Inf

Link

Inf

Link

Inf

Link

Inf

Link

Inf

Link

Inf

Link

Inf

Link

Inf

Link

Inf

Link

Inf

Link

Inf

Link

Inf

Link

Inf

Link

Inf

Link

 

 

Program spisok; Type tt=^elem; Elem=record Inf:char; //информационное поле Next:tt //указательное поле End; Var p,begl,endl:tt; //объявление указателей Value:char; I,n:integer;   Begin writeln('введите n'); readln(n); Begl:=nil; //начальные установки Endl:=nil; // пустого адреса For i:=1 to n do Begin New(p); //выделение динамической памяти Readln(value); P^.inf:=value; //занесение данных в информационное поле P^.next:=nil; //занесение пустого адреса в указательное поле If endl=nil then begl:=p //если создается 1^ый элемент списка Else endl^.next:=p; //если создается очередной элемент списка Endl:=p End; P:=begl; //установка р на начало списка While p<>nil do // nil-конец списка Begin Write(p^.inf, ' '); P:=p^.next //перемещение указателя р на следующий элемент списка End; End.

Результат решения задачи:   введите n п о л е п о л е

 

В список можно добавлять элементы и удалять из списка.

 

	Действие	Последовательность операторов
	Поиск элемента с заданным значением	P:=begl; While (p<>nil) and (p^.inf<>задан.значение) do p:=p^.next;
	Добавление элемента в начало списка	New(p); P^.inf:=значение; P^.next:= begl; Begl:=p;
	Перемещение указателя на элемент с адресом k	P:=begl; While p <>k do p:=p^.next;
	Добавление элемента в середину списка после k-ым	New(p); P^.inf:=значение; P^.next:=k^.next; k^.next:=p;
	Вставка элемента в середину списка перед k-ым	// вставка после k-го элемента New(p); P^.inf:=значение; P^.next:=k^.next; k^.next:=p;   // перестановка информационных полей k ßàp t:=k^.inf; k^.inf:= P^.inf; p^.inf:=t;
	Удаление элемента из начала списка	P:=begl; Begl:= P^.next; Dispose(p);
	Удаление элемента из конца списка	P:=begl; While p<>endl do //перемещение р на предпоследний элемент p:=p^.next; Dispose(endl); Endl:=p; Endl^.next:=nil;
	Удаление элемента после k -го	p:=k^.next; k^.next:= P^.next; Dispose(p);
	a) Удаление k–го элемента	p:=k^.next; k^.inf:= p^.inf; k^.next:= p^.next; Dispose(p);
б) Удаление k–го элемента	P:=begl; //установка p перед k While p^.next<>k do p:=p^.next; P^.next:= k^.next; Dispose(k);

 

Пример1: Создать односвязный линейный список, содержащий числа.

Сложить положительные элементы списка.

 

 

 

Program Spisok11;

{создать односвязный линейный список, содержащий числа.

Сложить положительные элементы списка.}

Uses Crt;

Type aa =^spisok;

spisok = record

zn:integer;

next:aa;

end;

Var

s,p:aa;

i,zna,kol, sum:integer;

// процедура добавление элемента в список

Procedure AddSp;

var q:aa;

Begin

if s=nil then //создается первый элемент

Begin

New(p);

s:=p

End

Else begin

q:=p;

New(p);

q^.next:=p;

end;

p^.next:=nil;

Writeln('Введите значение',i,' элемента');

readln(zna);

p^.zn:=zna;

end;

// функция определения конца списка

Function GoNext:boolean;

Begin

if p^.next <> nil then

Begin

p:=p^.next;

GoNext:=true;

End

else GoNext:=false

end;

//функция освобождения памяти и вывода элементов списка

Function DisposeAll:boolean;

var q:aa;

Begin

p:=s;

while p<>nil do

Begin

q:=p^.next;

write(p^.zn,' ');

Dispose(p);

p:=q;

end;

writeln;

writeln('Освобождение памяти...');

DisposeAll:=true;

end;

 

begin //операторы основной программы

 

s:=nil; // nil- признак конца списка

writeln('Введите количество элементов списка');

readln(kol);

for i:=1 to kol do //создание списка

Addsp;

 

p:=s; //установка р на начало списка

Repeat

if p^.zn>0 then

sum:=sum+p^.zn; //суммируем положительные элементы

until not gonext;

 

if sum=0 then writeln('в списке нет полож. элементов')

else writeln('sum=',sum);

DisposeAll;

End.

 

Результаты решения задачи:

 

Введите количество элементов списка

Введите значение1 элемента

Введите значение2 элемента

Введите значение3 элемента

Введите значение4 элемента

-56

sum=8

3 5 0 -56

Освобождение памяти...

 

Методические указания по методике отладки программ в интегрированной среде PascalABC