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

【数据结构】- 链表之单链表(下)

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

前言

未来藏在迷雾中 叫人看来胆怯 带你踏足其中 就会云开雾散

本章是关于数据结构中的链表之单链表(下)

提示：以下是本篇文章正文内容，下面案例可供参考

一、单链表(下)

1.1 查找+修改

//SList.h
SLTNode* STFind(SLTNode* phead, SLTDataType x);
//SList.c
SLTNode* STFind(SLTNode* phead, SLTDataType x)
{
  SLTNode* cur = phead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
//Test.c
void TestSList()
{
  SLTNode* plist = NULL;
  SLPushFornt(&plist, 1);
  SLPushFornt(&plist, 2);
  SLPushFornt(&plist, 3);
  SLPushFornt(&plist, 4);
  SLTPrint(plist);
  SLTNode* pos = STFind(plist, 3);
  if (pos)//判断是否为空
  {
    pos->data = 30;
  }
  SLTPrint(plist);
}

1.2 在任意位置插入

1.2.1 在pos位置插入(也就是pos位置之前)

//SList.h
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在pos之前插入
//SList.c
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  assert(pphead);
  assert(pos);
  if (*pphead == pos)
  {
    SLPushFornt(pphead, x);
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    SLTNode* newnode = BuyTNode(x);
    prev->next = newnode;
    newnode->next = pos;
  }
}
//Test.c
void TestSList()
{
  SLTNode* plist = NULL;
  SLPushFornt(&plist, 1);
  SLPushFornt(&plist, 2);
  SLPushFornt(&plist, 3);
  SLPushFornt(&plist, 4);
  SLTPrint(plist);
  SLTNode* pos = STFind(plist, 3);
  if (pos)//判断是否为空
  {
    SLInsert(&plist, pos, 30);
  }
}

流程图

多个节点

一个节点

1.2.2 在pos位置之后插入

//SList.h
void SLInsertAfter(SLTNode* pos, SLTDataType x);//在pos之后插入
//SList.c
void SLInsertAfter(SLTNode* pos, SLTDataType x)
{
  assert(pos);
  SLTNode* newnode = BuyTNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}
//Test.c
void TestSList()
{
  SLTNode* plist = NULL;
  SLPushFornt(&plist, 1);
  SLPushFornt(&plist, 2);
  SLPushFornt(&plist, 3);
  SLPushFornt(&plist, 4);
  SLTPrint(plist);
  SLTNode* pos = STFind(plist, 2);
  if (pos)//判断是否为空
  {
    SLInsertAfter(pos, 30);
  }
  SLTPrint(plist);
}

流程图：

注意：

下面这种写法就存在了问题newnode指向了它自己造成了错误

void SLInsertAfter(SLTNode* pos, SLTDataType x)
{
  assert(pos);
  SLTNode* newnode = BuyTNode(x);
  pos->next=newnode;
  newnode->next=pos->next;
}

流程图：

1.3 在任意位置删除

1.3.1 删除pos位置得值

//SList.h
void SLErase(SLTNode** pphead, SLTNode* pos);
//SList.c
void SLErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pphead);
  assert(pos);
  if (pos == *pphead)
  {
    SLPopFornt(pphead);//头删
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
  }
}
//Test.c
void TestSList()
{
  SLTNode* plist = NULL;
  SLPushFornt(&plist, 1);
  SLPushFornt(&plist, 2);
  SLPushFornt(&plist, 3);
  SLPushFornt(&plist, 4);
  SLTPrint(plist);
  SLTNode* pos = STFind(plist, 3);
  if (pos)//判断是否为空
  {
    SLErase(&plist, pos);
  }
  SLTPrint(plist);
}

流程图：

1.3.2 删除pos位置后面的值

