带头节点单向非循环链表的基本操作(c语言实现)

头节点

头节点是数据结构中的一个概念,特别是在链表结构中。

它通常被设置为链表的第一个节点之前的一个节点,其数据域一般不存储链表中的实际数据,而它的指针域则存储指向链表中第一个实际节点的指针。

头节点的主要作用如下:

  1. 使得对链表的操作更加统一和方便,特别是在链表为空或者需要在链表头部进行插入、删除操作时,头节点的存在可以避免一些特殊情况的处理,从而简化代码并减少出错的可能性。
  2. 当链表为空时,头指针会指向头节点,从而避免头指针为空的情况,这在某种程度上增强了链表结构的健壮性。

需要注意的是,头节点并不是链表所必需的,它主要是为了操作方便而引入的。而头指针则是链表所必需的,它总是指向链表的第一个节点(无论是否存在头节点

带头节点单向不循环链表

我们也是借用结构体来表示一个单链表的定义

typedef int SLTDatatype;

typedef struct SListNode
{
SLTDataType data;
struct SListNode*next;
}SLTNode;

 SLTNode是“Singly Linked List Node”的缩写,它表示单链表中的结点。

在“SLTNode”这个缩写中,中间的“T”通常代表“Type”或者“Node”的缩写。在这里,“T”更是为了强调这是一个特定的类型(Type)或者是一个结点(Node)的表示。

链表的基本操作 

带头节点单向不循环链表的基本操作包括:

  1. 创建链表:首先需要定义一个链表结构体,其中每个结点包含一个数据域和一个指向下一个结点的指针。然后,通过动态内存分配(如使用malloc函数)来创建链表的各个结点,并将它们按照顺序连接起来。头结点作为链表的起始点,其指针域指向第一个实际的数据结点。
  2. 清空链表:遍历链表,逐个释放每个结点的内存空间,直到链表为空。注意,需要确保正确处理头结点,避免内存泄漏。
  3. 销毁链表:在清空链表后,还需要释放头结点的内存空间,以完全销毁整个链表。
  4. 头插法:在链表的头部插入新结点。具体操作为:创建一个新结点,将其数据域设置为要插入的数据,然后将其指针域指向头结点的下一个结点,最后更新头结点的指针域,使其指向新结点。
  5. 尾插法:在链表的尾部插入新结点。这需要遍历链表找到最后一个结点,然后创建一个新结点,将其数据域设置为要插入的数据,并将最后一个结点的指针域指向新结点。
  6. 任意位置插入法:在链表的任意位置插入新结点。首先找到要插入位置的前一个结点,然后创建一个新结点,将其数据域设置为要插入的数据,并将其指针域指向要插入位置的原结点,最后更新前一个结点的指针域,使其指向新结点。
  7. 头删法:删除链表的头部结点。具体操作为:将头结点的下一个结点作为新的头结点,然后释放原头结点的内存空间。
  8. 尾删法:删除链表的尾部结点。这需要遍历链表找到倒数第二个结点,然后将其指针域设置为NULL,并释放原尾部结点的内存空间。
  9. 任意位置删除法:删除链表的任意位置结点。首先找到要删除结点的前一个结点,然后更新前一个结点的指针域,使其跳过要删除的结点,并指向要删除结点的下一个结点,最后释放要删除结点的内存空间。
  10. 查询链表中是否有想要的数据:遍历链表,逐个比较结点的数据域与要查询的数据是否相等,若相等则返回该结点的位置或数据,否则继续遍历直到链表结束。

这些基本操作构成了带头节点单向不循环链表的基本功能,可以根据具体需求进行组合和扩展。需要注意的是,在实际编程中,还需要考虑错误处理、边界条件以及内存管理的安全性等问题。

一,链表的初始化

带头节点单向非循环链表和不带头节点单向非循环链表的初始化操作不同,带头节点的需要先搞出头节点来,而另外一个不用

void SLTInit(SLTNode** pphead)
{
	*pphead = (SLTNode*)malloc(sizeof(SLTNode));//创建头节点
	if (*pphead == NULL)
	{
		perror("malloc fail");
		return;
	}
	(*pphead)->next = NULL;//头结点的next置空
    (*pphead) -> data = 0;//仅仅是为了防止潜在的错误而设定的
}

经过这个操作我们得注意一个点:*pphead代表的是头节点,而不是第一个元素。

第一个元素是(*pphead)->next 

二,创建新结点

SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//分配内存
	if (newnode == NULL)//如果内存分配失败
	{
		perror("malloc fail");
		return NULL;
	}
//给新结点赋值
	newnode->data = x;
	newnode->next = NULL;
 
	return newnode;
}

