<数据结构> 链表 - 单链表(c语言实现)(一)

简介: <数据结构> 链表 - 单链表(c语言实现)(一)

(关于哨兵位结点)


哨兵位结点也叫哑节点。哨兵位结点也是头结点 。该节点不存储有效数据,只是为了方便操作 (如尾插时用带哨兵位的头结点很爽,不需要判空)。


有哨兵位结点的链表,第一个元素应该是链表第二个节点(head -> next,head为哨兵位结点)对应的元素。


有哨兵位结点的链表永不为空 (因为至少有一个结点——哨兵位结点),这样可以避免判断头是否为空,起到简化代码、减少出错的作用。


一、不带哨兵位单链表结点的创建


🚩

下面的自定义类型、函数名里SLT:

来源于单链表的英文:Single Linked List


1.1 typedef 链表的数据类型

typedef 一下链表数据域的数据类型,目的 是如果以后需要改变链表数据类型直接在typedef后改一下即可,否则要在程序中一个个的改,麻烦并且易出错


typedef int SLTDataType;

1.2 结点的结构体创建

凡是有多个数据的 → 创建结构体。

数据域: 存储的数据data,类型是SLTDataType。

指针域: 存下一个结点的地址next,类型是结构体指针 struct SListNode*。

typedef struct SListNode  //line1
{ //line2
  SLTDataType data;//数据域  //line3
  struct SListNode* next;//指针域  //line4
}SLTNode; //line5


🔺 注意:指针域的结构体指针不可以是SLTNode*

编译器的查找规则:编译的时候,如果要用到一个函数或者一个类型,它不会向下查找,只能向上查找。具体来说,SLTNode*在第五行以后才起作用,在第四行的时候还没有定义“SLTNode* ”


二、单链表要实现的功能


1、打印链表:将链表各个结点数据域中的数据按顺序打印出来


2、创建一个新结点:插入一个结点的时候要创建一个新结点,干脆封装成一个函数,后面直接调用即可


3、在链表尾部插入一个数据(尾插)


4、删除链表尾部的结点(尾删)


5、在链表头部插入一个数据(头插)


6、删除链表头部的结点(头删)


7、查找某个结点:返回结点地址


8、删除某个结点


9、单链表中插入结点


10、销毁链表


三、需要包含的头文件


#include<stdio.h>
#include<stdlib.h>
#include<assert.h>


四、函数接口一览


//打印 单链表
void SLTPrint(SLTNode* phead);
//动态申请一个节点
SLTNode* BuySLTNode(SLTDataType x);
//尾插(并给节点中的data赋值)
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头插(并给节点中的data赋值)
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//头删
void SLTPopFront(SLTNode** pphead);
//查找并返回结点地址
SLTNode* SLFind(SLTNode* phead, SLDataType x);
//删除某个结点
void SLErase(SLTNode** pphead, SLTNode* pos);
//pos前 插入结点
void SLInsert(SLTNode** pphead, SLTNode* pos, SLDataType x);
//销毁
void SLDestroy(SLTNode** pphead);


为什么有些函数参数传递的是二级指针,有些是一级指针?

因为有些函数需要改变传入的结点 。


phead可能为空:链表一开始为空(main()函数中定义SLTNode* phead = NULL),对于插入类的函数,第一次插入时phead为空,那么就要改变phead指向的空间(要在函数中创建一个新结点,phead改变为该结点的地址),即需要改变phead,而phead是一级指针,因为要改变指针需要传递指针的指针——二级指针,即传递指针变量phead的地址——&phead。


但是像打印这样的函数,不需要改变phead,只需要遍历一遍链表,打印出各结点的数据即可,所以传phead(一级指针)就好,不需要二级指针。

相关文章
|
27天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
123 9
|
6天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
28 5
|
26天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
63 16
|
26天前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
87 8
|
29天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
55 4
|
29天前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
42 0
|
18天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
23 1
|
21天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
24天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
26天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
47 4