静态链表

Gegu · 发表于 2016-7-13 15:12

EDA365欢迎您！

您需要登录才可以下载或查看，没有帐号？注册

x

在归并两个链表为一个链表时，不需要另建新表的结点空间，而只需将原来两个链表中结点之间的关系解除，重新按元素值非递减的关系将多有结点链接成一个链表即可。
有时，也可借用一维数组来描述线性链表，其类型说明如下所示：
//------------------线性表的静态单链表存储结构-------
#define MAXSIZE 1000 //链表的最大长度
typedef struct{
ElemType data;
int    cur}component,SLinkList[MAXSIZE];
这种描述方法便于在不设“指针”类型的高级程序设计语言中使用链表结构。在如上描述的链表中，数组的一个分量表示一个结点，同时用游标代替指针指示结点在数组中的相对位置。数组的第零分量可看成头结点，其指针域指示链表的第一个结点。这种存储结构仍需要预先分配一个较大的空间，但在作线性表的插入和删除操作时不需要移动元素，仅需修改指针，故仍具有链式存储结构的主要优点。为了和指针型描述的线性链表相区别，我们给这种用数组描述的链表起名叫静态链表。

0

　

1


  1

ZHAO

2


2

QIAN

3


3

SUN

4


4

LI

5


5

ZHOU

6


6

WU

7


7

ZHENG

8


8

WANG

0


9

　

　


10

　

　




(a)



修改前的状态

0

　

1


1

ZHAO

2


2

QIAN

3


3

SUN

4


4

LI

9


5

ZHOU

6


6

WU

8


7

ZHENG

8


8

WANG

0


9

SHI

5


10

　

　




(b)



修改后的状态
假设S为SLinkList型变量，则S[0].cur指示第一个结点在数组中的位置，若设i=S[0].cur，则S.data存储线性表的第一个数据元素，且S.cur指示第二个结点在数组中的位置。一般情况，若第i个分量表示链表的第k个结点，则S.cur指示第k+1个结点的位置。因此在静态链表中实现线性表的操作和动态链表相似，以整型游标i代替动态指针p，i=S.cur的操作实为指针后移，例如，在静态链表中实现的定位函数LocateElem
intLocateElem_SL(SLinkList S,ElemType e){
//若静态单链线性表L中查找第1个值为e的元素。
//若找到，则返回它在L中的位序，否则返回0.
i=S[0].cur    //i指示表中第一个结点
while(i&&S.data!=e)i=S.cur;//在表中顺链查找
return i;
}//LocateElem_SL
指针修改的操作和前面描述的单链表中的插入与删除的算法类似，不同的是，需用户自己实现malloc和free这两个函数。为了辨明数组中哪些分量未被使用，解决的办法是将所有未被使用过以及被删除的分量用游标链成一个备用的链表，每当进行插入时便可从备用链表上取得第一个结点作为待插入的新结点；反之，在删除时将从链表中删除下来的结点链接到备用链表上。