List | 静态链表 —— 游标实现
目录
2、让CursorSpace数组中的单元代替malloc和free的职能
一、概述
1、动态链表
以前学习的各种链表都是由指针实现的，链表中结点的分配和回收(即释放)都是由系统提供的标准函数malloc和free动态实现的，故称之为动态链表。
2、静态链表
但是有的高级语言，如BASIC、FORTRAN等，没有提供“指针”这种数据类型，此时若想采用链表做存储结构，只能通过数组实现，并必须使用"游标"来模拟指针，由程序员自己编写“分配结点”和“回收结点”的过程。
这种用数组描述的链表叫做静态链表，这种描述方法叫做游标实现法。
注意
在链表的指针实现中有两个重要的特点：
1、数据存储在一组结构体中。每一个结构体包含有数据以及指向下一个结构体的指针。
2、一个新的结构体可以通过调用malloc而从系统全局内存得到，并可通过调用free而被释放。
二、具体实现
游标法必须能够模仿实现以上两条特性：
1、要有一个全局的结构体数组
暂且命名为CursorSpace数组：
数组作为顺序存储元素，每个元素为一个结构体，有两个变量：data实现数据存储，next实现指向下一个结点的在数组中位置，进而实现类似链表的功能。
????该数组类似与系统中的内存，申请节点，释放节点均在此数组中进行。
????并且数组的大小决定链表的最大节点数。
????对于该数组中的任何单元，其数组下标可以用来代表一个地址。
struct Node {
int data; //数据域
int next; //模拟指针，即下一个位置的数组下标
} CursorSpace[SpaceSize];
2、CursorsSpace数组模拟代替malloc和free操作
我们通过一个freelist表来模拟内存，我们通常也称之为备用链表。freelist表的表头设定为CursorSpace[0]，表头之后连着的节点均在freelist表内，即仍在内存中待申请使用的节点。一旦从“内存”中malloc了这一个节点，那么此节点就不在freelist中了。
????数组首元素CursorSpace[0]作为备用链表头结点，其游标值next为0表示指向空。
????最开始初始化的状态：数组中所有的节点均在freelist中。
以下为初始化freelist（备用链表）的函数。
void initialize(int SpaceSize) {
for(int i = 0;; i++) {
CursorSpace[i]->data = 0; //数据域置零
//到了最后一个空间
if(i + 1 == SpaceSize) {
CursorSpace[i].next = 0; //相当于指向NULL
break;
}
CursorSpace[i].next = i + 1;
}
}备用链表freelist的初始情况如下图所示，slot为其下标，element为数据域（全初始化为零），next为下一个节点的下标：
熟悉了freelist的基本结构那么对于malloc和free的模拟实现就很容易理解了。
Ⅰ. malloc的模拟实现
注意我们模拟的环境：freelist（备用链表）为我们的模拟内存。
那么malloc操作就是从freelist中申请并移除一个节点，返回其下标，我们默认申请头节点之后第一个节点，代码实现如下：
int CursorAlloc() {
int p;
p = CursorSpace[0].next; //获取头节点后第一个节点
CursorSpace[0].next = CursorSpace[p].next; //从freelist中删除标为p的节点
return p; //返回申请成功的节点下标
}
如果无法理解，可以手动实现几次CursorAlloc操作。
Ⅱ. free的模拟实现
注意我们模拟的环境：freelist（备用链表）为我们的模拟内存。
那么malloc操作就是，传入待free节点下标，将待free节点回收到（重新插入）freelist中，我们默认插入到头节点之后，代码实现如下：
void CursorFree(int p) {
CursorSpace[p].next = CursorSpace[0].next;
CursorSpace[0].next = p;
}如果无法理解，可以手动实现几次CursorFree操作。
三、其他操作
关于游标链表的插入、删除、查找等操作
未完待续...
end
欢迎关注个人公众号“鸡翅编程”，这里是认真且乖巧的码农一枚，旨在用心写好每一篇文章，平常会把笔记汇总成推送更新~
上一篇： 数据结构与算法——python排序算法(冒泡排序)
下一篇： 用博客记录自己的学习历程