@[toc]

本篇文章将讲解线性表的链式实现。

链式存储的定义

通过前面的学习我们知道，顺序表中的元素内存地址连续，存取效率高，但是也有它的缺点，比如有空间限制，插入删除效率低等。
为了解决这一问题，链式实现就诞生了，链式存储结构定义如下：

在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的).

对于顺序存储，元素的地址即可表示元素的先后顺序，因为它们的地址之间也是连续的，如下图：
在这里插入图片描述
但是链式存储结构中的元素地址并不一定是连续的，它们如何能够建立线性表中的顺序关系呢？
有一个办法，就是在某个地址存储了元素值之后，还存储了它下一个元素的地址，也就是说，通过该地址，我们就可以找到该元素的下一个元素，然后下一个元素又存放了下下个元素的地址，以此类推，也能够建立起元素之间的关系，如下图：
在这里插入图片描述
在该结构中：
地址1000存放了元素值1和它的下一个元素值2的地址，通过1963便找到了元素值2；
而地址1963存放了元素值2和它的下一个元素值3的地址，通过1112便找到了元素值3；
而地址1112存放了元素值3和它的下一个元素值4的地址，通过1002便找到了元素值4；
而地址1002存放了元素值4和它的下一个元素值5的地址，通过1054便找到了元素值5；
而地址1054存放了元素值5和它的下一个元素值的地址，但元素值5是最后一个元素，所以该下一个元素值的地址应为NULL，通常在图中用符号^表示。

这样，我们通过自定义的数据类型作为一个结点，定义两个变量，其中存储元素值的变量为数据域，存储下一个元素地址的变量为指针域，这样就通过指针实现了一个链接起来的表，我们称其为链表，如下图：
在这里插入图片描述
通过指针，我们将原本随意存储的结点有顺序地连接起来，将上图整理一下：

这样的一个单向的链表我们称之为单链表，当然还有双链表、循环链表等等，这些放到后面说。
为了操作方便，通常会在链表的头部增设一个头结点，该结点不存储任何有效数据，当然你也可以在头结点中存储结点的有效信息，如长度等。

链式存储的相关概念

上面已经说到，链式存储即通过若干个结点形成链表。

结点：数据元素的存储映像，由数据域和指针域两部分组成
链表：由n个结点通过指针链组成的一个线性表
单链表：结点只有一个指针域的链表
双链表：结点有两个指针域的链表
循环链表：首尾相接的链表

尤其需要注意以下几个概念：

首元结点：链表中存储第一个数据元素的结点
头结点：为了操作方便增设的一个结点，在首元结点之前
头指针：指向链表中第一个结点的指针

如下图为带头结点的单链表：
在这里插入图片描述
下图为带头结点的双链表：

下图为带头结点的循环链表：

单链表的定义

本篇文章先来说一说单链表。
结点定义如下：

#define ElemType int

typedef struct Node{
   
   
    ElemType data;        //数据域
    struct Node *next;    //指针域
}Node,*LinkList;

单链表的初始化

前面说到，为了操作方便，我们通常要在链表头部增设一个头结点，那么增设头结点究竟有什么好处呢？
增设了头结点之后，对于首元结点，它的前面也有一个结点，所以对它的操作和对其它结点的操作是一样的。而如果没有头结点，就需要对首元结点进行特殊处理。
这里我们实现具有头结点的单链表，带头结点的单链表初始化非常简单，创建出一个头结点即完成了初始化。

LinkList create_list(){
   
   
    //创建头结点
    LinkList l = (LinkList) malloc(sizeof(Node));
    if(l == NULL){
   
   
        exit(-1);
    }
    l->next = NULL;//头结点初始无指向
}

这样便创建了一个空的单链表。
而有些时候，我们需要通过一些数据创建出一个非空的单链表，有两种方式：

头插法
尾插法
头插法
头插法，顾名思义就是在头部进行插入，首先创建一个头结点：

头结点的创建很简单，然后我们插入第一个结点：

让插入结点的指针域等于头结点的指针域，然后让头结点指向插入的结点即可完成插入。
插入第二个结点：

