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

【数据结构】单链表之--无头单向非循环链表

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

前言：前面我们学习了动态顺序表并且模拟了它的实现，今天我们来进一步学习，来学习单链表！一起加油各位，后面的路只会越来越难走需要我们一步一个脚印！

单链表

今天我们要实现的全部功能就如下所示，功能很多我们一步一步来，一起来手撕链表吧！加油！

typedef int SLNDataType;

typedef struct SList
{
  int val;
  struct SList* next;
}SLNode;

//单链表的打印
void SLTPrint(SLNode* phead);

//单链表的尾插
void SLTPushBack(SLNode** pphead, SLNDataType x);

//单链表的头插
void SLTPushFront(SLNode** pphead, SLNDataType x);

//单链表的尾删
void SLTPopback(SLNode** pphead);

//单链表的头删
void SLTPopFront(SLNode** pphead);

//单链表的元素查找
SLNode* SLFind(SLNode* phead, SLNDataType x);

//单链表的插入-在pos的前面插入
SLNode* SLInsert(SLNode** pphead,SLNode* pos, SLNDataType x);//需要自己思考一级还是二级

//单链表的删除
void SLTErase(SLNode** pphead, SLNode* pos);


//单链表的销毁
void SLTDestroy(SLNode** pphead);


//单链表的删除-pos之后的元素
void SLTEraseAfter(SLNode* pos,SLNDataType x);

//单链表插入-pos之后插入
void SLTInsertAfter(SLNode* pos,SLNDataType x);

动态申请一个结点

代码思路，首先我们要开辟一个结构体，来开始我们今天的单链表

typedef struct SList
{
  int val;
  struct SList* next;
}SLNode;

当然了，我们肯定得写一个接口，来申请动态开辟的一个结点(这个我们在前面写顺序表的时候就写过了，就不过多介绍这个了)，可以看下图帮助自己理解 

SLNode* CreateNewNode(SLNDataType x)//开辟一个新的节点
{
  SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
  if (newnode == NULL)//判断是否有空间
  {
    perror("malloc fail");
    exit(-1);
  }
  newnode->val = x;
  newnode->next = NULL;
  return newnode;
}

单链表的打印

代码思路：单链表中我们可以知道它是如下图这种形式，每一个结构体中存着下个节点的地址，我们可以通过判断结构体指针是否为空指针来依次打印

void SLTPrint(SLNode* phead)
{
  SLNode* cur = phead;//通过头节点依次访问
  while (cur != NULL)
  {
    printf("%d->", cur->val);
    cur = cur->next;
  }
  printf("NULL\n");
}

单链表的尾插

在写代码之前，我们需要重新复习一下，对形参的修改不会改变实参,形参是实参的一个临时拷贝（请牢牢记住，后面有很大的作用），这在后面帮助我们理解单链表有很大的帮助。

我们先来看一串代码

void swap(int* a, int* b)
{
  int tmp = 0;
  tmp = *a;
  *a = *b;
  *b = tmp;
}

int main()
{
  int a = 3;
  int b = 5;
  swap(&a, &b);
  printf("a = %d,b = %d", a, b);
  return 0;
}

我们要想改变

void swap(int** a, int** b)
{
  int tmp = 0;
  tmp = **a;
  **a = **b;
  **b = tmp;
}

int main()
{
  int arr1[] = { 1 };
  int arr2[] = { 2 };
  int* a = arr1;
  int* b = arr2;
  swap(&a, &b); 
  printf("*a = %d, *b = %d",*a, *b);
  return 0;
}

由这些可以知道，我们要想修改一级指针里面的值，我们要用二级指针接收。接下来我们就开始上我们的第一盘凉菜了！

代码思路：首先我们肯定要考虑两种情况，即一种是链表是空的什么都没有，另一种即链表中有值，需要我们尾增新的值，我们可以借助下图来帮助我们分析！我们通过循环找到该链表的尾结点，然后让尾部结点中的next，假如链表中没有值是空链表，我们直接指向新的结点即可。

