【C 数据结构】单链表

  • 开发
  • 29

文章目录


本文中若未指定，则默认链表存在首元结点。

【 1. 基本原理 】

  • 与顺序表不同，链表 不限制数据的物理存储状态（存储空间是否连续） ，使用链表存储的数据元素，其 物理存储位置是随机的 。
  • 例如，使用链表存储 1,2,3 ，数据的物理存储状态如图所示：
  • 上图根本无法体现出各数据之间的逻辑关系。对此，链表的解决方案是，每个数据元素在存储时都配备一个指针，用于指向自己的直接后继元素：
    在这里插入图片描述
  • 数据元素随机存储，并通过指针表示数据之间逻辑关系 的存储结构就是 链式存储结构。

1.1 链表的节点

  • 链表中每个数据的存储都由以下两部分组成：
    • 数据元素本身，其所在的区域称为数据域；
    • 指向直接后继元素的指针，所在的区域称为指针域；
  • 链表中存储各数据元素的结构，即 节点。如图所示：
    在这里插入图片描述
  • 也就是说， 链表实际存储的是一个一个的节点，真正的数据元素包含在这些节点中，如图所示：
    在这里插入图片描述
  • 链表中每个节点的具体实现，需要使用 C 语言中的结构体， 每个节点都是一个结构体，具体实现代码为：
    • 由于指针域中的指针要指向的也是一个节点，因此要声明为 Link 类型（这里要写成 struct Link* 的形式）。
//定义结点类型
typedef struct Node {
    int data;       //数据类型，你可以把int型的data换成任意数据类型，包括结构体struct等复合类型
    struct Node *next;          //单链表的指针域
} Node,*LinkedList;  
//Node表示结点的类型，LinkedList表示指向Node结点类型的指针类型

1.2 头指针、头节点、首元节点

  • 一个完整的链表需要由以下几部分构成：
    • 头指针：一个普通的指针，它的特点是 永远指向链表第一个节点的位置。很明显，头指针用于指明链表的位置，便于后期找到链表并使用表中的数据；
    • 节点：链表中的节点又细分为头节点、首元节点和其他节点：
      • 头节点：其实就是一个 不存任何数据的空节点，通常作为链表的第一个节点。对于链表来说，头节点不是必须的，它的作用只是为了方便解决某些实际问题；链表中有头节点时，头指针指向头节点；反之，若链表中没有头节点，则头指针指向首元节点。
      • 首元节点：由于头节点（也就是空节点）的缘故，链表中称 第一个存有数据的节点 为首元节点。首元节点只是对链表中第一个存有数据节点的一个称谓，没有实际意义；
      • 其他节点：链表中其他的节点。
  • 一个存储 {1,2,3} 的完整链表结构如图所示：
    在这里插入图片描述

【 2. 链表的创建 】

  • 创建一个链表需要做如下工作：
    • 声明一个头指针（如果有必要，可以声明一个头节点）；
    • 创建多个存储数据的节点，在创建的过程中，要随时与其前驱节点建立逻辑关系；

2.0 创建1个空链表（仅有头节点）

  • 创建一个指向链表节点的指针，申请一块链表节点的内存，使该指针指向该块内存（若该指针指向空，表示内存申请失败，输出信息提示），最后将该指针指向的节点的指针域指向NULL空，表示该链表初始化后仅有1个节点。
Node* listinit(){
    Node *L;
    L=(Node*)malloc(sizeof(Node));      //开辟空间 
    if(L==NULL){                     //判断是否开辟空间失败，这一步很有必要
        printf("申请空间失败");
        //exit(0);                  //开辟空间失败可以考虑直接结束程序
    }
    L->next=NULL;       //指针指向空
    return L;
}

2.1 创建单链表（头插入法）*- 从键盘输入值

  • 先创建一个头节点，头节点的指针域指向空。插入新节点时，将新节点的指针域指向头节点的next，再将头节点的next指向该新节点。
    在这里插入图片描述
  • C 实现
//单链表的建立1，头插法建立单链表
Node *LinkedListCreatH() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申请头结点空间
    L->next = NULL;                     //初始化一个空链表
  // L始终指向头节点
    int x;                         //x为链表数据域中的数据
    while(scanf("%d",&x) != EOF) {
        Node *p;
        p = (Node *)malloc(sizeof(Node));   //申请新的结点
        p->data = x;                     //结点数据域赋值
        p->next = L->next;     //将结点插入到表头L-->|2|-->|1|-->NULL
        L->next = p;
    }
    return L;

