程序员经验分享-hwhale

单链表的增删改查操作详解之C语言版

2023-11-12

单链表在应用中经常用到增加新结点、删除结点、修改结点、查找结点等操作，本文针对上述基本操作做了简单汇总，并给出了详细的算法。

一、在单链表中增加结点

在链表中增加新结点是经常要用到的操作，增加新结点大致可以分为在链表末尾增加、在链表头增加、在中间某个位置增加等三种情形。增加新结点也称为插入新结点。链表结点的接头体如下：

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

1.在链表尾插入新结点
假设有单链表如下：
在这里插入图片描述
增加元素为3的新结点，得到如下新链表：
在这里插入图片描述
算法流程：
1）生成新结点s存储元素3
2）让p指向表头h
3）让p依次后移到链表尾
4）将s链接到p之后
算法：

s = ( LNode* )malloc( sizeof( LNode ) ); 
s->data = 3;	 
s->next = NULL; 
p = h;
while( p->next != NULL )
{
	p = p->next;
	p->next = s;
}

2.在链表头插入新结点
在表头插入新结点比较简单，生成新结点之后挂在表头之后即可。
在这里插入图片描述
算法为：

s = ( LNode* )malloc( sizeof( LNode ) ); 
s->data = 3;	 
s->next = h->next; //此部关键，先把s和结点1链接上。
h->next = s;

3.在链表中间某个位置插入新结点
已有链表如下:
在这里插入图片描述
想在元素为4的结点之前插入新结点s，插入过程为：
1）生成新结点s；
2）引入两个临时指针p和q，p通过遍历指向4的结点，q作为p的直接前驱
3）把新结点s插入到q和p之间
在这里插入图片描述
算法实现（只考虑了插值成功未考虑失败）：

key = 4;
s = ( LNode* )malloc( sizeof( LNode ) ); 
s->data = 3;
q = h;
p = q->next;
while( p->data != key )
{
	q = p;
	p = p->next;
}
q->next = s;
s->next = p;

二、在单链表中删除结点

1.删除一个结点
在这里插入图片描述
删除元素为3的结点，其算法如下：

key = 3;
q = h;
p = q->next;
while( p != NULL && p->data != key )//当p结点的值不是key，则q和p平行后移，
{
	q = p;           //q先指向p，之后p再后移
	p = p->next;
}
if( p == NULL )
	输出链表中无目标结点
else
	q->next = p->next;
free( p );

2.删除与某个元素相同的全部结点
在这里插入图片描述
删除链表中元素为3的全部结点，则算法为：

	key = 3;
	q = head;
	p = head->next;
	//定位
	while( p != NULL)
	{
		if( p->data == key )
		{
			q->next = p->next;
			free(p);
			p = q->next;
		}
		else
		{
			q = p;
			p = p->next;
		}
	}

3.删除单链表中所有相同的结点
删除单链表中所有值重复的结点，使得所有结点的值都不相同。
算法思路：从单链表的第一个结点开始，对每个结点进行检查：检查链表中该结点的所有后继结点，只要有值和该结点的值相同，则删除之；然后检查下一个结点，直到所有的结点都检查。
算法如下：

	ptr = head->next; 
	while( ptr!= NULL)    //检查链表中所有结点 
	{
		q = ptr;     
		p = ptr->next;
		while ( p != NULL )  //检查结点q的所有后继结点p
		{
			if( p->data == ptr->data )
			{
				q->next = p->next;  
				free(p);  
				p  = q->next;              
			}
			else   
            {
				q = p;  
				p = p->next;           
			}
		}//执行完一轮扫描(可以删除一个相同的值的所有结点)，开始下一轮 
		ptr = ptr->next ;
	}

三、修改某个结点

修改链表中第一个值为3的结点中的值为10。算法如下：

newData = 10;
key = 3;
p = h->next;
while( p != NULL && p->data != key )
	p = p->next;
if( p == NULL )
	输出链表中无目标结点
else
	p->data = newData;
	free( p );

四、查找某个结点

在单链表中查找值为2的结点

key = 2;
p = h->next;
while( p != NULL && p->data != key )
	p = p->next;
if( p == NULL )
	输出链表中无目标结点
else
	查找成功

