2.5 态链表★2◎4

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