扫码获取更多资源

●静态链表

有时，也可以借用一维数组来描述线性表，数组的大小一般要大于线性表当前长度。数 组中一个分量表示一个结点，在存储元素值的同时，还使用游标(cur)代替单链表中的指针, 存储指示其后继的相对地址(最后一个分量游标域值为0),这种用数组描述的链表称为静 态链表(Static Linked List)

静态链表的结点结构

静态链表的结点结构如图2-21所示。其 数据域中，data为数据域，存放元素的数据；cur为游标 域，存放其后继的相对地址。

数组中的第0个分量可以看成头结点：其数据域可以不存储任何信息，也可以存储如 线性表的长度等附加信息；其游标域指示静态链表的第一个结点。 图2-22给出了一个静态链表的示例。图2-22(a)是一个修改之前的静态链表；图2-22(b) 是插入元素“Shi”和删除元素“ Zheng”之后的静态链表。

静态链表的主要特点

静态链表存储结构仍然需要预先分配一个较大的空间，但在作线性表的插入和删除时 不需要移动元素，仅修改指针即可，因此仍然具有链式存储结构的主要优点。

算法设计

在静态链表中实现线性表的操作和单链表相似，以整型游标i代替动态指针p,i = SLiJ. cur的操作即为指针后移(类似于单链表操作中的p = p —>next)。

算法描述

算法分析

(1)问题规模：静态链表的结点个数(设值为n)。

(2)基本操作：顺链向后査找元素。

(3)时间分析：算法执行时间主要花费在while循环中的基本操作上。查找成功时的平 均执行次数是(n-l)/2,查找不成功时的执行次数是n,因此算法2-29的时间复杂度为O(n)。

联系我们：