2.3 线性表的链式存储结构

线性表的另一种存储形式是链式存储结构，链式存储结构中又有单（向）链表与双（向）链表。

2.3.1 单链表及其基本运算

1.单链表

线性表的链式存储结构简称链表，是用一组任意的存储单元（这组存储单元可以是连续的，也可以是不连续的）存储线性表中的数据元素。因此，为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（直接后继的存储位置）。由这两部分信息组成一个“结点”，如图2-4所示，表示线性表中一个数据元素ai。其中存储数据元素信息的域称为数据域，存储直接后继存储位置的域称为指针域。指针域中存储的信息又称为指针或链。

由分别表示a1,a2,…,an的n个结点依次相连构成的链表，称为线性表的链式存储表示，由于此类链表的每个结点中只包含一个指针域，故称为单链表或线性链表，如图2-5所示。

与顺序表类似，在链式存储结构中仍以第一个数据元素的存储地址作为线性表的基地址，并用一个指针指向它，该指针通常称为头指针，线性表中所有数据元素都可以从头指针出发找到。因为线性表的最后一个数据元素没有后继，因此最后一个结点中的“指针”为空指针（图中用Λ表示）。

出于对操作上方便性的考虑，在第一个结点之前附加一个“头结点”，令该结点中指针域的指针指向第一个表元素结点，并令头指针指向头结点，如图2-6（a）所示。

值得注意的是，若线性表为空，在不带头结点的情况下，头指针为空，但在带头结点的情况下，链表的头指针不为空，而是其头结点中指针域的指针为空，如图2-6（b）所示。

由上可见，单链表可以由头指针唯一确定，其存储结构描述如下。

typedef struct Lnode    / * 结点类型定义 * /
{ ElementType data;
  struct Lnode *next;
}ListNode;
typedef ListNode *LinkList;/ * LinkList为指向ListNode的指针类型* /

若head是指向某一单链表的头指针，则可用下列语句声明：

LinkList head;

它指向表中第一个结点（对于带头结点的单链表，则指向单链表的头结点），若head=NULL（对于带头结点的单链表为head->next=NULL），则表示单链表为一个空表，其长度为0。若不是空表，则可以通过头指针访问表中的任意结点，获得相应结点数据域的值。对于带头结点的单链表head，p=head->next指向表中的第一个结点a1，即p->data表示a1，而p->next指向a2，p->next->data表示a2，依次类推。

2.单链表上基本运算的实现

（1）查找运算。在带头结点的单链表中查找（数据域的）值为x的结点，若找到，则返回指向该结点的指针，否则返回NULL。查找过程从单链表的头指针指向的头结点出发，顺着链逐个将结点的值与给定值x作比较。

具体算法描述如下。

LinkList Locate( LinkList head,ElemType x)
/ * 在带头结点的单链表head中查找值为x的结点* /
{  p=head->next; / * 从表中第一个结点查找起 * /
   while (p!=NULL && p->data!=x)
      p=p->next;  / * 指针后移* /
   return p;
}/ * Locate * /

算法的平均时间复杂度为O(n)，n为单链表的结点数。

（2）单链表插入操作。在带头结点的单链表head中第i个数据元素之前插入一个数据元素x，需要首先在单链表中找到第i-1个结点（由pre指向该结点），然后申请一个新的结点（由p指向该结点），其数据域的值为x，并修改第i-1个结点的指针使其指向p，然后使p结点的指针域指向第i个结点。插入过程如图2-7所示。具体算法描述如下。

void InsList(LinkList head,int i,ElemType x)
/*在带头结点的单链表head中第i个位置（前）插入值为x的新结点*/
{
    pre=head;k=0;
    while (pre!=NULL && k<i-1)
   /*查找第i-1个结点，并由pre指向该结点*/
   {  pre=pre->next;
      k=k+1;
   }
   if (k!=i-1 || pre==NULL)  /*没有第i-1个结点*/
         printf("Error")；
      else
      {  p=(LinkList)malloc(sizeof(ListNode));
         p->data=x;
         p->next=pre->next;
         pre->next=p
    }
}/* InsList */

单链表中有n个结点时，则（前）插入操作的插入位置有n+1个，即1≤i≤n+1。当i=n+1时，则认为是在表尾插入一个结点。该算法的平均时间复杂度为O(n)。

（3）删除。在带头结点的单链表head中删除第i个结点，则首先要找到第i-1个结点并使pre指向第i-1个结点，而后删除第i个结点并释放结点空间。删除过程如图2-8所示。具体算法描述如下。

void DelList(LinkList head,int i)
/*在带头结点的单链表head中删除第i个结点*/
{
    pre=head;k=0;
    while(pre->next!=NULL && k<i-1)
    {  pre=pre->next;
       k=k+1;
    }
    if(!(pre->next) && k<=i-1)    /* 没有第i个结点*/
          printf("Error");
    else
    {  p=pre->next;
       pre->next=pre->next->next;  /*删除结点p*/
       free(p); /*释放结点所占空间*/
    }
} /* DelList */

单链表中有n个结点，则删除操作的删除位置有n个，即1≤i≤n。该算法的平均时间复杂度为O(n)。

以上3个基本运算均是在带头结点的单链表上实现的。下面仅以删除操作为例，给出其在不带头结点的单链表上的实现。希望读者能够比较出单链表带头结点后算法的简洁之处。

LinkList DelList(LinkList head,int i)
/*在不带头结点的单链表head中删除第i个结点*/
{  if (head==NULL)
   {  printf(“Empty link”);
      return(NULL);
   }
   if (i==1)
   {  p=head;
      head=head->next;
      free(p);
      return(head);
   }
   pre=head;k=0;
   while(pre->next!=NULL && k<i-1)
   {  pre=pre->next;
      k=k+1;
   }
   if(!(p->next) && k<=i-1)   /* 没有第i个结点*/
         printf(“Inexistent node”);
   else
   {  p=pre->next;
      pre->next=pre->next->next; /*删除结点p*/
      free(p); /*释放结点所占空间*/
   }
   return(head);
} /* DeleList */

【例2-2】输入一批值作为单链表中结点数据域的值，写一算法，建立相应的带头结点的单链表。

要建立一带头结点的单链表，可考虑使用如下两种方法。一是首先建一带头结点的空单链表，然后逐一将元素插入到第一个结点之前；二是先建一不带头结点的单链表（每次将元素作为第一个结点插入），然后建立头结点，并链接前面所建的单链表。实际上前一种方法在建立了头结点之后，就是反复地调用插入算法。下面所用的是后一种方法。

LinkList Create()
/*建一带头结点的单链表*/
{  p=q=NULL;
   /*p指向新结点，用于存放输入的数据；q指向构造过程中的单链表的链首*/
   scanf(&x);
   while (x!=FLAG)
   /* FLAG为一与x类型相同的特殊值（作为输入数据的结束标志用）*/
   {
      p=(LinkList)malloc(sizeof(ListNode));
      p->data=x;
      p->next=q
      q=p;
      scanf(&x);
   }
   head=(LinkList)malloc(sizeof(ListNode))
   head->next=p;
   return (head);
}/* Create */

2.3.2 循环链表

循环单链表是单链表的另一种形式，其特点是表中最后一个结点的指针不再是空，而是指向头结点（带头结点的单链表）或第一个结点（不带头结点的单链表），整个链表形成一个环，这样从表中任意结点出发都可找到其他的结点。考虑到各种操作实现的方便性，循环单链表一般均指带头结点的循环单链表。如图2-9（a）所示为带头结点的循环单链表的空表表示，如图2.9（b）所示为带头结点的循环单链表的非空表表示。循环单链表的存储结构描述（类型定义）与单链表的完全相同。

循环链表的基本操作的实现和单链表的基本一致，差别仅在于判别链表中最后一个结点的条件不再是“后继是否为空”（p!=NULL或p->next!=NULL），而是“后继是否为头结点”（p!=head或p->next!=head）。

【例2-3】对如图2-10（a）所示的两个循环链表，写一算法实现两个链表的合并。合并后ra链表在前，rb链表在后，如图2-10（b）所示。

要合并ra链表与rb链表，并使得rb链接在ra的尾部，也就是ra链表的尾结点的指针指向rb链表的第一个结点，rb链表的尾结点的指针指向ra链表的头结点，需引入两个指针pra与prb分别指向ra与rb的尾结点。合并算法描述如下。

void Merge(LinkList ra,LinkList rb)
/*将循环单链表ra、rb合并，合并后ra在前rb在后*/
{
    pra=ra->next;
    while (pra->next!=ra) /*移动pra使其指向ra表的尾结点*/
         pra=pra->next;
    prb=rb->next;
    while (prb->next!=rb) /*移动prb使其指向rb表的尾结点*/
         prb=prb-->next;
    prb->next=ra;
    pra->next=rb—>next;
    free(rb);
}/* Merge */

合并后的循环链表如图2-10（b）所示。如果ra链表与rb链表中元素的个数分别是m与n，则算法的时间复杂度是O(m+n)。

2.3.3 双向链表

在以上讨论的单链表中，每个结点只有一个指向其后继的指针域，因此，在这样的结构上查找某一结点的后继所需的时间复杂度是O(1)，而查找某一结点的前驱所需的时间复杂度是O(n)。为了克服单链表这种单向性的缺点，可利用双向链表。

双向链表中的每个结点都有两个指针域，一个指向其后继，另一个指向其前驱，双向链表的结点结构如图2-11所示，其相应的类型描述如下。

typedef struct DNode
{   ElemType data；
   struct DNode *prior，*next；
}DoubleNode,* DoubleList；

双向链表与单链表类似，也有循环表，考虑到算法的方便性，一般使用带头结点的双向循环链表。如图2-12（a）所示是带头结点的空双向循环链表，图2.12（b）所示是带头结点非空双向循环链表。

在双向链表中，那些只涉及后继指针的算法，如求表长度，获取表中的第i个元素，元素定位（获取某一元素的位置）等，与单链表中相应的算法相同。但对于插入和删除操作，则涉及前驱和后继两个方向的指针变化，因此与单链表中的算法有所不同。

插入操作时（在第i个结点之前插入值为x的结点），首先定位第i个结点并由p指向它，如图2-13（a）所示，然后修改指针，如图2-13（b）所示。下面是插入算法。

void DlinkIns(DoubleList head,int i,ElemType x)
/*带头结点的双向循环链表由head指向，在head中的第i个结点前插入值为x的新结点*/
{
    p=head->next;k=1;
    while (p!=head && k<i)
    /*查找第i个结点，并由p指向该结点*/
    {  p=p->next;
       k=k+1;
    }
    if(k!=i)  /*没有第i个结点*/
         printf("Error")；
    else
    {
         s=(DoubleList)malloc(sizeof(DoubleNode));
         s->data=x;
         s->prior=p->prior;
         p->prior->next=s;
         s->next=p;
         p->prior=s;
    }
}/* DlinkIns */

双向循环链表的删除操作与插入操作类似，首先也是定位第i个结点并由p指向它，然后修改指针。定位第i个结点的过程与插入完全相同，如图2-14（a）所示。指针的修改与插入时不同，只需修改两个指针，如图2-14（b）所示，最后释放第i个结点的空间，相应的操作语句如下。

p->prior->next=p-->next;p->next->prior=p->prior;free(p);