 Сообщение было отмечено Hasa как решение
Решение
Ну односвязанный список можно и на массиве реализовать. Принцип тот же - каждый элемент хранит адрес следующего элемента. Только элементы будут расположены не в динамической памяти, а в статической - в статическом массиве. В этом случае адресовать элементы можно или по индексу массива или по адресу ячеек памяти - через указатели. Если адресовать элементы через индекс массива, то указатели здесь не потребуются. Но если задачу надо решать именно через указатели, тогда могу предложить следующий код. Список реализован на статическом массиве, выполняется создание списка (значения элементов вводит пользователь), а затем из него удаляются элементы с чётными значениями.
| Pascal | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
| program Project1;
const
{Размер массива - это наибольшее количество элементов, которое может содержать список.}
M = 10;
type
{Тип основных данных элемента списка.}
TData = Integer;
{Указатель на элемент списка.}
TPElem = ^TElem;
{Элемент списка.}
TElem = record
Data : TData; {Основные данные элемента.}
PNext : TPElem; {Указатель на следующий элемент.}
end;
{Массив элементов - хранилище элементов списка.}
TArr = array[1..M] of TElem;
{Тип, описывающий список и хранилище элементов.}
TDList = record
Arr : TArr; {Массив - хранилище элементов списка.}
PFirst, PLast : TPElem; {Указатели на первый и на последний элементы списка.}
end;
{Процедуры для работы со списком.}
{Инициализация списка и хранилища данных.}
procedure Init(var aL : TDList);
var
i : Integer;
begin
aL.PFirst := nil;
aL.PLast := nil;
for i := Low(aL.Arr) to High(aL.Arr) do
aL.Arr[i].PNext := nil;
end;
{Добавление элемента в конец списка. Если в хранилище есть свободное место,
то в конец списка добавляется новый элемент и функция возвращает значение True.
Если свободного места нет, то операция отменяется и функция возвращает значение False.}
function Add(var aL : TDList; const aData : TData) : Boolean;
var
PElem : TPElem;
i : Integer;
begin
Add := False;
{Поиск свободного элемента (это элемент в массиве, который не принадлежит списку).
Признак свободного элемента:
указатель на следующий элемент является пустым (aL.Arr[i].PNext = nil) и при этом
адрес элемента не совпадает с адресом последнего элемента списка (aL.PLast <> @aL.Arr[i]).}
PElem := nil;
for i := Low(aL.Arr) to High(aL.Arr) do
if (aL.Arr[i].PNext = nil) and (aL.PLast <> @aL.Arr[i]) then
begin
PElem := @aL.Arr[i]; {Или так: PElem := Addr(aL.Arr[i]);}
Break;
end;
{Если свободных элементов нет, то выходим.}
if PElem = nil then
Exit;
{Если найден свободный элемент, то инициализируем его и добавляем в список.}
{Записываем данные.}
PElem^.Data := aData;
{Так как этот элемент будет последним в списке, то указатель на следующий
элемент делаем равным NIL.}
PElem^.PNext := nil;
{Если список пуст, то новый элемент станет первым элементом списка.}
if aL.PFirst = nil then
aL.PFirst := PElem
{Если список непустой, то новый элемент прикрепляем к последнему элементу списка.}
else
aL.PLast^.PNext := PElem;
{Новый элемент становится последним элементом списка.}
aL.PLast := PElem;
Add := True;
end;
{Распечатка списка.}
procedure LWriteln(const aL : TDList);
var
PElem : TPElem;
begin
PElem := aL.PFirst; {Указатель на первый элемент списка.}
while PElem <> nil do
begin
{Если это не первый элемент, то в распечатке ставим перед ним запятую.}
if PElem <> aL.PFirst then
Write(', ');
Write(PElem^.Data); {Распечатываем данные текущего элемента.}
PElem := PElem^.PNext; {Получаем указатель на следующий элемент.}
end;
if aL.PFirst = nil then
Writeln('Список пуст.')
else
Writeln;
end;
var
L : TDList;
Data : TData;
PElem, PPrev, PDel : TPElem;
i, Code : Integer;
S : String;
begin
{Инициализация списка и хранилища.}
Init(L);
repeat
{Диалог добавления элементов в список.}
Writeln('Задайте элементы списка.');
Writeln('Для прекращения ввода оставьте пустую строку и нажмите Enter.');
i := 1;
repeat
Write('Элемент №', i, ': ');
Readln(S);
if S <> '' then
begin
Val(S, Data, Code);
if Code = 0 then {Если число задано правильно.}
begin
{Попытка добавить элемент в список.}
if Add(L, Data) then
Inc(i) {Номер следующего элемента.}
else
begin
Writeln('Нет свободного места в хранилище! Дальнейшее добавление элементов в список - невозможно.');
S := '';
end;
end
else {Если число задано неверно.}
Writeln('Неверный ввод! Должно быть введено целое число. Повторите.');
end;
until S = '';
Writeln('Задан список: ');
LWriteln(L);
{Удаление из списка элементов с чётными значениями.}
PPrev := nil; {Указатель на предыдущий элемент.}
PElem := L.PFirst; {Указатель на текущий элемент.}
while PElem <> nil do
if PElem^.Data mod 2 = 0 then {Если элемент содержит чётное значение, то удаляем этот элемент.}
begin
if PElem = L.PFirst then {Если удаляемый элемент является первым элементом списка.}
L.PFirst := PElem^.PNext
else {Если удаляемый элемент НЕ является первым элементом списка.}
PPrev^.PNext := PElem^.PNext;
if PElem = L.PLast then {Если удаляемый элемент является последним элементом списка.}
L.PLast := PPrev;
PDel := PElem;
PElem := PElem^.PNext;
PDel^.PNext := nil;
end
else {Если элемент содержит нечётное значение, то переходим к следующему элементу.}
begin
PPrev := PElem;
PElem := PElem^.PNext;
end;
Writeln('Список после удаления элементов с чётными значениями:');
LWriteln(L);
{Инициализация списка и хранилища.}
Init(L);
Writeln('Повторить - Enter, выход - любой символ + Enter.');
Readln(S);
until S <> '';
end. |
|
Эта же задача, но реализация без указателей - только через индексы массива.
| Pascal | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
| program Project1;
const
{Размер массива - это наибольшее количество элементов, которое может содержать список.}
M = 10;
type
{Тип основных данных элемента списка.}
TData = Integer;
{Элемент списка.}
TElem = record
Data : TData; {Основные данные элемента.}
NNext : Integer; {Индекс следующего элемента.}
end;
{Массив элементов - хранилище элементов списка.}
TArr = array[1..M] of TElem;
{Тип, описывающий список и хранилище элементов.}
TDList = record
Arr : TArr; {Массив - хранилище элементов списка.}
NFirst, NLast : Integer; {Индексы первого и последнего элементов списка.}
end;
const
{Недействительный индекс массива - это индекс за пределами диапазона индексации массива.}
NNull = Low(TArr) - 1;
{Процедуры для работы со списком.}
{Инициализация списка и хранилища данных.}
procedure Init(var aL : TDList);
var
i : Integer;
begin
aL.NFirst := NNull;
aL.NLast := NNull;
for i := Low(aL.Arr) to High(aL.Arr) do
aL.Arr[i].NNext := NNull;
end;
{Добавление элемента в конец списка. Если в хранилище есть свободное место,
то в конец списка добавляется новый элемент и функция возвращает значение True.
Если свободного места нет, то операция отменяется и функция возвращает значение False.}
function Add(var aL : TDList; const aData : TData) : Boolean;
var
i, N : Integer;
begin
Add := False;
{Поиск свободного элемента (это элемент в массиве, который не принадлежит списку).
Признак свободного элемента:
индекс следующего элемента является недействительным (aL.Arr[i].NNext = NNull) и при этом
индекс элемента не совпадает с индексом последнего элемента списка (aL.NLast <> i).}
N := NNull;
for i := Low(aL.Arr) to High(aL.Arr) do
if (aL.Arr[i].NNext = NNull) and (aL.NLast <> i) then
begin
N := i;
Break;
end;
{Если свободных элементов нет, то выходим.}
if N = NNull then
Exit;
{Если найден свободный элемент, то инициализируем его и добавляем в список.}
{Записываем данные.}
aL.Arr[N].Data := aData;
{Так как этот элемент будет последним в списке, то индекс следующего
элемента делаем равным NNull.}
aL.Arr[N].NNext := NNull;
{Если список пуст, то новый элемент станет первым элементом списка.}
if aL.NFirst = NNull then
aL.NFirst := N
{Если список непустой, то новый элемент прикрепляем к последнему элементу списка.}
else
aL.Arr[aL.NLast].NNext := N;
{Новый элемент становится последним элементом списка.}
aL.NLast := N;
Add := True;
end;
{Распечатка списка.}
procedure LWriteln(const aL : TDList);
var
N : Integer;
begin
N := aL.NFirst; {Индекс первого элемента списка.}
while N <> NNull do
begin
{Если это не первый элемент, то в распечатке ставим перед ним запятую.}
if N <> aL.NFirst then
Write(', ');
Write(aL.Arr[N].Data); {Распечатываем данные текущего элемента.}
N := aL.Arr[N].NNext; {Получаем индекс следующего элемента.}
end;
if aL.NFirst = NNull then
Writeln('Список пуст.')
else
Writeln;
end;
var
L : TDList;
Data : TData;
N, NPrev, NDel : Integer;
i, Code : Integer;
S : String;
begin
{Инициализация списка и хранилища.}
Init(L);
repeat
{Диалог добавления элементов в список.}
Writeln('Задайте элементы списка.');
Writeln('Для прекращения ввода оставьте пустую строку и нажмите Enter.');
i := 1;
repeat
Write('Элемент №', i, ': ');
Readln(S);
if S <> '' then
begin
Val(S, Data, Code);
if Code = 0 then {Если число задано правильно.}
begin
{Попытка добавить элемент в список.}
if Add(L, Data) then
Inc(i) {Номер следующего элемента.}
else
begin
Writeln('Нет свободного места в хранилище! Дальнейшее добавление элементов в список - невозможно.');
S := '';
end;
end
else {Если число задано неверно.}
Writeln('Неверный ввод! Должно быть введено целое число. Повторите.');
end;
until S = '';
Writeln('Задан список: ');
LWriteln(L);
{Удаление из списка элементов с чётными значениями.}
NPrev := NNull; {Индекс предыдущего элемента.}
N := L.NFirst; {Индекс текущего элемента.}
while N <> NNull do
if L.Arr[N].Data mod 2 = 0 then {Если элемент содержит чётное значение, то удаляем этот элемент.}
begin
if N = L.NFirst then {Если удаляемый элемент является первым элементом списка.}
L.NFirst := L.Arr[N].NNext
else {Если удаляемый элемент НЕ является первым элементом списка.}
L.Arr[NPrev].NNext := L.Arr[N].NNext;
if N = L.NLast then {Если удаляемый элемент является последним элементом списка.}
L.NLast := NPrev;
NDel := N;
N := L.Arr[N].NNext;
L.Arr[NDel].NNext := NNull;
end
else {Если элемент содержит нечётное значение, то переходим к следующему элементу.}
begin
NPrev := N;
N := L.Arr[N].NNext;
end;
Writeln('Список после удаления элементов с чётными значениями:');
LWriteln(L);
{Инициализация списка и хранилища.}
Init(L);
Writeln('Повторить - Enter, выход - любой символ + Enter.');
Readln(S);
until S <> '';
end. |
|
1
|
А про то, как реализовать односвязанный список в статике, нигде ничего не сказано.
(
Сообщение было отмечено Hasa как решение
