AI 助理
备案控制台
开发者社区 云计算 文章 正文

数据结构--单链表

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


链表

概念与结构

链表是一种常见的数据结构，用于存储和组织数据。它由一系列节点组成，每个节点包含两部分：数据和指向下一个节点的指针。

链表中的节点在内存中可以分布在任意位置，不像数组那样需要连续的存储空间。每个节点都包含了存储的数据以及指向下一个节点的指针。通过这种方式，链表可以灵活地分配和管理内存空间。就像一节节连动的火车车厢；

在数据结构中，呈现：

逻辑图中，呈现：

在逻辑图中，链式结构是连续性的，但实际上不一样连续；从数据结构中看出，链表是通过地址来联系在一起的，不需要地址的连续性；在我们要解决链表相关问题时，只需要画出逻辑图即可；

注意：

结点的空间在堆区中开辟；堆区中申请出的空间，会按照一定的策略进行分配，两次申请的空间可能连续，可能不连续；

链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

1. 单向或者双向

2. 带头或者不带头

3. 循环或者非循环

可以通过一定的组合达成不同种类的链表；

这里我们比较常用的是有两种结构：

在这里，我们将先实现无头单向非循环链表，这是链表中结构最为简单的；简称单链表。

单链表的接口实现

先写一下它的结构：

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLTDataType;
typedef struct SLTNode
{
  SLTDataType data;
  struct SListNode* next;
  
}SLTNode;

结构体中放入一个数据存储类型和一个结构体指针；结构体指针存放下一个结点的地址；

单链表打印

void SLTrint(SLTNode* phead)
{
  SLTNode* cur = phead;
  while (cur)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}

将链表从头到尾遍历一遍，用一个cur指针来进行移动，在while循环中不断遍历打印出结果；打印完就进入下一个结点；

增加链表结点

SLTNode* BuySListNode(SLTDataType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
    perror("mallco fail");
    exit(-1);
  }
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
}

用动态内存分配进行扩容，同时对data和next进行初始化；最后返回结点；

 

尾插

void SLPushBack(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newnode = BuySListNode(x);
  if (* pphead == NULL)
  {
    * pphead = newnode;
  }
  else
  {
    SLTNode* tail = * pphead;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
  
}

这里要注意，我们的形参用到了二级指针，因为当结构体指针为空时，我们就需要对结构体指针进行改变，用二级指针接收结构体指针的地址，能够有效的访问，否则将会报错；当结构体指针不为空时，就利用结构体指针通过循环访问到尾结点，然后在尾结点进行连接；

 

验证：

void Test3()
{
  SLTNode* plist = NULL;
  SLPushBack(&plist, 1);
  SLPushBack(&plist, 2);
  SLPushBack(&plist, 3);
  SLPushBack(&plist, 4);
  SLTrint(plist);
  
}
int main()
{
  Test3();
  return 0;
}

尾删

void SLPopBack(SLTNode** pphead)
{
  assert(pphead);
  //判空
  assert(*pphead);
  //一个节点
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  //其他
  else
  {
    SLTNode* tailPrev = NULL;
    SLTNode* tail = *pphead;
    while (tail->next)
    {
      tailPrev = tail;
      tail = tail->next;
    }
    free(tail);
    tailPrev->next = NULL;
  }
}

当删除的是第一个结点，将会改变结构体指针的地址，所以形参要引用二级指针；其他情况就先找到尾结点，然后进行删除；

 

验证：

void Test3()
{
  SLTNode* plist = NULL;
  SLPushBack(&plist, 1);
  SLPushBack(&plist, 2);
  SLPushBack(&plist, 3);
  SLPushBack(&plist, 4);
  SLTrint(plist);
  SLPopBack(&plist);
  SLTrint(plist);
  
}
int main()
{
  Test3();
  return 0;
}

头插头删

void SLPushFront(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newnode = BuySListNode(x);
  
  newnode->next = *pphead;
  *pphead = newnode;
}
void SLPopFront(SLTNode** pphead)
{ 
  assert(pphead);
  //判空
  assert(*pphead);
  //其他
  SLTNode* newhead = (*pphead)->next;
  free(*pphead);
  *pphead = newhead;
}

头插相对尾插来说比较容易，因为有头指针，所以不用遍历循环来找到尾结点；并且无论头节点是否为空，操作程序都保持一致；

头删只要找到头结点的下一个结点，那么就可以删除了；

 

验证：

void Test2()
{
  SLTNode* plist = NULL;
  SLPushBack(&plist, 1);
  SLPushBack(&plist, 2);
  SLPushBack(&plist, 3);
  SLPushBack(&plist, 4);
  SLPushBack(&plist, 5);
  SLTrint(plist);
  SLPushFront(&plist, 6);
  SLPushFront(&plist, 7);
  SLPushFront(&plist, 8);
  SLPushFront(&plist, 9);
  SLTrint(plist);
  SLPopFront(&plist);
  SLTrint(plist);
}
int main()
{
  Test2();
  return 0;
}

查找与插入

SLTNode* SLFind(SLTNode* phead, SLTDataType x)
{
  //判空
  assert(phead);
  SLTNode* cur = phead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
  assert(pos);
  SLTNode* newnode = BuySListNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
  
}

查找：在循环里面通过结点的data与x进行匹配，找到就返回该结点，找不到返回空；如果有多个结点的data与x一致，返回链表最接近头指针的；

插入：是在pos后面进行插入，这样插入比较方便，不用考虑头指针是否为空的问题；

 

验证：

void Test3()
{
  SLTNode* plist = NULL;
  SLPushBack(&plist, 1);
  SLPushBack(&plist, 2);
  SLPushBack(&plist, 3);
  SLPushBack(&plist, 4);
  SLTrint(plist);
  SLTNode* pos = SLFind(plist, 3);
  SLTInsertAfter(pos, 88);
  SLTrint(plist);
}
int main()
{
  Test3();
  return 0;
}

删除pos结点

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pos);
  if (pos == *pphead)
  {
    SLPopFront(pphead);
  }
  else
  {
    SLTNode* perv = *pphead;
    while (perv->next != pos)
    {
      perv = perv->next;
    }
    perv->next = pos->next;
    free(pos);
  }
}
void SLTEraseAfter(SLTNode* pos)
{
  assert(pos);
  //检查尾节点
  assert(pos->next);
  SLTNode* posNext = pos->next;
  pos->next = posNext->next;
  free(posNext);
}

