2.3 线性表的链式存储及其操作的实现_数据结构（C语言版）-QQ阅读男生科幻网

书名：数据结构（C语言版）
作者名：邓文华主编
本章字数：6056字
更新时间：2020-08-28 01:27:57

2.3 线性表的链式存储及其操作的实现

由于顺序表的存储特点是用物理上的相邻关系实现逻辑上的相邻关系，它要求用连续的存储单元顺序存储线性表中各元素，因此，在对顺序表插入、删除时，需要通过移动数据元素来实现，影响了运行效率。本节介绍线性表的链式存储结构，它不需要用地址连续的存储单元来实现，因为它不要求逻辑上相邻的两个数据元素在物理上也相邻。在链式存储结构中，数据元素之间的逻辑关系是通过“链”来连接的，因此对线性表的插入、删除不需要移动数据元素。

2.3.1 单链表

链表是通过一组任意的存储单元来存储线性表中的数据元素的，那么怎样表示数据元素之间的线性关系呢？即如何来“链”接数据元素间的逻辑关系呢？为此在存储数据元素时，对每个数据元素ai，除了存放数据元素的自身信息ai之外，还需要和ai一起存放其后继数据元素ai+1所在的存储单元的地址，这两部分信息组成一个“结点”，结点的结构如图2.6所示，每个数据元素都如此。存放数据元素自身信息的单元称为数据域，存放其后继元素地址的单元称为指针域。因此n个元素的线性表通过每个结点的指针域拉成了一个“链子”，称之为链表。如图2.6所示，每个结点中只有一个指向后继的指针，所示称其为单链表。

图2.6 单链表结点的结构

链表是由结点构成的，结点定义如下：

typedef struct node
{ datatype data;                /*存放数据元素*/
           struct node *next;   /*存放下一个结点的地址*/
} LNode *LinkList；

定义头指针变量：

LinkList H；

如图2.7所示是线性表（a1, a2, a3, a4, a5, a6, a7, a8）对应的链式存储结构示意图。

图2.7 链式存储结构示意图

当然，必须将第一个结点的地址160放到一个指针变量中，如H中，最后一个结点没有后继，其指针域必须置空（即NULL），表明此表到此结束，这样就可以从第一个结点的地址开始“顺藤摸瓜”，找到表中的每个结点。

作为线性表的一种存储结构，人们关心的是结点间的逻辑结构，而并不关心每个结点的实际地址，所以通常的单链表用图2.8的形式表示而不用图2.7的形式表示，其中，符号∧表示空指针（下同）。

实际应用中通常用“头指针”来标识一个单链表，如单链表L、单链表H等，是指某链表的第一个结点的地址放在指针变量L、H中，头指针为“NULL”则表示一个空表。

需要进一步指出的是：上面定义的LNode是结点的类型，LinkList是指向LNode类型结点的指针类型。为了增强程序的可读性，通常将标识一个链表的头指针定义为LinkList类型的变量，如LinkList L。当L有定义时，值要么为NULL（表示一个空表），要么为第一个结点的地址，即链表的头指针。将操作中用到指向某结点的指针变量说明为：LNode *类型，如

LNode *p；

则语句p=malloc(sizeof(LNode));完成了申请一块 LNode 类型的存储单元的操作，并将其地址赋值给指针变量p。如图2.9所示，p所指的结点为*p，*p的类型为LNode型，所以该结点的数据域为(*p).data或p->data，指针域为(*p).next或p->next，而语句free(p);则表示释放p所指的结点。

图2.8 链表示意图

图2.9 申请一个结点

2.3.2 单链表基本操作的实现

1.建立单链表

（1）在链表的头部插入结点建立单链表

链表与顺序表不同，它是一种动态管理的存储结构，链表中的每个结点占用的存储空间不是预先分配的，而是运行时系统根据需求生成的，因此建立单链表要从空表开始，每读入一个数据元素则申请一个结点，然后插在链表的头部，如图2.10展现了线性表（25, 45, 18, 76, 29）的链表的建立过程，因为是在链表的头部插入，读入数据的顺序和线性表中的逻辑顺序是相反的。

图2.10 在头部插入结点建立单链表

算法2.7 单链表的建立算法（头部插入）。

