linkedlist.pm

PERL语言资料 可以用于PERL程序设计

# Fig. 20.6: LinkedList.pm
# Object-oriented linked-list implementation.

use warnings;
use strict;

package ListNode;    # start package ListNode 

# ListNode constructor 
sub new 
{
   my $type = shift();
   my $class = ref( $type ) || $type;
   my $self = { data => $_[ 0 ], nextLink => $_[ 1 ] };
                
   bless( $self, $class );
   return $self;
}

package LinkedList;  # start package LinkedList 

# LinkedList constructor 
sub new 
{
   my $type = shift();
   my $class = ref( $type ) || $type;
   my $self = { head => undef };
   
   bless( $self, $class );
   return $self;
}

# function to insert a new node in the list in ascending order
sub insertNode 
{
   my ( $self, $data ) = @_;
   
   my $previous = undef;
   my $current = $self->head();
   
   # This loop determines the nodes between which the new
   # node will be inserted. When this loop completes, variable
   # $previous references the node before the one being 
   # inserted and $current references the node after the one 
   # being inserted.
   while ( defined( $current ) && $data gt $current->{ data } ) {
      $previous = $current;
      $current = $current->{ nextLink };
   }

   # if $previous is still undefined, we are inserting
   # at the head of the list.
   unless ( defined( $previous ) ) { 
      $self->{ head } = new ListNode( $data, $current );
   }
   else { 
      $previous->{ nextLink } = new ListNode( $data, $current );
   }
}

# function to remove a node from the list
sub deleteNode 
{
   my ( $self, $data ) = @_;
   
   my $previous = undef;
   my $current = $self->head();
   
   # This loop locates the node to delete. When this loop 
   # completes, variable $previous references the node before 
   # the one being deleted and $current references the node 
   # being deleted.
   while ( defined( $current ) && $data ne $current->{ data } ) {
      $previous = $current;
      $current = $current->{ nextLink };
   }
   
   # if we found the element in the list,
   # we delete it and return 1   
   if ( defined( $current ) ) { 

      unless ( defined( $previous ) ) {  
         $self->{ head } = $self->{ head }{ nextLink };
      }
      else {
         $previous->{ nextLink } = $current->{ nextLink };
      }

      return 1;  # element was deleted
   }
   else {
      return 0;  # element was not deleted
   }
}

# function that returns the head reference for the list
sub head 
{  
   return $_[ 0 ]->{ head };
}

# function that traverses the list and outputs each element
sub printList 
{
   my $self = shift();
   
   if ( !defined( $self->head() ) ) {
      print( "List is empty.\n\n" );
      return;
   }  

   print( "The list is:\n" );
   my $current = $self->{ head };

   while ( defined( $current ) ) {
      print( $current->{ data } );       # print current data
      $current = $current->{ nextLink }; # move to next node
         
      if ( defined( $current ) ) {       # if next node exists,
         print( " --> " );               # output -->
      }
   }

   print( "\n" );
}

return 1;

###########################################################################
#  (C) Copyright 2001 by Deitel & Associates, Inc. and Prentice Hall.     #
#  All Rights Reserved.                                                   #
#                                                                         #
#  DISCLAIMER: The authors and publisher of this book have used their     #
#  best efforts in preparing the book. These efforts include the          #
#  development, research, and testing of the theories and programs        #
#  to determine their effectiveness. The authors and publisher make       #
#  no warranty of any kind, expressed or implied, with regard to these    #
#  programs or to the documentation contained in these books. The authors #
#  and publisher shall not be liable in any event for incidental or       #
#  consequential damages in connection with, or arising out of, the       #
#  furnishing, performance, or use of these programs.                     #
###########################################################################