В прямом односвязном линейном списке связь устанавливается от i-го элемента к i+1.
i i+1 i+2
| 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^.next<>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
2015-05-14
309