void SLTPushBack(SLNode** pphead, SLNDataType x)//尾插节点
{
  assert(pphead);//判断传过来的链表是否存在

  SLNode* newnode = CreateNewNode(x);//开辟节点
  if (*pphead == NULL)//判断传来的是否是空指针，如果为空就直接开辟新的节点
  {
    *pphead = newnode;
  }
  else
  {
    SLNode* tail = *pphead;
    while (tail->next != NULL)//只有尾结点的next才是空
    {
      tail = tail->next;//找到尾节点
    }
    tail->next = newnode;//将为节点的值指向新节点
  }
}

这里大家肯定会有很多疑问，为什么是 **phead ,我们来看下图

函数测试与结果运行图：

void Test1()
{
  SLNode* plist = NULL;
  SLTPushBack(&plist, 1);//尾插
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPushBack(&plist, 4);
  SLTPrint(plist);
}


int main()
{
  Test1();
  return 0;
}

单链表的头插

代码思路：单链表的头插我们依然得借助图像来帮助我们分析如下图，我们让*phead指向newnode开辟的结点，在让newnode->next指向原本的头结点即可完成头插，当然我们依然得用二级指针接收，因为我们要修改的一级指针。

代码实现：

void SLTPushFront(SLNode** pphead, SLNDataType x)//单链表的头插
{
  assert(pphead);
  SLNode* newnode = CreateNewNode(x);//开辟一个新的节点
  newnode->next = *pphead;//将头节点地址存放在next中
  *pphead = newnode;  //在让头节点指向Newnode，此时newnode就称为了头节点
}

函数测试与效果图：

void Test2()
{
  SLNode* plist = NULL;
  SLTPushFront(&plist, 2);//头插
  SLTPushFront(&plist, 2);
  SLTPushFront(&plist, 9);
  SLTPrint(plist);
}

int main()
{
  //Test1();
  Test2();
  return 0;
}

单链表的尾删

思路分析：在单链表的尾部删除中，我们需要考虑两种情况一种为单节点，一种为多节点，即一种删除完后链表中的值为空，另一种即删除最后一个后仍然还有结点。当然了，我们依然得先画图分析，如下图。我们看图一，可以知道，我们直接找到 *phead这个结点将他free掉即可，然后将 *phead置为空指针，即可完成单结点的删除。我们看图二，我们得找到一个尾结点将它释放，将尾部结点的前一个结点中的next即保留最后一个结点中的地址，让它置为空指针即删除完毕，由此我们可以通过一个快慢指针，一个指针往后走，一个保留前一个结点的地址，因此我们可以找到最后一个结点并保留前一个结点的地址。


代码思路：

void SLTPopback(SLNode** pphead)//单链表的尾删
{
  //一个节点
  //多个节点
  assert(pphead);
  assert(*pphead);
  if ((*pphead)->next == NULL)//单节点
  {
    free(*pphead);//释放pphead所在的空间
    *pphead = NULL;//将pphead置为空指针
  }
  else//多节点
  {
    SLNode* tail = *pphead;//铜鼓快慢指针来找到节点
    SLNode* prev = NULL;
    while (tail->next != NULL)//找到尾节点
    {
      //倒数第一步(尾节点的前一个节点时)
      prev = tail;//此时prev就是记录后一个节点的地址
      tail = tail->next;//此时找到了NULL
    }
    free(tail);//释放掉记录尾结点的地址
    prev->next = NULL;//将此时赋值为NULL即删除成功
  }
}

函数测试与运行结果：

void Test3()
{
  SLNode* plist = NULL;
  printf("打印删除之前的\n");
  SLTPushFront(&plist, 2);//头增
  SLTPushFront(&plist, 2);
  SLTPushFront(&plist, 9);
  SLTPrint(plist);
  printf("打印删除之后的\n");
  SLTPopback(&plist);//尾删
  SLTPopback(&plist);
  SLTPrint(plist);
}

