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

一文教会你单向链表 2

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

6.尾删

void slist_popback(SlistNode** phead)
{
  if (*phead == NULL)
  {
    printf("链表为空，操作失败\n");
    return;
  }
  if ((*phead)->next == NULL)
    //如果只有一个节点，我们就不可能找到上一个节点，因此单独处理
  {
    free(*phead);//直接释放
    *phead = NULL;
    return;
  }
  SlistNode* tmp = *phead;
  SlistNode* prev = NULL;//用来存储目标的上一个节点
  while (tmp->next)
  {
    prev = tmp;
    tmp=tmp->next;
  }
  prev->next = NULL;//改变上一个节点的指向
  free(tmp);
}

测试代码：

void test4()
{
  SlistNode* plist = NULL;
  slist_popback(&plist);//直接删除，测试报错
  slist_pushback(&plist, 10086);//依次尾插10086，666，555，111
  slist_pushback(&plist, 666);
  slist_pushback(&plist, 555);
  slist_pushback(&plist, 111);
  print_slist(plist);
  slist_popback(&plist);//删除111
  print_slist(plist);
  slist_popback(&plist);//删除555
  print_slist(plist);
  slist_popback(&plist);//删除666
  print_slist(plist);
  slist_popback(&plist);//删除10086
  print_slist(plist);
  slist_popback(&plist);//删除空链表
  print_slist(plist);
}
int main()
{
  test4();
}

f3401efd4aa34cccae766917c5aba76d.png


7.查找

在对指定位置操作之前，我们得先找到目标位置才行，找到目标位置是比较简单的，简单地遍历一遍链表，找的到就返回对应的地址，找不到就返回空指针

SlistNode* slist_find(SlistNode* phead,SLDateType x)
{
  while (phead)
  {
    if (phead->data == x)
    {
      return phead;
    }
    phead=phead->next;
  }
  return NULL;
}

8.删除指定节点位置之后

void slist_erase_after(SlistNode* pos)
{
  if (pos == NULL ||pos->next==NULL )
    //如果为空则删除失败，如果下一个节点为空也不能删除
  {
    printf("该位置无效，操作失败\n");
    return;
  }
  SlistNode* tmp = pos->next;
  pos->next = pos->next->next;
  free(tmp);
}

测试代码


void test5()
{
  SlistNode* plist = NULL;//创建一个链表头
  slist_pushback(&plist, 1);//通过尾插依次将1，2，3头插进链表中
  slist_pushback(&plist, 2);
  slist_pushback(&plist, 3);
  print_slist(plist); 
  SlistNode* pos=slist_find(plist,1);//查找1所在的位置
  slist_erase_after(pos);//将1之后删除
  print_slist(plist);
  pos = slist_find(plist, 3);//查找3所在的位置
  slist_erase_after(pos);//将3之后删除，但是3之后没有节点，删除必定失败
  print_slist(plist);
}
int main()
{
  test5();
}

9ef2507220784a18bc1676ae14298d41.png


9.删除指定位置节点

void slist_erase(SlistNode* pos,SlistNode**phead)
{
  if (pos == NULL)//为空就别删了
  {
    printf("该位置无效，操作失败\n");
    return;
  }
  if(*phead==pos)//当只有一个节点时,操作不到两个节点，单独处理
  {
    SlistNode*tmp=(*phead)->next;
    free(*phead);
    *phead = tmp;
    return;
  }
  SlistNode* cur = *phead;
  while (cur->next)
  {
    if (cur->next == pos)
    {
      break;
    }
    cur=cur->next;
  }
  //此时phead的next就是目标节点
  SlistNode* tmp = cur->next;
  cur->next = cur->next->next;//将目标节点的上一个节点链接到目标节点的下一个地址
  free(tmp);
}


测试代码：

void test6()
{
  SlistNode* plist = NULL;//创建一个链表头
  slist_pushback(&plist, 1);//通过尾插依次将1，2，3头插进链表中
  slist_pushback(&plist, 2);
  slist_pushback(&plist, 3);
  print_slist(plist);
  SlistNode* pos = slist_find(plist, 1);//查找1所在的位置
  slist_erase(pos, &plist);//将1删除
  print_slist(plist); 
   pos = slist_find(plist, 2);//查找2所在的位置
  slist_erase(pos, &plist);//将2删除
  print_slist(plist);
   pos = slist_find(plist, 3);//查找3所在的位置
  slist_erase(pos, &plist);//将3删除
  print_slist(plist);
}
int main()
{
  test6();
}

