Двусвязный список в виде класса Опции

[Rei-li]

Здравствуйте.
Проверьте, пожалуйста, правильно ли выполнено задание:
Реализуйте заданную структуру данных (двусвязный список целых чисел) в виде класса (набора классов).
Не используйте стандартные классы .NET для представления коллекций ( разрешается использование только массивов).

program Project2;

{$APPTYPE CONSOLE}

uses
  SysUtils;

type
  PList = ^TList;
  TList = record
    inf  : integer;
    prior: PList;
    next : PList
  end;

  TListDual = object
  private
    pfirst, plast : PList;
  public
    constructor Init;
    destructor RemoveList;
    procedure Print_forward;
    procedure Print_back;
    procedure Insert( NewInf : integer);
  end;

constructor TListDual.Init; {инициализация списка }
begin
  pfirst := nil; plast := nil;
end;


destructor TListDual.RemoveList; {уничтожение списка}
var
  q: Plist;
begin
  if pfirst = nil then writeln('List not init')
  else
  begin
    while pfirst <> nil do
    begin
      q := pfirst;
      pfirst := pfirst^.next;
      dispose(q);
    end;
  end;
  plast := nil;
end;

procedure TListDual.Print_forward; { процедура печати элементов с первого(начало) }
var start : PList;
begin
  if pfirst = nil then writeln('List not init')
  else
  begin
    start := pfirst;
    while (start <> nil) do
    begin
      write(start^.inf, ' ');
      start := start^.next;
    end;
    WriteLn;
  end;
end;

procedure TListDual.Print_back; { процедура печати элементов с последнего(начало) }
var last : PList;
begin
  if plast = nil then writeln('List not init')
  else
  begin
    last := plast;
    while (last <> nil) do
    begin
      write(last^.inf, ' ');
      last := last^.prior;
    end;
    WriteLn;
  end;
end;


procedure TListDual.Insert( NewInf : integer); {процедура вставки элементов в конец списка(информационная часть) }
var
  p : PList;
begin
  new(p);
  p^.inf := NewInf;
  p^.next := nil;
  if (pfirst=nil) and (plast=nil) {если пустой список} then
  begin
    pfirst := p;
    pfirst^.prior := nil;
  end
  else {список не пуст, добавляем элемент в конец и корректируем указатели}
  begin
    plast^.next := p;
    p^.prior := plast;
  end;
  plast := p;
end;

begin
  { TODO -oUser -cConsole Main : Insert code here }
end.

[IUnknown]

Здесь:

procedure TListDual.Insert( NewInf : integer); {процедура вставки элементов в конец списка(информационная часть) }
var
  p : PList;
begin
  new(p);
  p^.inf := NewInf;
  p^.next := nil;
  if (pfirst=nil) and (plast=nil) {если пустой список} then
  begin
    pfirst := p;
    pfirst^.prior := nil;
  end
  else {список не пуст, добавляем элемент в конец и корректируем указатели}
  begin
    plast^.next := p;
    p^.prior := plast;
  end;
  plast := p;
end;

все делается проще:

procedure TListDual.Insert( NewInf : integer); 
var p : PList;
begin
   new(p);
   p^.inf := NewInf;
   p^.next := nil;
   p^.prior := plast;

   if (pfirst=nil) {если пустой список}
      then pfirst := p
   else {список не пуст, добавляем элемент в конец }
      plast^.next := p;

   plast := p;
end;

Остальное вроде нормально, напиши тестовую программу и проверь, работает ли, нет ли утечек, не вылетает ли где...

[Rei-li]

Спасибо. В том то и дело, что оно работает, но меня смущает формулировка вопроса, что надо реализовать список в виде класса

[IUnknown]

Значит, сделай так:

program Project2;
{$APPTYPE CONSOLE}
uses
   SysUtils;

type
   TList = class
      inf  : integer;
      prior: TList;
      next : TList;

      constructor Create(AInf : Integer;
                         APrev, ANext : TList);
   end;

   TListDual = class
   private
      pfirst, plast : TList;
   public
      constructor Create;
      destructor Destroy; override;

      procedure Print_forward;
      procedure Print_back;
      procedure Insert(NewInf : integer);

      function IsEmpty : Boolean;
   end;

constructor TList.Create(AInf : Integer;
                         APrev, ANext : TList);
