Основы программирования — второй семестр 08-09; Михалкович С.С.; IIб часть — различия между версиями

type
  Node<DataType> = class
    data: DataType;
    next: Node<DataType>;
    
    constructor (d: DataType; n: Node<DataType>);
    begin
      data := d;
      next := n;
    end;
  end;

begin
  var p := new Node<char>('!', nil);  // под объект класса Node<char> выделилась динамическая память;
                                      // p начала указывать на эту динамическую память
end.

/// <summary>
/// Узел односвязного линейного списка
/// </summary>
type SNode<T> = class
public // <- для печати write

  /// Поле данных
  data: T;

  /// Поле связи со следующим узлом
  next: SNode<T>;
  
  /// <summary>
  /// Инициализирует новый экземпляр узла односвязного списка
  /// со значением dt поля данных и ссылкой next на следующий узел
  /// </summary>
  /// <param name="dt">Значение поля данных узла</param>
  /// <param name="next">Сслыка на следующий узел. По умолчанию: nil</param>
  constructor(dt: T; next: SNode<T> := nil);
  begin
    data := dt;
    self.next := next;
  end;
end;

/// Умный конструктор типа SNode: вывод типа и экономия на слове new
function MkSnode<T>(dt: T; next: SNode<T> := nil) := new SNode<T>(dt, next);

var f: file of integer;
Assign(f, 'numbers.dat');
Reset(f);

var a: integer;
Read(f, a);
var head := new Node<integer>(a, nil);

var cur := head;
while not Eof(f) do
begin
  read(f, a);
  cur.next := new Node<integer>(a, nil);
  cur := cur.next;
end;

Close(f);

// x — искомый символ
var cur := head;
while (cur <> nil) and (cur.data <> x) do
  cur := cur.next;

if cur = nil then
  // не найдено
else
  // cur — ссылка на искомый x

type
  Node<T> = class
    data: T;
    prev, next: Node<T>;
    
    constructor (d: T;  p, n: Node<T>);
    begin
      data := d;
      prev := p;
      next := n;
    end;
  end;

first := nil;
last := nil;

type
  Node<T> = class
    data: T;
    prev, next: Node<T>;
    
    constructor (d: T;  p, n: Node<T>);
    begin
      data := d;
      prev := p;
      next := n;
    end;
  end;

  DoubleLinkedList<T> = class
    first, last: Node<T>;
    
    constructor;
    begin
      first := nil;
      last := nil;
    end;

    procedure AddFirst(d: T);
    begin
      first := new Node<T>(d, nil, first);
      if first.next <> nil then
        first.next.prev := first
      else  // если список был пуст
        last := first;
    end;
    procedure AddLast(d: T);
    begin
      last := new Node<T>(d, last, nil);
      if last.prev <> nil then
        last.prev.next := last
      else  // если список был пуст
        first := last;
    end;

    procedure DeleteFirst;
    begin
      first := first.next;
      if first = nil then
        last := nil
      else  
        first.prev := nil;
    end;
    procedure DeleteLast;
    begin
      last := last.prev;
      if last = nil then
        first := nil
      else
        last.next := nil;
    end;

    procedure InsertBefore(cur: Node<T>; d: T);
    begin
      if cur = first then
        AddFirst(d)
      else
      begin
        cur.prev := new Node<T>(d, cur.prev, cur);
        cur.prev.prev.next := cur.prev;
      end;
    end;
    procedure InsertAfter(cur: Node<T>; d: T);
    begin
      if cur = last then
        AddLast(d)  
      else
      begin
        cur.next := new Node<T>(d, cur, cur.next);
        cur.next.next.prev := cur.next;
      end;
    end;

    function RemoveAt(cur: Node<T>): Node<T>;
    begin
      if cur = first then
        begin
          DeleteFirst;
          Result:=first;
        end       
      else if cur = last then
        begin
          DeleteLast;
          Result:=nil;
        end
      else if cur = last then
      begin
        DeleteLast;
        result := nil;
      end
      else
      begin
        cur.prev.next := cur.next;
        cur.next.prev := cur.prev;
        result := cur.next;
      end;
    end;

    procedure Print;
    begin
      var cur := first;
      while cur <> nil do
      begin
        writeln(cur.data);
        cur := cur.next;
      end;
    end;
    procedure PrintReverse;
    begin
      var cur := last;
      while cur <> nil do
      begin
        writeln(cur.data);
        cur := cur.prev;
      end;
    end;
  end;

var list: DoublyLinkedList<integer>;
// создание списка

var cur := list.first;
while cur <> nil do
  if cur.data < 0 then
    cur := list.RemoveAt(cur)
  else
    cur := cur.next;