数据结构链表的两种创建方法（数据结构学习笔记）

数据结构链表的两种创建方法（数据结构学习笔记）第一种是以结构体为基本单元，一个结构体对应一个节点，结构体中有两个元素，一个是该节点存放的数据data，另一个是该节点存放的游标cur，也相当于单链表中的next指针(注意cur中存放的是下一个节点的下标，等同于链表中的指针域，都是表示下一个节点的位置信息的)；静态链表有两种形式：怎么办呢？于是就有人想出使用数组来代替指针，虽然现在大部分语言都可以靠指针或对象引用机制来实现链表，这种用数据代替指针描述单链表的思想是很独到的，这种用数据描述的链表叫静态链表。也叫游标实现法。这种想法很巧妙，实现也很简单。链表是一种链式存储结构，是因为它每一个节点中存放着下一个节点的地址，通过指针与地址使得链表被称作链。那么在一些高级语言中，因为封装较完备，我们无法对地址直接进行操作，如java，C#。所以静态链表可以在某种意义上替代链表。我们知道很多语言，可能没有指针，但是数组这种基本的数据类型一定会有，静态

C语言中的指针的作用是：通过指针不仅可以对数据本身，还可以对存储数据的变量地址进行操作。指针就是内存地址，指针变量是用来存放内存地址的变量。

指针的本意是在一个变量中保存另一个变量的地址，以提供将”地址“变量化的能力。如果没有指针，将无法用一个变量引用另一个变量，只能把变量的值拷贝一份赋给另一个变量。

C语言提供了完善的指针操作，包括：为指针赋值、内存分配（malloc）、取变量地址、让指针可以参与运算等，这使得C程序员能够任意操作可用内存。Java、C#等虽不使用指针，但因为启用了对象引用机制，从某种角度也间接实现了指针的某些作用。

但Basic、Fortran等早期的编程语言是没有指针的，也没有对象引用机制，从而无法实现很多基本的数据结构，如链表、树、图等，这些数据结构都必须用指针来保存前驱或后继节点的地址。

怎么办呢？于是就有人想出使用数组来代替指针，虽然现在大部分语言都可以靠指针或对象引用机制来实现链表，这种用数据代替指针描述单链表的思想是很独到的，这种用数据描述的链表叫静态链表。也叫游标实现法。这种想法很巧妙，实现也很简单。

链表是一种链式存储结构，是因为它每一个节点中存放着下一个节点的地址，通过指针与地址使得链表被称作链。那么在一些高级语言中，因为封装较完备，我们无法对地址直接进行操作，如java，C#。所以静态链表可以在某种意义上替代链表。

我们知道很多语言，可能没有指针，但是数组这种基本的数据类型一定会有，静态链表就是利用数组来模拟实现链表的功能。

静态链表有两种形式：

第一种是以结构体为基本单元，一个结构体对应一个节点，结构体中有两个元素，一个是该节点存放的数据data，另一个是该节点存放的游标cur，也相当于单链表中的next指针(注意cur中存放的是下一个节点的下标，等同于链表中的指针域，都是表示下一个节点的位置信息的)；

第二种是构建两个同步的数组，一个数组存放data 一个数组同步存放该下标对应的cur。其实这俩差不多，第一种更加好理解一点。

其实我们能将静态链表这一个数组拆成两个链表来看，因为一开始创建数组没有元素存储，所以一开始待存储链表很长，已存储链表为空。我们需要存储数据的时候，就把带存储链表的第一个节点取下，用来存放数据，并把它接到已存储链表上，这样带存储链表越来越短，已存储链表越来越长。

一、实现方法

基本思路是：第一个节点（下标index=0）的data不存放数据，cur存放待存储链表的第一个节点下标（注意：是还没有利用过的节点下标），最后一个节点的（下标为length-1）的data不存放数据，cur存放已存储链表的第一个节点的下标。

5-1

为了方便插入数据，通常把数组建立得大一些，以便有一些空闲空间可以便于插入时不至于溢出。线性表的静态链表存储结构的代码如下：

#define MAXSIZE 1000 // 假设链表的最大长度是1000 typedef struct { ElemType data; // 数据 int cur; // 游标 }Component StaticLinkList[MAXSIZE]；

将一维数组space中各分量链成一备用链表，space[0].cur是头指针，“0”表示空指针，初始化的数组状态，见下面代码：