begin
   Inf := AInf;
   Prior := APrev; Next := ANext;
end;

constructor TListDual.Create;
begin
   pfirst := nil; plast := nil;
end;

function TListDual.IsEmpty : Boolean;
begin
   Result := (pFirst = nil);
end;

destructor TListDual.Destroy;
var q : Tlist;
begin
   if IsEmpty then writeln('List not init')
   else
   begin
      while not IsEmpty do
      begin
         q := pfirst;
         pfirst := pfirst.next;
         q.Free;
    end;
  end;
  plast := nil;
  inherited;
end;

procedure TListDual.Print_forward;
var start : TList;
begin
   if IsEmpty then writeln('List not init')
   else
   begin
      start := pfirst;
      while (start <> nil) do
      begin
         write(start.inf, ' ');
         start := start.next;
      end;
      WriteLn;
   end;
end;

procedure TListDual.Print_back;
var last : TList;
begin
   if IsEmpty then writeln('List not init')
   else
   begin
      last := plast;
      while (last <> nil) do
      begin
         write(last.inf, ' ');
         last := last.prior;
      end;
      WriteLn;
   end;
end;

procedure TListDual.Insert( NewInf : integer);
var p : TList;
begin
   P := TList.Create(NewInf, PLast, nil);
   if IsEmpty then
      pfirst := P
   else
      plast.next := p;

   plast := P;
end;

var
   L : TListDual;
   i : Integer;
begin
  L := TListDual.Create;
  for i := 1 to 10 do
  begin
     L.Insert(i);
  end;
  L.Print_Back;
  L.Print_Forward;
  L.Free;
end.

- будет тебе в виде набора классов. Проверял в FPC, вроде работает, утечек не дает... Что непонятно в реализации - спрашивай.

Сообщение отредактировано: IUnknown - 20.09.2011 23:14

[Гость]

Огромное спасибо !!!
Буду разбираться. Может еще подскажете: в другом задании надо написать обобщенную реализацию для этого двусвязного списка, позволяющую хранить объекты (ссылочные переменные); Для этого в теле программы просто надо запустить методы,или я что-то неправильно поняла?

[IUnknown]

Ничего особенного делать не надо, разницы, что именно хранить, целые числа или ссылки на объект класса, никакой нет. Только не надейся, что все будет вот так вот безоблачно Во-первых, проблема будет с выводом данных (печать через WriteLn допустима для встроенных типов, но не для объектов, WriteLn просто не умеет печатать объекты). Но это еще не все. Проблема вторая: при уничтожении списка нужно удалять и его содержимое. В случае, который рассмотрен выше (список целых) этого делать не надо, а вот если список будетхранить ссылки на какие-то объекты, то объекты эти надо будет уничтожать, иначе будут утечки. И тут возникает вопрос: а как, собственно, отличить, работает список с Integer-ами (или Boolean-ами, или Double-ами), которые удалять не надо, или с объектами самописных типов, которые удалять-таки нужно? Вот тут, я имею в виду:

type
   T = TSomeClass; // Какой-то тип, потомок TObject, как все классы

   // Класс, хранящий элемент списка, практически не изменяется,
   // разве что добавляется деструктор. В котором и будет проблема
   TList = class 
      inf  : T;
      prior: TList;
      next : TList;

      constructor Create(AInf : T; APrev, ANext : TList);
      destructor Destroy; override;
   end;


constructor TList.Create(AInf : T; APrev, ANext : TList);
begin
   Inf := AInf;
   Prior := APrev; Next := ANext;
end;
destructor TList.Destroy;
begin
   inf.Free; // Попытка сделать это, когда Inf - переменная простого типа - ошибка
end;


   // Создаваться элемент списка может так:
   L := TListDual.Create;
   for i := 1 to 10 do
   begin
      L.Insert( TSomeClass.Create('Object #' + IntToStr(i)) );
  end;

, не сделать вышеописанное в деструкторе - утечка, когда работаем с классами. Что делать думаешь? Какие есть мысли по преодолению проблемы?

[Rei-li]

Я так понимаю, что в проблеме с деструктором дело в ограничениях, но конкретно еще не разобралась (расскажите, пожалуйста, я на правильном пути?)
А по поводу вывода данных пока мыслей нет

[TarasBer]

> Какие есть мысли по преодолению проблемы?

