C语言_数据结构总结4：不带头结点的单链表

纯C语言代码，不涉及C++

0. 结点结构

typedef int ElemType;
typedef struct LNode {
    ElemType data;  //数据域
    struct LNode* next;  //指针域
}LNode, * LinkList;

1. 初始化

不带头结点的初始化，即只需将头指针初始化为NULL即可

void InitLink2(LinkList* L) {*L = NULL;
}

2. 头插法

对于不带头结点的单链表，头插法的核心思想是：
每次插入新节点时，将新节点的 next 指针指向当前链表的头节点，然后更新链表的头指针，使其指向新节点。
这样新节点就成为了链表的第一个节点，插入操作的时间复杂度为 O(1)。

int headInsert(LinkList* L, ElemType value) {LinkList s = (LinkList)malloc(sizeof(LNode));if (s == NULL){printf("内存分配失败!\n");return -2;}s->data = value;s->next = *L;*L = s;  //更新头结点指向新结点return 0;  //插入成功
}

3. 尾插法

尾插法的核心思路是每次都将新节点插入到链表的末尾。
对于不带头结点的单链表，需要考虑链表为空的特殊情况。
当链表为空时，新插入的节点就是链表的头节点；
当链表不为空时，需要先遍历到链表的尾部，然后将新节点连接到尾部节点的后面。

int tailInsert(LinkList* L, ElemType value) {LinkList s = (LinkList)malloc(sizeof(LNode));if (s == NULL){printf("内存分配失败!\n");return -2;}s->data = value;s->next = NULL;  //因为新结点s要插入到链表尾部//若链表为空，新结点就是头结点if (*L == NULL){*L = s;}else{//1.找到链表的尾结点LinkList p = *L;while (p->next != NULL) {p = p->next;}p->next = s;  //将新节点插入到尾结点后面}return 0; //插入成功
}

4. 插入

int insertLNode2(LinkList* L, int pos, ElemType value) {if (pos < 1) {printf("插入位置不合法!\n");return -1;}LinkList s = (LinkList)malloc(sizeof(LNode));if (s == NULL) {printf("内存分配失败!\n");return -2;}s->data = value;if (pos == 1) {s->next = *L;*L = s;}else {LinkList p = *L;int i = 1;while (p != NULL && i < pos - 1) {p = p->next;i++;}if (p == NULL) {printf("插入位置不合法,已超出链表长度!\n");free(s);return -1;}s->next = p->next;p->next = s;}return 0;
}

5. 删除

！不带头结点的单链表进行删除结点操作需要分情况考虑：

若要删除的是头节点，需要直接更新头指针；
若删除的是其他节点，需要找到该节点的前一个节点。

！在不带头结点的单链表删除操作中，当 pos == 1 时，不能直接使用 free(*L);，而要进行 *L = (*L)->next;

直接 free(*L); 存在的问题

free(*L); 这行代码的作用是释放 *L 所指向的内存空间。但执行完这一步后，链表的头指针 *L 仍然指向这块已经被释放的内存，形成了一个野指针。野指针是非常危险的，因为后续如果对这个野指针进行解引用操作（例如访问 (*L)->data 或 (*L)->next），会导致未定义行为，可能会使程序崩溃。而且，由于头指针没有更新，链表的后续节点就无法再被访问到，整个链表就丢失了。

*L = (*L)->next; 操作的意义

当 pos == 1 时，意味着要删除链表的第一个节点（即头节点）。*L = (*L)->next; 这行代码的作用是更新头指针，让它指向原来头节点的下一个节点。具体步骤如下：

  1. 保存原头节点指针：

LinkList temp = *L;

》这行代码将原头节点的指针保存到临时变量 temp 中，方便后续释放该节点的内存。
     2. 更新头指针：

*L = (*L)->next;

》》将头指针 *L 更新为原头节点的下一个节点。这样，新的头指针就指向了链表的第二个节点（如果存在的话），链表仍然可以正常访问。
   3. 释放原头节点内存：

free(temp);

》》》释放临时变量 temp 所指向的内存，即原头节点的内存。

以下删除的操作完整代码：

int deleteNode(LinkList* L, int pos) {if (pos < 1){printf("删除位置无效!\n");return -1;}if (*L == NULL){printf("当前链表为空!\n");return -2;}if (pos == 1)  //即删除头结点，（更新头结点）{LinkList temp = *L;*L = (*L)->next;free(temp);}else{LinkList p = *L;int i = 1;//找到第pos-1个结点while (p != NULL && i < pos - 1) {p = p->next;i++;}if (p == NULL || p->next == NULL){printf("删除位置不合法!\n");return -1;}LinkList temp = p->next;p->next = temp->next;free(temp);}return 0;  //删除成功
}