Bool InitList(StaticLinkList space) { for(int i = 0; i < MAXSIZE - 1; i ) { space[i].cur = i 1; } space[MAXSIZE - 1].cur = 0; // 目前静态链表为空，最后一个元素的cur为0 return true; }

我们举个例子说明，假设将数据存入静态链表，比如分别存放着"A”、“B”、“C”、“D”、“E”、“F”等数据，如图所示：

5-2

此时，”A“存有下一元素”B“的游标2，”C“存有下一元素”D“的下标3，”F“是最后一个有值的元素，所以它的cur是0。最后一个元素的cur因为”A“是第一个有值的元素而存它的下标1。第一个元素因空闲空间的第一个元素下标为7，所以它的cur存7。

二、插入操作

静态链表中要解决的是：如何用静态模拟动态链表结构的存储空间的分配，需要时申请，无用时释放。

在动态链表中，结点的申请和释放分别借用malloc()和free()两个函数来实现。在静态链表中，操作的是数组，不存在像动态链表的结点申请和释放问题，所以需要我们自己实现这两个函数，才可以做插入和删除操作。

为了判断数组中哪些分量未被使用，解决的办法是将所有未被使用过的和已被删除的分量用游标链成一个备用的链表，每当进行插入时，便可以从备用链表上取得第一个结点作为待插入的新结点。

节点申请的代码如下（ 若备用链表非空，则返回分配的结点下标，否则返回0）：

int Malloc_SLL(StaticLinkList space) { // 当前数组第一个元素cur的值，就是要返回的备用链表的第一个元素下标 int i = space[0].cur; if (space[0].cur) { // 由于拿出一个分量来使用了，就得把它的下一个分量用来做备用 space[0].cur = space[i].cur; } return i; }

现在如果需要在”B”和“C“之间插入一个值为”G“的元素，按照以前顺序存储结构的做法，应该要把”C”、“D”、“E”、“F”这些元素都往后移一位，但目前不用，因为有了新的手段。

新元素”G“想插队是吧？可以，让它先排在队伍最后第7个游标的位置，然后，将“B”原先的cur是游标为3的“C”，现在改成7，再将“G”的cur设置为3即可。这样，在绝大多数元素都没有变动的情况下，整个链表的次序发生了改变，如图所示：

5-3

参考代码如下：

// 在L中第i个元素之前插入新的元素e

Bool ListInsert(StaticLinkList L int i ElemType e) { int j k l; k = MAX_SIZE - 1; // 注意k首先是最后一个元素的下标 if (i < 1 || i > ListLength(L) 1) { return false; } j = Malloc_SLL(L); // 获得空闲分量的下标 if ( ! j) { return false; } L[j].data = e; // 将数据赋值给此分量的data for (l = 1; l < i; l ) { // 找到第i个元素之前的位置 k = L[k].cur; } L[j].cur = L[k].cur; // 把第i个元素之前的cur赋值给新元素的cur L[k].cur = j; // 把新元素的下标赋值给第i个元素之前元素的cur return true; }

这样，就实现了在数组中，不用移动元素，却插入了数据的操作。

三、删除操作

假如我们删除元素A 和前面一样，删除元素时，是需要释放结点的函数free()。现在也需自己实现：

5-4

// 删除在L中第i个数据元素e

Bool ListDelete(StaticLinkList L int i) { if (i < 1 || i > ListLength(L)) { return false; } int j k; k = MAX_SIZE - 1; for (j = 1; j < i; j ) { k = L[k].cur; } j = L[k].cur; L[k].cur = L[j].cur; Free_SSL(L j); return true; }

// 将下标为k的空闲结点回收到备用链表

void Free_SLL(StaticLinkList L int k) { L[k].cur = space[0].cur; // 把第一个元素cur值赋给要删除的分量cur L[0].cur = k; // 把要删除的分量下标赋值给第一个元素的cur }四、链表长度

静态链表的ListLength实现如下：

// 初始条件：静态链表L已存在。操作结果：返回L中数据元素个数

int ListLength(StaticLinkList L) { int j = 0； i = L[MAX_SIZE - 1].cur; while (i) { i = L[i].cur; j ; } return j; }

五、静态链表和动态链表的区别

1、 静态链表要预先申请一整块足够内存的空间，其能存储的元素个数在创建的那一刻就不能再更改了。
动态链表：之前实现的单链表，双链表，循环链表都属于动态链表，可以在使用过程中动态申请内存。

2、静态链表是一种用数组描述的链表，其实是为了给没有指针的高级语言设计的一种实现单链表功能的方法。
3、静态链表其实包括两个链表，一个是数据链表，一个是空闲链表。

4、静态链表的第一个节点和最后一个节点作为特殊元素处理，
第一个节点作为备用链表的表头，其cur值指向下一个空闲的节点。
最后一个节点作为数据链表的表头，其cur值指向第一个有数据的节点。
4、优点：在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进在顺序存储结构中插入和删除元素需要移动大量元素的缺点
缺点：没有解决连续存储分配带来的表长难以确定的问题。

5、注意静态链表的删除操作，删除操作要更新两个链表，数据链表要更新前一节点的cur 空闲链表要把空出的节点放入空闲链表的第一个节点（不能放入空闲链表的末尾，因为找不到空闲链表的末尾）。

【参考文献】数据结构(C语言版）、大话数据结构、算法导论、算法设计与分析基础。