链表的游标实现

    如果需要链表而又不使用指针，就会用到游标实现。
    链表的指针实现有两条重要特性：

数据存储在一组结构体中。每一个结构体中。每一个结构体包含数据以及指向下一个结构体的指针。一个新的结构体可以用通过调用 malloc 而从系统全局内存中得到，并可通过调用 free 释放。

    游标法必须能够模仿实现这两条特性。

满足条件一的逻辑方法是要有一个全局的结构体数组。对于该数组中的任何单元，其数组下标可以用来代表一个地址。
对于条件二，让数组中的单元代行 malloc 和 free 的职能。为此，我们保留一个表，这个表由不在任何表中的单元构成。该表将用单元 0 作为表头。

链表游标实现的声明：

#ifndef _Cursor_H

typedef int PtrToNode;
typedef PtrTonode List;
typedef PtrTonode Position;

void InitializeCursorSpace( void );

List MakeEmpty( List L );
int IsEmpty( const List L );
int IsLast( const Position P, const List L );
Position Find( int X, const List L );
void Delete( int X, List L );
Position FindPrevious( int X, List L, Position P );
void Insert( int X, List L, Position P );
void DeleteList( List L );
Position Header( const List L );
Position First( const List L );
Position Advance( const Position P );
int Retrieve( const Position P );

#endif
#define SpaceSize ( 5 )

struct Node
{
    int Element;
    Position Next;
};

struct Node CursorSpace[ SpaceSize ];

例程：

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

测试链表是否为空：

int IsEmpty( List L )
{
    return CursorSpace[ L ].Next == 0;
}

测试P是否为链表末尾的函数：

int IsLast( Position P, List L )
{
    return CursorSpace[ P ].Next == 0;
}

Find：

Position Find( int X, List L )
{
    Position P;
    P = CursorSpace[ L ].Next;
    while (P && CursorSpace[ P ].Element != X )
    {
        P = CursorSpace[ P ].Next;
    };
    return P;
}

对链表进行删除操作的例程：

void Delete( int X, List L )
{
    Position P, TmpCell;
    P = FindPrevious( X, L,P );
    if (!IsLast( P, L ) )
    {
        TmpCell = CursorSpace[ P ].Next;
        CursorSpace[ P ].Next = CursorSpace[ TmpCell ].Next;
        CursorFree( TmpCell );
    }
}

对链表进行插入操作的例程：

void Insert( int X, List L, Position P )
{
    Position TmpCell;
    TmpCell = CursorAlloc();
    if ( TmpCell == 0)
    {
        FatalError( "Out of space!!!" );
    }
    CursorSpace[ TmpCell ].Element = X;
    CursorSpace[ TmpCell ].Next = CursorSpace[ P ].Next;
    CursorSpace[ P ].Next = TmpCell;    
}