6. 按位查找

即：查找第pos个位置上的value值

int findValueByPos(LinkList L, int pos, ElemType* value) {if (pos < 1){printf("查找位置不合法!\n");return -1;}LinkList p = L;int i = 1;while (p != NULL && i < pos) {p = p->next;i++;}if (p == NULL){printf("查找位置超出链表长度!\n");return -1;}*value = p->data;return 0;
}

7. 按值查找

即：查找value值在链表的第pos个位置

int findPosByvalue(LinkList L,ElemType value) {LinkList p = L;int pos = 1;while (p != NULL) {if (p->data == value){return pos;}p = p->next;pos++;}return -1;  //查找失败，未在该链表中找到该value值
}

8. 链表打印

void printLink2(LinkList L) {if (L == NULL) {printf("链表为空!\n");return;}LinkList s = L;while (s != NULL) {printf("%d ", s->data);s = s->next;}printf("\n--------------------------------\n");
}

9. 释放空间

void freeList2(LinkList L) {LinkList p = L;while (p != NULL) {LinkList temp = p;p = p->next;free(temp);}
}

10. 测试代码

int main() {//测试插入方法LinkList L1;InitLink2(&L1);insertLNode2(&L1, 1, 11);insertLNode2(&L1, 2, 22);insertLNode2(&L1, 3, 33);printLink2(L1);  // 11 22 33 freeList2(L1);// 测试头插法LinkList L2;InitLink2(&L2);headInsert(&L2, 1);headInsert(&L2, 2);headInsert(&L2, 3);printLink2(L2);  // 3 2 1freeList2(L2);// 测试尾插法LinkList L3;InitLink2(&L3);tailInsert(&L3, 1);tailInsert(&L3, 2);tailInsert(&L3, 3);printLink2(L3);  // 1 2 3// 测试删除deleteNode(&L3, 3);printf("删除第三个结点后：");printLink2(L3);  //删除第三个结点后：1 2//测试按值查找printf("数值1在第%d个位置\n", findPosByvalue(L3, 1));  // 数值1在第1个位置//测试按位查找ElemType value;findValueByPos(L3, 1, &value);printf("第1个位置的值为%d\n", value);  // 第1个位置的值为1freeList2(L3);return 0;
}

11. 完整代码