LinkList Creat_LinkList1( )
     {  LinkList L=NULL；                   /*空表L为表头*/
        LNode *s;
        int x;                              /*设数据元素的类型为int */
        scanf("%d", &x);
        while (x!=flag)                     /*设flag为数据元素输入结束的标志*/
          { s=malloc(sizeof(LNode));        /*为插入元素申请空间*/
            s->data=x;                      /*将插入元素置入申请到的单元中*/
            s->next=L; L=s;
            scanf ("%d", &x);
           }
        return L;
}

（2）在单链表的尾部插入结点建立单链表

头部插入建立单链表简单，但读入的数据元素的顺序与生成的链表中元素的顺序是相反的，若希望次序一致，则用尾部插入的方法。因为每次操作都是将新结点插入到链表的尾部，所以需加入一个指针 R 用来始终指向链表中的尾结点。如图2.11展现了在链表尾部插入结点建立链表的过程。

图2.11 在尾部插入建立单链表

算法思路：初始状态时，头指针H=NULL，尾指针R=NULL，按线性表中元素的顺序依次读入数据元素，不是结束标志时，申请结点，将新结点插入到R所指结点的后面，然后R指向新结点（但第一个结点有所不同，读者注意下面算法中的有关部分）。

算法2.8 单链表的建立算法（尾部插入）。

LinkList Creat_LinkList2( )
   { LinkList L=NULL;
         LNode *s, *R=NULL;
         int x;                                   /* 设数据元素的类型为int */
         scanf("%d", &x);
         while (x!=flag)                          /* 设flag为数据元素输入结束的标志 */
            { s=malloc(sizeof(LNode)); s->data=x; /*申请空间并将插入元素置入该单元*/
              if (L==NULL) L=s;                   /*第一个结点的处理*/
             else R->next=s;                      /*其他结点的处理*/
             R=s;                                 /*R指向新的尾结点*/
             scanf("%d", &x);
          }
        if ( R!=NULL) R->next=NULL;               /*对于非空表，最后结点的指针域放空指针*/
        return L;
}

（3）在带头结点单链表的表尾插入元素建立单链表

在上面的算法中，第一个结点的处理和其他结点是不同的，原因是第一个结点加入时链表为空，它没有直接前趋结点，它的地址就是整个链表的指针，需要放在链表的头指针变量中；而其他结点有直接前趋结点，其地址放入直接前趋结点的指针域。“第一个结点”的问题在很多操作中都会遇到，如在链表中插入结点时，将结点插在第一个位置和其他位置是不同的，在链表中删除结点时，删除第一个结点和其他结点的处理也是不同的。

为了方便操作，有时在链表的头部加入一个“头结点”，头结点的类型与数据结点一致，标识链表的头指针变量L中存放该结点的地址，这样即使是空表，头指针变量L也不为空了。头结点的加入使得“第一个结点”的问题不再存在，也使得“空表”和“非空表”的处理一致。

头结点的加入完全是为了操作的方便，它的数据域无定义，指针域中存放的是第一个数据结点的地址，当空表时该指针域为空。

图2.12（a）和图2.12（b）分别是带头结点的单链表空表和非空表的示意图。

图2.12 带头结点的单链表

算法2.9 带头结点的单链表的建立算法。

LinkList Creat_LinkList3( )
    { LinkList L;
    LNode *R;
    int x;                                  /*设数据元素的类型为int */
    L=（LinkList）malloc(sizeof(Lnode));    /*申请头结点空间 */
    L->next=NULL；                          /*初始化，置空表*/
    R=L；
    scanf("%d", &x);
    while (x!=flag)
        { R->next=malloc(sizeof(LNode));    /*为插入元素申请空间*/
          R->next->data=x ；                /*将插入元素置入该单元*/
          R=R->next;                        /*R指向新的尾结点*/
          scanf("%d", &x);
        }
      R->next=NULL；                        /*置表尾结点的next指针为空*/
      return L;
}

2.求表长

算法思路：设一个移动指针p和计数器j，初始化后，p所指结点后面若还有结点，p向后移动，计数器加1。

（1）设L是带头结点的单链表（线性表的长度不包括头结点）。

算法2.10 求带头结点单链表的长度算法。

