用游标实现链表

某些语言，像BASIC和FORTRAN不支持指针，如果需要链表但又不能使用指针就必须有另外的实现方法。游标（cursor）可以实现这种功能。链表的指针实现中有2个特点：
1.数据存储在一组结构体中。每个结构体包含有数据以及指向下一个结构体的指针。
2.一个新的机构体可以通过调用malloc从系统全局内存得到，并可调用free释放。

游标必须能模仿实现以上2条特征。满足条件1的逻辑方法可以使用一个全局的结构体数组。对于该数组中的任何单元，其数组下标可以用来代表一个地址。图1给出链表游标实现的声明。

#ifndef _cursor_h
#define _cursor_h

#define SpaceSize 64

typedef int ElementType;
typedef int PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;

void InitializeCursorSpace();
List MakeEmpty(List l);
int IsEmpty(const List l);
int IsLast(const Position P, const List l);
Position Find(ElementType x, const List l);
void Delete(ElementType x, List l);
Position FindPrevious(ElementType x, const List l);
void Insert(ElementType x, List l, Position p);
void DeleteList(List l);

struct Node
{
    ElementType Element;
    Position Next;
};

struct Node CursorSpace[SpaceSize];

图1链表游标实现的声明

现在我们必须模拟条件2，让CusorSpace数组中的单元代替malloc\free的职能。对于Next，0的值等价于NULL指针。CursorSpace的初始化是一个简单的循环操作。图3表示出了malloc和free的游标实现。注意，如果没有可用空间，那么CursorAlloc将返回0，表明没有可用空间。

index	Element	Next
0 1 2 3 4 5		1 2 3 4 5 0

图2 一个初始化的CursorSpace

void InitializeCursorSpace()
{
        int i;
        for (i = 0; i < SpaceSize - 1; i++) {
                CursorSpace[i].Next = i + 1;
        }

        CursorSpace[SpaceSize - 1].Next = 0;
}

static Position CursorAlloc()
{
        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;
}

图3 例程：CursorSpace初始化、CursorAlloc、CursorFree

/*Return true if L is empty*/
int IsEmpty(List L)
{
    return CursorSpace[L].Next == 0;
}

图4 测试一个链表释放为空的函数-游标实现

/*Return true if P is the last position in list*/
/*Parameter L is unused in this implementation*/
int IsLast(Position P, List L)
{
    return CursorSpace[P].Next == 0;
}

图5 测试P是否是链表的末尾的函数-游标实现

/*Return Position of X in L;0 if not found*/
/*Uses a header node*/
Position Find(ElementType X, List L)
{
     Position P;
    P = CursorSpace[L].Next;
     while (P && CursorSpace[p].Element != X)
        P = CursorSpace[P].Next;
    return P;

}

图6 例程 Find函数游标实现

/*Delete first occurrence X from a list*/
/*Assume use of header node*/
void Delete(ElementType X, List L)
{
    Position P, TmpCell;
    P = FindPrevious(X, L);

    if (!IsLast(P, L)) {
    TmpCell = CursorSpace[P].Next;
    CursorSpace[P].Next = CursorSpace[TmpCell].Next;
    CursorFree(TmpCell);
    }
}

图7 对链表进行删除操作的例程 Delete - 游标实现

/*Insert(after legal position)*/
/*Header implementation assumed*/
/*Parameter L is unused in this implementation*/
void Insert(ElementType X, List L, Position P)
{
    Position TmpCell;
    TmpCell = CursorAlloc();
    if (0 == TmpCell)
        FatalError("Out of space!")

    CursorSpace[TmpCell].Element = X;
    CursorSpace[TmpCell].Next = CursorSpace[P].Next;
    CursorSpace[P].Next = TmpCell;
}

图8 对链表进行插入操作的例程 Insert-游标实现