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