2.2 创建单链表（尾插入法）- 从键盘输入值

  • 先创建一个头节点，头节点的指针域指向空，再创建一个尾指针，尾指针先指向头节点。插入新节点时，将尾指针的next指向该新节点，再将尾指针指向该新节点，最后将尾指针的next指空。
    在这里插入图片描述
  • C实现：
//单链表的建立2，尾插法建立单链表
Node *LinkedListCreatT() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申请头结点空间
    L->next = NULL;                  //初始化一个空链表
    Node *r;
    r = L;                          //r始终指向终端结点，开始时指向头结点
    int x;                         //x为链表数据域中的数据
    while(scanf("%d",&x) != EOF) {
        Node *p;
        p = (Node *)malloc(sizeof(Node));   //申请新的结点
        p->data = x;                     //结点数据域赋值
        r->next = p;            //将结点插入到表头L-->|1|-->|2|-->NULL
        r = p;
    }
    r->next = NULL;
    return L;
}

2.3 创建一个无头节点的链表 - 默认值

  • 创建一个存储 {1,2,3,4} 且无头节点的链表，C 实现：
link * initLink()
{
    link * p=NULL;//创建头指针
    link * temp = (link*)malloc(sizeof(link));//创建首元节点
    //首元节点temp先初始化
    temp->elem = 1;
    temp->next = NULL;
    p = temp;//头指针指向首元节点
    //从第二个节点开始创建
    for (int i=2; i<5; i++) // temp作为链表的尾节点
    {
     //创建一个新节点并初始化
        link *a=(link*)malloc(sizeof(link));
        a->elem=i;
        a->next=NULL;
        //将temp节点与新建立的a节点建立逻辑关系
        temp->next=a;
        //指针temp每次都指向新链表的最后一个节点，其实就是 a节点，这里写temp=a也对
        temp=temp->next;
    }
    temp->next=NULL; // 最后尾节点指向空
    //返回建立的节点，只返回头指针 p即可，通过头指针即可找到整个链表
    return p;
}
  • 实例：创建一个存储 {1,2,3,4} 的链表，并输出：
#include <stdio.h>
#include <stdlib.h>

//链表中节点的结构
typedef struct Link
{
    int  elem;
    struct Link* next;
}link;

//初始化链表的函数
link* initLink()
{
    link* p = NULL;//创建头指针
    link* temp = (link*)malloc(sizeof(link));//创建首元节点
    //首元节点先初始化
    temp->elem = 1;
    temp->next = NULL;
    p = temp;//头指针指向首元节点
    for (int i = 2; i < 5; i++)
    {
        link* a = (link*)malloc(sizeof(link));
        a->elem = i;
        a->next = NULL;
        temp->next = a;
        temp = temp->next;
    }
    temp->next=NULL;
    return p;
}

//用于输出链表的函数
void display(link* p)
{
    link* temp = p;//将temp指针重新指向头结点
    //只要temp指针指向的结点的next不是Null，就执行输出语句。
    while (temp)
    {
        printf("%d ", temp->elem);
        temp = temp->next;
    }
    printf("\n");
}

int main()
{
    printf("初始化链表为：\n");
    link* p = initLink();//初始化链表（1，2，3，4）
    display(p);
    return 0;
}

在这里插入图片描述

【 3. 链表插入元素 】

  • 链表插入元素只需做以下两步操作，即可将新元素插入到指定的位置：
    1.将新结点的 next 指针指向插入位置后的结点；
    2.将插入位置前结点的 next 指针指向插入结点；
  • 链表插入元素的操作必须是先步骤 1，再步骤 2；反之，若先执行步骤 2 即 将插入位置前结点的 next 指针指向插入结点，除非再添加一个指针，作为插入位置后续链表的头指针，否则会导致插入位置后的这部分链表丢失，无法再实现步骤 1。
  • 例如，我们在链表 1,2,3,4 的基础上分别实现在头部、中间部位、尾部插入新元素 5，其实现过程如图所示：
    在这里插入图片描述
  • 从图中可以看出，虽然新元素的插入位置不同，但实现插入操作的方法是一致的，都是先执行步骤 1 ，再执行步骤 2。
  • C 实现：指定位置插入元素
//单链表的插入，在链表的第i个位置插入x的元素
Node *LinkedListInsert(LinkedList L,int i,int x) {
    Node *pre;                      //pre为前驱结点
    pre = L;
    int tempi = 0;
    for (tempi = 1; tempi < i; tempi++) {
        pre = pre->next;                 //查找第i个位置的前驱结点
    }
    Node *p;                                //插入的结点为p
    p = (Node *)malloc(sizeof(Node));
    p->data = x;
    p->next = pre->next;
    pre->next = p;
  
    return L;
}

