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

【数据结构】单链表(长期维护)（1）

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

下面是本项目的大体思路梳理：

一、实现单链表

全部接口一览：

void SLTPrint(SLTNode* phead);//打印
void SLTPushBack(SLTNode** pphead,SLTDateType x);//尾插
void SLTPushiFront(SLTNode** pphead, SLTDateType x);//头插
void SLTPopBack(SLTNode** pphead);//尾删
void SLTPopFront(SLTNode** pphead);//头删
void SLTInsert(SLTNode** pphead,SLTNode* pos,SLTDateType x);//任意位置之前插入
SLTNode* SLTFind(SLTNode** pphead, SLTDateType x);//查找接口
void SLTInsertAfter(SLTNode* pos, SLTDateType x);//任意位置之后插入
void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos指向的节点
void SLTEraseAfter(SLTNode* pos);//删除pos指向之后的节点
void SLTDestroy(SLTNode** pphead);//销毁链表接口

1.创建链表的结构体

//定义单链表结构体
#define SLTDateType int
typedef struct SListNode
{
  SLTDateType date;//每个节点的数据
  struct SListNode* next;//每个节点存储下一个节点的地址
}SLTNode;

2.打印链表的接口实现

首先制造一些节点并进行相连操作

打印函数实现的思路：

void SLTPrint(SLTNode* phead)
{
  //定义一个新的指针
  SLTNode* pcur = phead;
  //循环打印即可，什么时候停止？pcur不指向空便不停止
  while (pcur)
  {
    //打印数据
    printf("%d->", pcur->date);
    //更新指针
    pcur = pcur->next;
  }
  //为了完善，我给最后也加一个NULL
  printf("NULL\n");
}

3.尾插接口实现

思路：定义一个新指针，找到原链表的尾节点，找到了接上即可。

这里为什么要分类进行讨论？这由思路决定的，因为如果是空链表的情况下，ptail->next根本就是错误的，因为不存在。

新空间开辟接口：

void SLTPushBack(SLTNode** pphead, SLTDateType x)
{
  assert(pphead);
  //申请一块新的空间
  SLTNode* newnode = SLTBuyNode(x);
  //分两种情况
  //链表为空
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else//链表不为空
  {
    SLTNode* ptail = *pphead;//用于找到链表的尾节点
    while (ptail->next)
    {
      ptail = ptail->next;
    }//找到尾节点
    ptail->next = newnode;//给他接上
  }
}
SLTNode* SLTBuyNode(SLTDateType x)
{
  //申请一块新的空间
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  //放内容
  newnode->date = x;
  newnode->next = NULL;
  //返回地址
  return newnode;
}

4.头插接口实现

思路：

尾插需要分情况讨论而头插怎么不需要呢？还是思路决定的，这个思路没有用到ptail->next所以就不需要考虑空链表的情况

void SLTPushiFront(SLTNode** pphead, SLTDateType x)
{
  assert(pphead);
  //申请一块新的空间
  SLTNode* newnode = SLTBuyNode(x);
  //把原来第一个结点的地址交给新节点的next
  newnode->next = *pphead;
  *pphead = newnode;//把头部指针更新一下
}

5.尾删接口实现

思路：

这里为什么要分只有一个节点和多个节点的不同情况？因为涉及到prev问题如果是只有一个节点，ptail指向第一个节点，那prev指针指向哪里？所以要对只有一个节点的链表单独进行处理。

void SLTPopBack(SLTNode** pphead)
{
  //检验
  assert(pphead);//原本的指针不能是空
  assert(*pphead);//传过来的不能是空指针给我删除啊
  //删除
  //这里分两种情况
  //1.只有一个节点的情况
  if (*pphead == NULL)
  {
    free(*pphead);
    *pphead = NULL;
    return;
  }
  else//多个节点的情况
  {
    //需要找到最后一个节点和倒数第二个节点
    //最后一个节点是为了释放空间
    //倒数第二个节点是为了把他的next部分置为空
    SLTNode* ptail = *pphead;
    SLTNode* prev = *pphead;
    while (ptail->next)
    {
      prev = ptail;
      ptail = ptail->next;
    }
    //第二个节点next置为空
    prev->next = NULL;
    //销毁第一个节点
    free(ptail);
    ptail = NULL;
  }
}

