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 1
	freeList2(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个位置的值为1

	freeList2(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 1
	freeList2(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个位置的值为1

	freeList2(L3);

    return 0;
}

12. 运行截图

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

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

相关文章

IDEA 基础配置: maven配置 | 服务窗口配置

IDEA 基础配置: maven配置 | 服务窗口配置

文章目录 IDEA版本与MAVEN版本对应关系maven配置镜像源插件idea打开服务工具窗口IDEA中的一些常见问题及其解决方案IDEA版本与MAVEN版本对应关系 查找发布时间在IDEA版本之前的dea2021可以使用maven3.8以及以前的版本 比如我是idea2021.2.2 ,需要将 maven 退到 apache-maven-3.…
阅读更多...
【单片机】ARM 处理器简介

【单片机】ARM 处理器简介

ARM 公司简介 ARM&#xff08;Advanced RISC Machine&#xff09; 是英国 ARM 公司&#xff08;原 Acorn RISC Machine&#xff09; 开发的一种精简指令集&#xff08;RISC&#xff09; 处理器架构。ARM 处理器因其低功耗、高性能、广泛适用性&#xff0c;成为嵌入式系统、移动…
阅读更多...
DeepSeek+知识库+鸿蒙，助力鸿蒙高效开发

DeepSeek+知识库+鸿蒙，助力鸿蒙高效开发

不知道你们发现没有&#xff0c;就是鸿蒙开发官网&#xff0c;文档也太多太多了&#xff0c;对于新手来说确实头疼&#xff0c;开发者大多是极客&#xff0c;程序的目的是让世界更高效&#xff01;看文档&#xff0c;挺头疼的&#xff0c;毕竟都是理科生。 遇到问题不要慌&…
阅读更多...
第十五届蓝桥杯省赛电子类单片机学习过程记录（客观题）

第十五届蓝桥杯省赛电子类单片机学习过程记录（客观题）

客观试题： 01．典型的BUCK电源电路包含哪些关键器件（ABCD） A. 电容 B. 二极管 C. 电感 D. MOSFET 解析： 典型的 BUCK 电源电路是一种降压型的直流-直流转换电路，它包含以下关键器件： A.电容：电容在电路中起到滤波的作用。输入电容用于平滑输入电压的波动，减少电源噪声对…
阅读更多...
uniapp uniCloud引发的血案（switchTab: Missing required args: “url“）！！！！！！！！！！

uniapp uniCloud引发的血案（switchTab: Missing required args: “url“）！！！！！！！！！！

此文章懒得排版了&#xff0c;为了找出这个bug, 星期六的晚上我从9点查到0点多&#xff0c;此时我心中一万个草泥马在崩腾&#xff0c;超级想骂人&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01; uniCloud 不想…
阅读更多...
源码：用Python进行电影数据分析实战指南

源码：用Python进行电影数据分析实战指南

源码&#xff1a;用Python进行电影数据分析实战指南 原创 IT小本本 IT小本本 2025年03月03日 22:28 北京 接上一篇文章&#xff1a;用Python进行电影数据分析实战指南 1、首先复制csv内容到csv文件中 2、接着创建.py文件复制源码内容 3、运行代码&#xff0c;就可以看到数据…
阅读更多...
GHCTF2025--Web

GHCTF2025--Web

upload?SSTI! import os import refrom flask import Flask, request, jsonify,render_template_string,send_from_directory, abort,redirect from werkzeug.utils import secure_filename import os from werkzeug.utils import secure_filenameapp Flask(__name__)# 配置…
阅读更多...
Unity Shader编程】之基础纹理

Unity Shader编程】之基础纹理

一&#xff0c;单张纹理 好的&#xff0c;用户想学习Unity Shader中的单张纹理章节。我需要根据提供的搜索结果来整理相关内容。首先&#xff0c;查看搜索结果中的相关部分&#xff0c;特别是‌、‌、‌、‌、‌这几条&#xff0c;因为它们提到了基础纹理、单张纹理的实现方法…
阅读更多...
SpringBoot使用注解扫描注册Java Web三大组件

SpringBoot使用注解扫描注册Java Web三大组件

使用注解扫描和注册Java Web三大组件&#xff08;Servlet、Filter、Listener&#xff09;非常方便。 1. Servlet 注册 Servlet 是 Java Web 开发的基础组件&#xff0c;用于处理客户端&#xff08;通常是浏览器&#xff09;发送的 HTTP 请求并生成响应。 Controller是基于 Ser…
阅读更多...
STM32F4 UDP组播通信：填一填ST官方HAL库的坑

STM32F4 UDP组播通信：填一填ST官方HAL库的坑

先说写作本文的原因&#xff0c;由于开项目开发中需要用到UDP组播接收的功能&#xff0c;但是ST官方没有提供合适的参考&#xff0c;使用STM32CubeMX生成的代码也是不能直接使用的&#xff0c;而我在网上找了一大圈&#xff0c;也没有一个能够直接解决的方案&#xff0c;deepse…
阅读更多...
JVM - 3.垃圾回收

JVM - 3.垃圾回收

1.垃圾收集的经典问题 1.哪些内存需要回收2.什么时候回收3.如何回收1.你知道哪几种垃圾回收器&#xff0c;各自的优缺点&#xff0c;重点讲一下cms和g12.JVM GC算法有哪些&#xff0c;目前的JDK版本采用什么回收算法3.G1回收器的回收过程 1.Java中垃圾的定义&#xff08;Garbag…
阅读更多...
重构谷粒商城09:人人开源框架的快速入门

重构谷粒商城09:人人开源框架的快速入门

谷粒商城09——人人开源框架的快速入门 前言&#xff1a;这个系列将使用最前沿的cursor作为辅助编程工具&#xff0c;来快速开发一些基础的编程项目。目的是为了在真实项目中&#xff0c;帮助初级程序员快速进阶&#xff0c;以最快的速度&#xff0c;效率&#xff0c;快速进阶…
阅读更多...
css实现元素垂直居中显示的7种方式

css实现元素垂直居中显示的7种方式

文章目录 * [【一】知道居中元素的宽高](https://blog.csdn.net/weixin_41305441/article/details/89886846#_1) [absolute 负margin](https://blog.csdn.net/weixin_41305441/article/details/89886846#absolute__margin_2) [absolute margin auto](https://blog.csdn.net…
阅读更多...
用Python写一个算24点的小程序

用Python写一个算24点的小程序

一、运行界面 二、显示答案——递归介绍 工作流程&#xff1a; 1. 基本情况&#xff1a;函数首先检查输入的数字列表 nums 的长度。如果列表中只剩下一个数字&#xff0c;它会判断这个数字是否接近 24&#xff08;使用 abs(nums[0] - 24) < 1e-10 来处理浮点数精度问题&…
阅读更多...
【长安大学】苹果手机/平板自动连接认证CHD-WIFI脚本(快捷指令)

【长安大学】苹果手机/平板自动连接认证CHD-WIFI脚本(快捷指令)

背景&#xff1a; 已经用这个脚本的记得设置Wifi时候&#xff0c;关闭“自动登录” 前几天实在忍受不了CHD-WIFI动不动就断开&#xff0c;一天要重新连接&#xff0c;点登陆好几次。试了下在网上搜有没有CHD-WIFI的自动连接WIFI自动认证脚本&#xff0c;那样我就可以解放双手&…
阅读更多...
双击PPT文件界面灰色不可用，需要再次打开该PPT文件才能正常打开

双击PPT文件界面灰色不可用，需要再次打开该PPT文件才能正常打开

双击PPT文件界面灰色不可用&#xff0c;需要再次打开该PPT文件才能正常打开 1. 软件环境⚙️2. 问题描述&#x1f50d;3. 解决方法&#x1f421;解决步骤 4. 结果预览&#x1f914; 1. 软件环境⚙️ Windows10 或 Windows11 专业版64位&#xff0c;安装MotionGo软件&#xff08…
阅读更多...
蓝桥杯[每日两题] 真题：好数 神奇闹钟 (java版)

蓝桥杯[每日两题] 真题：好数 神奇闹钟 (java版)

题目一&#xff1a;好数 题目描述 一个整数如果按从低位到高位的顺序&#xff0c;奇数位&#xff08;个位、百位、万位 &#xff09;上的数字是奇数&#xff0c;偶数位&#xff08;十位、千位、十万位 &#xff09;上的数字是偶数&#xff0c;我们就称之为“好数”。给定…
阅读更多...
蓝桥杯刷题周计划（第二周）

蓝桥杯刷题周计划（第二周）

目录 前言题目一题目代码题解分析 题目二题目代码题解分析 题目三题目代码题解分析 题目四题目代码题解分析 题目五题目代码题解分析 题目六题目代码题解分析 题目七题目代码题解分析 题目八题目题解分析 题目九题目代码题解分析 题目十题目代码题解分析 题目十一题目代码题解分…
阅读更多...
ThinkPHP框架

ThinkPHP框架

在电脑C磁盘中安装composer 命令 在电脑的D盘中创建cd文件夹 切换磁盘 创建tp框架 创建一个aa的网站&#xff0c;更换路径到上一步下载的tp框架路径 在管理中修改路径 下载压缩包public和view 将前面代码中的public和view文件替换 在PHPStom 中打开文件 运行指定路径 修改demo…
阅读更多...
Spring学习笔记：工厂模式与反射机制实现解耦

Spring学习笔记：工厂模式与反射机制实现解耦

1.什么是Spring? spring是一个开源轻量级的java开发应用框架&#xff0c;可以简化企业级应用开发 轻量级 1.轻量级(对于运行环境没有额外要求) 2.代码移植性高(不需要实现额外接口) JavaEE的解决方案 Spring更像是一种解决方案&#xff0c;对于控制层&#xff0c;它有Spring…
阅读更多...
最新文章

Copyright @ 2022~2023