静态链表的实现

  • A+

静态链表,其实就是用数组的方式来实现线性表的链式结构

当然的,它的大小也是固定的(要先确定大小)

并不能可以一直增长

它是一些没有指针或者引用这样机制的编程语言

用来实现线性表的链式结构的替代

想法很精粹,所以我来实现一下它


这里使用的也是C#语言

这里使用了类来表示静态表

好像有点怪,不果最主要的还是理解它的思想

①这里使用了一个结构体来保存结点的数据与用一个int的变量来保存它下一个元素的数组下表

②声明节点数组,当前长度,最大长度和一个用于保存线性表最后结点的数组下表的变量


这里是静态链表的构造函数

用于初始化链表

主要的工作有

①确定数组的最大长度,如果没有就是用默认的大小

②使用已知的最大长度,初始化话数组的大小

③第一个0下标数组元素的cur用于保存备用链表的第一个结点,因为新建的链表,所以没有元素,除去0后,所以备用链表的数组下标为1

④数组的最后一个元素的cur用于保存数据元素的第一个结点的数组下标,这里是空链表,所以没有元素,初始化为0,表示为空链表

⑤初始化备用链表一个接一个,上一个数组元素的cur保存下一个元素的数组下标

⑥初始化备用链表的最后一个元素的cur为0表示备用链表结束

⑦初始化最后一个数据元素为特殊结点,这里是为了快速在尾部添加元素的而设立的


很熟悉吧!

线性表我也用了这么一个方法

它是获取到指定位置的结点的数组的下标

就是要这么拗口

①先判断是否等于0,是的话就返回特殊结点(相当于头结点吧)

②判断结点是否在数据域的范围之内,不是就返回错误

③初始化一个int i = 1用于计数,初始化subscript为第一个元素结点的数组下标

④判断subscript是否为0,是的话表示为空链表

⑤用一个while循环找到第index个结点的数组下标

⑥返回这个下标


不同于平常的链表了

静态链表其实是两条链

一条用于保存数据,一条为备用链表(就是空闲的地方)

当我们每次插入或添加元素的时候

我们都要先从备用链表中取出一个位置来

当然,删除的时候,空闲出来的结点也要放回到空闲链表中

这里的操作看注释吧!!


回收空闲结点就是把它插入到备用链表的第一个

①首先将回收结点的下一个结点cur赋值为当前备用链表的第一个结点的下标

②指定备用链表的第一个结点为回收结点


这里是静态链表怎么添加元素

①通过刚才的方法在备用链表中获取一个空闲的位置

②通过while循环找到链表的最后一个结点

③将要插入的数据赋值给新加结点的data

④赋值新加结点的cur为0,表示它准备成为最后一个结点了

⑤将当前最后一个结点的下一个结点cur指定为添加的结点下标

⑥最后指定最后一个结点为添加的结点,用于快速添加

⑦链表的长度+1

如果在头部添加元素的话,使用头结点,就是下标为_maxLength-1

是非常容易的,我这里就不实现了


这个是用已经知道了的最后的结点来插入新结点

对比上面的步骤

它就是少了去遍历寻找到最后的结点

使用空间换时间

只要保存最后一个结点的下标

这个效果是非常好的

代码具体步骤可以参考上面的添加


这个是静态链表的插入

①要插入结点就要首先获得插入位置的前一个结点

②判断前一个结点与插入位置结点是否存在

③在备用链表中获取一个可用的空间作为新的结点

④将数据赋值给新结点的data

⑤赋值新加结点的下一个结点cur为被插入结点

⑥将被插入结点的上一个结点的下一个结点cur赋值为新加结点

⑦最后链表的长度+1


删除静态链表指定位置的结点

①同样的删除元素也需要获取到被删结点的上一个结点

②同样的也需要判断一下被删结点和被删结点的上一结点是否存在

③通过被删结点的上一个结点获取到被删结点的下标

④取出被删结点的数据赋值给element用于返回

⑤赋值被删结点的下一个结点cur为被删结点的下一个结点

⑥回收被删结点的下标

⑦链表的长度-1


测试

结果
静态链表的实现

  • 我的微信
  • 扫一扫加我微信
  • weinxin
  • 微信我的
  • 我微信扫一扫加
  • weinxin

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: