C语言单链表的基本操作总结(增删改查)「建议收藏」

C语言单链表的基本操作总结(增删改查)「建议收藏」1.链表概述  链表是一种常见的数据结构。它与常见的数组是不同的,使用数组时先要指定数组包含元素的个数,即为数组的长度,但是如果向这个数组中加入的元素超过了数组的大小时,便不能将内容全部保存。  链表这种存储方式,其元素个数是不受限定的,当进行添加元素的时候存储的个数就会随之改变。  链表一般有两种形式,有空头链表和无空头链表。  在链表中有一个头指针变量,这个指针变量保存一个地址,…

大家好,又见面了,我是你们的朋友全栈君。

1.链表概述

  链表是一种常见的数据结构。它与常见的数组是不同的,使用数组时先要指定数组包含元素的个数,即为数组的长度,但是如果向这个数组中加入的元素超过了数组的大小时,便不能将内容全部保存。
  链表这种存储方式,其元素个数是不受限定的,当进行添加元素的时候存储的个数就会随之改变。
图0

图1
  链表一般有两种形式,有空头链表和无空头链表。
图2
  在链表中有一个头指针变量,这个指针变量保存一个地址,通过这个地址来找到这个链表,头指针节点指向第一个节点,在链表中每个节点包含两个部分:数据部分和指针部分。虽然结构体不能含有与本身类型相同的结构,但是可以含有之相同类型结构的指针,这种定义是链表的基础,链表中每一项都包含在何处能找到下一项的信息。而最后一个节点的指针指向必须为空NULL,从链表的原理来看不用担心链表的长度会超出范围这种问题。

2.链表的基本使用

2.0 准备工作

  使用链表时,首先应包含一些基本的头文件,因为涉及到内存的操作和字符串的操作。

#include "stdio.h"				
#include "stdlib.h"				//提供malloc()和free()
#include "string.h"				//提供strcpy()等

malloc函数
其函数原型如下:

  • void *malloc(unsigned int size);

这个函数返回的是个void类型指针,所以在使用时应注意强制类型转换成需要的指针类型。
free函数
其函数原型如下:

  • void free(void *p);

这个函数是用来释放指针p作指向的内存区。

2.1 创建节点(结构体)

struct Node
{
	int a;				//数据域
	struct Node* next;	//指针域(指向节点的指针)
};

2.2 全局定义链表头尾指针 方便调用

struct Node* head= NULL;
struct Node* end = NULL;

2.3 创建链表,实现在链表中增加一个数据(尾添加)————增

void AddListTill(int a )
{
		//创建一个节点
		struct Node* temp=(struct Node*)malloc(sizeof(struct Node));		//此处注意强制类型转换

		//节点数据进行赋值
		temp->a=a;
		temp->next=NULL;		
		
		//连接分两种情况1.一个节点都没有2.已经有节点了,添加到尾巴上
		if(NULL==head)
		{	

			head=temp;
		//	end=temp;
		}
		else
		{
		end->next=temp;
	//	end=temp;			//尾结点应该始终指向最后一个
		}
		end=temp;			//尾结点应该始终指向最后一个
}

AddListTill函数的功能是尾添加的方式在链表的尾部增加一个节点,其中输入的参数是这个节点的数据。首先创建一个节点并申请一个节点的内存,之后对传入节点的数据进行赋值,注意尾添加的新节点的指针应指向空;此时分两种情况,1是链表中一个节点都没有,那么这个节点既是头结点也是尾结点;2是已经有节点,那么新添加的节点将成为最后一个节点,而之前的节点因为成为了倒数第二个节点了所以它的指针应该指向新添加的节点,之后全局变量尾结点应该指向现在的节点(注意操作的先后顺序不能变)。

2.4 遍历链表 —————查

void ScanList()
{
	struct Node *temp =head;		//定义一个临时变量来指向头
	while (temp !=NULL)
	{
		printf("%d\n",temp->a);
		temp = temp->next;		//temp指向下一个的地址 即实现++操作
	}

}

ScanList函数的功能是遍历这个链表,首先定义一个用于遍历的临时指针,用while循环实现遍历输出等操作。

2.5 查询指定的节点 (遍历 一个个找)

struct Node* FindNode(int a )
{
	struct Node *temp =head;
	while(temp !=NULL)
	{
	if(a == temp->a)
	{
		return temp;
	}
	temp = temp->next;
	}
	//没找到
		return NULL;
} 