74afc777139c4a9abaffd6c03dca429c.png


10.在指定位置节点之后插入

void slist_insert_after(SlistNode* pos, SLDateType x)
{
  if (pos == NULL)
  {
    printf("目标不存在，操作失败\n");
    return;
  }
  SlistNode* newnode = buy_slistnode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}

测试代码：

void test7()
{
  SlistNode* plist = NULL;//创建一个链表头
  slist_pushback(&plist, 1);//通过尾插依次将1，2，3头插进链表中
  slist_pushback(&plist, 2);
  slist_pushback(&plist, 3);
  SlistNode* pos = slist_find(plist, 1);//查找1所在的位置
  slist_insert_after(pos, 10086);//在1之后进行插入
  print_slist(plist);
  pos = slist_find(plist, 3);//查找3所在的位置
  slist_insert_after(pos, 520);//在3之后进行插入
  print_slist(plist);
  pos = slist_find(plist, 10086);//查找10086所在的位置
  slist_insert_after(pos,9 );//在10086之后进行插入
  print_slist(plist);
}
int main()
{
  test7();
}

2383e8f65c574f6786391429ba982b7d.png


11.在指定位置节点之前插入

void slist_insert_before(SlistNode* pos, SLDateType x,SlistNode**phead)
{
  if (pos == NULL)
  {
    printf("目标不存在，操作失败\n");
    return;
  } 
  SlistNode* newnode = buy_slistnode(x);
  if (*phead==pos)//在第一个节点前插入，没有上一个节点，单独处理
  {
    newnode->next = pos;
    *phead = newnode;
    return;
  }
  SlistNode* cur = *phead;
  while (cur)//为空意味着找不到
  {
    if (cur->next == pos)//找到上一个节点了
    {
      break;
    }
    cur = cur->next;
  }
  if (cur == NULL)
  {
    printf("目标不存在，操作失败\n");
    return;
  }
  cur->next = newnode;
  newnode->next = pos;
}

测试代码

void test8()
{
  SlistNode* plist = NULL;//创建一个链表头
  slist_pushback(&plist, 1);//通过尾插依次将1，2，3头插进链表中
  print_slist(plist);
  SlistNode* pos = slist_find(plist, 1);//查找1所在的位置
  slist_insert_before(pos, 10086,&plist);//在1之前插入666
  print_slist(plist);
  slist_pushback(&plist, 2);
  slist_pushback(&plist, 3);
  pos = slist_find(plist, 10086);//查找10086所在的位置
  slist_insert_before(pos, 666, &plist);//在10086之前插入666
  print_slist(plist);
  pos = slist_find(plist, 3);//查找3所在的位置
  slist_insert_before(pos, 999, &plist);//在3之前插入999
  print_slist(plist);
}
int main()
{
  test8();
}

c8f8f9d66bfc427ca3b5d175595dad26.png


三、全部代码

1.接口头文件

//链表博客版.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDateType;
//链表成员我们先用int，int简单好懂
//而之所以要给它取个SLDateType的别名
//不仅仅是因为方便和int进行区分
//更主要的是以后链表的成员不想用int类型的话
//直接在这里进行修改即可
typedef struct SlistNode
{
  SLDateType data;//成员
  struct SlistNode* next;
  //这里给它取名叫next其实是为了方便到时使用，其实你叫它abc也是可以的
  // 在链表中，一个节点通过地址链接到下一个节点，就像串串一样把它们穿起来，而这个地址则是它们唯一的联系，
  //我们这讲述的是单向链表，所以只能够是前面的找到后面的，从后面找到前面是不可能实现的。
}SlistNode;
SlistNode* buy_slistnode(SLDateType x);
//头插
void slist_pushfront(SlistNode**phead,SLDateType x);
//打印链表
void print_slist(SlistNode* phead);
//尾插
void slist_pushback(SlistNode** phead, SLDateType x);
//头删
void slist_popfront(SlistNode** phead);
//尾删
void slist_popback(SlistNode**phead);
//查找
SlistNode* slist_find(SlistNode*phead,SLDateType x);
//删除指定位置之后
void slist_erase_after(SlistNode*pos);
//删除指定位置
void slist_erase(SlistNode* pos,SlistNode**phead);
//在指定位置之后插入
void slist_insert_after(SlistNode* pos, SLDateType x);
//在指定位置之前插入
void slist_insert_before(SlistNode* pos, SLDateType x, SlistNode** phead);