6.头删接口的实现

思路：

void SLTPopFront(SLTNode** pphead)
{
  //检验
  assert(pphead);//检验你别给我传个空
  assert(*pphead);//检验链表不为空，空链表删除什么？
  //开始准备删除
  SLTNode* next = (*pphead)->next;//记录一下要接上的地址
  free(*pphead);//释放第一个节点
  *pphead = next;
}

7.查找接口实现

查找接口是做什么的呢？找一个节点的地址的。

思路实现：

SLTNode* SLTFind(SLTNode** pphead, SLTDateType x)
{
  //检查
  assert(pphead);//别传空指针进来
  //这里可以传空链表吗？可以！顶多找不到给你返回一个NULL嘛
  //遍历链表
  SLTNode* pcur = *pphead;
  while (pcur)//当pcur找到NULL时候就会停止
  {
    if (pcur->date == x)
    {
      return pcur;//满足条件，返回该节点的地址
    }
    pcur = pcur->next;//更新指针
  }
  //如果什么都没有找到的话，是不是会不太合适\
  // 所以我们规定如果没有找到，返回NULL地址
  return NULL;
}

8.在指定位置之前插入数据

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
  //检验
  assert(pphead);//传入地址不得为空
  assert(pos);//pos不得为空
  assert(*pphead);//要加上链表不得为空，\
  这是因为pos是链表的一个节点的地址，如 \
    果链表不存在，那么pos也会不存在
  //这里要分情况进行处理
  //1.pos刚好是头节点
  if (pos == *pphead)
  {
    //直接调用头插
    SLTPushiFront(pphead,x);
    return;
  }
  else//2.如果pos不是头节点
  {
    SLTNode* prev = *pphead;
    //让prev找到pos之前的节点的地址
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    
    SLTNode* newnode = SLTBuyNode(x);//申请空间
    prev->next = newnode;//把新空间链接到我们前一个节点
    newnode->next = pos;//把新空间与pos指向的空间链接在一起
  }
}

9.在指定位置之后插入数据的接口实现

思路：

思考：上面说的关联新节点的错误是如何引起的呢？

答：因为新节点的后面的节点的地址表示是靠的pos->next

void SLTInsertAfter(SLTNode* pos, SLTDateType x)//之后
{
  //检查
  assert(pos);
  
  //申请空间
  SLTNode* newnode = SLTBuyNode(x);
  //关联新节点的错误写法，原因：pos值的改变
  //pos->next = newnode;
  //newnode->next = pos->next;
  //关联新节点的正确写法：
  //先接后面，再接前面
  newnode->next = pos->next;
  pos->next = newnode;
}

10.删除指定位置的节点

思路：

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
  //检查
  assert(pphead);//不得传空
  assert(*pphead);//不得为空链表
  assert(pos);
  //pos刚好是头节点的情况，头删
  if (*pphead == pos)
  {
    //头删
    SLTPopFront(pphead);
    return;
  }
  //如果不是头节点
  else {
    //找到pos之前的节点
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
    pos = NULL;
  }
}

11.删除指定位置之后的节点接口实现

思路：

void SLTEraseAfter(SLTNode* pos)
{
  //检查
  assert(pos);//传过来的地址不可以为空
  assert(pos->next);//传过来的地址的下一个地址不得为空
  SLTNode* del = pos->next;//记录要删除的节点的地址
  pos->next = pos->next->next;//更新pos中next的地址
  free(del);//释放空间
  del = NULL;//临时指针及时置为空
}

12.销毁链表接口

思路：

void SLTDestroy(SLTNode** pphead)
{
  assert(pphead);//传过来的指针不得为空
  assert(*pphead);//链表不得为空，空链表不用销毁
  //创建遍历指针
  SLTNode* pcur = *pphead;
  //循环销毁
  while (pcur)//啥时候停止？pcur指向NULL
  {
    SLTNode* next = pcur->next;
    free(pcur);
    pcur = next;
  }
  //最后把头指针也置为NULL
  *pphead = NULL;
}

全部代码合集

