3.2.8 Cursor Implementation of Linked Lists

来源:百度文库 编辑:神马文学网 时间:2024/03/29 13:39:28

Many languages, such as BASIC and FORTRAN, do notsupportpointers.

The two importantitems present in a pointer implementation of linked lists are

1. The data is storedin a collection of structures. Each structure contains the data and apointerto the next structure.

2. A new structure canbe obtained from the system's global memory by a call to mallocandreleased by a call to free.

A value of 0 for next istheequivalent of a pointer.

 

********************************************************************

/* START: fig3_28.txt */

       #ifndef _Cursor_H

        #define _Cursor_H

 

       typedef int PtrToNode;

       typedef PtrToNode List;

       typedef PtrToNode Position;

 

        voidInitializeCursorSpace( void );

 

        ListMakeEmpty( List L );

        intIsEmpty( const List L );

        intIsLast( const Position P, const List L );

       Position Find( ElementType X, const List L );

        voidDelete( ElementType X, List L );

       Position FindPrevious( ElementType X, const List L );

        voidInsert( ElementType X, List L, Position P );

        voidDeleteList( List L );

       Position Header( const List L );

       Position First( const List L );

       Position Advance( const Position P );

       ElementType Retrieve( const Position P );

 

        #endif    /* _Cursor_H*/

 

/* END*/

********************************************************************

        /*Place in the interface file */

        struct Node

        {

           ElementType Element;

           Position    Next;

        };

 

       struct Node CursorSpace[ SpaceSize ];

********************************************************************

/* START: fig3_31.txt */

       static Position

        CursorAlloc( void )

        {

           Position P;

 

           P = CursorSpace[ 0 ].Next;

           CursorSpace[ 0 ].Next = CursorSpace[ P ].Next;

 

           return P;

        }

 

        staticvoid

        CursorFree( Position P )

        {

           CursorSpace[ P ].Next = CursorSpace[ 0 ].Next;

           CursorSpace[0 ].Next = P;

        }

/* END */

********************************************************************

If the value of L is 5 and thevalue of Mis 3, then L represents the list a,b,e, and M represents the list c,d,f.

********************************************************************

        void

        InitializeCursorSpace(void )

        {

           int i;

 

           for( i = 0; i < SpaceSize; i++ )

               CursorSpace[ i ].Next = i + 1;

           CursorSpace[ SpaceSize - 1 ].Next = 0;

        }

********************************************************************

        List

        MakeEmpty( List L )

        {

           if( L != NULL )

               DeleteList( L );

           L = CursorAlloc( );

           if( L == 0 )

               FatalError( "Out of memory!" );

           CursorSpace[ L ].Next = 0;

           return L;

       }

********************************************************************

/* START: fig3_32.txt */

        /*Return true if L is empty */

 

        int

        IsEmpty( List L )

        {

           return CursorSpace[ L ].Next == 0;

        }

/* END */

********************************************************************

/* START: fig3_33.txt */

        /*Return true if P is the last position in list L */

        /*Parameter L is unused in this implementation */

 

        int

IsLast( Position P, List L )

        {

           return CursorSpace[ P ].Next == 0;

        }

/* END*/

********************************************************************

/* START: fig3_34.txt */

        /*Return Position of X in L; 0 if not found */

        /*Uses a header node */

 

       Position

        Find( ElementType X, List L )

        {

           Position P;

 

/* 1*/      P= CursorSpace[L ].Next;

/* 2*/      while(P&& CursorSpace[ P ].Element != X )

/* 3*/         P = CursorSpace[ P ].Next;

 

/*4*/      returnP;

        }

/* END */

********************************************************************

/* START: fig3_35.txt */

        /*Delete from a list */

        /*Assume that the position is legal */

        /*Assume use of a header node */

 

        void

        Delete( ElementType X, List L )

        {

           Position P, TmpCell;

 

           P = FindPrevious( X, L );

 

           if( !IsLast( P, L ) )  /* Assumption of header use */

           {                     /* X is found; delete it */

               TmpCell = CursorSpace[ P ].Next;

               CursorSpace[ P ].Next = CursorSpace[ TmpCell ].Next;

               CursorFree(TmpCell );

           }

        }

/* END */

********************************************************************

        /*If X is not found, then Next field of returned value is 0 */

        /*Assumes a header */

 

        Position

        FindPrevious( ElementType X, List L )

        {

           Position P;

 

/* 1*/      P= L;

/* 2*/      while(CursorSpace[P ].Next &&

                   CursorSpace[ CursorSpace[ P ].Next ].Element != X )

/*3*/         P = CursorSpace[ P ].Next;

 

/*4*/      returnP;

        }

 

********************************************************************

/* START: fig3_36.txt */

        /*Insert (after legal position P) */

        /*Header implementation assumed */

        /*Parameter L is unused in this implementation */

 

        void

        Insert( ElementType X, List L, Position P )

        {

           Position TmpCell;

 

/* 1*/      TmpCell =CursorAlloc( );

/* 2*/      if(TmpCell == 0)

/* 3*/         FatalError( "Out of space!!!" );

 

/* 4*/      CursorSpace[TmpCell].Element = X;

/* 5*/      CursorSpace[TmpCell].Next = CursorSpace[ P ].Next;

/* 6*/      CursorSpace[P].Next = TmpCell;

        }

/* END */

********************************************************************