同样是让插入结点的指针域等于头结点的指针域，此时头结点指向元素值为1的结点，这样插入结点就会指向元素值为1的结点，然后让头结点指向插入结点，完成插入。
从上面的插入操作中可以看出，头插法实现的链表，其元素值位置和给定的元素序列正好相反。
下面是代码实现：
```
LinkList create_listH(int *a,int length){
     
     
 int i;
 LinkList l,s;
 //创建头结点
 l = (LinkList) malloc(sizeof(Node));
 if(l == NULL){
     
     
     exit(-1);
 }
 l->next = NULL;//头结点初始无指向
 for(i = 0;i < length;i++){
     
     
     //创建新结点
     s = (LinkList) malloc(sizeof(Node));
     if(s == NULL){
     
     
         exit(-1);
     }
     s->data = a[i];
     //头插法插入新结点
     s->next = l->next;    //新结点指向头结点的指向
     l->next = s;        //头结点指向新结点
 }
 return l;//返回头结点
}
```
通过传入一个int数组和数组长度，构建单链表。
尾插法
尾插发，顾名思义就是在尾部进行插入；，首先创建一个头结点：

我们需要借助一个结点类型变量作为尾结点，初始尾结点指向头结点。
插入第一个结点：

让尾结点指向插入的结点，然后将插入结点赋值给尾结点。
插入第二个结点：

千万记得将尾结点的指针域置为NULL，否则链表就没有结束条件了。
代码实现如下：
```
LinkList create_listP(int *a,int length){
     
     
 int i;
 LinkList l,p,s;
 //创建头结点
 l = (LinkList) malloc(sizeof(Node));
 if(l == NULL){
     
     
     exit(-1);
 }
 p = l;        //尾结点初始为头结点
 for(i = 0;i < length;i++){
     
     
     //创建新结点
     s = (LinkList) malloc(sizeof(Node));
     if(s == NULL){
     
     
         exit(-1);
     }
     s->data = a[i];
     //尾插法插入结点
     p->next = s;    //尾结点指向新结点
     p = s;            //此时新结点为链表的尾结点
 }
 p->next = NULL;    //尾结点指针域为NULL
 return l;//返回头结点
}
```
单链表的遍历
介绍完了单链表的初始化，我们先来看看如何遍历单链表，也好对上面的算法进行一个测试。

假设有上面的一个单链表，该如何进行遍历呢？
很简单，从头结点开始，根据指针域依次遍历，并判断指针域的指向，如果为NULL，则说明为尾结点，此时遍历结束，完成遍历。

代码实现如下：
```
void traverse_list(LinkList l){
     
     
 //变量p初始指向首元结点
 LinkList p = l->next;
 while(p != NULL){
     
     
     printf("%d\t",p->data);//输出元素值
     p = p->next;//让p指向下一个结点
 }
}
```
这样遍历函数也完成了，我们可以测试一下，测试代码：
```
void main(){
     
     
 LinkList l,l2;
 int a[] = {
     
     1,2,3,4};
 l = create_listH(a,4);
 l2 = create_listP(a,4);
 traverse_list(l);
 printf("\n");
 traverse_list(l2);
 getchar();
}
```
运行结果：
```
4 3 2 4
1 2 3 4
```
单链表的基本操作

判断单链表是否为空
对于单链表的非空判断，我们只需要判断头结点的指针域是否为NULL即可。若头结点的指针域为NULL，则单链表中仅含有头结点，此时表示该单链表为空；若头结点的指针域不为NULL，则表示单链表非空。
代码如下：
```
int ListEmpty(LinkList l){
     
     
 if(l->next == NULL){
     
     
     return 1;
 }else{
     
     
     return 0;
 }
}
```
单链表的销毁
单链表的销毁可不像顺序表一样只释放数组内存就行了，单链表的销毁需要从头结点开始，依次释放接下来的所有结点。

