C语言中单链表的基本操作指南(增删改查)

目录
  • 1.链表概述
  • 2.链表的基本使用
    • 2.0 准备工作
    • 2.1 创建节点(结构体)
    • 2.2 全局定义链表头尾指针 方便调用
    • 2.3 创建链表,实现在链表中增加一个数据(尾添加)————增
    • 2.4 遍历链表 —————查
    • 2.5 查询指定的节点 (遍历 一个个找)
    • 2.6 链表清空——————全部删除
    • 2.7.在指定位置插入节点 ————在指定位置增
    • 2.8尾删除————删
    • 2.9 删除头——————删
    • 2.10 删除指定节点
  • 3. 测试主程序
  • 总结

1.链表概述

链表是一种常见的数据结构。它与常见的数组是不同的,使用数组时先要指定数组包含元素的个数,即为数组的长度,但是如果向这个数组中加入的元素超过了数组的大小时,便不能将内容全部保存。

链表这种存储方式,其元素个数是不受限定的,当进行添加元素的时候存储的个数就会随之改变。

  链表一般有两种形式,有空头链表和无空头链表。

在链表中有一个头指针变量,这个指针变量保存一个地址,通过这个地址来找到这个链表,头指针节点指向第一个节点,在链表中每个节点包含两个部分:数据部分和指针部分。虽然结构体不能含有与本身类型相同的结构,但是可以含有之相同类型结构的指针,这种定义是链表的基础,链表中每一项都包含在何处能找到下一项的信息。而最后一个节点的指针指向必须为空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");
	}

*/

}

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

总结

到此这篇关于C语言中单链表的增删改查基本操作的文章就介绍到这了,更多相关C语言单链表增删改查操作内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C语言之单链表的插入、删除与查找

    单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素.要实现对单链表中节点的插入.删除与查找的功能,就要先进行的单链表的初始化.创建和遍历,进而实现各功能,以下是对单链表节点的插入.删除.查找功能的具体实现: #include<stdio.h> #include<stdlib.h> #include<string.h> typedef int ElemType; /** *链表通用类型 *ElemType 代表自定义的数据类型 *struct

  • C语言中单链表的基本操作指南(增删改查)

    目录 1.链表概述 2.链表的基本使用 2.0 准备工作 2.1 创建节点(结构体) 2.2 全局定义链表头尾指针 方便调用 2.3 创建链表,实现在链表中增加一个数据(尾添加)----增 2.4 遍历链表 -----查 2.5 查询指定的节点 (遍历 一个个找) 2.6 链表清空------全部删除 2.7.在指定位置插入节点 ----在指定位置增 2.8尾删除----删 2.9 删除头------删 2.10 删除指定节点 3. 测试主程序 总结 1.链表概述 链表是一种常见的数据结构.它与

  • C语言数据结构之单链表与双链表的增删改查操作实现

    目录 前言 单链表的增删改查 定义结构体以及初始化 增加结点 删除结点 查找修改结点 移除结点 最终效果 双链表的基本操作 初始化建表 遍历双链表 指定位置插入结点 指定位置删除结点 查找结点位置 最终效果 结语 前言 上篇博客分享了创建链表传入二级指针的细节,那么今天就分享几个c语言课程实践设计吧.这些程序设计搞懂了的话相当于链表的基础知识牢牢掌握了,那么再应对复杂的链表类的题也就能慢慢钻研了.学习是一个积累的过程,想要游刃有余就得勤学苦练! 单链表的增删改查 (1)项目需求 构造带有头结点的

  • 详解Go语言中单链表的使用

    目录 链表 单链表结构 创建节点 遍历链表 头插法 尾插法 遍历方法 链表长度 链表转数组 数组转链表 链表 一种物理存储单元上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的.链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成.每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域.使用链表结构可以避免在使用数组时需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理.但是链表失去

  • C语言中单链表(不带头结点)基本操作的实现详解

    目录 一.单链表的概念 二.单链表的基本操作 1.创建单个结点 2.创建具有n个结点的链表 3.打印单链表 4.尾插 5.尾删 6.头插 7.头删 8.查找某个结点 9.在某个结点后面插入 10.在某个结点前面插入 11.删除某个位置后面的结点 12.删除某个结点 13.销毁单链表 三.测试代码 通过对顺序表的学习,我们可以发现顺序表有以下几点缺陷: 1.空间不够时需要扩容,扩容尤其是用realloc进行异地扩容时,是有一定代价的,其次还可能存在一定空间浪费. 2.头部或者中间插入删除,需要挪动

  • Java描述数据结构学习之链表的增删改查详解

    前言 链表是一种常见的基础数据结构,它是一种线性表,但在内存中它并不是顺序存储的,它是以链式进行存储的,每一个节点里存放的是下一个节点的"指针".在Java中的数据分为引用数据类型和基础数据类型,在Java中不存在指针的概念,但是对于链表而言的指针,指的就是引用数据类型的地址. 链表和数组都是线性的数据结构,对于数组而言其长度是固定的,由于在内存中其是连续的,因此更适合做查找与遍历,而链表在内存中是并不是顺序存储的,但是由于其是通过"指针"构成的,因此在插入.删除时

  • C语言数据结构顺序表中的增删改(头插头删)教程示例详解

    目录 头插操作 头删操作 小结 头插操作 继上一章内容(C语言数据结构顺序表中的增删改教程示例详解),继续讲讲顺序表的基础操作. 和尾插不一样,尾插出手阔绰直接的开空间,咱头插能开吗?好像没听说过哪个接口可以在数据前面开一片空间吧,那我们思路就只有一个了——挪数据.那应该从第一位开始挪吗?注意,这和 memcpy 函数机制是一样的,并不意味着后面数据一起挪动,也不会彼此独立,而是相互影响,挪动的数据会对后面数据进行覆盖. 那我们的逻辑就应该是从后往前挪,那我们就直接定一个下标,指向这段空间的最后

  • java实现单链表增删改查的实例代码详解

    package 数据结构算法.链表; /* *定义节点 * 链表由节点构成 */ public class Node<E> { private E e; //数据data private Node<E> next; //指向下一个节点 public Node() { } public Node(E e) { this.e = e; } public Node<E> getNext() { return next; } public void setNext(Node&l

  • Java 单链表数据结构的增删改查教程

    我就废话不多说了,大家还是直接看代码吧~ package 链表; /** * *1)单链表的插入.删除.查找操作: * 2)链表中存储的是int类型的数据: **/ public class SinglyLinkedList { private Node head = null; //查找操作 public Node findByValue(int value){ Node p = head; //从链表头部开始查找 while(p.next != null && p.data != va

  • Java如何实现单链表的增删改查

    一.新建学生节点类 Stu_Node节点包含: 学号:int num; 姓名:String name; 性别:String gender; 下一个节点:Stu_Node next; 为了便于打印节点内容需要重写toString方法 class Stu_Node{ int num; String name; String gender; Stu_Node next; @Override public String toString() { return "Stu_Node{" + &qu

  • Java实现单链表SingleLinkedList增删改查及反转 逆序等

    节点类 可以根据需要,对节点属性进行修改.注意重写toString()方法,以便后续的输出操作. //节点类 class Node { public int id; public String name; public Node next; public Node(int id, String name) { this.id = id; this.name = name; } @Override public String toString() { return "Node{" + &

随机推荐