2.接口实现

#include"链表博客版.h"
SlistNode* buy_slistnode(SLDateType x)
//使用节点指针作为返回类型，来拿到创建好的新节点
{
  SlistNode* newnode = (SlistNode*)malloc(sizeof(SlistNode));
  //使用malloc创建一个新节点
  if (newnode == NULL)
  {
    perror("buy_slistnode");
    exit(-1);//创建失败直接中止程序
  }
  newnode->data = x;//将节点内容修改成需要的值
  newnode->next = NULL;//将链接对象置为空，因为不知道要链接谁
  return newnode;
}
void slist_pushfront(SlistNode** phead, SLDateType x)
//采用二级指针的原因是，当没有节点的时候，我们要对首节点的地址进行修改
{
  //先创建一个新的节点
  SlistNode* newnode = buy_slistnode(x);
  //我们要头插是吧，也就是说新创建的节点是新的头
  //那么我们是不是应该把我们自己原来的头更新一下
  //然后再将之前的节点，也就是之前的头链接到新的头后面
/*  *phead = newnode;
  newnode->next = *phead;*/
  //但这是错误的，原因很简单，你的头更新了，那么你就找不到之前的节点了
    //换一下顺序即可
  newnode->next = *phead;
  *phead = newnode;
}
void print_slist(SlistNode* phead)
{
  while (phead)//phead不为空意味着还有节点没被访问完
  {
    printf("%d->", phead->data);
    phead=phead->next;//指向下一个节点
  }
  printf("NULL\n");//访问完了打印空，提示已经访问完了
}
void slist_pushback(SlistNode** phead, SLDateType x)
{
  SlistNode* tmp = *phead;
  //创建一个首节点的拷贝，避免影响到首节点的指向
  SlistNode* newnode = buy_slistnode(x);//创建一个新节点
  if (*phead==NULL)//当*phead==NULL时，意味着链表为空
  {
    *phead = newnode;//直接链接
    return;
  }
  while(tmp->next)
  //当成员的next为空的时候意味着已经找到目标了
  // 跳出循环
  //接下来就是把这个成员的指向改变
  {
    tmp = tmp->next;
  }
  tmp->next = newnode;
}
void slist_popfront(SlistNode** phead)
{
  if (*phead==NULL)//空了就别删了
  {
    printf("链表为空，操作失败\n");
    return;
  }
  SlistNode* tmp = (*phead)->next;
  //储存头的下一个节点，避免找不到
  free(*phead);//直接释放头节点
  *phead =tmp;//头节点重新指向下一个节点
}
void slist_popback(SlistNode** phead)
{
  if (*phead == NULL)
  {
    printf("链表为空，操作失败\n");
    return;
  }
  if ((*phead)->next == NULL)
    //如果只有一个节点，我们就不可能找到上一个节点，因此单独处理
  {
    free(*phead);//直接释放
    *phead = NULL;
    return;
  }
  SlistNode* tmp = *phead;
  SlistNode* prev = NULL;//用来存储目标的上一个节点
  while (tmp->next)
  {
    prev = tmp;
    tmp=tmp->next;
  }
  prev->next = NULL;//改变上一个节点的指向
  free(tmp);
}
SlistNode* slist_find(SlistNode* phead,SLDateType x)
{
  while (phead)
  {
    if (phead->data == x)
    {
      return phead;
    }
    phead=phead->next;
  }
  return NULL;
}
void slist_erase_after(SlistNode* pos)
{
  if (pos == NULL ||pos->next==NULL )
    //如果为空则删除失败，如果下一个节点为空也不能删除
  {
    printf("该位置无效，操作失败\n");
    return;
  }
  SlistNode* tmp = pos->next;
  pos->next = pos->next->next;
  free(tmp);
}
void slist_erase(SlistNode* pos,SlistNode**phead)
{
  if (pos == NULL)//为空就别删了
  {
    printf("该位置无效，操作失败\n");
    return;
  }
  if(*phead==pos)//当只有一个节点时,操作不到两个节点，单独处理
  {
    SlistNode*tmp=(*phead)->next;
    free(*phead);
    *phead = tmp;
    return;
  }
  SlistNode* cur = *phead;
  while (cur->next)
  {
    if (cur->next == pos)
    {
      break;
    }
    cur=cur->next;
  }
  //此时phead的next就是目标节点
  SlistNode* tmp = cur->next;
  cur->next = cur->next->next;//将目标节点的上一个节点链接到目标节点的下一个地址
  free(tmp);
}
void slist_insert_after(SlistNode* pos, SLDateType x)
{
  if (pos == NULL)
  {
    printf("目标不存在，操作失败\n");
    return;
  }
  SlistNode* newnode = buy_slistnode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}