第一种删除是删除pos结点，但需要判断该结点是否为首结点；而且需要遍历找到pos结点的前一个结点；比较麻烦；

第二种删除是删除pos结点后一个结点，只需要通过pos结点连接到下下一个结点即可，最后free掉pos的下一个结点；

验证：

void Test3()
{
  SLTNode* plist = NULL;
  SLPushBack(&plist, 1);
  SLPushBack(&plist, 2);
  SLPushBack(&plist, 3);
  SLPushBack(&plist, 4);
  SLTrint(plist);
  SLTNode* pos = SLFind(plist, 3);
  SLTInsertAfter(pos, 88);
  SLTrint(plist);
  SLTErase(&plist, pos);
  SLTrint(plist);
  
}
int main()
{
  Test3();
  return 0;
}

 

void Test3()
{
  SLTNode* plist = NULL;
  SLPushBack(&plist, 1);
  SLPushBack(&plist, 2);
  SLPushBack(&plist, 3);
  SLPushBack(&plist, 4);
  SLTrint(plist);
  SLTNode* pos = SLFind(plist, 3);
  SLTInsertAfter(pos, 88);
  SLTrint(plist);
  SLTEraseAfter(pos);
  SLTrint(plist);
  
}
int main()
{
  Test3();
  return 0;
}

摧毁

void SLTDestroy(SLTNode** pphead)
{
  assert(pphead);
  SLTNode* cur = *pphead;
  while (cur)
  {
    SLTNode* prev = cur;
    cur = cur->next;
    free(prev);
  }
  *pphead = NULL;
}

通过记住头结点的下一个结点，free掉头节点，然后头节点的下一个结点成为新的头节点；

验证：

void Test3()
{
  SLTNode* plist = NULL;
  SLPushBack(&plist, 1);
  SLPushBack(&plist, 2);
  SLPushBack(&plist, 3);
  SLPushBack(&plist, 4);
  SLTrint(plist);
  SLTNode* pos = SLFind(plist, 3);
  SLTInsertAfter(pos, 88);
  SLTrint(plist);
  SLTDestroy(&plist);
  SLTrint(plist);
}
int main()
{
  Test3();
  return 0;
}