int Length_LinkList1(LinkList L)
   { LNode *p=L;                  /* p指向头结点*/
     int j=0;
     while (p->next)
          { p=p->next; j++ }      /* p所指的是第j个结点*/
     return j;
}

（2）设L是不带头结点的单链表。

算法2.11 求不带头结点单链表的长度算法。

int Length_LinkList2 (LinkList L)
    { LNode *p=L;
      int j;
      if (p==NULL) return 0;      /*空表的情况*/
      j=1;                        /*在非空表的情况下，p所指的是第一个结点*/
      while (p->next )
            { p=p->next; j++ }
      return j;
}

从上面两个算法中看到，不带头结点的单链表空表情况要单独处理，而带上头结点之后则不用了。在以后的算法中不加说明则认为单链表是带头结点的。这两个算法的时间复杂度均为O(n)。

3.查找操作

（1）按序号查找Get_LinkList(L, i)。

算法思路：从链表的第一个元素结点起，判断当前结点是否是第i个，若是，则返回该结点的指针，否则继续查找下一个结点，直到表结束为止。若没有第i个结点，则返回空指针。

算法2.12 单链表按序号查找元素算法。

LNode *Get_LinkList(LinkList L, Int i);
                    /*在单链表L中查找第i个元素结点，找到返回其指针，否则返回空指针*/
    { LNode *p=L;
      int j=0;
      while (p->next !=NULL && j<i )
          { p=p->next;  j++; }
      if (j==i) return p;
       else return NULL;
}

（2）按值查找即定位 Locate_LinkList(L, x)。

算法思路：从链表的第一个元素结点起，判断当前结点的值是否等于x，若是，则返回该结点的指针，否则继续查找下一结点，直到表结束为止。若没有找到值为x的结点，则返回空指针。

算法2.13 单链表的元素定位算法。

LNode *Locate_LinkList( LinkList L, datatype x)
                   /*在单链表L中查找值为x的结点，找到后返回其指针，否则返回空指针*/
    { LNode *p=L->next;
      while ( p!=NULL && p->data != x)
          p=p->next;
      return p;
    }

上述两算法的时间复杂度均为O(n)。

4.插入操作

（1）后插结点：设p指向单链表中某结点，s指向待插入的值为X的新结点，将*s插入到*p的后面，插入示意图如图2.13所示。

操作如下：

① s->next=p->next;

② p->next=s;

注意：两个指针的操作顺序不能交换。

（2）前插结点：设p指向链表中某结点，s指向待插入的值为X的新结点，将*s插入到*p的前面，插入示意图如图2.14所示，与后插不同的是：首先要找到*p的前趋*q，然后完成在*q之后插入*s，设单链表头指针为L，操作如下：

图2.13 在*p之后插入*s

图2.14 在*p之前插入*s

q=L;
① while (q->next!=p)
        q=q->next;    /*找*p的前趋*/
② s->next=q->next;
③ q->next=s;

后插操作的时间复杂度为O(1)，前插操作因为要找*p的前趋，时间复杂度为O(n)；其实人们关心的是数据元素之间的逻辑关系，所以仍然可以将*s插入到*p的后面，然后将p->data与s->data交换即可，这样既满足了逻辑关系，又能使得时间复杂度为O(1)。

（3）插入运算Insert_LinkList(L, i, x)。

算法思路：

① 找到第i-1个结点；若存在则继续步骤②，否则结束；

② 申请、填装新结点；

③ 将新结点插入，结束。

算法2.14 单链表的元素插入算法。

int Insert_LinkList( LinkList L, int i, datatype x)
                                         /*在单链表L的第i个位置上插入值为x的元素*/
{ LNode * p, *s;
  p=Get_LinkList(L, i-1);                     /*查找第i-1个结点*/
  if (p==NULL)
        { printf("参数i错")； return 0； }    /*第i-1个点不存在，不能插入*/
   else {
         s=malloc(sizeof(LNode))；            /*申请、填装结点*/
         s->data=x；
         s->next=p->next；                    /*新结点插入在第i-1个结点的后面*/
         p->next=s；
         return 1；
      }
  }

上述算法的时间复杂度为O(n)。

5.删除操作

