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

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

Динамические структуры данных, к которым относятся односвяные и двусвязные списки, традиционно излагаются в теме "Указатели". С другой стороны, в языке 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;

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

Новости

29.08.16. Вышла версия 3.2. Реализован оператор yield.

12.02.16. Вышла версия 3.1. Добавлены кортежи в стиле (a,b) и кортежное присваивание (a,b) := (b,a)

31.12.15. Версия 3.0.0.1128. Реализованы обобщенные методы расширения для операций

22.12.15. Версия 3.0.0.1116. Реализован новый синтаксис extension-методов

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

// Функция определения простоты числа
// Уровень сложности: 1

function IsPrime(N: integer): boolean;
begin
  Result := True;
  if N<2 then
    Result := False
  else
    for var i:=2 to round(sqrt(N)) do
      if N mod i = 0 then
      begin
        Result := False;
        exit;
      end;
end;

begin
  for var i:=2 to 20 do
    Println(i,IsPrime(i));
end.