三,指定结点的后插操作

//通常情况下,我们是按照*pos是头节点的标准来设计这个操作的
//在指定结点pos后面添加一个元素
// 在指定结点pos后面添加一个元素  
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {  
    assert(pos != NULL && pos->next != NULL); // 确保pos不为空且pos不是链表的最后一个节点  
    SLTNode* newnode = BuySLTNode(x);  
    newnode->next = pos->next;  
    pos->next = newnode;  
}

四,指定结点的前插操作

// 在指定结点pos前添加一个元素  
void SLTInsertFront(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
    assert(pphead != NULL && *pphead != NULL && pos != NULL);
    if (*pphead == pos) {
        perror("头节点不能前插\n");
        exit(-1);
    }
    SLTNode* cur = *pphead;
    while (cur->next != pos) {
        if (cur->next == NULL) {
            perror("目标结点pos不在链表中\n");
            exit(-1);
        }
        cur = cur->next;
    }
    SLTNode* newnode = BuySLTNode(x);
    newnode->next = pos;
    cur->next = newnode;
}

五,在链表头部插入新结点

// 在链表头部插入新结点  
void ListInsertFront(SLTNode** pphead, SLTDataType data) {
    assert(pphead != NULL && *pphead != NULL);
    SLTNode* newnode = BuySLTNode(data);
    newnode->next = (*pphead)->next;
    (*pphead)->next = newnode;
}

六,在链表尾部插入新结点 

// 在链表尾部插入新结点   
void InsertRear(SLTNode** pphead, SLTDataType data) {
    assert(pphead != NULL && *pphead != NULL);
    SLTNode* newnode = BuySLTNode(data);
    SLTNode* tail = *pphead;
    while (tail->next) {
        tail = tail->next;
    }
    tail->next = newnode;
}

七,删除链表的第一个结点 

// 删除链表的头部结点  
void DeleteFront(SLTNode** pphead) {
    if ((*pphead)->next == NULL) {//我们要注意*pphead是头节点,不是第一个结点
        printf("List is empty!\n");
        return;
    }
    SLTNode* p = (*pphead)->next;
    (*pphead)->next = p->next; // 头结点指向原第二个结点  
    free(p); // 释放原第一个结点内存  
}

八,删除链表的最后一个结点

// 删除链表的尾部结点  
void DeleteRear(SLTNode** pphead) {
    if ((*pphead)->next == NULL) {
        printf("List is empty!\n");
        return;
    }
    SLTNode* p = *pphead;
    SLTNode* q = NULL;
    while (p->next->next) { // 找到倒数第二个结点  
        q = p;
        p = p->next;
    }
    //p为倒数第二个
    //q为倒数第三个
    q->next = NULL; // 最后一个结点的前一个结点指向NULL  
    free(p->next); // 释放原尾部结点内存  
}

九,释放链表

// 释放链表内存  
void FreeList(SLTNode* head) {
    SLTNode* cur = head;
    while (cur) {
        SLTNode* next = cur->next;
        free(cur);
        cur = next;
    }
}

十,打印链表