完整代码

slist.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLTDataType;
typedef struct SLTNode
{
  SLTDataType data;
  struct SListNode* next;
  
}SLTNode;
void SLTrint(SLTNode* phead);
SLTNode* BuySListNode(SLTDataType x);
void SLPushBack(SLTNode** pphead, SLTDataType x);
void SLPushFront(SLTNode** pphead, SLTDataType x);
void SLPopBack(SLTNode** pphead);
void SLPopFront(SLTNode** pphead);
SLTNode* SLFind(SLTNode* phead, SLTDataType x);
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
void SLTErase(SLTNode** pphead, SLTNode* pos);
void SLTEraseAfter(SLTNode* pos);
void SLTDestroy(SLTNode** phead);

slist.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include"Slist.h"
void SLTrint(SLTNode* phead)
{
  SLTNode* cur = phead;
  while (cur)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
SLTNode* BuySListNode(SLTDataType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
    perror("mallco fail");
    exit(-1);
  }
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
}
void SLPushBack(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newnode = BuySListNode(x);
  if (* pphead == NULL)
  {
    * pphead = newnode;
  }
  else
  {
    SLTNode* tail = * pphead;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
  
}
void SLPushFront(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newnode = BuySListNode(x);
  
  newnode->next = *pphead;
  *pphead = newnode;
}
void SLPopBack(SLTNode** pphead)
{
  assert(pphead);
  //判空
  assert(*pphead);
  //一个节点
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  //其他
  else
  {
    SLTNode* tailPrev = NULL;
    SLTNode* tail = *pphead;
    while (tail->next)
    {
      tailPrev = tail;
      tail = tail->next;
    }
    free(tail);
    tailPrev->next = NULL;
  }
}
void SLPopFront(SLTNode** pphead)
{ 
  assert(pphead);
  //判空
  assert(*pphead);
  //其他
  SLTNode* newhead = (*pphead)->next;
  free(*pphead);
  *pphead = newhead;
}
SLTNode* SLFind(SLTNode* phead, SLTDataType x)
{
  //判空
  assert(phead);
  SLTNode* cur = phead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
  assert(pos);
  SLTNode* newnode = BuySListNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
  
}
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pos);
  if (pos == *pphead)
  {
    SLPopFront(pphead);
  }
  else
  {
    SLTNode* perv = *pphead;
    while (perv->next != pos)
    {
      perv = perv->next;
    }
    perv->next = pos->next;
    free(pos);
  }
}
void SLTEraseAfter(SLTNode* pos)
{
  assert(pos);
  //检查尾节点
  assert(pos->next);
  SLTNode* posNext = pos->next;
  pos->next = posNext->next;
  free(posNext);
}
void SLTDestroy(SLTNode** pphead)
{
  assert(pphead);
  SLTNode* cur = *pphead;
  while (cur)
  {
    SLTNode* prev = cur;
    cur = cur->next;
    free(prev);
  }
  *pphead = NULL;
}