FindNode函数的功能仍然是遍历链表,只不过会对每个节点中的数据进行一一判断,若找到则返回该节点,若没找到则返回NULL。

2.6 链表清空——————全部删除

void FreeList()
{
	//一个一个NULL
	struct Node *temp =head;		//定义一个临时变量来指向头
	while (temp !=NULL)
	{
	//	printf("%d\n",temp->a);
		struct Node* pt =temp;
		temp = temp->next;		//temp指向下一个的地址 即实现++操作
		free(pt);					//释放当前
	}
	//头尾清空	不然下次的头就接着0x10
	head =NULL;
	end =NULL;
}

FreeList函数仍是采用遍历的方式一个一个的将节点内存释放,最后实现全部删除的效果,但是要注意在最后应该讲头尾节点至NULL否则下次的链表将会接着这次的头尾。

2.7.在指定位置插入节点 ————在指定位置增

void AddListRand(int index,int a)
{	

    if (NULL==head)
	{
		printf("链表没有节点\n");
		return;
	}	
    struct Node* pt =FindNode(index);
	if(NULL==pt)    //没有此节点
	{
		printf("没有指定节点\n");
		return;
	}
    //有此节点
    //创建临时节点,申请内存
	struct Node* temp =(struct Node *)malloc(sizeof(struct Node));
	//节点成员进行赋值
	temp->a=a;
	temp->next=NULL;
	//连接到链表上 1.找到的节点在尾部 2.找到的节点在中间 
	if (pt == end)
	{
	//尾巴的下一个指向新插入的节点
	end->next=temp;
	//新的尾巴
	end=temp;
	}else
	{
	// 先连后面 (先将要插入的节点指针指向原来找到节点的下一个)
	temp->next=pt->next;
	//后连前面
	pt->next=temp;
	}

}

首先要知道在指定节点插入的过程就像手拉手得人在一条线,这时来了一个新人,他要求站在甲之后,首先要找到甲的位置,如果链表为空或者没有甲则无法插入,如果链表不为空并且甲在这个链表中,则还要看甲是在链表中间还是甲就在最后的尾巴上,如果在尾巴上则新插入的即为尾巴如图1,若在甲乙之间则需要先连上后面乙再连上前面的甲,如图2。
在这里插入图片描述
在这里插入图片描述

2.8尾删除————删


void DeleteListTail()
{ 
	if (NULL == end)
	{
		printf("链表为空,无需删除\n");
		return;
	}
	//链表不为空 
	//链表有一个节点
	 if (head==end)
	 {
		 free(head);
		 head=NULL;
		 end=NULL; 
	 }
	 else
	 {
		//找到尾巴前一个节点
		 struct Node* temp =head;
		 while (temp->next!=end)
		 {
			 temp = temp->next;
		 }
		 //找到了,删尾巴
		//释放尾巴
		 free(end);
		 //尾巴迁移
		 end=temp;
		 //尾巴指针为NULL
		 end->next=NULL;
	 }

}

尾删除的过程和前面一样首先应判断这个链表是不是为空或者只有一个节点,若只有一个节点则直接置NULL,若不为空,则先通过遍历找到倒数第二个节点,安徽将最后一个节点释放内存,再讲倒数第二个节点设置为end,然后将它的指针指向NULL。

2.9 删除头——————删

void DeleteListHead()
{	//记住旧头
	struct Node* temp=head;
	//链表检测 
	if (NULL==head)
	{
			printf("链表为空\n");
			return;
	}

	head=head->next;//头的第二个节点变成新的头
	free(temp);

}

先定义一个临时变量指向旧的头,将头的第二个记为新的头指针head,之后将旧的头释放

2.10 删除指定节点

void DeleteListRand(int a)
{

	//链表判断 是不是没有东西
	if(NULL==head)
	{
	printf("链表没东西\n");
	return;
	}
    //链表有东西,找这个节点
	struct Node* temp =FindNode(a);
	if(NULL==temp)
	{
	printf("查无此点\n");
	return;
	}
	//找到了,且只有一个节点
	if(head==end)
	{
	free(head);
	head=NULL;
	end=NULL;
	}
	else if(head->next==end) //有两个节点
	{
	//看是删除头还是删除尾
	if(end==temp)
		{	DeleteListTail(); }
	else if(temp==head)
		{	DeleteListHead(); }	
	}
	else//多个节点
	{
		//看是删除头还是删除尾
		if(end==temp)
			DeleteListTail();
		else if(temp==head)
			DeleteListHead();	
		else	//删除中间某个节点
		{	//找要删除temp前一个,遍历
			struct Node*pt =head;
			while(pt->next!=temp)
			{
			pt=pt->next;
			}
			//找到了
			//让前一个直接连接后一个 跳过指定的即可
			 pt->next=temp->next;
			 free(temp);
		
		}
	}
	

}

