AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

数据结构（初阶）—— C语言实现单链表

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

一、链表的概念


       链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

       链表由两个部分组成：数据域和指针域，数据域用来存放数据，指针域用来链接到下一个数据，具体看下图；

1ecd1b2606ed46e9956a89f231c9802c.png

 从图中可以看出，每个数据的下面的指针域里都存储了下一个数据的地址，那么我们通过访问第一个数据的地址，顺藤摸瓜就能访问到其他数据

二、单链表的接口实现

1.首先创建一个链表的结构

typedef int SLDataType;//这里typedef可以用于存储类型之间的切换
typedef struct SListNode
{
  SLDataType Data;//数据域
  struct SListNode* next;//指针域
}SLNode;

2.单链表的结点申请

//动态申请一个结点
SLNode* BuyListNode(SLDataType x)
{
  SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
  if (newnode == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
  newnode->Data = x;       //x的值存放在newnode数据域中
  newnode->next = NULL;    //newnode的指针域置空
  return newnode;
}

3.单链表的打印 

//单链表的打印
void SListPrint(SLNode* phead)
{
  assert(phead);
  SLNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->Data);  //打印链表数据
    cur = cur->next;  //让cur指向下一个数据
  } //当cur为空时，链表打印结束
  printf("NULL\n\n");
}

1ecd1b2606ed46e9956a89f231c9802c.png

4.单链表的尾插 

//单链表的尾插
void SListPushBack(SLNode** pphead, SLDataType x)
{
  assert(pphead);
  SLNode* newnode = BuyListNode(x);//插入数据需要申请结点
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
        //尾插--就去找链表的尾巴
    SLNode* tail = *pphead;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
        //找到尾巴，把尾结点的指针域指向插入的新结点的地址
    tail->next = newnode;
  }
}

1ecd1b2606ed46e9956a89f231c9802c.png

5.单链表的头插

//单链表的头插
void SListPushFront(SLNode** pphead, SLDataType x)
{
  assert(pphead);
  SLNode* newnode = BuyListNode(x);
  newnode->next = *pphead; //让newnode的指针域指向链表的数据域（就是链表的头）
  *pphead = newnode; //让newnode作新链表的头
}

1ecd1b2606ed46e9956a89f231c9802c.png

6.单链表的尾删 

//单链表的尾删
void SListPopBack(SLNode** pphead)
{
  assert(*pphead);
    //如果链表为空
  if (*pphead == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
        //先要找到尾结点（tail），在记录一下尾结点的前一个结点（prev）；
    SLNode* tail = *pphead;
    SLNode* prev = NULL;
    while (tail->next != NULL)
    {
      prev = tail;
      tail = tail->next;
    }
        //找到尾结点了，释放它并置空；
    free(tail);
    tail = NULL;
        //此时尾结点的前一个结点（prev）还保存着tail结点的数据的地址，要让它置空；
    prev->next = NULL;
  }
}

1ecd1b2606ed46e9956a89f231c9802c.png

7.单链表的头删 

//单链表的头删
void SListPopFront(SLNode** pphead)
{
  assert(*pphead);
  SLNode* next = (*pphead)->next;//记录头结点的下一个结点的地址
  free(*pphead);//释放头结点
  *pphead = next;//头结点的下一个结点作新的头
}

8.单链表的查找 

//单链表的查找
SLNode* SListFind(SLNode* phead, SLDataType x)
{
  assert(phead);
  SLNode* cur = phead;
  while (cur != NULL)
  {
    if (cur->Data == x)
    {
      return cur;
    }
    else
    {
      cur = cur->next;
    }
  }
  return NULL;
}

9.单链表在pos位置前插入一个结点 

