【CPP】游标（静态）链表

这次的代码基本来自《数据结构与算法分析——C语言描述》这本神书和网上别人写的代码。主要讲一下游标链表的原理。

游标（Cursor）链表，即是用数组和数组下标来代替指针实现链表的一种东西。在许多编程语言中，指针是不被支持的。在这种情况下如果我们需要自己来实现链表（虽然大多数这类语言都不需要自己实现链表），就可以使用数组和游标来实现。由于我们通过声明数组下标变量来代替指针，所以把那个下标变量叫做游标。由于这个链表的储存空间由数组来提供，所以叫做静态链表。

在实现游标链表时，最主要是要模拟出指针（游标），和内存的申请与释放（malloc,free）。这里我们先看看代码头，这次的代码是由纯C的函数构成。

首先我们初始化模拟内存的数组CursorSpace，我们申请一个足够大的数组，然后让这个数组每个元素指向下一位的下标为自己的下一个数，让数组末指向数组头，这样我们就将整个数组内存串成了一个大的循环链表空间，在这里我们让0号位表示空白空间的头。然后这里我们可以看到，每次我们alloc时，函数都会在CursorSpace找到0号位的下一位来返回，然后让0号位指向自己的后一位。这样我们便通过这种指针般的下标申请到了一位空位，且保持着空内存的小循环。然后当我们free时用类似的方法，让打算free的空间被0号位链接，把内容清空，就达成了free的效果。

接着是几个简单的函数，参数中的List L在开头时就声明过了时int类型的数，实际上因为这个程序的内存中可以存放多个链表，所以这个参数代表的是链表的头（头下标）。

刚才上面的MakeEmpty函数中有调用到DeleteList函数。这个函数先将链表头接在0号位，然后一个一个将链表的元素free掉，全部free完自然链表就被删除完全并入了空内存中了。

Insert没有什么特别的，alloc空间后将空间接在链表的目标位置。

然后是Find函数和FindPrevious函数，由于是单链表，所以可以用简单的循环遍历整个链表找出想要的数据位置，利用Find和FindPrevious函数可以和Insert配合达成自由的数据插入操作。

最后是一个简单的Delete函数，Delete函数中要注意的是保证删除后前一个元素能再成功接上后一个元素，而且要注意用IsLast判断是否链表为空。

以上便是这次的静态链表的解释，代码本身比较稳健，大家大可以把代码下载下来然后自己在main函数里去测试这个链表。照例在最后放上代码的下载。

链接：http://pan.baidu.com/s/1hsOnYUo 密码：slgm