我们定义一个变量P指向头结点，为什么需要变量P？因为当你释放头结点之后，后面的所有结点你就找不到了，所以要用变量P存储一下。
当准备释放头结点时，让变量P指向首元结点，此时释放头结点后，我们仍然保存着后面的结点位置，让L指向P，然后又让P指向下一个结点，接着释放L，依次类推，直到释放所有结点。
代码如下：
```
void DestroyList(LinkList l){
     
     
 LinkList p;
 while(l != NULL){
     
     
     p = l;//让p指向l
     l = l->next;//l指向下一个结点
     free(p);//释放内存
 }
}
```
清空单链表
清空单链表不同于销毁，单链表被清空后，链表仍然存在，不过只存在头结点，其它结点被释放，此时链表状态为空。
清空单链表很简单，不过它要从首元结点开始，依次释放结点。
需要注意的是，在释放结点的时候，仍然要保存当前结点的下一个结点。
比如在释放首元结点之后，其后面的结点就无法找到了，此时应该再定义一个变量存储下一个结点，然后将首元结点删除，依次类推。
```
void ClearList(LinkList l){
     
     
 LinkList p,q;
 p = l->next;//p指向首元结点
 while(p != NULL){
     
     
     q = p->next;//q存放p的下一个结点
     free(p);//释放p的内存
     p = q;//让p指向q
 }
 //将头结点指针域置为NULL
 l->next = NULL;
}
```
求单链表表长
求单链表的表长非常简单，从首元结点开始遍历，直到尾结点，期间每遇到一个结点就让计数器加1，最后返回计数器数量即可。
代码如下：
```
int ListLength(LinkList l){
     
     
 LinkList p;
 int i = 0;//计数器
 p = l->next;//p初始指向首元结点
 while(p != NULL){
     
     
     i++;//计数器加1
     p = p->next;//p指向下一个结点
 }
 return i;//返回单链表长度
}
```
单链表的查找
上面的一些操作都是较为简单的，下面介绍一些难度较大的操作，先从查找说起。单链表的查找分为两种：
查找指定位置的元素值
查找指定元素值的位置

查找指定位置的元素值

如何通过指定位置查找其元素值呢？
比如下面的一个单链表：
在这里插入图片描述
首先我们需要找到指定位置的结点，然后返回该结点的数据域。
举个例子，要想查找上图单链表中位置为2的元素值，应该如何查找呢？
通过一个计数器i，定义一个变量p初始指向首元结点，此时计数器加1,；然后让p指向下一个结点，此时计数器再加1，当计数器i等于2时，说明查找的指定位置已经找到，此时p指向的就是待查找的结点，最后返回结点数据域即可。
在这里插入图片描述
当然还需要考虑一些异常情况，若一个长度为n的单链表，查找位置的范围：[1，n]。

综上所述，算法步骤如下：

从首元结点开始，依次扫描每个结点
每扫描过一个结点，就让计数器加1
当计数器等于查找位置时，停止扫描

代码实现如下：

int GetElem(LinkList l,int pos,int *val){
   
   
    int length;
    int count = 1;//计数器.若p指向头结点,则count = 0;若p指向首元结点,则count = 1
    LinkList p = l->next;
    //得到单链表的长度
    length = ListLength(l);
    //判断pos值的合法性
    if(pos < 1 || pos > length){
   
   
        return -1;
    }
    //当count = pos时退出循环,且p不能为NULL
    while(p != NULL && count < pos){
   
   
        p = p->next;//p指向下一个结点
        count++;//计数器加1
    }
    //获取元素值
    *val = p->data;
    return 1;//查找成功
}

查找指定元素值的位置

如何查找指定元素值的位置呢？
比如下面的一个单链表：
在这里插入图片描述
从首元结点开始，依次比较结点数据域与指定的元素值，若相等，则查找成功；若所有结点都比较过了，仍然没有找到，则查找失败。
为了得到元素值的位置，我们需要一个计数器来记录结点的位置。
举个例子，要想查找元素值为3的结点位置，该如何实现呢？
在这里插入图片描述
综上所述，算法步骤如下；

从首元结点开始，依次扫描每个结点，让结点的数据域与查找值比较
如果找到一个结点的数据域与查找值相等，则返回该结点位置
如果遍历完链表仍未找到，返回-1表示查找失败

代码如下：

int LocateElem(LinkList l,int val){
   
   
    LinkList p;
    int count = 1;//计数器
    p = l->next;//p初始指向首元结点
    //若p的数据域等于val时退出循环，且p不为NULL
    while(p != NULL && p->data != val){
   
   
        p = p->next;//p指向下一个结点
        count++;//计数器加1
    }
    if(p == NULL){
   
   
        return -1;
    }
    return count;//返回结点位置
}

循环退出有两种情况，一种是找到了查找值，此时返回count即可；一种是链表全部扫描了一遍，此时说明并没有找到，这时候p的值为NULL，所以应该在循环后面加上对p的非空判断。若p为NULL，说明查找失败，返回-1即可。

对于查找算法，由于单链表只能顺序存取，所以查找算法的时间复杂度为O(n)。

单链表的插入

查找说完了，我们继续来学习一下单链表的插入和删除操作，这两个操作要比查找算法更复杂一些，需要一定的思考，我们先来看看插入。
比如下面的一个单链表：

若要在位置2插入一个结点，该如何实现呢？
要想在指定位置插入结点，需要找到指定位置的前一个结点，这里我们就需要找到位置1的结点，我们暂且称其为p；位置2的结点称其为q；待插入的结点称其为s，插入步骤如下：