test.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include"Slist.h"
void Test1()
{
  int n;
  SLTNode* plist = NULL;
  printf("请输入链表长度");
  scanf("%d", &n);
  printf("请输入值");
  for (int i = 0; i < n; i++)
  {
    int val;
    scanf("%d", &val);
    SLTNode* newnode = BuySListNode(val);
    newnode->next = plist;
    plist = newnode;
  }
  SLTrint(plist);
}
void Test2()
{
  SLTNode* plist = NULL;
  SLPushBack(&plist, 1);
  SLPushBack(&plist, 2);
  SLPushBack(&plist, 3);
  SLPushBack(&plist, 4);
  SLPushBack(&plist, 5);
  SLTrint(plist);
  SLPushFront(&plist, 6);
  SLPushFront(&plist, 7);
  SLPushFront(&plist, 8);
  SLPushFront(&plist, 9);
  SLTrint(plist);
  SLPopFront(&plist);
  SLTrint(plist);
}
void Test3()
{
  SLTNode* plist = NULL;
  SLPushBack(&plist, 1);
  SLPushBack(&plist, 2);
  SLPushBack(&plist, 3);
  SLPushBack(&plist, 4);
  SLTrint(plist);
  SLTNode* pos = SLFind(plist, 3);
  SLTInsertAfter(pos, 88);
  SLTrint(plist);
  SLTDestroy(&plist);
  SLTrint(plist);
}
int main()
{
  Test3();
  return 0;
}
文章标签：
存储
关键词：
数据结构单链表
诡异森林。
目录
相关文章
睡觉待开机
|
3月前
【数据结构】单链表(长期维护)（1）
【数据结构】单链表(长期维护)（1）
睡觉待开机
30 0
java冯坚持
|
1月前
|
算法 程序员 索引
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈，并展示了如何利用栈和中缀表达式实现一个综合计算器。
java冯坚持
31 1
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
白子寰
|
1月前
|
存储
[数据结构] -- 单链表
[数据结构] -- 单链表
白子寰
26 1
杀死一只知更鸟debug
|
2月前
|
存储 Java
java数据结构，线性表链式存储（单链表）的实现
文章讲解了单链表的基本概念和Java实现，包括头指针、尾节点和节点结构。提供了实现代码，包括数据结构、接口定义和具体实现类。通过测试代码演示了单链表的基本操作，如添加、删除、更新和查找元素，并总结了操作的时间复杂度。
杀死一只知更鸟debug
32 1
java数据结构，线性表链式存储（单链表）的实现
努力学习的小廉
|
1月前
|
存储
【数据结构】——单链表实现
【数据结构】——单链表实现
努力学习的小廉
28 2
徐霞客320
|
1月前
|
存储
数据结构2——单链表
数据结构2——单链表
徐霞客320
33 1
是店小二呀
|
1月前
|
存储
【初阶数据结构】深入解析单链表:探索底层逻辑（无头单向非循环链表）（一）
【初阶数据结构】深入解析单链表:探索底层逻辑（无头单向非循环链表）
是店小二呀
45 1
星霜旅人
|
1月前
|
存储
数据结构（单链表）
数据结构（单链表）
星霜旅人
16 0
平凡程序猿~
|
1月前
|
存储
数据结构--单链表
数据结构--单链表
平凡程序猿~
23 0
是店小二呀
|
1月前
|
存储 缓存
【初阶数据结构】深入解析单链表:探索底层逻辑（无头单向非循环链表）（二）
【初阶数据结构】深入解析单链表:探索底层逻辑（无头单向非循环链表）
是店小二呀
46 0

热门文章

最新文章

  • 1
    我花了一夜用数据结构给女朋友写个H5走迷宫游戏
  • 2
    数据结构学习笔记【持续更新】
  • 3
    基于OHCI的USB主机 —— OHCI（自定义数据结构）
  • 4
    【数据结构7】查找
  • 5
    数据结构（2）：栈的原理和实现
  • 6
    算法导论第十四章 数据结构的扩张
  • 7
    学数据结构，只需要基本的编程体验
  • 8
    R语言学习笔记（一）数据结构
  • 9
    基于OHCI的USB主机 —— UFI数据结构2
  • 10
    数据结构示例——堆排序过程
  • 1
    `geopandas`是一个开源项目，它为Python提供了地理空间数据处理的能力。它基于`pandas`库，并扩展了其对地理空间数据（如点、线、多边形等）的支持。`GeoDataFrame`是`geopandas`中的核心数据结构，它类似于`pandas`的`DataFrame`，但包含了一个额外的地理列（通常是`geometry`列），用于存储地理空间数据。
    70
  • 2
    “解锁Python高级数据结构新姿势：图的表示与遍历，让你的算法思维跃升新高度
    44
  • 3
    Redis数据结构—跳跃表 skiplist 实现源码分析
    65
  • 4
    逆袭之路！用 Python 玩转图的 DFS 与 BFS，让数据结构难题无处遁形
    65
  • 5
    Python中的列表（List）和元组（Tuple）是两种重要的数据结构
    56
  • 6
    【数据结构OJ题】链表分割
    32
  • 7
    【数据结构常见七大排序（三）上】—交换排序篇【冒泡排序】And【快速排序】
    46
  • 8
    【数据结构常见七大排序（二）】—选择排序篇【直接选择排序】And【堆排序】
    34
  • 9
    【数据结构常见七大排序（一）】—插入排序篇【直接插入排序】And【希尔排序】
    47
  • 10
    【数据结构OJ题】链表的回文结构
    39

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    手把手教你白嫖阿里云服务器(免费领服务器)