admin 
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）插入和删除操作都不需要移动数据元素。
静态链表适用于最大数据元素数量固定的应用，以及不支持“指针”的高级语言中。
评论列表 人参与