先让s结点指向q结点，即：s->next = p->next。

再让p结点指向s结点，即：p->next = s。这样即可完成插入。
这两个步骤顺序千万不要颠倒，若是先执行了p->next = s，则q结点的位置就找不到了，也就无法实现插入了。
现在的问题就在于如何找到插入位置的前一个结点，不过这已经在查找算法中说过了，就不重复讲解了。
插入算法代码如下：
int InsertList(LinkList l,int pos,int val){
    
    
    LinkList p,s;
    int length,i = 0;
    length = ListLength(l);
    p = l;//p初始指向头结点
    //判断pos值合法性
    if(pos < 1 || pos > length + 1){
    
    
        return -1;
    }
    //找到插入位置的前一个结点
    while(p != NULL && i < pos - 1){
    
    
        p = p->next;//p指向下一个结点
        i++;
    }
    //循环结束后，p为插入位置的前一个结点
    //创建新结点
    s = (LinkList) malloc(sizeof(Node));
    if(s == NULL){
    
    
        exit(-1);
    }
    //插入结点
    s->data = val;
    s->next = p->next;
    p->next = s;
    return 1;//插入成功，返回1
}
单链表的删除

说完插入，接下来就是删除操作了，比如下面的一个单链表：

要想删除位置为2的结点，该如何实现呢？
同样地，要想删除指定位置的结点，仍然需要找到删除位置的前一个结点，我们暂且将位置为2的结点称为q，它的前一个结点称为p，它的后一个结点称为s，则删除步骤如下：

先找到删除位置的前一个结点p，然后定义一个变量p保存结点q，接着让p指向结点s，即：p->next = q ->next，也可以写做p->next = p->next->next，最后释放结点q的内存：free(q)。
删除算法代码如下：
int DeleteList(LinkList l,int pos,int *val){
    
    
    LinkList p,q;
    int length,i = 0;
    length = ListLength(l);
    p = l;//p初始指向头结点
    //判断pos值的合法性
    if(pos < 1 || pos > length){
    
    
        return -1;
    }
    //找到删除位置的前一个结点
    while(p != NULL && i < pos - 1){
    
    
        p = p->next;
        i++;
    }
    //此时p为删除位置的前一个结点
    q = p->next;//q保存删除位置结点
    //保存数据
    *val = q->data;
    //删除结点
    p->next = q->next;
    free(q);//释放结点内存
    return 1;//删除成功，返回1
}
对于插入和删除算法的时间复杂度，因为它无需移动任何元素，只需要改变指针指向，所以两个算法的时间复杂度均为O(1)。

源代码

文章中的所有代码：

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

#define ElemType int

typedef struct Node{
   
   
    ElemType data;        //数据域
    struct Node *next;    //指针域
}Node,*LinkList;

int DeleteList(LinkList l,int pos,int *val){
   
   
    LinkList p,q;
    int length,i = 0;
    length = ListLength(l);
    p = l;//p初始指向头结点
    //判断pos值的合法性
    if(pos < 1 || pos > length){
   
   
        return -1;
    }
    //找到删除位置的前一个结点
    while(p != NULL && i < pos - 1){
   
   
        p = p->next;
        i++;
    }
    //此时p为删除位置的前一个结点
    q = p->next;//q保存删除位置结点
    //保存数据
    *val = q->data;
    //删除结点
    p->next = q->next;
    free(q);//释放结点内存
    return 1;//删除成功，返回1
}

int InsertList(LinkList l,int pos,int val){
   
   
    LinkList p,s;
    int length,i = 0;
    length = ListLength(l);
    p = l;//p初始指向头结点
    //判断pos值合法性
    if(pos < 1 || pos > length + 1){
   
   
        return -1;
    }
    //找到插入位置的前一个结点
    while(p != NULL && i < pos - 1){
   
   
        p = p->next;//p指向下一个结点
        i++;
    }
    //循环结束后，p为插入位置的前一个结点
    //创建新结点
    s = (LinkList) malloc(sizeof(Node));
    if(s == NULL){
   
   
        exit(-1);
    }
    //插入结点
    s->data = val;
    s->next = p->next;
    p->next = s;
    return 1;//插入成功，返回1
}

int LocateElem(LinkList l,int val){
   
   
    LinkList p;
    int count = 1;//计数器
    p = l->next;//p初始指向首元结点
    //若p的数据域等于val时退出循环，且p不为NULL
    while(p != NULL && p->data != val){
   
   
        p = p->next;//p指向下一个结点
        count++;//计数器加1
    }
    if(p == NULL){
   
   
        return -1;
    }
    return count;//返回结点位置
}