#include<stdio.h>
#include<stdlib.h>
/*不带头结点的单链表
*/typedef int ElemType;
typedef struct LNode {ElemType data;  //数据域struct LNode* next;  //指针域
}LNode, * LinkList;// 操作1——不带头结点的初始化，即只需将头指针初始化为NULL即可
void InitLink2(LinkList* L) {*L = NULL;
}// 操作2——不带头结点的插入操作
int insertLNode2(LinkList* L, int pos, ElemType value) {if (pos < 1) {printf("插入位置不合法!\n");return -1;}LinkList s = (LinkList)malloc(sizeof(LNode));if (s == NULL) {printf("内存分配失败!\n");return -2;}s->data = value;if (pos == 1) {s->next = *L;*L = s;}else {LinkList p = *L;int i = 1;while (p != NULL && i < pos - 1) {p = p->next;i++;}if (p == NULL) {printf("插入位置不合法!\n");free(s);return -1;}s->next = p->next;p->next = s;}return 0;
}//操作2.1——不带头结点的头插法建立单链表方法
int headInsert(LinkList* L, ElemType value) {LinkList s = (LinkList)malloc(sizeof(LNode));if (s == NULL){printf("内存分配失败!\n");return -2;}s->data = value;s->next = *L;*L = s;  //更新头结点指向新结点return 0;  //插入成功
}//操作2.3——不带头结点的尾插法建立单链表方法
/*
尾插法的核心思路是每次都将新节点插入到链表的末尾。
对于不带头结点的单链表，需要考虑链表为空的特殊情况。
当链表为空时，新插入的节点就是链表的头节点；
当链表不为空时，需要先遍历到链表的尾部，然后将新节点连接到尾部节点的后面。
*/
int tailInsert(LinkList* L, ElemType value) {LinkList s = (LinkList)malloc(sizeof(LNode));if (s == NULL){printf("内存分配失败!\n");return -2;}s->data = value;s->next = NULL;  //因为新结点s要插入到链表尾部//若链表为空，新结点就是头结点if (*L == NULL){*L = s;}else{//1.找到链表的尾结点LinkList p = *L;while (p->next != NULL) {p = p->next;}p->next = s;  //将新节点插入到尾结点后面}return 0; //插入成功
}// 操作3——删除第pos个位置的值
/*
删除操作需要分情况考虑，若要删除的是头节点，需要直接更新头指针；
若删除的是其他节点，需要找到该节点的前一个节点。
*/
int deleteNode(LinkList* L, int pos) {if (pos < 1){printf("删除位置无效!\n");return -1;}if (*L == NULL){printf("当前链表为空!\n");return -2;}if (pos == 1)  //即删除头结点，（更新头结点）{LinkList temp = *L;*L = (*L)->next;free(temp);}else{LinkList p = *L;int i = 1;//找到第pos-1个结点while (p != NULL && i < pos - 1) {p = p->next;i++;}if (p == NULL || p->next == NULL){printf("删除位置不合法!\n");return -1;}LinkList temp = p->next;p->next = temp->next;free(temp);}return 0;  //删除成功
}// 操作4——按位查找：查找第pos个位置上的value值
int findValueByPos(LinkList L, int pos, ElemType* value) {if (pos < 1){printf("查找位置不合法!\n");return -1;}LinkList p = L;int i = 1;while (p != NULL && i < pos) {p = p->next;i++;}if (p == NULL){printf("查找位置超出链表长度!\n");return -1;}*value = p->data;return 0;
}// 操作5——按值查找：查找value值在链表的第pos个位置
int findPosByvalue(LinkList L,ElemType value) {LinkList p = L;int pos = 1;while (p != NULL) {if (p->data == value){return pos;}p = p->next;pos++;}return -1;  //查找失败，未在该链表中找到该value值
}// 操作6——不带头结点的单链表打印操作
void printLink2(LinkList L) {if (L == NULL) {printf("链表为空!\n");return;}LinkList s = L;while (s != NULL) {printf("%d ", s->data);s = s->next;}printf("\n--------------------------------\n");
}// 操作7——释放不带头结点链表内存
void freeList2(LinkList L) {LinkList p = L;while (p != NULL) {LinkList temp = p;p = p->next;free(temp);}
}int main() {//测试插入方法LinkList L1;InitLink2(&L1);insertLNode2(&L1, 1, 11);insertLNode2(&L1, 2, 22);insertLNode2(&L1, 3, 33);printLink2(L1);  // 11 22 33 freeList2(L1);// 测试头插法LinkList L2;InitLink2(&L2);headInsert(&L2, 1);headInsert(&L2, 2);headInsert(&L2, 3);printLink2(L2);  // 3 2 1freeList2(L2);// 测试尾插法LinkList L3;InitLink2(&L3);tailInsert(&L3, 1);tailInsert(&L3, 2);tailInsert(&L3, 3);printLink2(L3);  // 1 2 3// 测试删除deleteNode(&L3, 3);printf("删除第三个结点后：");printLink2(L3);  //删除第三个结点后：1 2//测试按值查找printf("数值1在第%d个位置\n", findPosByvalue(L3, 1));  // 数值1在第1个位置//测试按位查找ElemType value;findValueByPos(L3, 1, &value);printf("第1个位置的值为%d\n", value);  // 第1个位置的值为1freeList2(L3);return 0;
}

12. 运行截图

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

是德科技十周年：以创新丈量未来，用科技赋能世界

是德科技十周年：以创新丈量未来，用科技赋能世界

是德科技成立十周年&#xff0c;以全球测试测量领域领军者的姿态&#xff0c;书写了一部突破与创新的发展史诗。作为从惠普、安捷伦深厚技术积淀中孕育而生的行业标杆&#xff0c;十年来是德科技始终站在科技浪潮之巅&#xff0c;构建起覆盖5G通信、人工智能、汽车电子、量子计…
阅读更多...
循环神经网络（RNN）：时序建模的核心引擎与演进之路

循环神经网络（RNN）：时序建模的核心引擎与演进之路

在人工智能处理序列数据的战场上&#xff0c;循环神经网络&#xff08;RNN&#xff09;如同一个能够理解时间的智者。从 2015 年谷歌神经机器翻译系统颠覆传统方法&#xff0c;到 2023 年 ChatGPT 实现对话连续性&#xff0c;这些突破都植根于 RNN 对时序建模的深刻理解。本文将…
阅读更多...
【单片机通信技术】STM32 HAL库 SPI主从机通过串口发送数据