情况与前面增加类似不再赘述,具体见图
在这里插入图片描述

3. 测试主程序

下面是测试用的主程序,主要实现了链表的增删查改等基本操作。

void main ()
{	
	struct Node *pFind ;
	//创建5个节点
	for(i=0;i<6;i++)
	AddListTill(i);
	
//	AddListRand(4,14);		//在指定位置4增加节点14
//	DeleteListTail();		//删除一个尾结点
	DeleteListRand(4);		//删除4节点
	ScanList();				//便利输出链表
	FreeList();				//删除链表
/*	pFind = FindNode(5);	//查找5节点

	if (pFind !=  NULL)
	{
		printf("找到%d\n",pFind->a);	//找到节点并且输出该节点数据
	}
	else
	{
		printf("No Find!\n");
	}

*/

}

有关无空头的单链表的基本操作就总结到这里,当然还有双链表等更复杂的数据结构,以及遍历和查找的优化算法也有待进一步探索与学习。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/149290.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • Sharepoint MasterPage页里的31个ContentPlaceHolder占位符[通俗易懂]

    Sharepoint MasterPage页里的31个ContentPlaceHolder占位符[通俗易懂]自定义SharepointMasterPage页,共有31个ContentPlaceHolder占位符,一个也不能少因为在应用到网站或网页时,网站或网页要向MasterPage页里对应的ContentPlaceHolder里填入内容,若有的ContentPlaceHolder不需要则可以把它隐藏掉而不要将其删除。<%@Masterlanguage=”C#”%…

  • C语言中什么是常量表达式_c语言整型表达式

    C语言中什么是常量表达式_c语言整型表达式常量表达式c语言,整型表达式和常量表达式中都没有变量参与吧?完整问题:好评回答:表达式没有变量参与?不是很清楚这个问题的定义,只是知道(ab)这种表达式下a和b都可以是变量Java编译器对于String常量表达式的优化是什么呢?完整问题:Java编译器对于String常量表达式的优化是什么呢?好评回答:首先把问题摆出来,先看这个代码Stringa=”ab”;Stringb=”a”…

  • python把局部变量赋值给全局变量_局部变量不赋初值

    python把局部变量赋值给全局变量_局部变量不赋初值理解的都没问题。但我想聊聊出现这种情况的原因。在讲原因之前,需要先知道python中变量的搜索顺序,这个顺序是LGB(不考虑闭包情况)即local本地,global全局,builtin内建。比如:a=1deftest():a=3print(a)test()函数内声明了局部变量a,在打印中使用,在本地环境中命中,因此使用的是3。也许你会问这个知识点我早就知道了,这和本问题有什么关…

    2022年10月24日
  • git查看,修改用户名和邮箱「建议收藏」

    git查看,修改用户名和邮箱「建议收藏」1.gitconfig命令查看用户名,邮箱gitconfiguser.namegitconfiguser.email2.gitconfig命令修改自己的用户名和邮箱//仅对当前仓库有效gitconfig–localuser.email”你的名字”gitconfig–localuser.email”你的邮箱”//对当前用户的所有仓库有效gitconfig–globaluser.email”你的名字”gitconfig–global

  • 实现经常使用的配置文件/初始化文件读取的一个C程序[通俗易懂]

    实现经常使用的配置文件/初始化文件读取的一个C程序

  • 为猪脸识别而进行自己数据集的构建、训练「建议收藏」

    为猪脸识别而进行自己数据集的构建、训练「建议收藏」在实际过程中走了弯路,特地进行说明记录,以备今后参考。思路是先构建VOC2007格式的猪脸数据集,在转换成tf格式,然后利用tf的objectdetectionapi进行训练。原因是把2种构建方式都熟悉一遍,并把所有流程过一遍。1、构架VOC2007格式的猪脸数据集前提:在某个目录下建立如下关系的子目录。                               

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号