//单链表在pos位置前插入一个结点
void SListInsert(SLNode** pphead, SLNode* pos, SLDataType x)
{
  assert(pphead);
  assert(pos);
  SLNode* newnode = BuyListNode(x);//申请结点
    //如果只有一个结点
  if (*pphead == pos)
  {
    newnode->next = *pphead;
    *pphead = newnode;
  }
  else
  {
        //找到pos位置的前一个结点，并记录
    SLNode* posprev = *pphead;
    while (posprev->next != pos)
    {
      posprev = posprev->next;
    }
        //让新结点的指针域指向pos，再让pos的前一个结点的指针域重新指向新结点的数据域地址，就很好的插入到pos的前面了
    newnode->next = pos;
    posprev->next = newnode;
  }
}

1ecd1b2606ed46e9956a89f231c9802c.png

10.单链表在pos位置后插入一个结点

//单链表在pos位置后插入一个节点
void SListInsertAfter(SLNode* pos, SLDataType x)
{
  assert(pos);
  SLNode* newnode = BuyListNode(x);//申请结点
  newnode->next = pos->next;//让新结点的指针域指向pos位置的下一个结点的数据域地址
  pos->next = newnode;//pos的指针域指向新结点的数据域地址
}

1ecd1b2606ed46e9956a89f231c9802c.png

11.单链表删除pos位置的结点 

//单链表删除pos位置的节点
void SListErase(SLNode** pphead, SLNode* pos)
{
  assert(*pphead);
    //如果链表只有一个结点
  if (*pphead == pos)
  {
    SListPopBack(pphead);
  }
  else
  {
        //找到pos位置的前一个位置（posPrev），并记录
    SLNode* posPrev = *pphead;
    while (posPrev->next != pos)
    {
      posPrev = posPrev->next;
    }
        //让pos位置的前一个结点posPrev的指针域指向pos结点的指针域，如果pos位置还有结点，即指向了pos位置的下一个结点的数据域的地址；
    posPrev->next = pos->next;
    free(pos);//释放pos
  }
}

1ecd1b2606ed46e9956a89f231c9802c.png

12.单链表删除pos位置后的结点 

//单链表删除pos位置后的节点
void SListEraseAfter(SLNode* pos)
{
  assert(pos);
  assert(pos->next);
  SLNode* next = pos->next;
  pos->next = next->next;
  free(next);
}

13.单链表的销毁

    单链表的销毁并不能和顺序表一样直接释放，顺序表是开辟的连续的空间，链表不是；

要将链表释放需要释放每一个结点；

       可以采用双指针； 

//单链表的销毁
void SListDestroy(SLNode** pphead)
{
  assert(*pphead);
  SLNode* cur = *pphead;
  while (cur != NULL)
  {
    SLNode* next = cur->next;
    free(cur);
    cur = next;
  }
  *pphead = NULL;
}

1ecd1b2606ed46e9956a89f231c9802c.png

三、源文件

SList.h 

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataType;
typedef struct SListNode
{
  SLDataType Data;
  struct SListNode* next;
}SLNode;
//动态申请一个节点
SLNode* BuyListNode(SLDataType x);
//单链表的打印
void SListPrint(SLNode* phead);
//单链表的尾插
void SListPushBack(SLNode** pphead, SLDataType x);
//单链表的头插
void SListPushFront(SLNode** pphead, SLDataType x);
//单链表的尾删
void SListPopBack(SLNode** pphead);
//单链表的头删
void SListPopFront(SLNode** pphead);
//单链表的查找
SLNode* SListFind(SLNode* phead, SLDataType x);
//单链表在pos位置前插入一个节点
void SListInsert(SLNode** pphead, SLNode* pos, SLDataType x);
//单链表在pos位置后插入一个节点
void SListInsertAfter(SLNode* pos, SLDataType x);
//单链表删除pos位置的节点
void SListErase(SLNode** pphead, SLNode* pos);
//单链表删除pos位置后的节点
void SListEraseAfter(SLNode* pos);
//单链表的销毁
void SListDestroy(SLNode** pphead);

SList.c 