【单片机通信技术】STM32 HAL库 SPI主从机通过串口发送数据

一、说明 使用STM32F103C8T6最小系统板&#xff0c;让板载SPI1与SPI2通信&#xff0c;通过串口收发数据。本文章说明了在配置与编写时遇到的一些问题&#xff0c;以及详细说明如何使用cubeMAX进行代码编写。 二、CubeMAX配置 1.时钟配置选择外部高速时钟 2.系统模式与时钟配…
阅读更多...
批量删除 Excel 中所有图片、某张指定图片以及二维码图片

批量删除 Excel 中所有图片、某张指定图片以及二维码图片

在 Excel 文档中&#xff0c;我们可以在工作表中插入大量的图片&#xff0c;我们也可以删除工作表中的图片。少量的图片我们可以直接删除&#xff0c;但是我们我们有大量的 Excel 文档&#xff0c;那如何快速删除所有 Excel 表格中的所有图片呢&#xff1f;我们除了常规删除 Ex…
阅读更多...
【算法】大数据查重

【算法】大数据查重

大数据查重 哈希表 找出第一个出现重复的数字 || 找所有重复出现的数字 #include <iostream> #include <vector> #include <unordered_map> #include <unordered_set> #include <stdlib.h> #include <time.h> #include <string> …
阅读更多...
网格图学习（附题单与做题思路）

网格图学习（附题单与做题思路）

文章目录 一、DFS 经典题型695. 岛屿的最大面积 二、BFS 经典题型994. 腐烂的橘子**算法选择对照表** 一、DFS 经典题型 岛屿的最大面积 LeetCode 695描述&#xff1a;求网格中最大的陆地连通区域面积解题&#xff1a;DFS 遍历所有相邻陆地&#xff0c;标记已访问关键点&#…
阅读更多...
安装树莓派3B+环境（嵌入式开发）

安装树莓派3B+环境（嵌入式开发）

一、环境配置 1、下载树莓派镜像工具 点击进入下载连接 进入网站&#xff0c;点击下载即可。 2、配置wifi及ssh 将SD卡插入读卡器&#xff0c;再接入电脑&#xff0c;随后打开Raspberry Pi Imager下载工具&#xff0c; 选择Raspberry Pi 3 选择64位的操作系统 选择SD卡 选择…
阅读更多...
Leetcode 刷题记录 06 —— 矩阵

Leetcode 刷题记录 06 —— 矩阵

本系列为笔者的 Leetcode 刷题记录&#xff0c;顺序为 Hot 100 题官方顺序&#xff0c;根据标签命名&#xff0c;记录笔者总结的做题思路&#xff0c;附部分代码解释和疑问解答。 目录 01 矩阵置零 方法一&#xff1a;标记数组 方法二&#xff1a;两个标记变量 02 螺旋矩阵…
阅读更多...
前端 | 向后端传数据，判断问题所在的调试过程

前端 | 向后端传数据，判断问题所在的调试过程

目录 ​编辑 1. 在 vue 文件中&#xff0c;在调用函数之前 先打印传入的数据 2. 在 js 文件中&#xff0c;打印接收到的数据 3. 在浏览器 Network 面板查看请求数据 4. 在 server.js 中查看请求数据 5. 确保 JSON 格式正确 知识点&#xff1a;JSON.stringify(req.body, …
阅读更多...
江科大51单片机笔记【11】AT24C02（I2C总线）

江科大51单片机笔记【11】AT24C02（I2C总线）

一、存储器 1.介绍 RAM的特点是存储速度特别快&#xff0c;但是掉电会丢失&#xff1b;ROM的特点是存储速度特别慢&#xff0c;但是掉电不会丢失 SRAM是所有存储器最快的&#xff0c;一般用于电脑的CPU高速缓存&#xff0c;容量相对较少&#xff0c;成本较高&#xff1b;DRAM…
阅读更多...
Python绘制数据分析中经典的图形--列线图

Python绘制数据分析中经典的图形--列线图

Python绘制数据分析中经典的图形–列线图 列线图是数据分析中的经典图形&#xff0c;通过背后精妙的算法设计&#xff0c;展示线性模型&#xff08;logistic regression 和Cox&#xff09;中各个变量对于预测结果的总体贡献&#xff08;线段长短&#xff09;&#xff0c;另外&…
阅读更多...
Golang学习笔记_44——命令模式

