Динамические структуры данных, к которым относятся односвяные и двусвязные списки, традиционно излагаются в теме "Указатели". С другой стороны, в языке PascalABC.NET переменные класса являются ссылками на объекты, выделяемыми в динамической памяти, и являются по-существу скрытыми указателями. Поэтому заманчиво рассказать основные операции со списками, используя ссылки вместо указателей. Остроты ощущений добавляет тот факт, что в PascalABC.NET для объектов производится автоматическая сборка мусора, поэтому освобождаемую память не надо возвращать явно.
Рассмотрим основные операции с линейными односвязными списками и приведем реализацию для указателей (слева) и ссылок (справа). Всюду считается, что переменная p имеет тип PNode для указателей и Node для ссылок.
1. Предварительные описания.
type PNode = ^Node; Node = record data: integer; next: PNode; end; function NewNode(data: integer; next: PNode): PNode; begin New(Result); Result^.data := data; Result^.next := next; end; |
type Node = class data: integer; next: Node; constructor (d: integer; n: Node); begin data := d; next := n; end; end;
|
Реализация с указателями - явно более "многословная". К тому же функция NewNode является внешней, и связь ее с типом PNode определяется только близостью к нему в тексте программы.
2. Вставка элемента со значением x в начало списка, на который указывает p.
p := NewNode(x,p); |
p := new Node(x,p); |
Почти одинаково. Во втором случае вызывается конструктор класса Node, возвращающий ссылку на созданный объект.
3. Удаление элемента из начала непустого списка, на который указывает p.
var t := p; p := t^.next; Dispose(t); |
p := p.next; |
Здесь на компактности записи решения со ссылками сказывается сборка мусора - на первый элемент больше никто не указывает, поэтому память, им занимаемая, будет освобождена при следующей сборке мусора.
4. Вставка элемента со значением x после текущего, на который указывает p.
p^.next := NewNode(x,p^.next); |
p.next := new Node(x,p.next); |
Одно и то же. Только ^ не надо ставить - красота! Ссылка - это разыменованный указатель. Шапочки вовсе не нужны!
5. Удаление элемента, следующего за текущим, на который указывает p.
var t := p^.next; if t<>nil then begin p^.next := t^.next; Dispose(t); end; |
if p.next<>nil then p.next := p.next.next; |
В указатель на следующий записать адрес элемента, следующего за следующим. Опять-таки, во втором случае на удаляемый узел никто больше не указывает, поэтому память под него будет освобождена при следующей сборке мусора.
6. Вставка элемента со значением x перед текущим, на который указывает p.
p^.next := NewNode(p^.data,p^.next); p^.data := x; p := p^.next; |
p.next := new Node(p.data,p.next); p.data := x; p := p.next; |
Трюк. Вставляем после текущего элемента его копию, после чего меняем в текущем элементе значение на x. Решения равноценны.
7. Удаление текущего элемента, на который указывает p.
var t := p^.next; p^:= t^; Dispose(t); |
p.data := p.next.data; p.next := p.next.next; |
Элемент, следующий за текущим, должен существовать. В случае указателей мы можем скопировать оба поля за одно присваивание: p^:= t^. Но и это не помогает - код со ссылками все равно короче!
8. Вывод списка, на первый элемент которого указывает p.
while p<>nil do begin write(p^.data,' '); p := p^.next; end; |
while p<>nil do begin write(p.data,' '); p := p.next; end; |
Равноценные решения.
9. Поиск элемента со значением x. На первый элемент списка указывает p.
while (p<>nil) and (p^.data<>x) do p := p^.next; var found := p<>nil; |
while (p<>nil) and (p.data<>x) do p := p.next; var found := p<>nil; |
Равноценные решения. Шапочек справа - нет
10. Разрушение списка.
while p<>nil do begin var t := p; p := p^.next; Dispose(t); end; |
p := nil; |
Вот здесь - все преимущества сборки мусора. Присвоил указателю на первый узел списка нулевое значение - и все узлы стали недоступны. При следующей сборке мусора они будут собраны.
01.02.24. На ресурсе Stepik в ознакомительном режиме открыт курс "PascalАВС.NЕТ: продвинутый уровень".
10.07.23. Вышел релиз версии PascalABC.NET 3.9.0. Нововведения описаны здесь.
20.05.23. На странице https://pascalabc.net/stepikcourse опубликованы новые курсы по PascalABC.NET от центра олимпиадного программирования DL Club.
08.05.23. Вышла версия PascalABC.NET 3.9.0.beta. Основное - ковариантные параметры обобщений, аргументы по умолчанию при вызове подпрограммы, модуль автоматической проверки LightPT.
22.02.23. Открыта регистрация на конференцию «Использование системы программирования PascalABC.NET в обучении программированию»