//SList.h
#pragma once
#include<stdlib.h>
#include<stdio.h>
#include<assert.h>
//定义单链表结构体
#define SLTDateType int
typedef struct SListNode
{
  SLTDateType date;//每个节点的数据
  struct SListNode* next;//每个节点存储下一个节点的地址
}SLTNode;
void SLTPrint(SLTNode* phead);//打印
void SLTPushBack(SLTNode** pphead,SLTDateType x);//尾插
void SLTPushiFront(SLTNode** pphead, SLTDateType x);//头插
void SLTPopBack(SLTNode** pphead);//尾删
void SLTPopFront(SLTNode** pphead);//头删
void SLTInsert(SLTNode** pphead,SLTNode* pos,SLTDateType x);//任意位置之前插入
SLTNode* SLTFind(SLTNode** pphead, SLTDateType x);//查找接口
void SLTInsertAfter(SLTNode* pos, SLTDateType x);//任意位置之后插入
void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos指向的节点
void SLTEraseAfter(SLTNode* pos);//删除pos指向之后的节点
void SLTDestroy(SLTNode** pphead);//销毁链表接口
//SList.c
#include"SList.h"
SLTNode* SLTBuyNode(SLTDateType x)
{
  //申请一块新的空间
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  //放内容
  newnode->date = x;
  newnode->next = NULL;
  //返回地址
  return newnode;
}
SLTNode* SLTFind(SLTNode** pphead, SLTDateType x)
{
  //检查
  assert(pphead);//别传空指针进来
  //这里可以传空链表吗？可以！顶多找不到给你返回一个NULL嘛
  //遍历链表
  SLTNode* pcur = *pphead;
  while (pcur)//当pcur找到NULL时候就会停止
  {
    if (pcur->date == x)
    {
      return pcur;//满足条件，返回该节点的地址
    }
    pcur = pcur->next;//更新指针
  }
  //如果什么都没有找到的话，是不是会不太合适\
  // 所以我们规定如果没有找到，返回NULL地址
  return NULL;
}
void SLTPrint(SLTNode* phead)
{
  //定义一个新的指针
  SLTNode* pcur = phead;
  //循环打印即可，什么时候停止？pcur不指向空便不停止
  while (pcur)
  {
    //打印数据
    printf("%d->", pcur->date);
    //更新指针
    pcur = pcur->next;
  }
  //为了完善，我给最后也加一个NULL
  printf("NULL\n");
}
void SLTPushBack(SLTNode** pphead, SLTDateType x)
{
  assert(pphead);
  //申请一块新的空间
  SLTNode* newnode = SLTBuyNode(x);
  //分两种情况
  //链表为空
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else//链表不为空
  {
    SLTNode* ptail = *pphead;//用于找到链表的尾节点
    while (ptail->next)
    {
      ptail = ptail->next;
    }//找到尾节点
    ptail->next = newnode;//给他接上
  }
}
void SLTPushiFront(SLTNode** pphead, SLTDateType x)
{
  assert(pphead);
  //申请一块新的空间
  SLTNode* newnode = SLTBuyNode(x);
  //把原来第一个结点的地址交给新节点的next
  newnode->next = *pphead;
  *pphead = newnode;//把头部指针更新一下
}
void SLTPopBack(SLTNode** pphead)
{
  //检验
  assert(pphead);//原本的指针不能是空
  assert(*pphead);//传过来的不能是空指针给我删除啊
  //删除
  //这里分两种情况
  //1.只有一个节点的情况
  if (*pphead == NULL)
  {
    free(*pphead);
    *pphead = NULL;
    return;
  }
  else//多个节点的情况
  {
    //需要找到最后一个节点和倒数第二个节点
    //最后一个节点是为了释放空间
    //倒数第二个节点是为了把他的next部分置为空
    SLTNode* ptail = *pphead;
    SLTNode* prev = *pphead;
    while (ptail->next)
    {
      prev = ptail;
      ptail = ptail->next;
    }
    //第二个节点next置为空
    prev->next = NULL;
    //销毁第一个节点
    free(ptail);
    ptail = NULL;
  }
}
void SLTPopFront(SLTNode** pphead)
{
  //检验
  assert(pphead);//检验你别给我传个空
  assert(*pphead);//检验链表不为空，空链表删除什么？
  //开始准备删除
  SLTNode* next = (*pphead)->next;//记录一下要接上的地址
  free(*pphead);//释放第一个节点
  *pphead = next;
}
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
  //检验
  assert(pphead);//传入地址不得为空
  assert(pos);//pos不得为空
  assert(*pphead);//要加上链表不得为空，
  //这是因为pos是链表的一个节点的地址，如 
    //果链表不存在，那么pos也会不存在
  //这里要分情况进行处理
  //1.pos刚好是头节点
  if (pos == *pphead)
  {
    //直接调用头插
    SLTPushiFront(pphead,x);
    return;
  }
  else//2.如果pos不是头节点
  {
    SLTNode* prev = *pphead;
    //让prev找到pos之前的节点的地址
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    
    SLTNode* newnode = SLTBuyNode(x);//申请空间
    prev->next = newnode;//把新空间链接到我们前一个节点
    newnode->next = pos;//把新空间与pos指向的空间链接在一起
  }
}
void SLTInsertAfter(SLTNode* pos, SLTDateType x)//之后
{
  //检查
  assert(pos);
  
  //申请空间
  SLTNode* newnode = SLTBuyNode(x);
  //关联新节点的错误写法，原因：pos值的改变
  //pos->next = newnode;
  //newnode->next = pos->next;
  //关联新节点的正确写法：
  //先接后面，再接前面
  newnode->next = pos->next;
  pos->next = newnode;
}
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
  //检查
  assert(pphead);//不得传空
  assert(*pphead);//不得为空链表
  assert(pos);
  //pos刚好是头节点的情况，头删
  if (*pphead == pos)
  {
    //头删
    SLTPopFront(pphead);
    return;
  }
  //如果不是头节点
  else {
    //找到pos之前的节点
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
    pos = NULL;
  }
}
void SLTEraseAfter(SLTNode* pos)
{
  //检查
  assert(pos);//传过来的地址不可以为空
  assert(pos->next);//传过来的地址的下一个地址不得为空
  SLTNode* del = pos->next;//记录要删除的节点的地址
  pos->next = pos->next->next;//更新pos中next的地址
  free(del);//释放空间
  del = NULL;//临时指针及时置为空
}
void SLTDestroy(SLTNode** pphead)
{
  assert(pphead);//传过来的指针不得为空
  assert(*pphead);//链表不得为空，空链表不用销毁
  //创建遍历指针
  SLTNode* pcur = *pphead;
  //循环销毁
  while (pcur)//啥时候停止？pcur指向NULL
  {
    SLTNode* next = pcur->next;
    free(pcur);
    pcur = next;
  }
  //最后把头指针也置为NULL
  *pphead = NULL;
}
//test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
void test1()
{
  //头指针
  SLTNode* phead = NULL;
  //造一点结点
  SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
  node1->date = 1;
  SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
  node2->date = 2;
  SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
  node3->date = 3;
  SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
  node4->date = 4;
  SLTNode* node5 = (SLTNode*)malloc(sizeof(SLTNode));
  node5->date = 5;
  //链接这些节点
  phead = node1;
  node1->next = node2;
  node2->next = node3;
  node3->next = node4;
  node4->next = node5;
  node5->next = NULL;
  //调用一下打印函数
  SLTPrint(phead);
}
void test2()
{
  SLTNode* phead = NULL;
  SLTPushBack(&phead,6);
  SLTPrint(phead);
  SLTPushiFront(&phead,0);
  SLTPushiFront(&phead,1);
  SLTPushiFront(&phead,2);
  SLTPushiFront(&phead,3);
  SLTPushiFront(&phead,4);
  SLTPushiFront(&phead,5);
  SLTPrint(phead);//5->4->3->2->1->0->6->NULL
  SLTPopBack(&phead);
  SLTPrint(phead);//5->4->3->2->1->0->NULL
  SLTPopFront(&phead);
  SLTPopFront(&phead);
  SLTPopFront(&phead);
  SLTPopFront(&phead);
  SLTPrint(phead);//1->0->NULL
  
  SLTNode* find = SLTFind(&phead,1);
  SLTInsert(&phead, find, 2);
  SLTPrint(phead);//2->1->0->NULL
  SLTInsertAfter(find, 8);
  SLTPrint(phead);//2->1->8->0->NULL
  
  SLTEraseAfter(find);
  SLTPrint(phead);//2->8->0->NULL
  SLTDestroy(&phead);
  SLTPrint(phead);//NULL
}
int main()
{
  //测试我的打印函数
  //test1();
  //测试我的插入与删除函数
  test2();
  return 0;
}

