数据结构—线性表的链式存储和运算—静态链表

下面先请看图2.22 ,在图2.22中,规模较大的结构数组sd[MAXSIZE] 中有两个链表:

其中链表SL是一个带头结点的单链表,表示了线性表(a1, a2, a3, a4, a5),而另一个单链表AV是将当前sd 中的空结点组成的链表。

数组sd的定义如下:
#define MAXSIZE … /*足够大的数*/
typedef struct
{datatype data;
int next;
}SNode; /*结点类型*/
SNode sd[MAXSIZE];
int SL,AV; /*两个头指针变量*/

这种链表的结点中也有数据域data和指针域next,与前面所讲的链表中的指针不同的是,这里的指针是结点的相对地址(数组的下标),称之为静态指针,这种链表称之为静态链表,空指针用-1表示,因为上面定义的数组中没有下标为-1的单元。

在图2.21中,SL是用户的线性表,AV模拟的是系统存储池中空闲结点组成的链表,当用户需要结点时,例如向线性表中插入一个元素,需自己向AV申请,而不能用系统函数malloc来申请,相关的语句为:
if(AV!=-1)
{ t=AV;
AV=sd[AV].next;
}
所得到的结点地址(下标)存入了t 中;不难看出当AV表非空时,摘下了第一个结点给用户。当用户不再需要某个结点时,需通过该结点的相对地址t 将它还给AV,相关语句为: sd[t].next=AV;AV=t;而不能调用系统的free 函数。交给AV表的结点链在了AV的头部。

下面通过线性表插入这个例子看静态链表操作。

例2.4 在带头结点的静态链表SL的第i个结点之前插入一个值为x的新结点。设静态链表的存储区域sd为全局变量。
int Insert_SList( int SL, datatype x, int i)
{ int p,s;
p=SL; j=0;
while(sd[p].next!=-1 && j<i-1)
{p=sd[p].next;j++;} /*找第i-1个结点*/
if(j==i-1)
{ if(AV!=-1) /*若AV表还有结点可用*/
{t=AV;
AV=sd[AV].next; /*申请、填装新结点*/
sd[t].data=x;
sd[t].next=sd[p].next; /*插入*/
sd[p].next=t;
return 1; /*正常插入成功返回*/
}
else{printf("存储池无结点");return 0;}
/*未申请到结点,插入失败*/
else{printf("插入的位置错误");return -1;}
/*插入位置不正确,插入失败*/
}
算法2.14

读者可将该算法和算法2.12相比较,除了一些描述方法有些区别外,算法思路是相同的。有关基于静态链表上的其它线性表的操作基本与动态链表相同,这里不再赘述。

如果引用本站的原创文章,请注明原文链接:,本站保留追究责任的权利!

发表评论