void slist_insert_before(SlistNode* pos, SLDateType x,SlistNode**phead)
{
  if (pos == NULL)
  {
    printf("目标不存在，操作失败\n");
    return;
  } 
  SlistNode* newnode = buy_slistnode(x);
  if (*phead==pos)//在第一个节点前插入，没有上一个节点，单独处理
  {
    newnode->next = pos;
    *phead = newnode;
    return;
  }
  SlistNode* cur = *phead;
  while (cur)//为空意味着找不到
  {
    if (cur->next == pos)//找到上一个节点了
    {
      break;
    }
    cur = cur->next;
  }
  if (cur == NULL)
  {
    printf("目标不存在，操作失败\n");
    return;
  }
  cur->next = newnode;
  newnode->next = pos;
}

3.测试

#include"链表博客版.h"
void test1()
{
  SlistNode* plist = NULL;//创建一个链表头
  slist_pushfront(&plist, 1);//依次将1，2，3头插进链表中
  slist_pushfront(&plist, 2);//那么链表最后应该是3为头，1为尾
  slist_pushfront(&plist, 3);
  print_slist(plist);
}
void test2()
{
  SlistNode* plist = NULL;
  slist_pushback(&plist, 10086);//依次尾插10086，666，555，111
  slist_pushback(&plist, 666);
  slist_pushback(&plist, 555);
  slist_pushback(&plist, 111);
  print_slist(plist);
}
void test3()
{
  SlistNode* plist = NULL;
  slist_popfront(&plist);//直接删除，测试报错
  slist_pushback(&plist, 10086);//依次尾插10086，666，555，111
  slist_pushback(&plist, 666);
  slist_pushback(&plist, 555);
  slist_pushback(&plist, 111);
  print_slist(plist);
  slist_popfront(&plist);//删除10086
  print_slist(plist);
  slist_popfront(&plist);//删除666
  print_slist(plist);
  slist_popfront(&plist);//删除555
  print_slist(plist);
  slist_popfront(&plist);//删除111
  print_slist(plist);
}
void test4()
{
  SlistNode* plist = NULL;
  slist_popback(&plist);//直接删除，测试报错
  slist_pushback(&plist, 10086);//依次尾插10086，666，555，111
  slist_pushback(&plist, 666);
  slist_pushback(&plist, 555);
  slist_pushback(&plist, 111);
  print_slist(plist);
  slist_popback(&plist);//删除111
  print_slist(plist);
  slist_popback(&plist);//删除555
  print_slist(plist);
  slist_popback(&plist);//删除666
  print_slist(plist);
  slist_popback(&plist);//删除10086
  print_slist(plist);
  slist_popback(&plist);//删除空链表
  print_slist(plist);
}
void test5()
{
  SlistNode* plist = NULL;//创建一个链表头
  slist_pushback(&plist, 1);//通过尾插依次将1，2，3头插进链表中
  slist_pushback(&plist, 2);
  slist_pushback(&plist, 3);
  print_slist(plist); 
  SlistNode* pos=slist_find(plist,1);//查找1所在的位置
  slist_erase_after(pos);//将1之后删除
  print_slist(plist);
  pos = slist_find(plist, 3);//查找3所在的位置
  slist_erase_after(pos);//将3之后删除，但是3之后没有节点，删除必定失败
  print_slist(plist);
}
void test6()
{
  SlistNode* plist = NULL;//创建一个链表头
  slist_pushback(&plist, 1);//通过尾插依次将1，2，3头插进链表中
  slist_pushback(&plist, 2);
  slist_pushback(&plist, 3);
  print_slist(plist);
  SlistNode* pos = slist_find(plist, 1);//查找1所在的位置
  slist_erase(pos, &plist);//将1删除
  print_slist(plist); 
   pos = slist_find(plist, 2);//查找2所在的位置
  slist_erase(pos, &plist);//将2删除
  print_slist(plist);
   pos = slist_find(plist, 3);//查找3所在的位置
  slist_erase(pos, &plist);//将3删除
  print_slist(plist);
}
void test7()
{
  SlistNode* plist = NULL;//创建一个链表头
  slist_pushback(&plist, 1);//通过尾插依次将1，2，3头插进链表中
  slist_pushback(&plist, 2);
  slist_pushback(&plist, 3);
  SlistNode* pos = slist_find(plist, 1);//查找1所在的位置
  slist_insert_after(pos, 10086);//在1之后进行插入
  print_slist(plist);
  pos = slist_find(plist, 3);//查找3所在的位置
  slist_insert_after(pos, 520);//在3之后进行插入
  print_slist(plist);
  pos = slist_find(plist, 10086);//查找10086所在的位置
  slist_insert_after(pos,9 );//在10086之后进行插入
  print_slist(plist);
}
void test8()
{
  SlistNode* plist = NULL;//创建一个链表头
  slist_pushback(&plist, 1);//通过尾插依次将1，2，3头插进链表中
  print_slist(plist);
  SlistNode* pos = slist_find(plist, 1);//查找1所在的位置
  slist_insert_before(pos, 10086,&plist);//在1之前插入666
  print_slist(plist);
  slist_pushback(&plist, 2);
  slist_pushback(&plist, 3);
  pos = slist_find(plist, 10086);//查找10086所在的位置
  slist_insert_before(pos, 666, &plist);//在10086之前插入666
  print_slist(plist);
  pos = slist_find(plist, 3);//查找3所在的位置
  slist_insert_before(pos, 999, &plist);//在3之前插入999
  print_slist(plist);
}
int main()
{
  test8();
}