五、完整的测试代码

1.代码

#include"stdio.h"
#include"malloc.h"
typedef  struct  Lnode
{   
	int           data;     //数据
	struct Lnode  *next;    //指针域
}LNode;
 
LNode *CreateLinkListTail( int a[], int n );
void display( LNode *head );
int SearchNode( LNode *head, int key );
void InsertNodeHead( LNode *head, int key );
void InsertNodeTail( LNode *head, int key );
void InsertNode( LNode *head, int key, int e );
void DeleteNode( LNode *head, int key );
void DeleteSameNode( LNode  *head, int key );
void DeleteAllSameNode( LNode  *head );
void ModifyNode( LNode *head, int key, int newKey );

int main()
{
	int a[] = { 1, 6, 4, 3, 5, 6, 1, 6 };
	int n = 8;
	LNode *head = CreateLinkListTail( a, n );
	display( head );
	int key = 5; 
	InsertNodeHead( head, key );
	display( head );
	InsertNodeTail( head, key );
	display( head );
	int e = 4;
	InsertNode( head, key, e );
	display( head );
	DeleteNode( head, key );
	display( head );
	DeleteSameNode( head, key );
	display( head );
	DeleteAllSameNode( head );
	display( head );

	int loc = SearchNode( head, key );
	if( loc == 0 )
	{
		printf( " 查找 %d 失败！！！\n", key );
	}
	else
	{
		printf( " 查找 %d 成功\n", key ); 
	}
	
	key = 3;
	int newKey = 10;
	ModifyNode( head, key, newKey );
	display( head );
	return 0;
}
LNode *CreateLinkListTail( int a[], int n )
{
	int i;
	LNode *head, *p, *s;
	head = (LNode*)malloc(sizeof(LNode));
	head->next = NULL;
	p = head;
	for( i = 0; i < n; i++ )
	{
		s = (LNode*)malloc(sizeof(LNode));
		s->data = a[i];
		s->next = NULL;
		p->next = s;
		p = s;
	} 
	return head;
}

void display( LNode *head )
{
	LNode *p;
	p = head->next;
	printf( " data in linklist: " );
	while( p != NULL )
	{
		printf( "%5d", p->data );
		p = p->next;
	}
	printf( "\n" );
}

int SearchNode( LNode *head, int key )
{
	int loc = 0;
	LNode  *p;
	p = head->next;
	while( p != NULL )
	{
		loc++;
		if( p->data  == key )
		{
			break;
		}
		p = p->next;
	}
	if( p == NULL )
		loc = 0;
	return loc;
} 

void ModifyNode( LNode *head, int key, int newKey )
{
	LNode  *p;
	p = head->next;
	while( p != NULL && p->data != key )
	{
		p = p->next;
	}
	if( p == NULL )
		printf( "%d 不在链表中\n", key );
	else
	{
		p->data = newKey;
	}
} 

void InsertNodeHead( LNode *head, int key )
{
	LNode *s = (LNode*)malloc(sizeof(LNode));
	s->data = key;
	s->next = head->next;
	head->next = s;
}
void InsertNodeTail( LNode *head, int key )
{
	LNode *p, *s;
	s = (LNode*)malloc(sizeof(LNode));
	s->data = key;
	s->next = NULL;
	p = head;
	while( p->next != NULL )
	{
		p = p->next;
	}
	p->next = s;
}
void InsertNode( LNode  *head, int key, int e )
{
	LNode *p, *q, *s;
	//先定位key所在的节点
	//插入新节点
	q = head; //q是p的直接前驱节点
	p = head->next;
	while( p != NULL )
	{
		if( p->data == e )
		{
			s= ( LNode * )malloc( sizeof( LNode ) );
			s->data = key;
			s->next = p->next;
			p->next = s;
			break;
		}
		q = p;
		p = p->next;
	}
	if( p == NULL )
	{
		s= ( LNode * )malloc( sizeof( LNode ) );
		s->data = e;
		s->next = NULL;
		q->next = s;
	}	
}

