深度剖析数据结构之单链表

简介: 深度剖析数据结构之单链表

在这篇文章中,你将熟练应用单链表,彻底玩转单链表,你会发现单链表真的很简单。

首先,来介绍一下单链表的构成,单链表由一个或者多个内存不连续的独立节点构成,每一个节点都是一个结构体节点内部具有两个属性:1.节点所存储的数据 2.下一个节点的地址。、

代码布局

  • SingleList.h文件中申明节点和函数
  • SingleList.c文件中实现函数
  • test.c文件中测试代码  

一.创建单链表

在SingleList.h文件中创建单链表

1. typedef struct SingleList
2. {
3.  datetype date;//存放数据
4.  struct SingleList* next;//存放下一个节点的地址
5. }SLT;

为了方便观察链表中的数据,我们可以写一个函数printSLT来方便测试代码。

二.打印链表

1. void printSLT(SLT* phead)
2. {
3.  SLT* cur = phead;//头节点备份
4.  while (cur != NULL)
5.  {
6.    printf("%d->", cur->date);//打印当前节点数据
7.    cur = cur->next;//节点后移
8.  }
9.  printf("NULL");//打印结尾
10. }

三.链表头部节点插入

链表的插入,从本质分析无非就是创建一个新节点---->将新节点与链表链接起来。只要做好这两步,我们就可以插入函数了。

插入的第一步是创建新节点,为了减少代码的冗余,写一个创建新节点的函数来完成这个任务。

1. SLT* buynewnode(datetype n)
2. {
3.  SLT* newnode = (SLT*)malloc(sizeof(SLT));//在堆上申请空间,防止处函数空间被销毁
4.  if (newnode == NULL)//判断是否申请成功
5.  {
6.    printf("malloc失败");
7.    return NULL;
8.  }
9.  newnode->date = n;//将节点数据初始化
10.   newnode->next = NULL;
11.   return newnode;//返回创建的节点的地址
12. }

插入的第二步就是将新节点与链表链接起来

看图,要想将newnode与原链表链接起来,需要让newnode->next指向*pphead(头节点地址),并且将新的头节点地址改为newnode的地址。代码如下

1. void pushhead(SLT** pphead, datetype n)
2. {
3.  SLT* newnode = buynewnode(n);//创建新节点
4.  //链接新节点
5.  newnode->next = *pphead;//newnode指向*pphead
6.  *pphead = newnode;//头节点地址改为newnode的地址
7. }

这里就体现了二级指针的作用了,要改变头节点地址,就必须把头节点地址 的地址传过来,解引用 头节点地址 的地址,才可以访问到头节点地址,进而改变头节点地址。

四.链表尾部节点插入

尾部插入逻辑相同,只需要创建新节点,链接新节点。需要分两种情况讨论,1,链表为空.2,链表不为空。当链表不为空时,需要找到尾节点tail,再将尾节点与新节点链接起来。当链表为空时,只需要将头节点地址改为新节点地址。代码如下

1. void pushback(SLT** pphead, datetype n)
2. {
3.  SLT* newnode = buynewnode(n);//创建新节点
4.  SLT* tail = *pphead;//使用tail找到尾节点
5.  if (tail != NULL)//链表不为空
6.  {
7.    while (tail->next != NULL)//利用尾节点特征:tail->next==NULL,找到尾节点
8.    {
9.      tail = tail->next;
10.     }
11.     tail->next = newnode;//链接尾节点与新节点
12.   }
13.   else//链表为空
14.   {
15.     *pphead = newnode;//把头节点地址改为新节点地址(二级指针作用)
16.   }
17. }

五.链表头部节点删除

链表节点的删除,首先要断言一下链表(空链表不可以删除),其次头部节点的删除只需要将头节点地址改为头节点下一个节点的地址,然后释放原头节点的空间。

1. void pophead(SLT** pphead)
2. {
3.  assert(*pphead);//断言链表,保证链表不为空
4.  SLT* tmp = *pphead;//备份原头节点地址,防止头节点地址改后找不到
5.  *pphead = (*pphead)->next;//把头节点地址改为头节点下一个节点的地址
6.  free(tmp);//释放原头节点空间,使用备份
7. }

当链表只有一个节点,这种删除方式也是可行的。

六.链表尾部节点删除

首先,断言一下链表(空链表不可以删除),其次,如果链表有两个以及两个以上节点,要想删除尾节点,必须先找到倒数第二个节点(tail),再释放尾节点(tail->next)内存空间,倒数第二个节点的next设置为NULL。如果链表只有一个节点,只需要释放头节点内存空间,再将头节点地址改为NULL。代码如下