int main()
{
  //Test1();
  //Test2();
  Test3();
  return 0;
}

单链表的头删

思路分析:实现头删，我们就是把头部中的空间free掉,在将 *phead指向原本的第二个节点即可，因此我们需要用一个结构体指针指向第二个节点将其保留下来传给原本的头指针。可以通过下图帮助自己分析，如下图。

代码思路实现：

void SLTPopFront(SLNode** pphead)//头删
{
  //空
  assert(pphead);
  //多个节点
  SLNode* tmp = (*pphead)->next;
  free(*pphead);
  *pphead = tmp;  
}

测试函数与运行结果：

void Test4()
{
  SLNode* plist = NULL;
  printf("打印删除之前的\n");
  SLTPushFront(&plist, 2);//尾增
  SLTPushFront(&plist, 2);
  SLTPushFront(&plist, 9);
  SLTPrint(plist);
  printf("打印删除之后的\n");
  SLTPopFront(&plist);//头删
  SLTPopFront(&plist);
  SLTPrint(plist);
}
int main()
{
  //Test1();
  //Test2();
  //Test3();
  Test4();
  return 0;
}

单链表的数值查找

思路分析：我们可以通过指针去一次遍历链表中的数据，找到对应值即找到了，返回此时指针的地址，遍历到最后一个NULL也没有找到时，即返回空指针，如下图

代码实现:

SLNode* SLFind(SLNode* phead, SLNDataType x)//查找
{
  assert(phead);
  SLNode* tail = phead;
  while (tail)
  {
    if(tail->val == x)
    {
      return tail;//返回此时指针的值
    }
    tail = tail->next;
  }
  return NULL;
}


函数测试与效果图：

void Test5()
{
  SLNode* plist = NULL;
  printf("打印删除之前的\n");
  SLTPushFront(&plist, 2);//尾增
  SLTPushFront(&plist, 2);
  SLTPushFront(&plist, 9);
  SLTPrint(plist);
  printf("查找结果:\n");
  printf("%p\n",SLFind(plist, 2));//查找数
  printf("%p\n", SLFind(plist, 99));
}
int main()
{
  //Test1();
  //Test2();
  //Test3();
  //Test4();
  Test5();
  return 0;
}


单链表的插入- 在pos的前面插入

思路分析：如果是多节点要想实现在pos的前面插入，首先我们要找到pos的前面一个节点让它指向我们新开辟的节点newnode然后再让newnode->next指向我们原本pos的所在的节点就完成了头插，如下图1所示。如果是单节点的时候，就是相当于头插，我们只需要判断是否是单节点，如果是就直接调用头插函数即可。

代码实现：

SLNode* SLInsert(SLNode** pphead, SLNode* pos, SLNDataType x)//单链表插入
{
  assert(pphead);
  assert(pos);
  assert(*pphead);
  //单节点
  if (*pphead == pos)
  {
    //头插
    SLTPushFront(pphead, x);
  }
  else
  {
    //多节点
    SLNode* tail = *pphead;
    SLNode* newnode = CreateNewNode(x);
    while (tail->next != pos)
    {
      tail = tail->next;
    }
    tail->next = newnode;
    newnode->next = pos;
  }
}

函数测试与效果图：

void Test6()
{
  SLNode* plist = NULL;
  printf("原本的值\n");
  SLTPushFront(&plist, 2);//尾增
  SLTPushFront(&plist, 2);
  SLTPushFront(&plist, 9);
  SLTPrint(plist);
  printf("插入之后的结果\n");
  SLNode* address = SLFind(plist, 2);//查找数
  SLInsert(&plist, address, 10);
  SLTPrint(plist);
}
int main()
{
  //Test1();
  //Test2();
  //Test3();
  //Test4();
  //Test5();
  Test6();
  return 0;
}