（1）删除结点：设p指向单链表中某结点，删除*p。其操作示意图如图2.15所示。通过示意图可见，要实现对结点*p的删除，首先要找到*p的前趋结点*q，然后完成指针的操作即可。删除结点的操作由下列语句实现：

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

显然，找*p前趋结点的时间复杂度为O(n)。

若要删除*p的后继结点（假设存在），则可以直接完成：

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

该操作的时间复杂度为O(1) 。

（2）删除运算：Del_LinkList(L, i)。

算法思路：

① 找到第i-1个结点；若存在则继续步骤②，否则结束；

② 若存在第i个结点则继续步骤③，否则结束；

③ 删除第i个结点，结束。

算法2.15 单链表的元素删除算法。

int Del_LinkList(LinkList L，int i)     /*删除单链表L上的第i个数据结点*/
   { LinkList p, s;
     p=Get_LinkList(L, i-1);            /*查找第i-1个结点*/
     if (p==NULL)
         { printf("第i-1个结点不存在"); return -1; }
     else if (p->next==NULL)
              { printf("第i个结点不存在"); return 0; }
           else
              { s=p->next;              /*s指向第i个结点*/
                p->next=s->next;        /*从链表中删除*/
                free(s);                /*释放s */
                return 1;
              }
}

算法2.15的时间复杂度为O(n)。

图2.15 删除*p

通过上面的基本操作可知：

①在单链表上插入、删除一个结点，必须知道其前趋结点；

②单链表不具有按序号随机访问的特点，只能从头指针开始按结点顺序进行。

2.3.3 循环链表

对于带头结点的单链表而言，最后一个结点的指针域是空指针，如果将该链表头指针置入该指针域，则使得链表头尾结点相连，就构成了单循环链表，如图2.16所示。

图2.16 带头结点的单循环链表

在单循环链表上的操作基本与非循环链表相同，只是将原来判断指针是否为NULL变为判断指针是否为头指针而已，没有其他较大的变化。

对于单链表，只能从头结点开始遍历整个链表；而对于单循环链表，则可以从表中任意结点开始遍历整个链表。不仅如此，有时对链表常做的操作是在表尾、表头进行的，此时可以改变一下链表的标识方法，不用头指针而用一个指向尾结点的指针R来标识，这样在许多时候可以提高操作效率。

例如，对两个单循环链表H1、H2的连接操作，是将H2的第一个数据结点接到H1的尾结点，如果用头指针标识，则需要找到第一个链表的尾结点，其时间复杂度为O(n)，而链表若用尾指针R1、R2来标识，则时间复杂度为O(1)。操作如下：

p= R1->next;               /*保存R1的头结点指针*/
R1->next=R2->next->next;   /*头尾连接*/
free(R2->next);            /*释放第二个表的头结点*/
R2->next=p;                /*组成循环链表*/

这一过程如图2.17所示。

图2.17 两个用尾指针标识的单循环链表的连接

2.3.4 双向链表

单链表的结点中只有一个指向其后继结点的指针域next，因此，若已知某结点的指针为p，其后继结点的指针则为p->next，而找其前趋则只能从该链表的头指针开始，顺着各结点的next域进行，也就是说，找后继的时间复杂度是O(1)，而找前趋的时间复杂度是O(n)，如果希望找前趋的时间复杂度达到O(1)，则只能付出空间的代价：每个结点再加一个指向前趋的指针域，结点的结构如图2.18所示，用这种结点组成的链表称为双向链表。

图2.18 双向链表的结点结构

双向链表结点的定义如下：

typedef struct dLNode
             { datatype data;
               struct dLNode *prior, *next;
             } DLNode, *DLinkList;

和单链表类似，双向链表通常也用头指针标识，也可以带头结点或做成循环结构，图2.19是带头结点的双向循环链表示意图，显然，通过某结点的指针p即可以直接得到它的后继结点的指针p->next，也可以直接得到它的前趋结点的指针p->prior。这样，在有些操作中需要找前趋时，则不需要再用循环。从下面的插入删除操作中可以看到这一点。

图2.19 带头结点的双循环链表

设p指向双向循环链表中的某一结点，即p中存储的是该结点的指针，则p->prior->next表示的是*p结点之前趋结点的后继结点的指针，即与p相等；类似地，p->next->prior表示的是*p结点之后继结点的前趋结点的指针，也与p相等，所以有以下等式：

