2.4.1 静态链表的存储结构

静态链表可通过一维数组来描述，用游标模拟指针。游标的作用就是指示元素的直接后继。这里的游标的数据类型不再是指针类型，而是一个整型。

要实现静态链表，通过一个结构体数组描述结点，结点包括两个域：数据域和指针域。数据域用来存放结点的数据信息，指针域指向直接后继元素。静态链表的类型描述如下：

在以上静态链表的类型定义中，SListNode是一个结点类型，SLinkList是一个静态链表类型，av是备用链表的指针，即av指向静态链表中一个未使用的位置。数组的一个分量（元素）表示一个结点，游标cur代替指针指示结点在数组中的位置。数组的第0个分量可以表示成头结点，头结点的cur域指向表中第一个结点。表中的最后一个结点的指针域为0，指向头结点，这样就构成一个静态循环链表。

例如，线性表（Yang,Zheng,Feng,Xu,Wu,Wang,Geng）采用静态链表存储的情况如图2.33所示。

假设s为SlinkList类型变量，则s[0].cur指示第一个结点在数组的位置，如果i=s[0].cur，则s[i].data表示表中的第一个元素，s[i].cur指示第二个元素在数组的位置。与动态链表的操作类似，游标cur代表指针next，i=s[i].cur表示指针后移，相当于p=p->next。

图2.33 静态链表