Подключить интерфейсы, чтобы было хоть какое-то автоудаление.

[IUnknown]

(расскажите, пожалуйста, я на правильном пути?)

На самом деле, возможных решений проблемы - 2 (кроме варианта с автоудалением экземпляра класса из памяти).

1) ограничить типы, с которыми сможет работать TListDual (скажем, либо это встроенные типы, либо наоборот, только классы), и уже опираясь на это, ибо ничего не вызывать в деструкторе TList, либо вызывать-таки деструктор хранимого объекта. На самом деле решение очень плохое, какая же тогда это обобщенная реализация, если накладываются такие ограничения.

2) каким-то образом в рантайме проверять, нужно ли вызывать деструктор хранимого объекта, или нет. Вот это уже лучше:

Uses ..., TypInfo;

// ...

destructor TList.Destroy;
begin
   if PTypeInfo(typeInfo(T)).Kind = tkClass then // Класс ? Очищаем ...
   begin
      // Вызов inf.Free компилятор не пропустит,
      // если работаешь со встроенным типом, поэтому используем

      FreeAndNil(inf)
   end;
end;

Ну, а по поводу печати - я бы сделал так: если тебе надо работать с каким-то типом, то позаботься, чтобы для этого типа существовала процедура, печатающее значение.

procedure PrintMe(Obj : твой_тип); overload;
begin
   // тут выводишь каким-то образом значение
end;

// Cкажем, для Integer-ов:
procedure PrintMe(Obj : Integer); overload;
begin
   write(Obj, ' ');
end;
// Для любых классов - может быть так:
procedure PrintMe(Obj : TObject); overload;
begin
   write(Obj.ToString, ' ');
   // Пускай класс сам разбирается, как выводить информацию
   // Обычно для этого как раз перегружается метод ToString()
end;

А все вызовы write(inf) внутри TListDual - заменить на вызовы PrintMe(inf)...

Сообщение отредактировано: IUnknown - 21.09.2011 10:44

[Lapp]

[offtop]Володь, давно подпись сменил? Я только заметил )). Класс!

Рекомендую аватар вырезать из фото 22 [/offtop]

[Rei-li]

Скажите, пожалуйста, надо писать именно T = TSomeClass;? Компилятор не пропускает
Вроде объявляют как-то типа TSomeClass<T>=class(TObject) или это не о том?

Сообщение отредактировано: Rei-li - 21.09.2011 16:39

[IUnknown]

Вроде объявляют как-то типа TSomeClass<T>=class(TObject)

Это дженерики. Тебе что, надо реализацию именно на дженериках? А версия Дельфи у тебя какая? 2009 или выше потребуется для Generic Classes.

Как-то вот так (Показать/Скрыть)

program Project1;

{$APPTYPE CONSOLE}
uses
   SysUtils, TypInfo;

type
   // Этим классом будем тестировать список
   TObj = class
      value : String;

      constructor Create(AValue : String);
      destructor Destroy; override;

      function ToString : string; override;
   end;

constructor TObj.Create(AValue : String);
begin
   Value := AValue;
end;

destructor TObj.Destroy;
begin
   Inherited;
end;

function TObj.ToString;
begin
   Result := Value;
end;

// А это, собственно, и будут 2 обобщенных класса, реализующих список
type
   TPrintProcedure<T> = reference to procedure(const Value: T);
   TList<T> = class
      inf : T;
      prior : TList<T>;
      next : TList<T>;

      constructor Create(AInf : T; APrev, ANext : TList<T>);
      destructor Destroy; override;
   end;

   TListDual<T> = class
   private
      pfirst, plast : TList<T>;
      PrintItem : TPrintProcedure<T>;

   public
      // Зададим процедуру печати отдельного айтема
      // прямо при инициализации списка ...
      constructor Create(const APrintItem : TPrintProcedure<T>);
      destructor Destroy; override;

      procedure Print_forward;
      procedure Print_back;

      procedure Insert(NewInf : T);

      function IsEmpty : Boolean;
   end;


constructor TList<T>.Create(AInf : T; APrev, ANext : TList<T>);
begin
   Inf := AInf;
   Prior := APrev; Next := ANext;
end;
destructor TList<T>.Destroy;
begin
   if PTypeInfo(typeInfo(T)).Kind = tkClass then
   begin
      FreeAndNil(inf)
   end;
