备案控制台
探索云世界
开发者社区 人工智能 文章 正文

线性表的链式实现(一)

2023-09-14 26
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 线性表的链式实现(一)

@[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. 头插法
  2. 尾插法

    头插法

    头插法，顾名思义就是在头部进行插入，首先创建一个头结点：
    在这里插入图片描述
    头结点的创建很简单，然后我们插入第一个结点：
    在这里插入图片描述
    让插入结点的指针域等于头结点的指针域，然后让头结点指向插入的结点即可完成插入。
    插入第二个结点：
    在这里插入图片描述
    同样是让插入结点的指针域等于头结点的指针域，此时头结点指向元素值为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;//返回单链表长度
}

    单链表的查找

    上面的一些操作都是较为简单的，下面介绍一些难度较大的操作，先从查找说起。单链表的查找分为两种：
  3. 查找指定位置的元素值
  4. 查找指定元素值的位置

查找指定位置的元素值

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

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

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

代码实现如下：

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. 从首元结点开始，依次扫描每个结点，让结点的数据域与查找值比较
  2. 如果找到一个结点的数据域与查找值相等，则返回该结点位置
  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;
}
文章标签：
存储
算法
梳中分的坤坤
目录
相关文章
唐唐思
|
2月前
|
C语言
链式二叉树（1）
链式二叉树（1）
唐唐思
28 0
唐唐思
|
2月前
链式二叉树（3）
链式二叉树（3）
唐唐思
23 0
zcx-yyds
|
6月前
|
存储
【数据结构】二叉树的链式实现及遍历
【数据结构】二叉树的链式实现及遍历
zcx-yyds
65 0
唐唐思
|
2月前
链式二叉树（2）
链式二叉树（2）
唐唐思
20 0
ZhangBlossom
|
9月前
|
存储 算法 C++
C/C++线性表之链式与顺序存储结构(附代码)（一）
C/C++线性表之链式与顺序存储结构(附代码)
ZhangBlossom
133 0
看到我请叫我滚去学习Orz
|
5月前
|
存储 算法
【数据结构】链式二叉树
【数据结构】链式二叉树
看到我请叫我滚去学习Orz
36 0
梳中分的坤坤
|
7月前
|
算法
线性表的链式实现(二)
线性表的链式实现(二)
梳中分的坤坤
15 0
ZhangBlossom
|
9月前
|
存储 数据可视化 C++
C/C++线性表之链式与顺序存储结构(附代码)（二）
C/C++线性表之链式与顺序存储结构(附代码)
ZhangBlossom
82 0
KOBE0824BRYANT
|
10月前
链式二叉树
链式二叉树
KOBE0824BRYANT
54 0
KOBE0824BRYANT
|
10月前
链式二叉树（下）
链式二叉树
KOBE0824BRYANT
29 0