1. void popback(SLT** pphead)
2. {
3.  assert(*pphead);//断言链表,保证链表不为空
4.  SLT* tail = *pphead;//倒数第二个节点tail
5.  if (tail->next != NULL)//两个以及两个以上节点
6.  {
7.    while (tail->next->next != NULL)//找到倒数第二个节点
8.    {
9.      tail = tail->next;//找到下一个节点
10.     }
11.     free(tail->next);//释放尾节点空间
12.     tail->next = NULL;//倒数第二个节点的next置为空
13.   }
14.   else//一个节点
15.   {
16.     free(*pphead);//直接释放节点空间
17.     *pphead = NULL;//将头节点地址改为空
18.   }
19. }

七.链表节点查找

链表节点查找 要实现的功能是找到存放指定date的节点,并返回该节点的地址。具体代码如下,注释很明确。

1. SLT* SLTfind(SLT* phead,datetype n)
2. {
3.  SLT* cur = phead;//备份头节点地址
4.  while (cur->date!=n)//循环遍历找到cur->date==n的节点cur
5.  {
6.    if (cur->next == NULL)//如果找到尾节点还没找到则返回NULL
7.      return NULL;
8. 
9.    cur = cur->next;
10.   }
11.     return cur;//尾节点前,提前找到则返回这个节点地址
12. }

八.链表节点修改

链表节点修改 要实现的功能是修改该节点的数据。要想将数据为n的节点的数据改为m,需要先找到数据为n的节点的地址,再改为m。

1. void modifySLT(SLT* phead, datetype n,datetype m)//数据为n的节点数据改为m
2. {
3.  SLT* pos = SLTfind(phead, n);//找到date==n的节点的地址
4.  pos->date = m;//该节点数据改为m
5. }

九.链表指定节点之后插入

插入节点的本质就是创建新节点,将新节点与链表链接起来。所以,要在指定位置之后插入只需要将pos->next与新节点链接起来,再将新节点与原来pos后面的那个节点链接起来。(注意顺序问题)

1. void pushafterpoint(SLT* pos, datetype n)
2. {
3.  SLT* newnode = buynewnode(n);//创建新节点
4. //链接新节点
5.  newnode->next = pos->next;//新节点的next存放pos位置节点的下一个节点地址
6.  pos->next = newnode;//pos指向新节点
7. }

十.链表指定节点之前插入

链表在指定位置之前插入,本质也是插入,只不过是链接新节点的细节不同。注意:如果指定位置是头节点,那么指定位置之前插入便是头插,所以分开来写。

1. void pushbehindpoint(SLT** pphead, SLT* pos, datetype n)
2. {
3.  SLT* newnode = buynewnode(n);//创建新节点
4.  if (pos == *pphead)//如果指定位置是头节点,头插
5.  {
6.    *pphead = newnode;
7.    newnode->next = pos;
8.  }
9.  else
10.   {
11.     SLT* tail = *pphead;//备份头节点地址
12.     while (tail->next != pos)//找到指定位置的上一个节点
13.     {
14.       tail = tail->next;
15.     }
16. //在上一个节点与pos之间链接新节点
17.     tail->next = newnode;//上一个节点指向新节点
18.     newnode->next = pos;//新节点指向指定位置节点
19.   }
20. }

十一.链表指定位置删除节点

首先,要断言一下链表(空链表不能删除)。这个函数要实现的功能是要删除指定位置的节点,步骤为:将指定位置前一个节点指定位置后一个节点链接起来,然后释放指定位置节点的内存空间。

1. void poppoint(SLT** pphead, SLT* pos)
2. {
3.  assert(*pphead);//保证链表不为空
4.  SLT* cur = *pphead;//备份pphead
5.  if (pos == *pphead)//如果指定位置是头节点,头删
6.  {
7.    *pphead = (*pphead)->next;
8.    free(cur);
9.  }
10.   else
11.   {
12.     while (cur->next != pos)//找到指定位置之前的节点
13.     {
14.       cur = cur->next;
15.     }
16.     //链接指定位置之前与之后
17.     cur->next = pos->next;
18.     //释放指定位置内存空间
19.     free(pos);
20.   }
21. }

到这里,单链表的基本操作几乎了解完了,但是要想熟练应用,融汇贯通,还要多加练习,做一些链表有关的OJ来加强理解,相信进步一定会很明显。

目录
打赏
0
0
0
0
0
分享
相关文章
|
3月前
|
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法,并分析时间复杂度,理解链表特点。实验内容包括循环链表应用(约瑟夫回环问题)、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践,加深对链表数据结构的理解和应用能力。
86 4
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
83 29
|
26天前
|
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
93 25
【C++数据结构——线性表】单链表的基本运算(头歌实践教学平台习题)【合集】
本内容介绍了单链表的基本运算任务,涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法,并提供了测试说明、通 - **任务描述**:实现单链表的基本运算。 - **相关知识**:包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**:平台会对你编写的代码进行测试,提供测试输入和预期输出。 - **通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了测试通过后的预期输出结果。 开始你的任务吧,祝你成功!
53 5
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
104 5
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
79 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
182 4
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等