Связные списки - новый стиль

Просмотров: 38477

Динамические структуры данных, к которым относятся односвяные и двусвязные списки, традиционно излагаются в теме "Указатели". С другой стороны, в языке 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;
 
  1. while p<>nil do
  2. begin
  3. write(p.data,' ');
  4. p := p.next;
  5. 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;

Вот здесь - все преимущества сборки мусора. Присвоил указателю на первый узел списка нулевое значение - и все узлы стали недоступны. При следующей сборке мусора они будут собраны.

Новости

05.05.20. Выпущена версия PascalABC.NET 3.6.3. Основное - срезы на запись и конструкция ^i для обращения к элементам по индексу с конца. Список остальных изменений - здесь.

09.04.2020. Бонус! В связи с переходом школ на дистанционное обучение выкладываем в открытый доступ книгу Осипова А.В. "PascalABC.NET: выбор школьника. Часть 1".

22.02.2020. Вышла версия 3.6.2. Основные изменения - здесь.

07.10.19. Выложена полная версия книги Осипова А.В. «PascalABC.NET: введение в современное программирование».

13.07.19. Опубликована презентация Новые возможности PascalABC.NET 3.5 (2015-2019 гг).

Случайная программа

// Создание случайного идеально сбалансированного 
// бинарного дерева и его инфиксный обход
// Уровень сложности: 2

type
  Node<T> = auto class
    data: T;
    left, right: Node<T>;
  end;

function CreateTree(n: integer): Node<integer>;
begin
  if n <= 0 then
    Result := nil
  else
    Result := new Node<integer>(
      Random(100),
      CreateTree((n-1) div 2),
      CreateTree(n-1 - (n-1) div 2));
end;

procedure InfixPrintTree<T>(r: Node<T>);
begin
  if r = nil then
    exit;
  InfixPrintTree(r.left);
  Print(r.data);
  InfixPrintTree(r.right);
end;

const N = 20;

begin
  var root := CreateTree(N);
  InfixPrintTree(root);
end.