Golang学习笔记_44——命令模式

Golang学习笔记_41——观察者模式 Golang学习笔记_42——迭代器模式 Golang学习笔记_43——责任链模式 文章目录 一、核心概念1. 定义2. 解决的问题3. 核心角色4. 类图 二、特点分析三、适用场景1. 事务管理系统2. 多媒体遥控器3. 操作审计系统 四、Go语言实现示例五、高级应用…
阅读更多...
致同报告：香港财政赤字加剧，扩大税基与增收迫在眉睫

致同报告：香港财政赤字加剧，扩大税基与增收迫在眉睫

2月26日香港政府2025-26年度财政预算案&#xff0c;&#xff08;以下简称“预算案”&#xff09;发布&#xff0c;香港财政司司长陈茂波提出一系列旨在减少开支并振兴香港经济的措施&#xff0c;以应对日益增长的财政赤字。主要提案包括对所有公务员实施冻薪、针对性税务宽减措…
阅读更多...
计算机网络笔记(二)——1.2互联网概述

计算机网络笔记(二)——1.2互联网概述

1.2.1网络的网络 起源于美国的互联网现已发展成为世界上最大的覆盖全球的计算机网络。 下面&#xff0c;我们先来看看关于网络、互连网、互联网(因特网)的一些基本概念。为了方便&#xff0c;后面我们所称呼的"网络"往往就是"计算机网络",而不是电信网或有…
阅读更多...
小程序开发总结

小程序开发总结

今年第一次帮别人做小程序。 从开始动手到完成上线&#xff0c;一共耗时两天。AI 让写代码变得简单、高效。 不过&#xff0c;小程序和 Flutter 等大厂开发框架差距实在太大&#xff0c;导致我一开始根本找不到感觉。 第一&#xff0c;IDE 不好用&#xff0c;各种功能杂糅在…
阅读更多...
DeepSeek开启AI办公新模式，WPS/Office集成DeepSeek-R1本地大模型！

DeepSeek开启AI办公新模式，WPS/Office集成DeepSeek-R1本地大模型！

从央视到地方媒体&#xff0c;已有多家媒体机构推出AI主播&#xff0c;最近杭州文化广播电视集团的《杭州新闻联播》节目&#xff0c;使用AI主持人进行新闻播报&#xff0c;且做到了0失误率&#xff0c;可见AI正在逐渐取代部分行业和一些重复性的工作&#xff0c;这一现象引发很…
阅读更多...
IntelliJ IDEA 2021版创建springboot项目的五种方式

IntelliJ IDEA 2021版创建springboot项目的五种方式

第一种方式&#xff0c;通过https://start.spring.io作为spring Initializr的url来创建项目。 第二种方式&#xff0c;通过https://start.spring.io官网来直接创建springboot项目压缩包&#xff0c;然后导入至我们的idea中。 点击generate后&#xff0c;即可生成压缩包&#xf…
阅读更多...
IDEA与Maven使用-学习记录（持续补充...）

IDEA与Maven使用-学习记录（持续补充...）

1. 下载与安装 以ideaIU-2021.3.1为例&#xff0c;安装步骤&#xff1a; 以管理员身份启动ideaIU-2021.3.1修改安装路径为&#xff1a;D:\Program Files\JetBrains\IntelliJ IDEA 2021.3.1勾选【创建桌面快捷方式】&#xff08;可选&#xff09;、【打开文件夹作为项目】&…
阅读更多...
MySQL入门手册

MySQL入门手册

MySQL入门手册&#xff1a;从零开始掌握数据库管理 &#x1f4d6; 一、MySQL是什么&#xff1f; MySQL 是一个开源的关系型数据库管理系统&#xff08;RDBMS&#xff09;&#xff0c;由瑞典MySQL AB公司开发&#xff0c;现隶属于Oracle旗下。它使用**结构化查询语言&#xff…
阅读更多...
从0到1入门RabbitMQ

从0到1入门RabbitMQ

一、同步调用 优势&#xff1a;时效性强&#xff0c;等待到结果后才返回 缺点&#xff1a; 拓展性差性能下降级联失败问题 二、异步调用 优势&#xff1a; 耦合度低&#xff0c;拓展性强异步调用&#xff0c;无需等待&#xff0c;性能好故障隔离&#xff0c;下游服务故障不影响…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023