今天的分享到这里就结束了，更新各位友友的来访，祝各位友友前程似锦O(∩_∩)O


关键词：
单向链表
大海里的番茄
目录
相关文章
卫卫周大胖
|
6月前
【数据结构】单链表之--无头单向非循环链表
【数据结构】单链表之--无头单向非循环链表
卫卫周大胖
42 2
是店小二呀
|
1月前
|
存储
【初阶数据结构】深入解析单链表:探索底层逻辑（无头单向非循环链表）（一）
【初阶数据结构】深入解析单链表:探索底层逻辑（无头单向非循环链表）
是店小二呀
45 1
java冯坚持
|
1月前
|
算法 Java
数据结构与算法学习六：单向环形链表应用实例的约瑟夫环问题
这篇文章通过单向环形链表的应用实例，详细讲解了约瑟夫环问题的解决方案，并提供了Java代码实现。
java冯坚持
21 0
是店小二呀
|
1月前
|
存储 缓存
【初阶数据结构】深入解析单链表:探索底层逻辑（无头单向非循环链表）（二）
【初阶数据结构】深入解析单链表:探索底层逻辑（无头单向非循环链表）
是店小二呀
46 0
老秦包你会
|
6月前
|
存储
数据结构第二课 -----线性表之单向链表
数据结构第二课 -----线性表之单向链表
老秦包你会
54 0
孙飞i
|
3月前
|
存储 JavaScript 前端开发
JavaScript实现单向链表
JavaScript实现单向链表
孙飞i
21 0
邢仕冲的一亩三分地
|
5月前
|
存储 算法
【单向链表】数据结构——单向链表的介绍与代码实现&笔记
【单向链表】数据结构——单向链表的介绍与代码实现&笔记
邢仕冲的一亩三分地
50 4
邢仕冲的一亩三分地
|
5月前
经典笔试题——单向链表的倒序
经典笔试题——单向链表的倒序
邢仕冲的一亩三分地
37 3
7fa6b5ui5pmtk
|
5月前
|
算法 C语言
数据结构——单向链表（C语言版）
数据结构——单向链表（C语言版）
7fa6b5ui5pmtk
46 2
好奇的菜鸟
|
5月前
|
Java
单向环形链表-约瑟夫问题(java)
单向环形链表-约瑟夫问题(java)
好奇的菜鸟
22 0