p->prior->next=p=p->next->prior

双向链表中结点的插入：设p指向双向链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的前面，其插入过程如图2.20所示。

操作如下：

① s->prior=p->prior;

② p->prior->next=s;

③ s->next=p;

④ p->prior=s;

指针操作的顺序不是唯一的，但也不是任意的，操作①必须要放到操作④的前面完成，否则*p的前趋结点的指针就丢掉了。读者把每条指针操作的含义搞清楚，就不难理解了。

双向链表中结点的删除：设p指向双向链表中某结点，删除*p。其删除操作过程如图2.21所示。

图2.20 双向链表中的结点插入

图2.21 双向链表中的结点删除

操作如下：

① p->prior->next=p->next;

② p->next->prior=p->prior;

free(p);

2.3.5 单链表的其他操作举例

【例2.4】已知单链表H，写一算法将其元素倒置，即实现如图2.22所示的操作，其中图2.22（a）为倒置前的状态，图2.22（b）为倒置后的状态。

图2.22 单链表的倒置

算法思路：依次取原链表中的每个结点，将其作为第一个结点插入到新链表中去，指针p用来指向当前结点，p为空时结束。

算法2.16 单链表的倒置算法。

void reverse ( Linklist H )
    { LNode *p, *q;
      p=H->next;                  /*p指向第一个数据结点*/
      H ->next=NULL;              /*将原链表置为空表H*/
     while ( p )
         { q=p;  p=p->next;
          q ->next=H->next;       /*将当前结点插到头结点的后面*/
          H ->next=q;
        }
}

该算法只是对链表顺序扫描一遍即完成了倒置，所以时间复杂度为O(n)。

【例2.5】已知单链表H，写一算法，删除链表中重复元素结点，即实现如图2.23所示的操作。图2.23（a）为删除前的单链表，图2.23（b）为删除后的单链表。

算法思路：用指针p指向链表的第一个数据结点，用另一个指针q从p的后继结点开始搜索到表尾，依次找出与p所指结点的值相同的结点并将其删除；然后p指向下一个结点，继续用q指针寻找与p所指结点值相同的结点并将其删除；依此类推，直到p指向最后结点时算法结束。

图2.23 删除重复结点

算法2.17 剔除单链表中的重复元素算法。

void pur_LinkList (LinkList H)
    { LNode *p, *q, *r；
      p=H->next;                            /*p指向第一个结点*/
      if (p== NULL) return；
      while (p->next)
          { q=p;
      while (q ->next)                      /*从*p的后继开始找重复结点*/
          { if (q ->next->data== p->data)
               { r=q ->next;                /*找到重复结点，用r指向，删除*r */
                 q ->next=r ->next;
                 free( r );
               }
            else q=q ->next;
           }                                /*while(q->next)*/
          p=p->next;                        /*p指向下一个，继续*/
           }                                /*while(p->next)*/
}

该算法的时间复杂度为O(n2)。

【例2.6】设有两个单链表A、B，其中元素递增有序，编写算法将A、B归并成一个按元素值递减（允许有相同值）有序的链表C，要求用A、B中的原结点形成，不能重新申请结点。

算法思路：利用A、B两表有序的特点，依次进行比较，将当前值较小者摘下，插入到C表的头部，得到的C表则为递减有序的。

算法2.18 有序单链表的合并算法。

LinkList merge(LinkList A, LinkList B)      /*设A、B均为带头结点的单链表*/
        {  LinkList C;
        LNode *p，*q，*s；
        p=A->next； q=B->next；
        C=A;  C->next=NULL;                 /*C表的头结点*/
        free ( B ) ;
        while (p&&q)
           { if (p->data<q->data)
              { s=p；p=p->next； }
           else
              { s=q；q=q->next； }          /*从原A、B表上摘下较小者*/
             s->next=C->next;               /*插入到C表的头部*/
             C->next=s;
           }                                /*while */
         if ( p== NULL)  p=q；
         while (p)                          /* 将剩余的结点一个个摘下，插入到C表的头部*/
           { s=p； p=p ->next；
             s->next=C->next;
             C->next=s;
           }
}

该算法的时间复杂度为O(m+n)。