//SList.h
void SLEraseAfter(SLTNode* pos);
//SList.c
void SLEraseAfter(SLTNode* pos)
{
  assert(pos);
  assert(pos->next);
  SLTNode* next = pos->next;
  pos->next = next->next;
  free(next);
}
//Test.c
void TestSList()
{
  SLTNode* plist = NULL;
  SLPushFornt(&plist, 1);
  SLPushFornt(&plist, 2);
  SLPushFornt(&plist, 3);
  SLPushFornt(&plist, 4);
  SLTPrint(plist);
    SLTNode* pos = STFind(plist, 3);
  if (pos)//判断是否为空
  {
    SLEraseAfter(pos);
  }
  SLTPrint(plist);
}

流程图：

二、完整代码

//SList.h
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
  SLTDataType data;
  struct SListNode* next;
}SLTNode;
void SLTPrint(SLTNode* phead);
void SLPushFornt(SLTNode** pphead, SLTDataType x);
void SLPushBack(SLTNode** pphead, SLTDataType x);
void SLPopFornt(SLTNode** pphead);
void SLPopBack(SLTNode** pphead);
SLTNode* STFind(SLTNode* phead, SLTDataType x);
//任意位置插入
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在pos之前插入
void SLInsertAfter(SLTNode* pos, SLTDataType x);//在pos之后插入
void SLErase(SLTNode** pphead, SLTNode* pos);//删除pos位置的值
void SLEraseAfter(SLTNode* pos);//删除pos位置的值
//SList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
void SLTPrint(SLTNode* phead)
{
  SLTNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
SLTNode* BuyTNode(SLTDataType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return;
  }
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
}
void SLPushFornt(SLTNode** pphead, SLTDataType x)
{
  SLTNode* newnode = BuyTNode(x);
  newnode->next  = *pphead;
  *pphead = newnode;
}
void SLPushBack(SLTNode** pphead, SLTDataType x)
{
  SLTNode* newnode = BuyTNode(x);
  //空链表
  if(*pphead==NULL)
  {
    *pphead = newnode;
  }
  //非空链表
  else
  {
    SLTNode* tail = *pphead;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}
void SLPopFornt(SLTNode** pphead)
{
  //空链表
  assert(*pphead);
  //一个节点
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  //多个节点:保存下一个节点，释放当前节点
  else
  {
    SLTNode* del = *pphead;
    *pphead = del->next;
    free(del);
  }
}
void SLPopBack(SLTNode** pphead)
{
  //空链表
  assert(*pphead);
  //有一个节点
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  有多个节点
  else
  {
  SLTNode* prev = NULL;
  SLTNode* tail = *pphead;
  //找尾
  while (tail->next == NULL)//或者写成while(tail->next)
  {
    prev = tail;
    tail = tail->next;
  }
  free(tail);
  prev->next = NULL;
    while (tail->next->next != NULL)
    {
      tail = tail->next;
    }
    free(tail->next);
    tail->next = NULL;
  }
}
SLTNode* STFind(SLTNode* phead, SLTDataType x)
{
  SLTNode* cur = phead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  assert(pphead);
  assert(pos);
  if (*pphead == pos)
  {
    SLPushFornt(pphead, x);
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    SLTNode* newnode = BuyTNode(x);
    prev->next = newnode;
    newnode->next = pos;
  }
}
//在pos之后插入
void SLInsertAfter(SLTNode* pos, SLTDataType x)
{
  assert(pos);
  SLTNode* newnode = BuyTNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}
//删除pos位置的值
void SLErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pphead);
  assert(pos);
  if (pos == *pphead)
  {
    SLPopFornt(pphead);//头删
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
  }
}
//删除pos位置后面的值
void SLEraseAfter(SLTNode* pos)
{
  assert(pos);
  assert(pos->next);
  SLTNode* next = pos->next;
  pos->next = next->next;
  free(next);
}
//Test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
void TestSList()
{
  SLTNode* plist = NULL;
  SLPushFornt(&plist, 1);
  SLPushFornt(&plist, 2);
  SLPushFornt(&plist, 3);
  SLPushFornt(&plist, 4);
  SLTPrint(plist);
  SLPushBack(&plist, 5);
  SLPopFornt(&plist);
  SLTPrint(plist);
  SLPopFornt(&plist);
  SLTPrint(plist);
  SLPopFornt(&plist);
  SLTPrint(plist);
  SLPopFornt(&plist);
  SLTPrint(plist);
  SLTNode* pos = STFind(plist, 3);
  if (pos)//判断是否为空
  {
    SLInsert(&plist, pos, 30);
  }
  SLTNode* pos = STFind(plist, 2);
  if (pos)//判断是否为空
  {
    SLInsertAfter(pos, 30);
  }
  SLTPrint(plist);
  SLTNode* pos = STFind(plist, 3);
  if (pos)//判断是否为空
  {
    SLErase(&plist, pos);
  }
  SLTPrint(plist);
  SLTNode* pos = STFind(plist, 3);
  if (pos)//判断是否为空
  {
    SLEraseAfter(pos);
  }
  SLTPrint(plist);
}
int main()
{
  TestSList();
  return 0;
}

