Weiss书中提到了链表的游标实现，什么是游标(Cursor)实现呢？
诸如BASIC和FORTRAN等许多语言都不支持指针。如果需要链表而又不能使用指针，这时我们可以使用游标（cursor）实现法来实现链表。
在链表的实现中有两个重要的特点：
1，数据存储在一组结构体中。每一个结构体包含有数据以及指向下一个结构体的指针。
2，一个新的结构体可以通过调用malloc而从系统全局内存（global memory）得到，并可以通过free而被释放。
个人理解为用一个结点数组来模拟实现内存的分配和释放，在结构体数组中，保留一个表freelist作为备用单链表，用来alloc或free游标可用空间，该表用0作为表头。刚开始时，freelist就是整个结构体数组。
从不同的表头（Index）出发形成了不同的单链表。如果定义一个大小为10的游标空间，则其初始化状态应如下：
| slot | Element | Next |
| 0 | 1 | |
| 1 | 2 | |
| 2 | 3 | |
| 3 | 4 | |
| 4 | 5 | |
| 5 | 6 | |
| 6 | 7 | |
| 7 | 8 | |
| 8 | 9 | |
| 9 | 0 |
Code is here~
.h 中的声明：
1 #ifndef CUSORLIST_H_INCLUDED 2 #define CUSORLIST_H_INCLUDED 3 4 typedef int PtrToNode; 5 typedef PtrToNode List; 6 typedef PtrToNode Position; 7 8 void InitializeCursorSpace(void); 9 10 #define ElementType int //set the type of element as Integer 11 // Functions 12 List MakeEmpty(List L); 13 List InitialList(); 14 int IsEmpty(const List L); 15 int IsLast(const Position P, const List L); 16 Position Find(ElementType X, const List L); 17 void Delete(ElementType X, List L); 18 Position FindPrevious(ElementType X, const List L); 19 void Insert(ElementType X, List L, Position P); 20 void DeleteList(List L); 21 Position Header(const List L); 22 Position First(const List L); 23 Position Last(const List L); 24 Position Advance(const Position P);//not implemented yet 25 ElementType Retrive(const Position P);//not implemented yet 26 27 #endif // CUSORLIST_H_INCLUDED
.c文件：
1 #include "CusorList.h" 2 #include <stdio.h> 3 #include <stdlib.h> 4 5 struct Node{ 6 ElementType Element; 7 Position Next; 8 }; 9 #define SpaceSize 40 10 11 struct Node CursorSpace[SpaceSize]; // CursorSpace here is an array of Nodes 12 void InitializeCursorSpace() { 13 int i; 14 for (i = 0; i < SpaceSize - 1; i++) { 15 CursorSpace[i].Next = i + 1; 16 } 17 CursorSpace[SpaceSize - 1].Next = 0; // here "0" means "NULL" 18 } 19 static Position CursorAlloc(void) { 20 // remember that Position(P) here is just a index of array, that's to say, an integer. 21 Position P; 22 P = CursorSpace[0].Next; 23 CursorSpace[0].Next = CursorSpace[P].Next; 24 return P; 25 } 26 static void CursorFree(Position P) { 27 CursorSpace[P].Next = CursorSpace[0].Next; 28 CursorSpace[0].Next = P; 29 } 30 int IsEmpty(const List L) { // Return true if L is empty 31 return CursorSpace[L].Next == 0; 32 } 33 int IsLast(const Position P, const List L) { // return true if P is the last Position 34 return CursorSpace[P].Next == 0; 35 } 36 Position Find(ElementType X, const List L) { // return Position of X in L; 0 if not found 37 Position P = CursorSpace[L].Next; 38 while (P && CursorSpace[P].Element != X) 39 P = CursorSpace[P].Next; 40 return P; 41 } 42 void Delete(ElementType X, List L) { // Delete the first occurrence of X from L 43 Position P, tmp; 44 P = FindPrevious(X, L); 45 if (!IsLast(P,L)) { 46 tmp = CursorSpace[P].Next; 47 CursorSpace[P].Next = CursorSpace[tmp].Next; 48 CursorFree(tmp); 49 } 50 } 51 Position FindPrevious(ElementType X, const List L) { 52 Position P = L; 53 Position tmp = CursorSpace[P].Next; 54 while (CursorSpace[tmp].Element != X && tmp) { 55 tmp = CursorSpace[tmp].Next; 56 P = CursorSpace[P].Next; 57 } 58 return P; 59 } 60 61 /*Insert(after legal position)*/ 62 /*Header implementation assumed*/ 63 /*Parameter L is unused in this implementation*/ 64 void Insert(ElementType X, List L, Position P) { 65 Position tmp; 66 tmp = CursorAlloc(); 67 if (0 == tmp) { 68 printf("Out of space!"); 69 } else { 70 CursorSpace[tmp].Element = X; 71 CursorSpace[tmp].Next = CursorSpace[P].Next; 72 CursorSpace[P].Next = tmp; 73 } 74 } 75 void DeleteList(List L) { 76 Position P = CursorSpace[L].Next; 77 Position tmp = P; 78 while (tmp != 0) { 79 P = CursorSpace[P].Next; 80 CursorFree(tmp); 81 if (P == 0) { 82 break; 83 } 84 tmp = P; 85 } 86 CursorSpace[L].Next = 0; 87 }