#include "SList.h"
//动态申请一个结点
SLNode* BuyListNode(SLDataType x)
{
  SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
  if (newnode == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
  newnode->Data = x;       //x的值存放在newnode数据域中
  newnode->next = NULL;    //newnode的指针域置空
  return newnode;
}
//单链表的打印
void SListPrint(SLNode* phead)
{
  assert(phead);
  SLNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->Data);  //打印链表数据
    cur = cur->next;  //让cur指向下一个数据
  } //当cur为空时，链表打印结束
  printf("NULL\n\n");
}
//单链表的尾插
void SListPushBack(SLNode** pphead, SLDataType x)
{
  assert(pphead);
  SLNode* newnode = BuyListNode(x);//插入数据需要申请结点
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
    //尾插--就去找链表的尾巴
    SLNode* tail = *pphead;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    //找到尾巴，把尾结点的指针域指向插入的新结点的地址
    tail->next = newnode;
  }
}
//单链表的头插
void SListPushFront(SLNode** pphead, SLDataType x)
{
  assert(pphead);
  SLNode* newnode = BuyListNode(x);
  newnode->next = *pphead; //让newnode的指针域指向链表的数据域（就是链表的头）
  *pphead = newnode; //让newnode作新链表的头
}
//单链表的尾删
void SListPopBack(SLNode** pphead)
{
  assert(*pphead);
  //如果链表为空
  if (*pphead == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    //先要找到尾结点（tail），在记录一下尾结点的前一个结点（prev）；
    SLNode* tail = *pphead;
    SLNode* prev = NULL;
    while (tail->next != NULL)
    {
      prev = tail;
      tail = tail->next;
    }
    //找到尾结点了，释放它并置空；
    free(tail);
    tail = NULL;
    //此时尾结点的前一个结点（prev）还保存着tail结点的数据的地址，要让它置空；
    prev->next = NULL;
  }
}
//单链表的头删
void SListPopFront(SLNode** pphead)
{
  assert(*pphead);
  SLNode* next = (*pphead)->next;//记录头结点的下一个结点的地址
  free(*pphead);//释放头结点
  *pphead = next;//头结点的下一个结点作新的头
}
//单链表的查找
SLNode* SListFind(SLNode* phead, SLDataType x)
{
  assert(phead);
  SLNode* cur = phead;
  while (cur != NULL)
  {
    if (cur->Data == x)
    {
      return cur;
    }
    else
    {
      cur = cur->next;
    }
  }
  return NULL;
}
//单链表在pos位置前插入一个结点
void SListInsert(SLNode** pphead, SLNode* pos, SLDataType x)
{
  assert(pphead);
  assert(pos);
  SLNode* newnode = BuyListNode(x);//申请结点
  //如果只有一个结点
  if (*pphead == pos)
  {
    newnode->next = *pphead;
    *pphead = newnode;
  }
  else
  {
    //找到pos位置的前一个结点，并记录
    SLNode* posprev = *pphead;
    while (posprev->next != pos)
    {
      posprev = posprev->next;
    }
    //让新结点的指针域指向pos，再让pos的前一个结点的指针域重新指向新结点的数据域地址，就很好的插入到pos的前面了
    newnode->next = pos;
    posprev->next = newnode;
  }
}
//单链表在pos位置后插入一个节点
void SListInsertAfter(SLNode* pos, SLDataType x)
{
  assert(pos);
  SLNode* newnode = BuyListNode(x);//申请结点
  newnode->next = pos->next;//让新结点的指针域指向pos位置的下一个结点的数据域地址
  pos->next = newnode;//pos的指针域指向新结点的数据域地址
}
//单链表删除pos位置的节点
void SListErase(SLNode** pphead, SLNode* pos)
{
  assert(*pphead);
  //如果链表只有一个结点
  if (*pphead == pos)
  {
    SListPopBack(pphead);
  }
  else
  {
    //找到pos位置的前一个位置（posPrev），并记录
    SLNode* posPrev = *pphead;
    while (posPrev->next != pos)
    {
      posPrev = posPrev->next;
    }
    //让pos位置的前一个结点posPrev的指针域指向pos结点的指针域，如果pos位置还有结点，即指向了pos位置的下一个结点的数据域的地址；
    posPrev->next = pos->next;
    free(pos);//释放pos
  }
}
//单链表删除pos位置后的节点
void SListEraseAfter(SLNode* pos)
{
  assert(pos);
  assert(pos->next);
  SLNode* next = pos->next;
  pos->next = next->next;
  free(next);
}
//单链表的销毁
void SListDestroy(SLNode** pphead)
{
  assert(*pphead);
  SLNode* cur = *pphead;
  while (cur != NULL)
  {
    SLNode* next = cur->next;
    free(cur);
    cur = next;
  }
  *pphead = NULL;
}