关键词：
数据结构单链表
睡觉待开机
目录
相关文章
java冯坚持
|
11月前
|
算法 程序员 索引
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈，并展示了如何利用栈和中缀表达式实现一个综合计算器。
java冯坚持
176 1
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
杀死一只知更鸟debug
|
存储 Java
java数据结构，线性表链式存储（单链表）的实现
文章讲解了单链表的基本概念和Java实现，包括头指针、尾节点和节点结构。提供了实现代码，包括数据结构、接口定义和具体实现类。通过测试代码演示了单链表的基本操作，如添加、删除、更新和查找元素，并总结了操作的时间复杂度。
杀死一只知更鸟debug
261 1
java数据结构，线性表链式存储（单链表）的实现
白子寰
|
11月前
|
存储
[数据结构] -- 单链表
[数据结构] -- 单链表
白子寰
84 1
努力学习的小廉
|
11月前
|
存储
【数据结构】——单链表实现
【数据结构】——单链表实现
努力学习的小廉
115 2
徐霞客320
|
11月前
|
存储
数据结构2——单链表
数据结构2——单链表
徐霞客320
78 1
是店小二呀
|
11月前
|
存储
【初阶数据结构】深入解析单链表:探索底层逻辑（无头单向非循环链表）（一）
【初阶数据结构】深入解析单链表:探索底层逻辑（无头单向非循环链表）
是店小二呀
131 1
小徐在进步
|
存储 算法 C语言
数据结构基础详解(C语言):单链表_定义_初始化_插入_删除_查找_建立操作_纯c语言代码注释讲解
本文详细介绍了单链表的理论知识，涵盖单链表的定义、优点与缺点，并通过示例代码讲解了单链表的初始化、插入、删除、查找等核心操作。文中还具体分析了按位序插入、指定节点前后插入、按位序删除及按值查找等算法实现，并提供了尾插法和头插法建立单链表的方法，帮助读者深入理解单链表的基本原理与应用技巧。
小徐在进步
1790 6
星霜旅人
|
11月前
|
存储
数据结构（单链表）
数据结构（单链表）
星霜旅人
75 0
平凡程序猿~
|
11月前
|
存储
数据结构--单链表
数据结构--单链表
平凡程序猿~
142 0
是店小二呀
|
11月前
|
存储 缓存
【初阶数据结构】深入解析单链表:探索底层逻辑（无头单向非循环链表）（二）
【初阶数据结构】深入解析单链表:探索底层逻辑（无头单向非循环链表）
是店小二呀
106 0