void DeleteNode( LNode  *head, int key )
{
	LNode *p, *q;
	q = head;
	p = head->next;
	//定位
	while( p != NULL )
	{
		if( p->data == key )
		{
			q->next = p->next;
			free(p);
			break;
		}
		q = p;
		p = p->next;
	}
}
void DeleteSameNode( LNode  *head, int key )
{
	LNode *p, *q;
	q = head;
	p = head->next;
	//定位
	while( p != NULL)
	{
		if( p->data == key )
		{
			q->next = p->next;
			free(p);
			p = q->next;
		}
		else
		{
			q = p;
			p = p->next;
		}
	}
}

void  DeleteAllSameNode( LNode  *head )
{
	LNode *ptr = head->next, *q, *p; 
	while( ptr!= NULL)    //检查链表中所有结点 
	{
		q = ptr;     
		p = ptr->next;
		while ( p != NULL )  //检查结点q的所有后继结点p
		{
			if( p->data == ptr->data )
			{
				q->next = p->next;  
				free(p);  
				p  = q->next;              
			}
			else   
            {
				q = p;  
				p = p->next;           
			}
		}//执行完一轮扫描(可以删除一个相同的值的所有结点)，开始下一轮 
		ptr = ptr->next ;
	}
}

2.测试结果
在这里插入图片描述

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

算法与数据结构

c语言

链表

数据结构

单链表的增删改查操作详解之C语言版 的相关文章

  • 富文本编辑器的使用方法

    富文本编辑器又称Rich Text Editor 简称RTE 它不同与文本编辑器 程序员可以到网上下载免费的富文本编辑器嵌于自己设计的网站或者程序里 方便用户编辑文章或者信息 主要用于发新闻类似的东西 它有着和word文档还有网上发论坛插图

  • ssd测试mAP的时候出现tensorflow版本问题,问题 _variable_v2_call() got an unexpected keyword argument ‘collections’

    这个问题是Tensorflow 版本太高导致的 我原来使用的 1 13 1 的版本不行 换成了 1 10 1就可以了

  • 2023年新能源汽车行业研究报告

    第一章 行业概况 新能源汽车 是指采用新型动力系统 完全或者主要依靠新型能源驱动的汽车 包括纯电动汽车 插电式混合动力汽车 增程式混合动力汽车和燃料电池汽车等 国际上 混合动力汽车 含中混 强混 插电式混动 汽车 天然气汽车 纯电动汽车和燃

  • 《一周搞定模电》—基本放大电路

    文章目录 TOC 文章目录 一 三极管放大电路 1 饱和失真和截至失真 2 静态工作点 二 放大电路改进 分压偏置电路 一 三极管放大电路 下图是共发射极放大电路 R8两端的电压值与输入信号是反向关系 仿真图如下所示 1 饱和失真和截至失真

