零基础学数据结构第2版（零基础学编程）最新章节_陈锐著

3.6　静态链表

前面介绍的各种链表结点的分配与释放都是由函数malloc和free动态实现，因此称为动态链表。但是有的高级程序设计语言（如Basic、Fortran等）没有指针类型，就不能利用上述办法动态地创建链表，可以巧妙利用静态链表实现动态链表的功能。本节主要介绍静态链表的存储结构及实现。

3.6.1　静态链表的存储结构

可利用一维数组实现静态链表，其类型说明如下。

#define ListSize 100
typedef struct
{
    DataType data;
    int cur;
}SListNode;
typedef struct
{
    SListNode list[ListSize];
    int av;
}SLinkList;

在以上静态链表的类型定义中，数组的一个分量表示一个结点，同时用游标（指示器cur）代替指针指示结点在数组中的相对位置。数组的第0分量可看成是头结点，其指针域指示链表的第一个结点。表中的最后一个结点的指针域为0，指向头结点，这样就构成一个静态循环链表。

SListNode是一个结点类型，SLinkList是一个静态链表类型，av是备用链表的指针，即av指向静态链表中一个未使用的位置。这种描述方法便于在不设“指针”类型的高级程序设计语言中使用链表结构。例如，线性表（Yang，Zheng，Feng，Xu，Wu，Wang，Geng）的静态链表存储情况如图3-35所示。

图3-35　静态链表

设s为SlinkList类型的变量，则s[0].cur指示头结点，如果令i=s[0].cur，则s[i].data表示表中的第1个元素“Yang”，s[i].cur指示第2个元素在数组的位置。这与动态链表的操作类似，i=s[i].cur将指针向前移动，相当于p=p->next操作，游标cur代表指针next。

3.6.2　静态链表的基本运算

①初始化静态链表。只需要让静态链表的游标cur指向下一个结点，并将链表的最后一个结点的cur域置为0。初始化静态链表的算法实现如下。

void InitSList(SLinkList *L)
/*
静态链表的初始化*/
{
     int i;
     for(i=0;i<ListSize;i++)
         (*L).list[i].cur=i+1;
     (*L).list[ListSize-1].cur=0;
     (*L).av=1;
}

②分配结点。从备用链表中取出一个结点空间，分配给要插入链表中的元素，并返回要插入结点的位置。分配结点的算法实现如下。

int AssignNode(SLinkList L)   
/*
从备用链表中取下一个结点空间，分配给要插入链表中的元素*/
{
    int i;
    i=L.av;
    L.av=L.list[i].cur;
    return i;
}

③回收结点。结点用过之后，要将空闲结点回收，以便其他结点使用，使其称为备用链表的空间。回收结点的算法实现如下。

void FreeNode(SLinkList L,int pos)
/*
将空闲结点插入备用链表*/
{
    L.list[pos].cur=L.av;
    L.av=pos;
}

④插入操作。在静态链表中第i个位置插入一个数据元素e。首先从备用链表中取出一个可用的结点，然后将其插入静态链表的第i个位置。

例如，在图3-36所示的静态链表中的第5个元素后插入元素“Hao”，首先从备用链表中取出一个空闲结点，即k=L.av，图3-36中为数组编号为8的结点；再使备用链表指向下一个有用结点，修改备用链表指针，使其指向下一个结点，即L.av=L.list[k].cur；然后把元素“Hao”放在新空闲结点中，即（*L）.list[k].data=e；再将新结点插入到对应的位置，这需要先找到前一个结点，让前一个结点的cur域指向新结点，然后让新结点的cur域指向下一个结点，图3-36中为L.list[5].cur=L.list[8].cur，L.list[8].cur=6。插入过程如图3-36所示。

图3-36　在静态链表中插入元素后

插入操作的算法实现如下。

void InsertSList(SLinkList *L,int i,DataType e)   
/*
插入操作*/
{ 
     int j,k,x;
     k=(*L).av;
     (*L).av=(*L).list[k].cur;
     (*L).list[k].data=e;
     j=(*L).list[0].cur;
     for(x=1;x<i-1;x++)
          j=(*L).list[j].cur;
      (*L).list[k].cur=(*L).list[j].cur;
      (*L).list[j].cur=k;
}

⑤删除操作。将静态链表中第i个位置的元素删除分为两种情况，如果删除的是第1个结点，则将头结点的cur域指向第2个结点，代码如下。