Test.c 

#include "SList.h"
void TestList1()
{
  SLTNode* plist = NULL;
  SListPushBack(&plist, 1);
  SListPushBack(&plist, 2);
  SListPushBack(&plist, 3);
  SListPushBack(&plist, 4);
  SListPushBack(&plist, 5);
  SListPrint(plist);
  //SListPushFront(&plist, 1);
  //SListPushFront(&plist, 2);
  //SListPushFront(&plist, 3);
  //SListPushFront(&plist, 4);
  //SListPushFront(&plist, 5);
  //SListPrint(plist);
}
void TestList2()
{
  SLTNode* plist = NULL;
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPushFront(&plist, 4);
  SListPushFront(&plist, 5);
  SListPopFront(&plist);
  SListPopFront(&plist);
  SListPrint(plist);
}
void TestList3()
{
  SLTNode* plist = NULL;
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 5);
  SListPrint(plist);
  SLTNode* pos = SListFind(plist, 2);
  int i = 1;
  while (pos)
  {
    printf("%d个pos节点:%p->%d\n", i++, pos, pos->data);
    pos = SListFind(pos->next, 2);
  }
  pos = SListFind(plist, 3);
  if (pos)
  {
    pos->data = 30;
  }
  SListPrint(plist);
}
void TestList4()
{
  SLTNode* plist = NULL;
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 4);
  SListPushFront(&plist, 5);
  SListPrint(plist);
  //SLTNode* pos = SListFind(plist, 5);
  //if (pos)
  //{
  //  SListInsert(&plist, pos, 30);
  //}
  //SListPrint(plist);
}
void TestList5()
{
  SLTNode* plist = NULL;
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 4);
  SListPushFront(&plist, 5);
  SListPrint(plist);
  /*
  SLTNode* pos = SListFind(plist, 5);
  SListInsertAfter(pos, 20);
  SListPrint(plist);
  */
  /*
  SLTNode* pos = SListFind(plist, 3);
  SListEase(&plist, pos);
  SListPrint(plist);
  */
  SLTNode* pos = SListFind(plist, 5);
  SListEaseAfter(pos);
  SListPrint(plist);
  SListDestory(&plist);
}
int main()
{
  TestList1();
  //TestList2();
  //TestList3();
  //TestList4();
  //TestList5();
  return 0;
}

下一期更新顺序表和链表相关的LeetCode题


