Версия для печати темы

Автор: kr3v3tkus 20.12.2006 21:43

оказывается надо сделать на основе двусвязного списка
я описывал вот так:

type
PNode = ^Node;
Node = record
     Info:Char;
     Next:PNode;
end;
TQueue = class
   private
     head,tail:PNode;
   public
     function Empty:Boolean;
     procedure Push (Value:Char);
     procedure Pop (var Value:Char);
     constructor Create;
     destructor Destroy; override;
end;

а надо дописать

     L,R :PNode;

ну, левый и правый указатель

Пожалста объясните зачем в очереди хвосту и голове 2 указателя и помогите с реализацией
получается нам не хватает одного указателя? у меня просто и с одним работало, препода уже месяца нету а завтра зачёт

я вот как реализовывал с одним указателем

procedure TQueue.Push (Value:Char);
var P:PNode;
begin
   new(P);
   p^.info:=value;
   p^.next:=nil;
   if empty then head:=p
   else tail^.next := p;
   tail:=p;
end;

procedure TQueue.Pop (var Value:Char);
var P:PNode;
begin
   if not Empty then
     begin
       value:=head^.info;
       p:=head;
       head:=p^.next;
       if head=nil then tail:=nil;
       dispose(p);
     end;
end;

... а с двумя просто на нил сводил один из них

procedure TQueue.Push (Value:Char);
 var P:PNode;
 begin
   new(P);
   p.info:=value;
   if empty then
     begin
       head:=p;
       p.next:=nil;
     end
   else
     begin
       tail.R := p;
       p.next:=tail;
     end;
   tail:=p;
 end;

procedure TQueue.Pop (var Value:Char);
 var P:PNode;
 begin
   if not Empty then
     begin
       value:=p.info;
       p:=head;
       head:=p.next;
       if head=nil then tail:=nil;
       dispose(p);
     end;
 end;

помогите плз

Автор: volvo 20.12.2006 22:22

Push я бы переделал вот так:

procedure TQueue.Push(Value:Char);
var P:PNode;
begin
  new(P);
  with p^ do begin
    info:=value;
    prev := tail; next := nil;
  end;

  if empty then head := p
  else tail^.next := p;

  tail := p
end;

Pop по-моему, нормально реализовано, во всяком случае, в глаза сразу ничего не бросается...

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

Автор: kr3v3tkus 20.12.2006 22:58

ууу пасибки, дело в том что на самом деле в задании не было написано про список, и реализовав его с 1 указателем я спросил у препода, типа как делать - наподобие стека только с головой и хвостом, а он мне и сказал, мол - да только как двусвязный кароче походу он просто не сам не понял и меня запутал