Board index » delphi » Link List , use recursive routine to reverse print the node of the list

Link List , use recursive routine to reverse print the node of the list

Hi all programmer,

I wish to know how to Display a dynamic link lists from its last node to
the first node, using ** recursive function **.

Assume:
type
       Ptr = ^node
       Node = Record
           Element : Integer;
           Next : Ptr;
       End;
var
       Head : Ptr;

Thanks for any one helps me. urgent !!!

 

Re:Link List , use recursive routine to reverse print the node of the list


Quote
> I wish to know how to Display a dynamic link lists from its last node
> to the first node, using ** recursive function **.

> Assume:
> type   Ptr = ^node
>        Node = Record
>            Element : Integer;
>            Next : Ptr;
>        End;
> var    Head : Ptr;

   With this structure, you can't.  To do so, you must have a
doubly-linked list (2 pointers in each node: Next and Prior) to "walk
backwards".  With a singly-linked list such as this, you can only "walk
forward" from the root.  With a different structure (the added Prior
pointer), you should see how the list can be traversed backwards...

Re:Link List , use recursive routine to reverse print the node of the list


Quote
Mike Copeland wrote:

.> > I wish to know how to Display a dynamic link lists from its last
node
.> > to the first node, using ** recursive function **.
.> >
.> > Assume:
.> > type   Ptr = ^node
.> >        Node = Record
.> >            Element : Integer;
.> >            Next : Ptr;
.> >        End;
.> > var    Head : Ptr;
.>
.>    With this structure, you can't.  To do so, you must have a
.> doubly-linked list (2 pointers in each node: Next and Prior) to "walk
.> backwards".  With a singly-linked list such as this, you can only
"walk
.> forward" from the root.  With a different structure (the added Prior
.> pointer), you should see how the list can be traversed backwards...

     I disagree.  It can be done, as stated.

Bob Schor
Pascal Enthusiast

Re:Link List , use recursive routine to reverse print the node of the list


Quote
In article <335F5CC2.4...@primenet.com>, Mike Copeland <mrc...@primenet.com> writes:

|> > I wish to know how to Display a dynamic link lists from its last node
|> > to the first node, using ** recursive function **.
|> >
|> > Assume:
|> > type   Ptr = ^node
|> >        Node = Record
|> >            Element : Integer;
|> >            Next : Ptr;
|> >        End;
|> > var    Head : Ptr;
|>
|>    With this structure, you can't.  To do so, you must have a
|> doubly-linked list (2 pointers in each node: Next and Prior) to "walk
|> backwards".  With a singly-linked list such as this, you can only "walk
|> forward" from the root.  With a different structure (the added Prior
|> pointer), you should see how the list can be traversed backwards...

Are you sure ?

I have never tried it, but to me the key lies in the recursive part.

Something like this should do it:

procedure reverse_print(entry : Ptr);
begin
   if (entry <> NIL)
   begin
      if (entry^.Next <> NIL) reverse_print(entry^.Next);
      writeln(i);
   end;
end;

 -Mike

Re:Link List , use recursive routine to reverse print the node of the list


Quote
Bob Schor <bsc...@vms.cis.pitt.edu> writes: > Mike Copeland wrote:

> .> > I wish to know how to Display a dynamic link lists from its last
> node
> .> > to the first node, using ** recursive function **.
> .> >
> .> > Assume:
> .> > type   Ptr = ^node
> .> >        Node = Record
> .> >            Element : Integer;
> .> >            Next : Ptr;
> .> >        End;
> .> > var    Head : Ptr;
> .>
> .>    With this structure, you can't.  To do so, you must have a
> .> doubly-linked list (2 pointers in each node: Next and Prior) to "walk
> .> backwards".  With a singly-linked list such as this, you can only
> "walk
> .> forward" from the root.  With a different structure (the added Prior
> .> pointer), you should see how the list can be traversed backwards...

>      I disagree.  It can be done, as stated.

> Bob Schor
> Pascal Enthusiast

I agree with Bob. For every node the element of the Next pointer should be printed before
its own element. Take a look at the next source code. It includes the revesreprint and the
normal print as well.

type   Ptr = ^node
       Node = Record
         Element : Integer;
         Next    : Ptr;
       End;
var    Head : Ptr;

Procedure ReversePrint(P : Ptr);
Begin
  If P^.Next <> Nil Then
    ReversePrint(P^.Next);
  WriteLn(P^.Element);
End;

Procedure NormalPrint(P : Ptr);
Begin
  WriteLn(P^.Element);
  If P^.Next <> Nil Then
    NormalPrint(P^.Next);
End;

Begin
  .... Initialize the linked list
  ReversePrint(Head);
  NormalPrint(Head);
End.

Christiaan Heidema

Other Threads