文章标签：
C语言
存储
关键词：
数据结构c语言
C语言数据结构
数据结构单链表
C语言单链表
数据结构C语言单链表
霄沫凡M
目录
相关文章
aliyun3611036241
|
12天前
|
存储 算法 C语言
通义灵码在考研C语言和数据结构中的应用实践 1-5
通义灵码在考研C语言和数据结构中的应用实践，体验通义灵码的强大思路。《趣学C语言和数据结构100例》精选了五个经典问题及其解决方案，包括求最大公约数和最小公倍数、统计字符类型、求特殊数列和、计算阶乘和双阶乘、以及求斐波那契数列的前20项和。通过这些实例，帮助读者掌握C语言的基本语法和常用算法，提升编程能力。
aliyun3611036241
49 4
ephemerals__
|
1天前
|
存储 C语言
【数据结构】顺序表（c语言实现）（附源码）
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列，常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构，其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别，并重点介绍了动态顺序表的实现，包括初始化、销毁、打印、增删查改等操作。最后，文章总结了顺序表的时间复杂度和局限性，并预告了后续关于链表的内容。
ephemerals__
10 3
java冯坚持
|
20天前
|
算法 程序员 索引
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈，并展示了如何利用栈和中缀表达式实现一个综合计算器。
java冯坚持
18 1
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
aliyun1622584902-46568
|
1天前
|
存储 算法 C语言
C语言数据结构（2）
【10月更文挑战第21天】
aliyun1622584902-46568
6 2
aliyun3611036241
|
12天前
|
存储 算法 C语言
【趣学C语言和数据结构100例】
《趣学C语言和数据结构100例》精选5个编程问题，涵盖求最大公约数与最小公倍数、字符统计、特殊序列求和及阶乘计算等，通过实例讲解C语言基础与算法思维，适合初学者实践学习。
aliyun3611036241
59 1
白子寰
|
15天前
|
存储
[数据结构] -- 单链表
[数据结构] -- 单链表
白子寰
19 1
GuGuStudy
|
21天前
|
存储 C语言
探索C语言数据结构：利用顺序表完成通讯录的实现
本文介绍了如何使用C语言中的顺序表数据结构实现一个简单的通讯录，包括初始化、添加、删除、查找和保存联系人信息的操作，以及自定义结构体用于存储联系人详细信息。
GuGuStudy
18 2
石小浪♪
|
22天前
|
存储 C语言
C语言单链表实现
一个用C语言编写的简单学生信息管理系统，该系统具备信息输入、成绩计算、排序、删除、查找、修改、保存和读取文件等功能。
石小浪♪
19 0
C语言单链表实现
努力学习的小廉
|
23天前
|
存储
【数据结构】——单链表实现
【数据结构】——单链表实现
努力学习的小廉
21 2
徐霞客320
|
25天前
|
存储
数据结构2——单链表
数据结构2——单链表
徐霞客320
30 1

热门文章

最新文章

  • 1
    C语言编程入门之--第四章C语言基本数据类型
  • 2
    【C语言】学习笔记4——数组
  • 3
    C语言OJ项目参考(1034) 求值
  • 4
    C# Json处理日期和Table
  • 5
    算法学习之C语言基础
  • 6
    C语言中的逗号操作符
  • 7
    c语言中常见错误总结
  • 8
    【C语言进阶】文件操作（一）
  • 9
    进阶C语言——指针【详解】（一）
  • 10
    LeetCode刷题(9)【树】前序&深度&平衡(C语言)
  • 1
    【MongoDB】MongoDB 如何处理复杂的数据结构？
    132
  • 2
    【数据结构】排序算法
    46
  • 3
    【数据结构】C语言实现链队列(附完整运行代码)
    121
  • 4
    深入理解InnoDB索引数据结构和算法
    312
  • 5
    【数据结构】深入浅出理解链表中二级指针的应用
    99
  • 6
    【数据结构】线性表的链式存储结构
    65
  • 7
    【数据结构】C语言实现顺序表万字详解(附完整运行代码)
    147
  • 8
    【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现（字典）（二）
    112
  • 9
    作者推荐 |【Redis技术进阶之路】「原理系列开篇」揭秘高效存储模型与数据结构底层实现（SDS）（三）
    76
  • 10
    金石推荐 | 【算法数据结构专题】「延时队列算法」史上手把手教你针对层级时间轮（TimingWheel）实现延时队列的开发实战落地（下）（一）
    125

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • 你的第一门C语言课
  • C语言学习教程

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    阿里云无影云电脑免费试用，最长可试用3个月