2.5 态链表★2◎4
2.5 静态链表★2◎4
线性表的顺序存储和链式存储各有优缺点,其中顺序存储算法设计简单便捷,不涉及存储空间的分配和释放操作,而链式存储算法插入和删除方便,不需要移动数据元素,那么可不可以将两种存储方式的优点综合起来呢?可以,这就是静态链表。
1.静态链表的存储结构表示
在某些高级语言中,没有“指针”的概念,因此人们使用一个一维数组描述链表,使用数组的下标作为指向数组元素的指针,这样“静态链表”就油然而生,如下定义了一个数据元素类型为Elemtype的静态链表。
我们定义数组元素LinkList[0]为静态链表的头结点,nCur为结点的指针域,当nCur取值为0时,表示链表已经结束;当nCur取值为1时,表示该结点未使用,如图2-8(a)所示。
(1)LinkList[0].nCur值为1,则线性表第1个数据元素为LinkList[1].data=2000。
(2)LinkList[1].nCur值为4,则线性表第2个数据元素为LinkList[4].data=2001。
(3)LinkList[4].nCur值为2,则线性表第3个数据元素为LinkList[2].data=2002。
(4)LinkList[2].nCur值为5,则线性表第4个数据元素为LinkList[5].data=2003。
(5)LinkList[5].nCur值为3,则线性表第5个数据元素为LinkList[3].data=2004。
(6)LinkList[3].nCur值为7,则线性表第6个数据元素为LinkList[7].data=2005。
(7)sLinkList[7].nCur值为0,则线性表结束。
故图2-8(a)中记载了线性表(2000,2001,2002,2003,2004,2005)。同理,图2-8(b)中记载了线性表(a,b,c,e,f),图2-8(c)记载了一个空静态链表。
2.静态链表的寻址算法
静态链表的前驱和后继的存储位置并不要求相邻,因此也必须通过“指针域”遍历整个线性表来查找。
例题:已知静态链表L第i个元素的数组下标为p,求其第i+1个元素的数组下标。
回答:L[p].nCur
3.静态链表插入算法
已知p是静态链表L中某一个元素的数组下标,新结点的数组下标为s,则将s插入p后面的步骤为:
4.静态链表删除算法
已知p是静态链表L中某一个元素的数组下标,则删除p所指向元素的后继元素的步骤为:
5.静态链表的特点
链式结构线性表的特点有:
(1)使用数组下标描述“指针域”。
(2)一次性分配所有存储空间,程序设计简单。
(3)所有数据元素存储在一个连续的空间段,但相邻两个元素不一定处于相邻的空间段。
(4)插入和删除操作都不需要移动数据元素。
静态链表适用于最大数据元素数量固定的应用,以及不支持“指针”的高级语言中。
2.5 态链表★2◎4