随机推荐

  • MySQL大小写敏感的解决方案

    不同的MySQL版本有不同的默认设定 具体情况需要具体分析 mysql是通过lower case table names参数来控制大小写敏感的 该参数在 mysqld 节点下 具体的含义笔者从官网截了一张图 关于lower case tab

  • 算法：链表数字相加

    算法 链表数字相加 问题 解决 问题 解决 class Solution def mergeNodes self head Optional ListNode gt Optional ListNode init re ListNode 0

  • 项目总结@Repository注解dao层接口扫描不到

    使用 Repository来注解 来注解dao层接口 运行运行项目不能扫描 应该是接触的项目比较少 第一次遇到这种情况 使用 Repository注解mapper接口发现项目运行找不到dao层的东西 我滴个神 以前用着这玩意不是挺好使的嘛

  • hashmap链表转化成红黑树的过程以及红黑树转化成链表的过程

    1 链表转红黑树的实现代码 该方法主要是将单向链表转化成双向链表 为了后面操作 比如在后面将红黑树放到数组上时 以及红黑树转成链表时简化操作 final void treeifyBin Node

  • C语言分别判断大小写英文字母，空格，数字和其他字符的个数

    输入一段字符串 分别判断小写字母 大写字母 数字 空格和其他字符各有几个 ASCII码中空格的ASCII码为32 A为65 a为97 程序代码 include

  • 世纪末的星期

    曾有邪教称1999年12月31日是世界末日 当然该谣言已经不攻自破 还有人称今后的某个世纪末的12月31日 如果是星期一则会 有趣的是 任何一个世纪末的年份的12月31日都不可能是星期一 于是 谣言制造商 又修改为星期日 1999年的12月

  • trap 信号捕获

    trap 信号捕获 命令说明 示例 产生信号 语法 选项说明 命令说明 Trap signals and other events Defines and activates handlers to be run when the shel

  • List去除空元素

    一 Collections singleton 一个用于创建只包含一个元素的不可变集合的方法 创建一个只包含一个值为null的元素的集合 list removeAll Collections singleton null list remo

  • Node.js搭建WEB服务器

    Node js搭建WEB服务器 1 安装Node和nodemon插件 2 引入http模块 3 创建服务监听端口 4 解析接口地址 5 解析get参数 6 解析post参数 1 安装Node和nodemon插件 全局安装nodemon插件

  • 超详细 Springboot 线程池用法一（自用）

    目录 前言 1 EnableAsync 和 Async 很关键 2 Thread 和 Runnable 要谨慎 3 数据类型 线程安全 要牢记 4 Configuration 和 Bean 很方便 5 ThreadPoolExecutor

  • uniapp图片裁剪插件开发整理

    工作之余 把工作中需要用的一个小工具封装成uniapp插件分享给大家 图片裁剪 使用场景 头像裁剪 对照片尺寸有特定要求的 实现思路 布局 做上下两层展示 下层展示一张亮度低一点全图 充当遮住部分 效果可以自定义比如说高斯模糊等 上层展示裁

  • 网络调试助手-Win & Linux

    网络调试助手 Win Linux 一 网络调试助手 二 Windows版 三 Linux版 参考链接 一 网络调试助手 PC桌面或嵌入式的客户端开发时常需要进行收发调试 常用的工具便是网络调试助手 支持UDP TCP客户端 服务端的模拟 二

  • [王垠系列]TeXmacs：一个真正“所见即所得”的排版系统

    TeXmacs 一个真正 所见即所得 的排版系统 好久没有推荐过自己喜欢的软件了 现在推荐一款我在美国做数学作业的私家法宝 TeXmacs 我恐怕不可能跟以前那么有闲心写个长篇的 TeXmacs 说明文档了 不过这东西如此的简单好用 所以基

  • STM32内部Flash读写问题

    STM32Flash读写之Flash调试技巧 文章目录 1 先熟悉所用MCU的Flash存储大小以及扇区地址 2 Flsah写之前为什么要先擦除 3 Flash擦除长时间占用CPU 4 实测Flash擦写占用的时间 5 Flash读写要注意

  • PTA 按等级统计学生成绩

    PTA 按等级统计学生成绩 int set grade struct student p int n int i count 0 for i 0 i

  • mysql设置update_time自动更新和create_time手动更新

    update time 设置update time 在更新时候才触发获取当前时间 关键语句 ON UPDATE CURRENT TIMESTAMP eg ALTER TABLE t emp tag CHANGE update time up

  • linux防火墙的开启、关闭、永久关闭

    防火墙是什么 我们为什么需要关闭防火墙 防火墙就是一个保护我们系统的软件服务 默认开启 但是我们在实际开发中 如果需要使用宿主机来连接虚拟机里面的redis mysql nginx tomcat等服务 需要将防火墙关闭 否则这个保护机制将不

  • SmartNews 基于 Flink 的 Iceberg 实时数据湖实践

    摘要 本文整理自 SmartNews 数据平台架构师 Apache Iceberg Contributor 戢清雨 在 Flink Forward Asia 2022 实时湖仓专场的分享 本篇内容主要分为五个部分 1 SmartNews 数

  • Edge浏览器新建标签页如何更改为指定网址？

    困扰我好久的问题 在网上找了半天 终于解决了 我就想在浏览器点加号打开新窗口时跳转到百度 便于查找 扩展 获取扩展 搜索New Tab Changer

  • 单链表的增删改查操作详解之C语言版

    单链表在应用中经常用到增加新结点 删除结点 修改结点 查找结点等操作 本文针对上述基本操作做了简单汇总 并给出了详细的算法 一 在单链表中增加结点 在链表中增加新结点是经常要用到的操作 增加新结点大致可以分为在链表末尾增加 在链表头增加 在

热门标签