int GetElem(LinkList l,int pos,int *val){
   
   
    int length;
    int count = 1;//计数器.若p指向头结点,则count = 0;若p指向首元结点,则count = 1
    LinkList p = l->next;
    //得到单链表的长度
    length = ListLength(l);
    //判断pos值的合法性
    if(pos < 1 || pos > length){
   
   
        return -1;
    }
    //当count = pos时退出循环,且p不能为NULL
    while(p != NULL && count < pos){
   
   
        p = p->next;//p指向下一个结点
        count++;//计数器加1
    }
    //获取元素值
    *val = p->data;
    return 1;//查找成功
}

int ListLength(LinkList l){
   
   
    LinkList p;
    int i = 0;//计数器
    p = l->next;//p初始指向首元结点
    while(p != NULL){
   
   
        i++;//计数器加1
        p = p->next;//p指向下一个结点
    }
    return i;//返回单链表长度
}

void ClearList(LinkList l){
   
   
    LinkList p,q;
    p = l->next;//p指向首元结点
    while(p != NULL){
   
   
        q = p->next;//q存放p的下一个结点
        free(p);//释放p的内存
        p = q;//让p指向q
    }
    //将头结点指针域置为NULL
    l->next = NULL;
}

void DestroyList(LinkList l){
   
   
    LinkList p;
    while(l != NULL){
   
   
        p = l;//让p指向l
        l = l->next;//l指向下一个结点
        free(p);//释放内存
    }
}

int ListEmpty(LinkList l){
   
   
    if(l->next == NULL){
   
   
        return 1;
    }else{
   
   
        return 0;
    }
}

void traverse_list(LinkList l){
   
   
    //变量p初始指向首元结点
    LinkList p = l->next;
    while(p != NULL){
   
   
        printf("%d\t",p->data);//输出元素值
        p = p->next;//让p指向下一个结点
    }
}

LinkList create_listP(int *a,int length){
   
   
    int i;
    LinkList l,p,s;
    //创建头结点
    l = (LinkList) malloc(sizeof(Node));
    if(l == NULL){
   
   
        exit(-1);
    }
    p = l;        //尾结点初始为头结点
    for(i = 0;i < length;i++){
   
   
        //创建新结点
        s = (LinkList) malloc(sizeof(Node));
        if(s == NULL){
   
   
            exit(-1);
        }
        s->data = a[i];
        //尾插法插入结点
        p->next = s;    //尾结点指向新结点
        p = s;            //此时新结点为链表的尾结点
    }
    p->next = NULL;    //尾结点指针域为NULL
    return l;//返回头结点
}

LinkList create_listH(int *a,int length){
   
   
    int i;
    LinkList l,s;
    //创建头结点
    l = (LinkList) malloc(sizeof(Node));
    if(l == NULL){
   
   
        exit(-1);
    }
    l->next = NULL;//头结点初始无指向
    for(i = 0;i < length;i++){
   
   
        //创建新结点
        s = (LinkList) malloc(sizeof(Node));
        if(s == NULL){
   
   
            exit(-1);
        }
        s->data = a[i];
        //头插法插入新结点
        s->next = l->next;    //新结点指向头结点的指向
        l->next = s;        //头结点指向新结点
    }
    return l;//返回头结点
}

LinkList create_list(){
   
   
    //创建头结点
    LinkList l = (LinkList) malloc(sizeof(Node));
    if(l == NULL){
   
   
        exit(-1);
    }
    l->next = NULL;//头结点初始无指向
    return l;
}

线性表的链式实现(一)

链式存储的定义

链式存储的相关概念

单链表的定义

单链表的初始化

头插法

尾插法

单链表的遍历

单链表的基本操作

判断单链表是否为空

单链表的销毁

清空单链表

求单链表表长

单链表的查找

查找指定位置的元素值

查找指定元素值的位置

单链表的插入

单链表的删除

源代码

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

线性表的链式实现(一)

链式存储的定义

链式存储的相关概念

单链表的定义

单链表的初始化

头插法

尾插法

单链表的遍历

单链表的基本操作

判断单链表是否为空

单链表的销毁

清空单链表

求单链表表长

单链表的查找

查找指定位置的元素值

查找指定元素值的位置

单链表的插入

单链表的删除

源代码

热门文章

最新文章

相关电子书