# 链表的游标（cursor）实现

```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];```

 Slot Element Next 0 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 0

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

 Slot Element Next 0 1 2 3 4 5 6 7 8 9 10 – b f header – header – c d e a 6 9 0 7 0 10 4 8 2 0 1

freelist：cursor_space[0]—>cursor_space[6]—>cursor_space[4]—>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;
}```
原文作者：ITtecman
原文地址: https://www.cnblogs.com/nufangrensheng/p/3594844.html
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。