诸如BASIC和FORTRAN等许多语言都不支持指针。如果需要链表而又不能使用指针，这时我们可以使用游标（cursor）实现法来实现链表。
在链表的实现中有两个重要的特点：
数据存储在一组结构体中。每一个结构体包含有数据以及指向下一个结构体的指针。
一个新的结构体可以通过调用malloc而从系统全局内存（global memory）得到，并可以通过free而被释放。
游标法必须能够模仿实现这两条特性:
定义一个全局的结构体数组（模拟系统全局内存）。对于数组中的任何单元，其数组下标可以用来代表一个地址。
typedef int ptr_to_node; typedef ptr_to_node list; typedef ptr_to_node position; struct node { element_type element; position next; }; struct node cursor_space[spacesize];在这个全局的结构体数组中，保留一个表freelist作为备用单链表，用来malloc或free游标可用空间，该表用0作为表头。刚开始时，freelist就是整个结构体数组。
需要理解的是：所有的链表，包括备用表和已用表，全部都在我们定义的全局结构体数组中，只是它们的表头不同，从不同的表头出发形成了不同的单链表。
假设我们定义了一个大小为11的游标空间，其初始化状态如下：
SlotElementNext0 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 0注：对于Next， 0的值等价于NULL指针。
上面的状态用链表形式表示为：cursor_space[0]—>cursor_space[1]—>cursor_space[2]—>cursor_space[3]—>cursor_space[4]—>cursor_space[5]—>cursor_space[6]—>cursor_space[7]—>cursor_space[8]—>cursor_space[9]—>cursor_space[10]—>NULL.
为执行malloc功能，将（在表头后面的）第一个元素从freelist中删除。为了执行free功能，我们将该单元放在freelist的前端。
malloc和free的游标实现如下：
static position cursor_alloc(void) { position p; p = cursor_space[0].next; cursor_space[0].next = cursor_space[p].next; return p; } static void cursor_free(position p) { cursor_space[p].next = cursor_space[0].next; cursor_space[0].next = p; }为加深理解，请参考如下实例:
SlotElementNext0 1 2 3 4 5 6 7 8 9 10- b f header - header - c d e a6 9 0 7 0 10 4 8 2 0 1如果单链表L的值是5，M的值是3，我们又规定了freelist表头为0，因此，从上表中我们可以得到三个链表：
freelist：cursor_space[0]—>cursor_space[6]—>cursor_space[4]—>NULL
L：header—>a—>b—>e—>NULL
M：header—>c—>d—>f—>NULL
freelist是分配L、M链表后还剩余的可分配空间。
游标实现
/* return ture if L is empty */ int isempty(list L) { return cursor_space[L].next = 0; } /* return true if P is the last position in list L */ int islast(position p, list L) { return cursor_space[P].next == 0; } /* return position of X in L; 0 if not found */ /* uses a header node */ position find(element_type X, list L) { position p; p = cursor_space[L].next; while(p && cursor_space[p].element != X) p = cursor_space[p].next; return p; } /* delete first occurence of X from a list */ /* assume use of a header node */ void delete(element_type X, list L) { position p, tmpcell; p = find_previous(X, L); if(!islast(p, L)) { tmpcell = cursor_space[p].next; cursor_space[p].next = cursor_space[tmpcell].next; cursor_free(tmpcell); } } /* insert (after legal position P) */ void insert(element_type X, list L, position P) { position tmpcell; tmpcell = cursor_alloc(); if(tmpcell == 0) fatal_error("out of sapce!!!"); cursor_space[tmpcell].element = X; cursor_space[tmpcell].next = cursor_space[P].next; cursor_space[P].next = tmpcell; }转载于:https://www.cnblogs.com/nufangrensheng/p/3594844.html
相关资源：各显卡算力对照表！