end;

constructor TListDual<T>.Create(const APrintItem : TPrintProcedure<T>);
begin
   pfirst := nil; plast := nil;
   PrintItem := APrintItem;
end;

function TListDual<T>.IsEmpty : Boolean;
begin
   Result := (pFirst = nil);
end;

destructor TListDual<T>.Destroy;
var q : Tlist<T>;
begin
   if IsEmpty then writeln('<list is empty>')
   else
   begin
      while not IsEmpty do
      begin
         q := pfirst;
         pfirst := pfirst.next;
         q.Free;
      end;
   end;
   plast := nil;
   inherited;
end;

procedure TListDual<T>.Print_forward;
var start : TList<T>;
begin
   if IsEmpty then writeln('<list is empty>')
   else
   begin
      start := pfirst;
      while (start <> nil) do
      begin
         PrintItem(start.inf);
         start := start.next;
      end;
      WriteLn;
   end;
end;

procedure TListDual<T>.Print_back;
var last : TList<T>;
begin
   if IsEmpty then writeln('<list is empty>')
   else
   begin
      last := plast;
      while (last <> nil) do
      begin
         PrintItem(last.inf);
         last := last.prior;
      end;
      WriteLn;
   end;
end;

procedure TListDual<T>.Insert(NewInf : T);
var p : TList<T>;
begin
   P := TList<T>.Create(NewInf, PLast, nil);
   if IsEmpty then
      pfirst := P
   else
      plast.next := p;

   plast := P;
end;

var
   L : TListDual<Integer>;
   LObj : TListDual<TObj>;
   i : Integer;
begin
   try
      // Сначала тестируем целочисленный список
      L := TListDual<Integer>.Create(
         procedure (const Value : Integer)
         begin
            write(Value, ' ');
         end
      );
      for i := 1 to 10 do
      begin
         L.Insert(i);
      end;
      L.Print_Back;
      L.Print_Forward;
      L.Free;

      // Потом - список TObj-ектов
      LObj := TListDual<TObj>.Create(
         procedure (const Value : TObj)
         begin
            write(Value.ToString, ' ');
         end
      );
      for i := 1 to 10 do
      begin
         LObj.Insert( TObj.Create('String #' + IntToStr(i)) );
      end;
      LObj.Print_Back;
      LObj.Print_Forward;
      LObj.Free;

      ReadLn;
   except
      on E:Exception do
         Writeln(E.Classname, ': ', E.Message);
   end;
end.

Я там немного поменял способ задания процедуры печати, если есть дженерики - значит есть и анонимные процедуры, вот их использование я и показал. Разумеется, проход вперед/назад по списку можно было сделать по-другому, через For .. In, но это еще усложнит код, так что не буду этого делать сейчас. Только, если тебя заинтересует

[offtop mode]

Володь, давно подпись сменил? Я только заметил )). Класс!

Спасибо. Нет, недавно, она появилась-то в доме всего месяц назад... Скоро еще добавлю фотографий.

Рекомендую аватар вырезать из фото 22

Не, это чересчур будет У меня, правда, бывает такое же выражение лица, когда я читаю некоторые вопросы, но не всегда же
[/offtop mode]

Сообщение отредактировано: IUnknown - 21.09.2011 18:01

[Rei-li]

Спасибо, мне именно на дженериках и надо было.
Но объясните, пожалуйста, запись: TPrintProcedure<T> = reference to procedure(const Value: T); или где можно почитать?

[IUnknown]

Вот тут можно почитать об анонимных методах: http://skiminog.livejournal.com/33854.html

[Rei-li]

Спасибо большое, классно написано. Многое стало более понятно

[TarasBer]

Почитал ссылку

> На практике очень часто применяются функции, создающие другие функции в зависимости от параметров. Это экономит время и место, в случае, если результирующая функция готовится к частому использованию.

А на самом деле там действительно создаются функции (т.е. выделяется кусок памяти, в него пишется тело новой функции, кусок помечается выполняемым), или создаются структуры из указателя и внутренних переменных, которые ведут себя как функции, только намного медленнее?

[IUnknown]

Анонимные методы реализуются с помощью интерфейса, имеющего один-единственный метод Invoke, совпадающий по сигнатуре с анонимным.

http://sergworks.wordpress.com/2010/01/27/...-the-internals/