单链表数值的删除-删除Pos前的值

思路分析：当然了单链表的删除我们依然得采用俩种情况，一种情况为单节点，一种情况为多节点，我们先来分析多节点，如果是多节点的情况，我们应当找到pos的节点将它释放掉，并且我们应当将pos的前一个节点将他记录下来，并让它指向pos之后的一个节点，此时我们即可完成数值的删除。如下图所示，如果是单节点的情况，我们可以直接当成头删，直接调用头删函数即可。

代码实例：

void SLTErase(SLNode** pphead, SLNode* pos)//数值的删除
{
  assert(pphead);//判断传来的结构体是否存在
  assert(*pphead);//判断是否为空指针
  assert(pos);//判断空地址
  if (*pphead == pos)
  {
    SLTPopFront(pphead);//头删
  }
  else
  {
    SLNode* tail = *pphead;
    while (tail->next != pos)
    {
      tail = tail->next;
    }
    tail->next = pos->next;
    free(pos);
    pos = NULL;
  }
}

函数测试与效果图：

void Test7()
{
  SLNode* plist = NULL;
  printf("原本的值\n");
  SLTPushFront(&plist, 2);//尾增
  SLTPushFront(&plist, 3);
  SLTPushFront(&plist, 2);
  SLTPushFront(&plist, 9);
  SLTPrint(plist);
  printf("删除之后的结果\n");
  SLNode* address = SLFind(plist, 2);//查找数
  SLTErase(&plist, address);
  SLTPrint(plist);
}
int main()
{
  //Test1();
  //Test2();
  //Test3();
  //Test4();
  //Test5();
  //Test6();
  Test7();
  return 0;
}

单链表的销毁

思路分析：要想销毁单链表中的所有值，我们只需要把单链表中的每个节点给它释放，并最后让头节点指向空指针即可，因此我们需要借助两个指针，一个指针指向tail的下一个节点，当释放掉tail后让tail可以指向下一个节点再依次释放，这样就可以达到链表的销毁的作用，如下图所示。

代码实例：

void SLTDestroy(SLNode** pphead)//单链表的销毁
{
  assert(*pphead);//判断传来的是否已经是空指针
  SLNode* tail = *pphead;
  SLNode* pre = NULL;
  while (tail != NULL)//找到尾节点
  {
    pre = tail->next;
    free(tail);//依次释放
    tail = pre;
  }
  *pphead = NULL;
}

函数测试与效果图:

void Test8()
{
  SLNode* plist = NULL;
  printf("原本的值\n");
  SLTPushFront(&plist, 2);//尾增
  SLTPushFront(&plist, 3);
  SLTPushFront(&plist, 2);
  SLTPushFront(&plist, 9);
  SLTPrint(plist);
  printf("删除之后的结果\n");
  SLTDestroy(&plist);
  SLTPrint(plist);
}

int main()
{
  //Test1();
  //Test2();
  //Test3();
  //Test4();
  //Test5();
  //Test6();
  Test8();
  return 0;
}

结语：今天的内容就到这里吧，谢谢各位的观看，如果有讲的不好的地方也请各位多多指出，作者每一条评论都会读的，谢谢各位。