热门文章

最新文章

  • 1
    软考中级软件设计师专项-数据结构与算法上篇
  • 2
    Redis核心数据结构与分布式锁实现详解
  • 3
    软考中的数据结构
  • 4
    【数据结构之旅】循环队列
  • 5
    024 栈追踪
  • 6
    【算法与数据结构】中缀表达式转为后缀表达式
  • 7
    用js来实现那些数据结构04（栈01-栈的实现）
  • 8
    GPS北斗双模技术应用开发研究—数据结构扩展
  • 9
    【数据结构】笔记（一）
  • 10
    函数调用栈
  • 1
    数据结构Python用队列实现杨辉三角形
    173
  • 2
    数据结构——栈（Stack）
    276
  • 3
    【数据结构】遍历二叉树（递归思想）--＞赋源码
    112
  • 4
    【数据结构】二叉树顺序实现（大堆）--＞赋源码
    82
  • 5
    【数据结构】栈和队列--＞理解和实现（赋源码)
    70
  • 6
    【数据结构】双向带头（哨兵位）循环链表 —详细讲解（赋源码）
    178
  • 7
    【数据结构】单链表--＞详细讲解，后赋源码
    58
  • 8
    深入探索堆：Go语言中的高效数据结构
    146
  • 9
    揭秘MongoDB：这个神奇的建模技巧将如何彻底改变你的数据结构？
    100
  • 10
    PHP 数据结构的巅峰对决：在机器学习的舞台上，谁将主宰沉浮？
    93

    • 相关课程

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

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    2025云栖大会，阿里云百炼邀请您的参与和见证