【 4. 链表删除元素 】

  • 从链表中删除指定数据元素时，实则就是将存有该数据元素的节点从链表中摘除，但作为一名合格的程序员，要对存储空间负责，对不再利用的存储空间要及时释放 。因此，从链表中删除数据元素需要进行以下 2 步操作：
    • 将要删除的节点的前一个节点的next指向要删除节点的next；
    • 可选：手动释放掉要删除节点的内存。

例如，从存有 1,2,3,4 的链表中删除元素 3，则此代码的执行效果如图所示：
在这里插入图片描述

  • C 实现：删除指定元素的节点
//单链表的删除，在链表中删除值为x的元素
Node *LinkedListDelete(Node *L,int x) {
    Node *p,*pre;                   //pre为前驱结点，p为查找的结点。
    p = L->next;
     
    while(p->data != x) {              //查找值为x的元素
        pre = p;
        p = p->next;
    }
    pre->next = p->next;          //删除操作，将其前驱next指向其后继。
    free(p); //从链表上摘下的节点p最终通过 free 函数进行了手动释放。
    
    return L;
}
  • C实现：删除指定位置的节点
//p为原链表，add为要删除元素的位置
Node *delElem(Node * p, int add)
{
    Node * temp = p;
    //遍历到被删除结点的上一个结点
    for (int i = 1; i < add; i++)
    {
        temp = temp->next;
        if (temp->next == NULL)
        {
            printf("没有该结点\n");
            return p;
        }
    }
    Node * del = temp->next;//单独设置一个指针指向被删除结点，以防丢失
    temp->next = temp->next->next;//删除某个结点的方法就是更改前一个结点的指针域
    free(del);//手动释放该结点，防止内存泄漏
    return p;
}

【 5. 链表查找元素 】

  • 从首元结点依次遍历表中节点，用被查找元素与各节点数据域中存储的数据元素进行比对，直至比对成功或遍历至链表最末端的 NULL（比对失败的标志）。
  • C 实现：查找指定值的元素位置
//p为原链表，elem表示被查找元素，函数返回被查元素的位置
//若返回值为-1表示链表中不存在该元素
int selectElem(link * p,int elem)
{
//新建一个指针t，初始化为头指针 p
    link * t=p;
    int i=1;
    //由于头节点的存在，因此while中的判断为t->next
    while (t->next) 
    {
        t=t->next;
        if (t->elem==elem) 
            return i;
        i++;
    }
    //程序执行至此处，表示查找失败
    return -1;
}

【 6. 链表修改元素 】

  • 更新链表中的元素，只需通过遍历找到存储此元素的节点，对节点中的数据域做更改操作即可。
  • C 实现：修改指定位置的元素
//add 表示更改结点在链表中的位置，newElem 为新的数据域的值
Node *amendElem(Node * p,int add,int newElem)
{
    Node  * temp=p;
    temp=temp->next;//在遍历之前，temp指向首元结点
    //遍历到待更新结点
    for (int i=1; i<add; i++) 
        temp=temp->next;
    temp->elem=newElem;
    return p;
}
  • C 实现：修改指定元素值
//链表内容的修改，再链表中修改值为x的元素变为为k。
Node *LinkedListReplace(LinkedList L,int x,int k) {
    Node *p=L->next;
    int i=0;
    while(p){
        if(p->data==x){
            p->data=k;
        }
        p=p->next;
    }
    return L;
}

【 7. 链表输出 】

  • 首先创建一个链表节点的指针，指向首元结点，然后判断该指针是否指向了空，若非空，则输出该指针指向的节点的信息，然后指针指向下一个节点循环判断，直到该指针为空。
//输出单链表
void printList(LinkedList L){
    Node *p=L->next;
    int i=0;
    while(p){
        printf("第%d个元素的值为:%d\n",++i,p->data);
        p=p->next;
    }
}

【 8. 实例 - 链表元素的增删查改 】

  • 对链表中数据元素做"增删查改"的实现过程及 C 语言代码：
#include <stdio.h>
#include <stdlib.h>
 
//定义结点类型
typedef struct Node {
    int data;           //数据类型，你可以把int型的data换成任意数据类型，包括结构体struct等复合类型
    struct Node *next;          //单链表的指针域
} Node,*LinkedList;
 
