cursor.c

weis的数据结构的实现方法很经典很强大

        #include "cursor.h"
        #include <stdlib.h>
        #include "fatal.h"

        /* 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;
        }

        static void
        CursorFree( Position P )
        {
            CursorSpace[ P ].Next = CursorSpace[ 0 ].Next;
            CursorSpace[ 0 ].Next = P;
        }
/* END */

        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*/      return P;
        }
/* 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*/      return P;
        }

/* 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 */


        /* Correct DeleteList algorithm */

        void
        DeleteList( List L )
        {
            Position P, Tmp;

/* 1*/      P = CursorSpace[ L ].Next;  /* Header assumed */
/* 2*/      CursorSpace[ L ].Next = 0;
/* 3*/      while( P != 0 )
            {
/* 4*/          Tmp = CursorSpace[ P ].Next;
/* 5*/          CursorFree( P );
/* 6*/          P = Tmp;
            }
        }

        Position
        Header( List L )
        {
            return L;
        }

        Position
        First( List L )
        {
            return CursorSpace[ L ].Next;
        }

        Position
        Advance( Position P )
        {
            return CursorSpace[ P ].Next;
        }

        ElementType
        Retrieve( Position P )
        {
            return CursorSpace[ P ].Element;
        }