Помощь - Поиск - Пользователи - Календарь
Полная версия: Двусвязный список в виде класса
Форум «Всё о Паскале» > Delphi, Assembler и другие языки. > Delphi
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
Ничего особенного делать не надо, разницы, что именно хранить, целые числа или ссылки на объект класса, никакой нет. Только не надейся, что все будет вот так вот безоблачно smile.gif Во-первых, проблема будет с выводом данных (печать через 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;



, не сделать вышеописанное в деструкторе - утечка, когда работаем с классами. Что делать думаешь? Какие есть мысли по преодолению проблемы? smile.gif
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)...
Lapp
[offtop]Володь, давно подпись сменил? Я только заметил )). Класс! good.gif

Рекомендую аватар вырезать из фото 22 yes2.gif
[/offtop]
Rei-li
Скажите, пожалуйста, надо писать именно T = TSomeClass;? Компилятор не пропускает
Вроде объявляют как-то типа TSomeClass<T>=class(TObject) или это не о том?
IUnknown
Цитата
Вроде объявляют как-то типа TSomeClass<T>=class(TObject)
Это дженерики. Тебе что, надо реализацию именно на дженериках? А версия Дельфи у тебя какая? 2009 или выше потребуется для Generic Classes.

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

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

[offtop mode]
Цитата
Володь, давно подпись сменил? Я только заметил )). Класс!
Спасибо. Нет, недавно, она появилась-то в доме всего месяц назад... Скоро еще добавлю фотографий. yes2.gif
Цитата
Рекомендую аватар вырезать из фото 22
Не, это чересчур будет smile.gif У меня, правда, бывает такое же выражение лица, когда я читаю некоторые вопросы, но не всегда же lol.gif

[/offtop mode]
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/
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.