// 打印链表  
void PrintList(SLTNode* head) {
    SLTNode* cur = head->next;
    while (cur) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

完整代码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

// 初始化链表  
void SLTInit(SLTNode** pphead) {
    *pphead = (SLTNode*)malloc(sizeof(SLTNode));
    if (*pphead == NULL) {
        perror("malloc fail");
        exit(EXIT_FAILURE);
    }
    (*pphead)->data = 0; // 初始化头结点的data字段  
    (*pphead)->next = NULL;
}

// 创建新结点  
SLTNode* BuySLTNode(SLTDataType x) {
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if (newnode == NULL) {
        perror("malloc fail");
        exit(EXIT_FAILURE);
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

// 在指定结点pos后面添加一个元素  
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
    assert(pos != NULL && pos->next != NULL); // 确保pos不为空且pos不是链表的最后一个节点  
    SLTNode* newnode = BuySLTNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
}

// 在指定结点pos前添加一个元素  
void SLTInsertFront(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
    assert(pphead != NULL && *pphead != NULL && pos != NULL);
    if (*pphead == pos) {
        perror("头节点不能前插\n");
        exit(-1);
    }
    SLTNode* cur = *pphead;
    while (cur->next != pos) {
        if (cur->next == NULL) {
            perror("目标结点pos不在链表中\n");
            exit(-1);
        }
        cur = cur->next;
    }
    SLTNode* newnode = BuySLTNode(x);
    newnode->next = pos;
    cur->next = newnode;
}

// 在链表头部插入新结点  
void ListInsertFront(SLTNode** pphead, SLTDataType data) {
    assert(pphead != NULL && *pphead != NULL);
    SLTNode* newnode = BuySLTNode(data);
    newnode->next = (*pphead)->next;
    (*pphead)->next = newnode;
}

// 在链表尾部插入新结点  
void InsertRear(SLTNode** pphead, SLTDataType data) {
    assert(pphead != NULL && *pphead != NULL);
    SLTNode* newnode = BuySLTNode(data);
    SLTNode* tail = *pphead;
    while (tail->next) {
        tail = tail->next;
    }
    tail->next = newnode;
}

// 释放链表内存  
void FreeList(SLTNode* head) {
    SLTNode* cur = head;
    while (cur) {
        SLTNode* next = cur->next;
        free(cur);
        cur = next;
    }
}

// 打印链表  
void PrintList(SLTNode* head) {
    SLTNode* cur = head->next;
    while (cur) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}
// 删除链表的头部结点  
void DeleteFront(SLTNode** pphead) {
    if ((*pphead)->next == NULL) {//我们要注意*pphead是头节点,不是第一个结点
        printf("List is empty!\n");
        return;
    }
    SLTNode* p = (*pphead)->next;
    (*pphead)->next = p->next; // 头结点指向原第二个结点  
    free(p); // 释放原第一个结点内存  
}

// 删除链表的尾部结点  
void DeleteRear(SLTNode** pphead) {
    if ((*pphead)->next == NULL) {
        printf("List is empty!\n");
        return;
    }
    SLTNode* p = *pphead;
    SLTNode* q = NULL;
    while (p->next->next) { // 找到倒数第二个结点  
        q = p;
        p = p->next;
    }
    //p为倒数第二个
    //q为倒数第三个
    q->next = NULL; // 最后一个结点的前一个结点指向NULL  
    free(p->next); // 释放原尾部结点内存  
}
// 测试代码  
int main() {
    SLTNode* head = NULL;
    SLTInit(&head);

    ListInsertFront(&head, 1);
    ListInsertFront(&head, 2);
    InsertRear(&head, 3);
    SLTInsertAfter(head->next, 4); // 插入到第二个节点后  
    SLTInsertFront(&head, head->next->next, 5); // 插入到第三个节点前  

    PrintList(head);

    FreeList(head);

    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/543638.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Pandas相比Excel的优势是哪些?

熟悉Pandas的同学会知道&#xff0c;Pandas相当于Python中的Excel&#xff0c;都是基于二维表的进行数据处理分析&#xff0c;不同的是&#xff0c;Pandas基于代码操作数据&#xff0c;Excel是图形化的分析工具。 不少人会问Excel比Pandas更简单&#xff0c;为什么还要学习Pan…

【NLP】大语言模型基础之Transformer结构

大语言模型基础之Transformer结构 1. Transformer结构总览2. 嵌入表示层2. 注意力层3. 前馈层4. 残差连接与层归一化5. 编码器和解码器结构参考文献 Transformer是一种深度学习模型架构&#xff0c;由Vaswani等人于2017年在论文《Attention is All You Need》中首次提出。它在自…

消除 BEV 空间中的跨模态冲突,实现 LiDAR 相机 3D 目标检测

Eliminating Cross-modal Conflicts in BEV Space for LiDAR-Camera 3D Object Detection 消除 BEV 空间中的跨模态冲突&#xff0c;实现 LiDAR 相机 3D 目标检测 摘要Introduction本文方法Single-Modal BEV Feature ExtractionSemantic-guided Flow-based AlignmentDissolved…

vue控制台报错Duplicate keys detected: ‘xxxxx‘. This may cause an update error.解决方案

截图报错&#xff1a; 错误分析&#xff1a; 1、提示 Duplicate keys detected &#xff0c;翻译为&#xff1a;检测到重复的密钥 2、检查 v-for 代码&#xff0c;具体如下&#xff1a; 发现问题&#xff1a;v-for中的key是一个相同的值 解决问题 因此处使用的是测试数据&…

【示例】MySQL-4类SQL语言-DDL-DML-DQL-DCL

前言 本文主要讲述MySQL中4中SQL语言的使用及各自特点。 SQL语言总共分四类&#xff1a;DDL、DML、DQL、DCL。 SQL-DDL | Data Definition Language 数据定义语言&#xff1a;用来定义/更改数据库对象&#xff08;数据库、表、字段&#xff09; 用途 | 操作数据库 # 查询所…

MATLAB 计算点投影到平面上的坐标(59)

MATLAB 计算点投影到平面上的坐标(59) 一、算法介绍二、算法实现1.代码2.结果一、算法介绍 点投影到平面,计算投影点的坐标,下面提供MATLAB版本的计算程序,直接运行即可,内有验证数据,具体看代码即可。 二、算法实现 1.代码 代码如下(示例): % 平面上的三个点分…

力扣--图论/Prim1584.连接所有点的最小费用

思路分析&#xff1a; 初始化&#xff1a;获取点的数量&#xff0c;并创建两个辅助数组 adjvex 和 lowcost&#xff0c;分别用于记录最小生成树的边信息和每个顶点到最小生成树的距离。Prim算法循环&#xff1a;在每一次循环中&#xff0c;选择一个未加入最小生成树的顶点 k&a…

登陆qq,经常收到qq游戏中心的推送信息,关闭推送信息

手动关闭推送信息的步骤&#xff1a; 1.点开左侧游戏中心 2、在打开界面&#xff0c;点击左下角自己的头像 3、打开设置中心&#xff0c;关闭所有的推送 4、完成关闭&#xff0c;不会推送了

使用 Prometheus 在 KubeSphere 上监控 KubeEdge 边缘节点(Jetson) CPU、GPU 状态

作者&#xff1a;朱亚光&#xff0c;之江实验室工程师&#xff0c;云原生/开源爱好者。 KubeSphere 边缘节点的可观测性 在边缘计算场景下&#xff0c;KubeSphere 基于 KubeEdge 实现应用与工作负载在云端与边缘节点的统一分发与管理&#xff0c;解决在海量边、端设备上完成应…

基于SSM+Jsp+Mysql的旅游网站设计与实现

开发语言&#xff1a;Java框架&#xff1a;ssm技术&#xff1a;JSPJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包…

数据链路层(上):以太网、二层交换机和网络风暴

目录 数据链路层知识概览 数据链路层设备 1、二层交换机 2、拓展&#xff1a;二层交换机与三层交换机有啥区别&#xff1f; 3、广播风暴 4、交换机以太网接口的工作模式 数据链路层的功能 数据链路层--以太网 1、以太网是什么&#xff1f; 2、以太网地址 数据链路层知…

手把手教你安装深度学习框架PyTorch:一键式安装指南

随着人工智能和深度学习的飞速发展&#xff0c;PyTorch作为一个强大而灵活的深度学习框架&#xff0c;受到了越来越多研究者和开发者的青睐。PyTorch不仅易于上手&#xff0c;而且支持动态计算图&#xff0c;使得调试和实验变得非常方便。本文将手把手教你如何安装PyTorch&…

端口协议(爆破、未授权)

常见端口服务及攻击方向&#xff1a; 弱口令爆破 工具&#xff1a;https://github.com/vanhauser-thc/thc-hydra hydra是一个支持多协议的自动化的爆破工具。 支持的服务、协议&#xff1a; telnet ftp pop3[-ntlm] imap[-ntlm] smb smbnt http-{head|get} http-{get|post}-…

Flutter第八弹 构建拥有不同项的列表

目标&#xff1a;1&#xff09;项目中&#xff0c;数据源可能涉及不同的模版&#xff0c;显示不同类型的子项&#xff0c;类似RecycleView的itemType, 有多种类型&#xff0c;列表怎么显示&#xff1f; 2&#xff09;不同的数据源构建列表 一、创建不同的数据源 采用类似Rec…

直播弹幕系统设计

本文仅提供思路参考&#xff0c;并非完备的详细设计。 特点 其实很类似IM即时通讯系统&#xff0c;是个变种&#xff0c;本质也是在一个空间内收发消息 消息及时性强&#xff0c;过期消息意义不大用户松散&#xff0c;随时来随时走可能有瞬时大批量弹幕&#xff08;比如比赛精…

漫途水产养殖水质智能监测方案,科技助力养殖业高效生产!

随着水产养殖业的蓬勃发展&#xff0c;水质和饲料等多重因素逐渐成为影响其持续健康发展的关键因素。由于传统养殖模式因监控和调节手段不足&#xff0c;往往造成养殖环境的恶化。需要通过智能化养殖&#xff0c;调控养殖环境&#xff0c;实现养殖的精细化管理模式&#xff0c;…

【Git教程】(九)版本标签 —— 创建、查看标签,标签的散列值,将标签添加到日志输出中,判断标签是否包含特定的提交 ~

Git教程 版本标签&#xff08;tag&#xff09; 1️⃣ 创建标签2️⃣ 查看存在的标签3️⃣ 标签的散列值4️⃣ 将标签添加到日志输出中5️⃣ 判断tag是否包含特定的提交&#x1f33e; 总结 大多数项目都是用 1.7.3.2和 “ gingerbread” 这样的数字或名称来标识软件版本的。在 …

《由浅入深学习SAP财务》:第2章 总账模块 - 2.6 定期处理 - 2.6.6 年初操作:科目余额结转

2.6.6 年初操作&#xff1a;科目余额结转 在使用事务代码 FAGLB03 查询科目余额时&#xff0c;可以看到按期间的发生额清单。其中&#xff0c;第一行称为“余额结转”&#xff0c;该行的累计余额代表上年度遗留下来的余额&#xff0c;也就是年初余额。对于资产负债表科目而言&a…

中华人民共和国密码行业标准-各类标准文档下载

国家密码管理局 中华人民共和国密码行业标准 GmSSL Project 密码行业标准化技术委员会公布了所有密码行业标准&#xff0c;并支持全文查看&#xff0c;参见密码行业标准列表 GM/T 0001-2012 祖冲之序列密码算法 GM/T 0002-2012 SM4分组密码算法(原SMS4分组密码算法) GM/…

深度剖析整型和浮点型数据在内存中的存储(C语言)

目录 整型在内存中的存储 为什么整型在内存中存储的是补码&#xff1f; 大小端字节序 为什么有大端小端&#xff1f; 浮点型家族 浮点数在内存中的存储 long long 整型在内存中的存储 整型在内存中有三种二进制表示形式&#xff1a;原码&#xff0c;反码&#xff0c;补码…