k=(*L).list[0].cur;
(*L).list[0].cur=(*L).list[k].cur;

如果删除的不是第1个结点，则先找到第i-1个元素的位置，修改cur域使其指向第i＋1个元素，例如要删除图3-37所示的静态链表中的第3个元素，需要根据游标找到第2个元素，将其cur域修改为第4个元素的位置，即L.list[2].cur=L.list[3].cur。算法实现代码如下。

j=(*L).list[0].cur;
for(x=1;x<i-1;x++)
     j=(*L).list[j].cur;
k=(*L).list[j].cur;
(*L).list[j].cur=(*L).list[k].cur;

然后将被删除的结点空间放到备用链表中。

(*L).list[k].cur=(*L).av;
 (*L).av=k;

删除第3个结点的操作如图3-37所示。

图3-37　删除静态链表的第3个结点

删除操作的实现代码如下。

void DeleteSList(SLinkList *L,int i,DataType*e)   
/*
删除操作*/
{
                int j,k,x;
                if(i==1)
                {
                        k=(*L).list[0].cur;
                        (*L).list[0].cur=(*L).list[k].cur;
                }
                else
                {
                        j=(*L).list[0].cur;
                        for(x=1;x<i-1;x++)
                                j=(*L).list[j].cur;
                        k=(*L).list[j].cur;
                        (*L).list[j].cur=(*L).list[k].cur;
                }
                (*L).list[k].cur=(*L).av;
                *e=(*L).list[k].data;
                (*L).av=k;
}

3.6.3　静态链表应用举例

【例3-8】利用静态链表的基本操作创建静态链表，通过键盘输入要插入的元素及位置向静态链表中插入元素，通过输入删除元素的位置删除静态链表中的元素。例如，创建一个静态链表{20，15，-82，37，52，8，-90}，在静态链表的第6个位置插入元素85后，静态链表变为{20，15，-82，37，52，85，8，-90}，输入1，删除第1个元素，静态链表变为{15，-82，37，52，85，8，-90}。

【分析】静态链表的插入和删除操作与单链表的操作类似，静态链表通过k=L.list[k].cur找到链表元素的下一个元素，插入和删除只需要修改静态链表的cur域。以上操作都可通过调用静态链表的基本操作实现，在插入元素的过程中，需要从备用链表中取出可用结点；在删除元素的过程中，需要注意将删除结点空间放入备用链表。程序的实现代码如下。

/*
包含头文件*/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
/*
静态链表类型定义*/
typedef int DataType;
#define ListSize 100
typedef struct
{
    DataType data;
    int cur;
}SListNode;
typedef struct
{
    SListNode list[ListSize];
    int av;
}SLinkList;
#include "SLinkList.h"
/*
函数声明*/
void PrintDList(SLinkList L,int n);
void main()
{
    SLinkList L;
    int i,num;
                int pos;
                int e;
                DataType a[]={20,15,-82,37,52,8,-90};
                num=sizeof(a)/sizeof(a[0]);
                InitSList(&L);
                for(i=1;i<=num;i++)
                        InsertSList(&L,i,a[i-1]);
    printf("
静态链表中的元素:");
                PrintDList(L,num);
                printf("
请输入要插入的元素及位置:");
                scanf("%d",&e);
                getchar();
                scanf("%d",&pos);
                getchar();
                InsertSList(&L,pos,e);
                printf("
插入元素后,
静态链表中的元素:");
                PrintDList(L,num+1);
                printf("
请输入要删除元素的位置:");
                scanf("%d",&pos);
                getchar();
                DeleteSList(&L,pos,&e);
                printf("
元素%d
已被删除。\n",e);
                printf("
删除元素后,
静态链表中的元素:");
                PrintDList(L,num);
}
void PrintDList(SLinkList L,int n)
/*
输出静态链表中的所有元素*/
{
                int j,k;
                k=L.list[0].cur;
                for(j=1;j<=n;j++)
                {
                        printf("%4d",L.list[k].data);
                        k=L.list[k].cur;
                }
                printf("\n");
}

程序运行结果如图3-38所示。

图3-38　静态链表插入与删除操作的程序运行结果

3.6 静态链表

3.6.1 静态链表的存储结构

3.6.2 静态链表的基本运算

3.6.3 静态链表应用举例

3.6　静态链表

3.6.1　静态链表的存储结构

3.6.2　静态链表的基本运算

3.6.3　静态链表应用举例