在图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<> {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相比较,除了一些描述方法有些区别外,算法思路是相同的。有关基于静态链表上的其它线性表的操作基本与动态链表相同,这里不再赘述。
|