2.4 静态链表在线视频

同学们大家好

我是云南大学信息学院教师孔兵

这节课我们讨论静态链表

上节课，我们讨论了链表

链表在有的应用背景下是有优势的

但是有的程序设计语言中是没有指针的

比如Java，在这样的程序设计语言中

要使用链表可以吗

我们说是可以的，可以使用静态链表

前面讲过的链表，我们可以称作动态链表

基本操作是malloc在内存中申请结点

每个结点有一个地址，为了描述数据元素的关系

每个结点附设一个指针，指针中存储器后继结点的地址

形成一个单链表，如图所示，ai结点存200

指明其后继结点ai+1的存储地址

当链表中删除一个单元后

把这个单元用free释放还给内存

总结一下动态链表就是，每个结点有一个地址

用指针把内存中不连续的单元链接起来

那么，没有指针怎么实现链表呢

主要的工具就是一个数组

声明一个数组S，假设S中有1000个单元

每个单元是一个结构体，包含两个成员

一个是data存储数据元素

一个是整型变量cur，我们把cur称为游标

那么在数组当中

如果我们把每个单元的下标看作是

这个单元在数组空间中的地址

就可以通过游标建立静态链表

比如说，ai存在数组第i个单元

ai+1存在数组第j个单元

为了描述ai的后继是ai+1

我们可以在第i个单元的cur中存j

用游标明示出其后继的存储位置，类似指针的作用

对线性表的其它元素也做类似设置

就可以获得静态链表存储的线性表

下面我们看个具体的例子

第1个图中，以百家姓赵钱孙李周吴郑王

为数据元素建立了一个静态链表

赵这个单元的游标是2

指明它的后继钱是存在数组下标的2号单元

同理，钱这个单元的游标是3

指明它的后继孙是存在数组下标的3号单元

后面的情况类似，最后一个元素是王

因为它没有后继，游标为0，表示链表结束

这个例子使用数组空间存储元素

借助游标描述关系，形成一个静态的一个单链表

第2个图是静态链表插入的演示

原链表中，李的后继是周，在5号单元

现在它的后继是施，在9号单元

施的后继是5号单元的周，在这里

我们是在静态链表的数据元素李后面插入一个数据元素施

最后一个图是链表的删除

吴的后继本来是7号单元的郑，删除了郑以后

吴的后继编程了8号单元的王

下面我们看一下静态链表的实现

静态链表的定义主要就是对这个数组空间的定义

首先声明一个常量MAXSIZE

作为个静态链表数组的大小

链表中的每个元素被定义成一个结构体

结构体中，包含两个成员

一个是存储数据元素的data，另一个是整型变量的游标

用Typedeef声明了一个以结构体

为元素类型的数组类型名字slinklist

slinklist这个数组类型，它的大小是MAXSIZE

它的变量是一个数组，就是我们要用到的

作为静态链表存储空间的

要实现静态链表，还有一些问题是需要我们考虑的

在前面讨论的动态链表中，我们需要一个结点的时候

就利用一个malloc函数来申请

当不需要这个结点的时候，用Free函数来释放

我们并不需要关心这些操作在内存空间中是如何实现的

也就是说我们不需要管理内存空间

但是在静态链表当中，存储空间是我们声明的一个数组

那么，当我们利用它来实现静态链表的时候

这块空间的管理工作就必须要由我们自己来完成

也就是说，申请结点，释放结点这样的操作

就必须由我们自己来做。下面我们简单的看一下

首先声明一个SLinkList的数组S

作为静态链表的存储空间

为了实现数组空间中申请结点

释放结点这样的操作

我们首先创建一个备用链表

备用链表也是一个静态链表

把没有用到空的数组结点组织成一个备用链表

当需要申请一个结点的时候呢

就从备用链表中取下一个结点

当不再使用某个结点时候

就把它插入到备用列表，以备后续使用

数组0号单元不存数据元素

相当于备用链表的头结点

把s[0].cur作为备用链表的头指针

我们先来看一下对链表空间的初始化

初始化的作用

就是把数组中的所有单元加入到备用链表中

以便于后续使用它

我们结合图看一下

图的左边是未初始化的样子

初始化完以后，s[0].cur是指向数组单元1

单元1的游标指向单元2

一直到单元998的游标指向单元999

999单元是备用链表的最后一个节点，它的游标是0

初始化函数实现很简单，主要就是一个循环语句

循环变量从0到998，每次循环呢

都是space[i].cur被赋值i+1

让前一个单元的游标指向它的下一个单元

循环结束以后，那么第999单元的游标赋值0

这是最后一个单元，这样就把所有可用的结点

都组织到了一个备用链表中

下面看一下申请结点和释放结点两个操作的实现

怎么实现申请结点操作呢

只需要从备用链表中取出一个结点

为了操作的方便

我们取的结点就是备用链表中的首先结点

申请函数的返回值类型是整型，如果申请成功

那么返回数组中可以使用的这个结点的下标

如果申请失败

就是说备用链表已经没有可用的结点了，返回0

它的参数呢，只有一个

就是作为静态链表存储空间的数组space

i=space[0].cur; 是让i指向首元结点

也就是我们要取的这个结点

如果space[0].cur为真

那么意味着备用链表中至少有一个结点可用

备用链表不空，那么space[0].cur=space[i].cur

这是在备用列表中删除首元节点

随后呢， i作为返回值

当返回值为零的时候

意味着备用链表空，结点申请失败

在静态链表中，释放某个结点

就是把它插入到备用链表中备用

为了插入方便，我们用头插法

把它插入到这个0号单元这个头结点之后

插入以后，作为备用链表新的首元结点

释放操作它涉及到两个参数

一个是作为存储空间的数组space

一个是我们要插入备用链表的单元对应的下标k

space[k].cur=space[0].cur;

让待插入结点的游标指向原来的备用链表的首元结点

space[0].cur=k; 让备用链表头结点的游标

指向这个新插入的这个节点

新插入的结点成为备用链表新的首元结点

关于静态链表的讨论，我们就进行到这儿

静态链表和动态链表有类似的性质

如插入删除不需要移动，我们前面已经看到了

同学们，这节课就到这

我们下节课再见