关键词：
数据结构单链表
数据结构链表
数据结构循环链表
链表单向
数据结构单向
卫卫周大胖
目录
相关文章
2的n次方_
|
15天前
|
存储 Java 索引
【数据结构】链表从实现到应用，保姆级攻略
本文详细介绍了链表这一重要数据结构。链表与数组不同，其元素在内存中非连续分布，通过指针连接。Java中链表常用于需动态添加或删除元素的场景。文章首先解释了单向链表的基本概念，包括节点定义及各种操作如插入、删除等的实现方法。随后介绍了双向链表，说明了其拥有前后两个指针的特点，并展示了相关操作的代码实现。最后，对比了ArrayList与LinkedList的不同之处，包括它们底层实现、时间复杂度以及适用场景等方面。
2的n次方_
31 10
【数据结构】链表从实现到应用，保姆级攻略
小徐在进步
|
11天前
|
存储 算法 C语言
数据结构基础详解(C语言):单链表_定义_初始化_插入_删除_查找_建立操作_纯c语言代码注释讲解
本文详细介绍了单链表的理论知识，涵盖单链表的定义、优点与缺点，并通过示例代码讲解了单链表的初始化、插入、删除、查找等核心操作。文中还具体分析了按位序插入、指定节点前后插入、按位序删除及按值查找等算法实现，并提供了尾插法和头插法建立单链表的方法，帮助读者深入理解单链表的基本原理与应用技巧。
小徐在进步
32 6
aliyun6365824167
|
1月前
|
算法 索引
【初阶数据结构篇】单链表算法题进阶
深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。
aliyun6365824167
14 0
aliyun6365824167
|
1月前
|
存储 算法
【初阶数据结构篇】顺序表和链表算法题
此题可以先找到中间节点，然后把后半部分逆置，最近前后两部分一一比对，如果节点的值全部相同，则即为回文。
aliyun6365824167
16 0
aliyun6365824167
|
1月前
|
存储 测试技术
【初阶数据结构篇】双向链表的实现（赋源码）
因为头结点的存在，plist指针始终指向头结点，不会改变。
aliyun6365824167
20 0
aliyun6365824167
|
1月前
|
存储 测试技术
【初阶数据结构篇】单链表的实现（附源码）
在尾插/尾删中，都需要依据链表是否为空/链表是否多于一个节点来分情况讨论，目的是避免对空指针进行解引用造成的错误。
aliyun6365824167
18 0
国中之林
|
1月前
|
算法
【数据结构与算法】共享双向链表
【数据结构与算法】共享双向链表
国中之林
11 0
小徐在进步
|
9天前
|
存储 人工智能 C语言
数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值&&特殊矩阵的压缩存储
本文首先介绍了栈的应用之一——括号匹配，利用栈的特性实现左右括号的匹配检测。接着详细描述了南京理工大学的一道编程题，要求判断输入字符串中的括号是否正确匹配，并给出了完整的代码示例。此外，还探讨了栈在表达式求值中的应用，包括中缀、后缀和前缀表达式的转换与计算方法。最后，文章介绍了矩阵的压缩存储技术，涵盖对称矩阵、三角矩阵及稀疏矩阵的不同压缩存储策略，提高存储效率。
小徐在进步
28 8
小徐在进步
|
11天前
|
存储 C语言
数据结构基础详解(C语言): 栈与队列的详解附完整代码
栈是一种仅允许在一端进行插入和删除操作的线性表，常用于解决括号匹配、函数调用等问题。栈分为顺序栈和链栈，顺序栈使用数组存储，链栈基于单链表实现。栈的主要操作包括初始化、销毁、入栈、出栈等。栈的应用广泛，如表达式求值、递归等场景。栈的顺序存储结构由数组和栈顶指针构成，链栈则基于单链表的头插法实现。
小徐在进步
44 3
2的n次方_
|
12天前
|
Java
【数据结构】栈和队列的深度探索，从实现到应用详解
本文介绍了栈和队列这两种数据结构。栈是一种后进先出（LIFO）的数据结构，元素只能从栈顶进行插入和删除。栈的基本操作包括压栈、出栈、获取栈顶元素、判断是否为空及获取栈的大小。栈可以通过数组或链表实现，并可用于将递归转化为循环。队列则是一种先进先出（FIFO）的数据结构，元素只能从队尾插入，从队首移除。队列的基本操作包括入队、出队、获取队首元素、判断是否为空及获取队列大小。队列可通过双向链表或数组实现。此外，双端队列（Deque）支持两端插入和删除元素，提供了更丰富的操作。
2的n次方_
14 0
【数据结构】栈和队列的深度探索，从实现到应用详解