总结

Ending,今天的链表之单链表(下)的内容就到此结束啦~，如果后续想了解更多，就请关注我吧。

关键词：
数据结构链表
数据结构单链表
链表数据结构
链表单链表
数据结构链表单链表
小沈熬夜秃头中
目录
相关文章
XIAZHI
|
1月前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法，并分析时间复杂度，理解链表特点。实验内容包括循环链表应用（约瑟夫回环问题）、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践，加深对链表数据结构的理解和应用能力。
XIAZHI
59 4
三三是该溜子
|
1天前
|
数据库
数据结构中二叉树，哈希表，顺序表，链表的比较补充
二叉搜索树，哈希表，顺序表，链表的特点的比较
三三是该溜子
10 0
数据结构中二叉树，哈希表，顺序表，链表的比较补充
龙大吉
|
28天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
54 5
ephemerals__
|
1月前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
98 4
肾透侧视攻城狮
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解（9）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
31 2
肾透侧视攻城狮
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构之单双链表按位、值查找；[前后]插入；删除指定节点；求表长、静态链表等代码及具体思路详解步骤；举例说明、注意点及常见报错问题所对应的解决方法
肾透侧视攻城狮
40 2
XIAZHI
|
1月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能，支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构，并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示，系统在处理小规模购物车时表现良好，但在大规模购物车操作下可能存在性能瓶颈。
XIAZHI
50 0
白子寰
|
2月前
|
存储
[数据结构] -- 单链表
[数据结构] -- 单链表
白子寰
28 1
ephemerals__
|
1月前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
69 0
白子寰
|
2月前
|
存储
[数据结构] -- 双向循环链表
[数据结构] -- 双向循环链表
白子寰
27 0

热门文章

最新文章

  • 1
    【C语言】深入浅出：C语言链表的全面解析
  • 2
    Python编程数据结构的深入理解
  • 3
    掌握Pandas核心数据结构：Series与DataFrame的四种创建方式
  • 4
    K-means聚类算法是机器学习中常用的一种聚类方法，通过将数据集划分为K个簇来简化数据结构
  • 5
    Python 中的数据结构与其他编程语言数据结构的区别
  • 6
    C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
  • 7
    Python 中的数据结构和算法优化策略
  • 8
    Python 中数据结构和算法的关系
  • 9
    在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
  • 10
    探索局域网电脑监控软件：Python算法与数据结构的巧妙结合
  • 1
    数据结构中二叉树，哈希表，顺序表，链表的比较补充
    10
  • 2
    探索局域网电脑监控软件：Python算法与数据结构的巧妙结合
    43
  • 3
    Pandas数据结构：Series与DataFrame
    43
  • 4
    Java 集合江湖：底层数据结构的大揭秘！
    36
  • 5
    es采用什么数据结构
    36
  • 6
    掌握Pandas核心数据结构：Series与DataFrame的四种创建方式
    142
  • 7
    Redis 5 种基础数据结构？
    28
  • 8
    C语言中的位运算技巧，涵盖基本概念、应用场景、实用技巧及示例代码，并讨论了位运算的性能优势及其与其他数据结构和算法的结合
    41
  • 9
    C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
    60
  • 10
    Python 中的数据结构和算法优化策略
    56

    • 相关课程

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

    • 相关电子书

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