//单链表的初始化
LinkedList LinkedListInit() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申请结点空间
    if(L==NULL){    //判断申请空间是否失败
        exit(0);    //如果失败则退出程序
    }
    L->next = NULL;          //将next设置为NULL,初始长度为0的单链表
    return L;
}
 
 
//单链表的建立1，头插法建立单链表
LinkedList LinkedListCreatH() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申请头结点空间
    L->next = NULL;                      //初始化一个空链表
 
    int x;                         //x为链表数据域中的数据
    while(scanf("%d",&x) != EOF) {
        Node *p;
        p = (Node *)malloc(sizeof(Node));   //申请新的结点
        p->data = x;                     //结点数据域赋值
        p->next = L->next;                    //将结点插入到表头L-->|2|-->|1|-->NULL
        L->next = p;
    }
    return L;
}
 
 
//单链表的建立2，尾插法建立单链表
 
LinkedList LinkedListCreatT() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申请头结点空间
    L->next = NULL;                  //初始化一个空链表
    Node *r;
    r = L;                          //r始终指向终端结点，开始时指向头结点
    int x;                         //x为链表数据域中的数据
    while(scanf("%d",&x) != EOF) {
        Node *p;
        p = (Node *)malloc(sizeof(Node));   //申请新的结点
        p->data = x;                     //结点数据域赋值
        r->next = p;                 //将结点插入到表头L-->|1|-->|2|-->NULL
        r = p;
    }
    r->next = NULL;
 
    return L;
}
 
 
//单链表的插入，在链表的第i个位置插入x的元素
 
LinkedList LinkedListInsert(LinkedList L,int i,int x) {
    Node *pre;                      //pre为前驱结点
    pre = L;
    int tempi = 0;
    for (tempi = 1; tempi < i; tempi++) {
        pre = pre->next;                 //查找第i个位置的前驱结点
    }
    Node *p;                                //插入的结点为p
    p = (Node *)malloc(sizeof(Node));
    p->data = x;
    p->next = pre->next;
    pre->next = p;
 
    return L;
}
 
 
//单链表的删除，在链表中删除值为x的元素
 
LinkedList LinkedListDelete(LinkedList L,int x) {
    Node *p,*pre;                   //pre为前驱结点，p为查找的结点。
    p = L->next;
     
    while(p->data != x) {              //查找值为x的元素
        pre = p;
        p = p->next;
    }
    pre->next = p->next;          //删除操作，将其前驱next指向其后继。
    free(p);
     
    return L;
}
 
//链表内容的修改，再链表中修改值为x的元素变为为k。
LinkedList LinkedListReplace(LinkedList L,int x,int k) {
    Node *p=L->next;
    int i=0;
    while(p){
        if(p->data==x){
            p->data=k;
        }
        p=p->next;
    }
    return L;
}
 
 
//便利输出单链表
void printList(LinkedList L){
    Node *p=L->next;
    int i=0;
    while(p){
        printf("第%d个元素的值为:%d\n",++i,p->data);
        p=p->next;
    }
} 
 
int main() {
    //创建 
    LinkedList list;
    printf("请输入单链表的数据：以EOF结尾\n");
    list = LinkedListCreatT();
    //list=LinkedListCreatT();
    printList(list);
     
    //插入 
    int i;
    int x;
    printf("请输入插入数据的位置：");
    scanf("%d",&i);
    printf("请输入插入数据的值：");
    scanf("%d",&x);
    LinkedListInsert(list,i,x);
    printList(list);
     
    //修改
    printf("请输入修改的数据：");
    scanf("%d",&i);
    printf("请输入修改后的值：");
    scanf("%d",&x);
    LinkedListReplace(list,i,x);
    printList(list);
     
    //删除 
    printf("请输入要删除的元素的值：");
    scanf("%d",&x);
    LinkedListDelete(list,x);
    printList(list);
 
    return 0;
}
阅读全部

相关推荐

  2. C语言数据结构——单链表

    2024-04-14 15:12:02       73 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-04-14 15:12:02       98 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-04-14 15:12:02       106 阅读

  9. 在Django里面运行非项目文件

    2024-04-14 15:12:02       87 阅读

  19. Python语言-面向对象

    2024-04-14 15:12:02       96 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-04-14 15:12:02       91 阅读

热门阅读

  8. 若依 ruoyi-vue 维护Ancestors字段 树转换成List

    2024-04-14 15:12:02       39 阅读

  18. 基于uni-app的埋点sdk设计

    2024-04-14 15:12:02       30 阅读

  22. 【24届数字IC秋招总结】正式批面试经验汇总2——星宸、硅谷数模

    2024-04-14 15:12:02       33 阅读

  23. 子集和问题(c++题解)

    2024-04-14 15:12:02       40 阅读

  25. 【C++】每日一题 54 螺旋矩阵

    2024-04-14 15:12:02       35 阅读

  26. CentOS7.x中用Docker搭建Minio服务器

    2024-04-14 15:12:02       36 阅读