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

1. Цепной односвязный список (стек, магазин)

Стек (от англ. stack — стопка) — структура
данных,
представляющая
из
себя
упорядоченный набор элементов, в которой
добавление новых элементов и удаление
существующих производится с одного
конца, называемого вершиной стека.
Притом первым из стека удаляется элемент,
который был помещен туда последним, то
есть в стеке реализуется стратегия
«последним вошел — первым вышел» (lastin, first-out — LIFO). Извлеченный элемент
для стека утрачивается навсегда.
1

2.

Цепной односвязный список
Структура стека
1
2
3
p
2

3. Создание цепного односвязного списка type link=^item; item=record v:link; g:integer; end; var 1 p, b:link; 2 i:integer; 3 begin

4 b:=nil;
5 for i:=1 to 5 do begin
6 new(p);
7 p^.g:=i;
8 p^.v:=b;
9 b:=p
10 end;
3

4.

var
1 p, b:link;
2 i:integer;
3 begin
b – вспомогательная переменная
p
b
4

5.

var
1 p, b:link;
2 i:integer;
3 begin
4 b:=nil;
b – вспомогательная переменная
p
b
.
5

6.

5 for i:=1 to 5 do begin
6
new(p);
для i=1
p^
p
b
.
6

7.

5 for i:=1 to 5 do begin
6
new(p);
7
p^.g:=i;
для i=1
p^
p^.v
p
1
b
.
p^.g
7

8.

для i=1
8 p^.v:=b;
p^
p
.
1
b
.
p^.v
p^.g
8

9.

для i=1
9
b:=p;
p^
p
.
1
p^.v
b^.v
p^.g
b^.g
b
9

10.

для i=2
6 new(p);
7 p^.g:=i;
b^
p
.
1
p^
p^.v
b^.v
2
p^.g
b^.g
b
10

11.

для i=2
8
p
p^.v:=b;
.
1
p^
p^.v
2
p^.g
b^
b
11

12.

для i=2
9
b:=p;
p
b
.
1
p^
2
b^
12

13.

для i=5
p
b
p^
.
1
2
3
4
5
b^
13

14. Просмотр цепного односвязного списка

14

15. Просмотр цепного односвязного списка 11 for i:=1 to 5 do begin 12 memo1.lines.add(inttostr(p^.g)); 13 p:=p^.v 14 end;

15

16.

для i=1
11 for i:=1 to 5 do begin
12 memo1.lines.add(inttostr(p^.g));
13 p:=p^.v
p
b
.
1
p^.v
2
3
4
5
p^
b^
16

17.

12
13
для i=1
memo1.lines.add(inttostr(p^.g));
p:=p^.v
p
b
.
1
p^.v
2
3
4
p^
5
b^
17

18.

12
13
для i=2
memo1.lines.add(inttostr(p^.g));
p:=p^.v
p
b
.
1
p^.v
2
3
4
p^
5
b^
18

19.

12
13
для i=2
memo1.lines.add(inttostr(p^.g));
p:=p^.v
p
.
b
1
p^.v
2
3
p^
4
5
b^
19

20.

12
13
для i=3
memo1.lines.add(inttostr(p^.g));
p:=p^.v
p
.
b
1
p^.v
2
3
p^
4
5
b^
20

21.

12
13
для i=3
memo1.lines.add(inttostr(p^.g));
p:=p^.v
p
.
b
1
p^.v
2
p^
3
4
5
b^
21

22.

12
13
для i=4
memo1.lines.add(inttostr(p^.g));
p:=p^.v
p
.
b
1
p^.v
2
p^
3
4
5
b^
22

23.

12
13
для i=4
memo1.lines.add(inttostr(p^.g));
p:=p^.v
p
.
p^.v
b
1
p^
2
3
4
5
b^
23

24.

12
13
для i=5
memo1.lines.add(inttostr(p^.g));
p:=p^.v
p
.
p^.v
b
1
p^
2
3
4
5
b^
24

25.

для i=5
12 memo1.lines.add(inttostr(p^.g));
13 p:=p^.v
p указывает на nil – при просмотре список
разрушается
p
b
.
.
1
2
3
4
5
b^
25

26. Просмотр цепного односвязного списка 11 while p<>nil do begin 12 memo1.lines.add(inttostr(p^.g)); 13 p:=p^.v 14 end; Так как

Просмотр цепного
односвязного списка
11 while p<>nil do begin
12 memo1.lines.add(inttostr(p^.g));
13 p:=p^.v
14 end;
Так как при просмотре список разрушается, рекомендуется (если этот
список нужен в дальнейшем) ДО НАЧАЛА ПРОСМОТРА ввести
дополнительную переменную, указывающую на начало списка.
26

27.

Просмотр цепного
односвязного списка c оставлением одного элемента
11 while p^.v<>nil do begin
12 memo1.lines.add(inttostr(p^.g));
13 p:=p^.v
14 end;
p
.
p^.v
b
1
p^
2
3
4
5
b^
27