链表入门:“单链表“的基本操作详解(C语言)

这篇具有很好参考价值的文章主要介绍了链表入门:“单链表“的基本操作详解(C语言)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一,了解链表

二,基本操作的实现

1.  在代码开头的预处理和声明

2.  对链表进行初始化

一个错误案例的分析:

3.  对链表进行“增”操作

(1) “头插法”在链表头结点之后插入结点

(2) “尾插法”在链表的最后一个结点后插入结点

(3) 在指定位置插入结点

3,对链表进行“删”操作

 (1) 从链表中删除第 i 个元素

 (2) 销毁单链表

4.  对链表进行“查”操作

(1) 打印链表中的元素

(2) 获取链表中元素的个数

(3) 在单链表中查找元素e的位置

 (4) 在单链表中获取 i 位置的元素

5.  对链表进行“改”操作

三,整体的实现和效果


一,了解链表

链式存储结构——借助指示元素存储地址的指针表示数据

                             元素间的逻辑关系:(逻辑相邻,物理不一定相邻)

链表是由一系列结点(链表中每一个元素称为结点)组成,每个结点包括两个部分:数据域(存储本结点的数据元素)和指针域(存储下一个结点的地址)。

由于链表在运行时可以动态生成结点,所以链表相比于数组,具有动态分配内存、方便插入和删除、节省空间等优点。

链表按照节点的连接方式可以分为单链表、双向链表和循环链表三种类型。这里我们只讨论单链表。

一些概念的了解

  • 头结点(在链表的首元结点之前附设的一个结点)是用来辅助链表操作的,它本身并不算作链表的节点,因此在统计链表长度时需要将头结点去掉。头结点的数据域通常不赋值
  • 头指针:指向第一个结点(链表有头结点的时候就是头结点)
  • 空链表:链表中无元素(有头结点)
  •  下图是一个带有头结点的单链表 

1.单链表的基本操作及应用 ①创建 ②插入 ③删除 ④查找 ⑤显示,数据结构,算法,数据结构,链表,c语言,学习,visual studio,windows

二,基本操作的实现

对数据的进行的操作基本就是“增删查改”。

1.  在代码开头的预处理和声明

#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
	int data;			//数据域
	struct node* next;	//指针域
}LinkNode;

如果你使用的是Visual Studio进行编写的代码,请在第一行添加:

#define _CRT_SECURE_NO_WARNINGS

2.  对链表进行初始化

1.单链表的基本操作及应用 ①创建 ②插入 ③删除 ④查找 ⑤显示,数据结构,算法,数据结构,链表,c语言,学习,visual studio,windows

LinkNode* InitList()
{
	//创建一个结构体指针并进行分配空间
	LinkNode* temp = (LinkNode*)malloc(sizeof(LinkNode));
    //将结构体指针的指针域赋值为NULL
	temp->next = NULL;
    //返回初始化完成的结构体指针
	return temp;
}
  •  malloc向内存申请一块连续可用的空间,开辟成功会返回指向这块空间的指针(类型为void*), 开辟失败返回NULL, 所以得判断是否开辟成功并对指向空间的指针的类型的强制转换。

 在main函数中创建指向结构体L的指针来接收已经初始化完成的链表(只有头结点)。

//创建一个指向结构体的指针来记录头结点
LinkNode* L = InitList();

一个错误案例的分析:

对下面错误的代码进行分析:

void InitList(LinkNode* pL){
    pL = (LinkNode*)malloc(sizeof(LinkNode));
    pL->next = NULL;
}
int main()
{
    LinkNode L;//创建一个结构体变量
    InitList(&L);//初始化链表
    //...
    return 0;
}

在main函数中创建了一个L结构体变量(L已经有了自己的地址),将L的地址传递给InitList()函数,InitList()函数内接收一个指向结构体变量L的指针pL。

  • 使用malloc开辟空间会返回一块空间的地址,而函数中 pL 是一个记录着 结构体变量L 地址的指针。如果把 开辟的空间地址 给到 pL ,则 pL 就指向了为malloc开辟的大小为sizeof(LinkNode)的空间的地址,此时pL不再记录的是结构体变量L的地址,后面的 pL->next = NULL;也只修改pL这个指针指向的空间的变量。当执行走出函数体后,pL这个指针就会被销毁,在main函数中,L还是未初始化。
  • 上面例子的正确修改: 把InitList函数中的 malloc开辟空间赋值给pL 的代码去掉

LinkNode* L    指向链表的某一个结点。(只能修改所指向结点中的内容)

LinkNode** L  指向记录链表地址的指针,可以修改链表。(可以改变一级指针的地址)

一级指针记录变量的地址,二级指针记录一级指针的地址。

一级指针只能修改所记录变量的内容,二级指针可以修改一级指针的内容(即一级指针的地址)。

3.  对链表进行“增”操作

(1) “头插法”在链表头结点之后插入结点

1.单链表的基本操作及应用 ①创建 ②插入 ③删除 ④查找 ⑤显示,数据结构,算法,数据结构,链表,c语言,学习,visual studio,windows

1. 从一个空表开始,重复读入数据:
2.生成新结点,将读入数据存放到新结点的数据域中3. 从最后一个结点开始,依次将各结点插入到链表的前端

void CreateLink_H()
{
	//创建一个带头结点的单链表
	LinkNode* L = (LinkNode*)malloc(sizeof(LinkNode));
	L->next = NULL;
	int n = 3, e = 0;//n为创建的新结点个数,e为结点的数据
	for (int i; i < n; i++)
	{
		//生成新结点P
		LinkNode* P = (LinkNode*)malloc(sizeof(LinkNode));
		//给新结点P的数据域赋值
		printf("请输入新结点元素e的值:\n");
		scanf("%d", &e);
		P->data = e;
		//将新结点插入表头
		P->next = L->next;
		L->next = P;
	}
}

(2) “尾插法”在链表的最后一个结点后插入结点

1.单链表的基本操作及应用 ①创建 ②插入 ③删除 ④查找 ⑤显示,数据结构,算法,数据结构,链表,c语言,学习,visual studio,windows

1.从一个空表L开始,将新结点逐个插入到链表的尾部,尾指针r指向链表的尾结点。
2.初始时,r同L均指向头结点。每读入一个数据元素则申请一个新结点,将新结点插入到尾结点后,r指向新结点。

void CreateLink_R(LinkNode* L)
{
	//创建一个带头结点的单链表
	LinkNode* L = (LinkNode*)malloc(sizeof(LinkNode));
	L->next = NULL;
	//创建一个尾指针指向头结点(空链表中的头就是尾)
	LinkNode* r = L;
	int n = 3, e = 0;//n为创建的新结点个数,e为结点的数据
	for (int i; i < n; i++)
	{
		//创建一个新结点
		LinkNode* P = (LinkNode*)malloc(sizeof(LinkNode));
		//给新结点P的数据域赋值
		printf("请输入新结点元素e的值:\n");
		scanf("%d", &e);
		P->data = e;
		//将新结点插入表尾
		P->next = NULL;
		r->next = P;
		//r指向新的尾结点
		r = P;
	}
}

(3) 在指定位置插入结点

1.单链表的基本操作及应用 ①创建 ②插入 ③删除 ④查找 ⑤显示,数据结构,算法,数据结构,链表,c语言,学习,visual studio,windows

1.单链表的基本操作及应用 ①创建 ②插入 ③删除 ④查找 ⑤显示,数据结构,算法,数据结构,链表,c语言,学习,visual studio,windows

  • 在 i 位置插入新元素, 需要找到第 i-1 个结点, 将第 i-1 个结点的指针域赋值给新结点P的指针域,然后将第 i-1 个结点的next赋值为新结点P的地址。
    int LinkInsert(LinkNode* L, int i, int e)
    {
    	//L为记录头结点的指针, i为插入位置, e为插入元素
    	LinkNode* temp = L;
    	int count = 0;		//默认长度为0
    	while (temp->next && count < i - 1)		
    	{		
    		//寻找第i个结点,并使temp指向第i-1个结点
    		temp = temp->next;
    		count++;
    	}
    	if (count < i - 1)
    	{
    		///第i个位置不存在,则进行提示并返回0
    		printf(">>>访问越界,请重试!\n");
    		return 0;
    	}
    	//在链表的第i个位置插入新结点P
    	LinkNode* P = (LinkNode*)malloc(sizeof(LinkNode));
    	P->data = e;
    	P->next = temp->next;		//将temp下一个结点给P的地址域
    	temp->next = P;				//将P的地址赋值给temp的地址域
    	return 1;					//成功插入则返回1
    }

 分析:

	int count = 0;
	while (temp->next && count < i - 1)		
	{		
		temp = temp->next;
		count++;
	}
  • temp->next 判断当前结点的下一个结点是否存在,如果不存在说明已经到达链表末尾。
  • count < i - 1 判断遍历过的结点个数是否小于 i - 1,即判断是否找到了第 i - 1 个结点。
  • 2个条件一起使用可以确保 temp 指针移动到第 i-1个结点的位置(i-1不大于表长时),并避免访问空指针导致的错误。
	if (count < i - 1)
	{
		///第i个位置不存在,则进行提示并返回0
		printf(">>>访问越界,请重试!\n");
		return 0;
	}

    在上面循环的while中已经根据 i 对count的值进行计数,count最大时等于链表长度,
    当 i-1 大于链表长度时,则无法访问到 i 结点(没有 i 这个结点). 则进行提示并返回。

·要注意的是:①结点的指针域记录着②结点的地址,所以不可以先把新结点的地址赋值给①结点(temp->next = P;)

而是先把②结点的地址赋给P的指针域,再把P的地址赋值给①结点的指针域,才能正确链接.

(P->next = temp->next; temp->next = P; )

3,对链表进行“删”操作

 (1) 从链表中删除第 i 个元素

1.单链表的基本操作及应用 ①创建 ②插入 ③删除 ④查找 ⑤显示,数据结构,算法,数据结构,链表,c语言,学习,visual studio,windows

  • 对第 i 个结点进行删除, 需要找到第 i -1 个结点, 将其指针域更改为第 i+1 个结点的地址, 然后再对第 i 个结点进行删除。
    int LinkDelect(LinkNode* L, int i) {
    	LinkNode* temp = L;
    	int count = 0;
    	while (temp->next && count < i - 1)
    	{
    		//寻找第i个结点,并使temp指向第i-1个结点
    		temp = temp->next;
    		count++;
    	}
    	if (!(temp->next) || count < i - 1)
    	{
    		///要删除的位置不存在,则进行提示并返回0
    		printf(">>>删除位置不合理,请重试!\n");
    		return 0;
    	}
    
    	LinkNode* P = temp->next;    //临时存储要删除结点的地址,用于后续释放
    	temp->next = P->next;
    	free(P);	//释放被删除的地址
    }
    

 分析:

  •  其中 while 遍历部分, 和 if 判断部分和上面插入的功能是一样的。
LinkNode* P = temp->next;
temp->next = P->next;
  • 这一部分代码就是将要删除结点( i )的后继结点的地址赋值给 i 的前驱结点的地址域, 当 i 结点删除后,也可以通过 i 的前驱结点内的地址域去访问到 i 的后继结点。
  • 在删除某个结点以后,需要将其原先的地址进行释放(防止内存泄漏), 上述代码使用指针P记录了要删除结点( i )的地址, 防止删除结点后地址丢失。
    free(P);	//释放被删除的地址

 (2) 销毁单链表

1.单链表的基本操作及应用 ①创建 ②插入 ③删除 ④查找 ⑤显示,数据结构,算法,数据结构,链表,c语言,学习,visual studio,windows

void LinkDestroy(LinkNode* L)
{
	LinkNode* P;
	while (L)//当L为NULL时停止
	{
		P = L;
		L = L->next;
		free(P);
	}
}
  •  创建一个指针P来指向L当前的结点
  • 然后L->next指向下一个结点
  • 删除P所指向的地址
  • 然后再循环执行上述过程,直到L指向NULL(空结点)

4.  对链表进行“查”操作

1.单链表的基本操作及应用 ①创建 ②插入 ③删除 ④查找 ⑤显示,数据结构,算法,数据结构,链表,c语言,学习,visual studio,windows

(1) 打印链表中的元素

开头先创建一个结构体指针指向头结点,通过循环遍历来获取每一个结点的数据并打印。1.单链表的基本操作及应用 ①创建 ②插入 ③删除 ④查找 ⑤显示,数据结构,算法,数据结构,链表,c语言,学习,visual studio,windows

void LinkPrint(LinkNode* L)
{
	LinkNode* P = L->next;
	printf(">链表中的元素为:");
	while (P)
	{
		printf(" %d", P->data);
		P = P->next;
	}
	printf("\n");
}

(2) 获取链表中元素的个数

使用计数器思想即可解决!最后记得返回计数器len(返回类型为int)。

int LinkLenght(LinkNode* L)
{
	LinkNode* temp = L;
	int len = 0;		//默认长度为0
	while (temp->next)
	{
		temp = temp->next;
		len++;	//遍历得到链表长度
	}
	return len;
}

(3) 在单链表中查找元素e的位置

整体思路和上面一样。

当指针P遍历找到数据e时,则会退出循环;反之,指针P找不到元素e则会循环到P=NULL。退出循环后进行判断,P为非空指针则表示找到数据e,返回其位置,P为空指针则返回0。

int LocationElem(LinkNode* L, int e)
{
	LinkNode* P = L;
	int index = 0;
	while (P && P->data != e)
	{
		P = P->next;
		index++;
	}
	if (P)
		return index;	//返回数据e的位置
	else
		return 0;       //找不到则返回0
}

 (4) 在单链表中获取 i 位置的元素

整体思路和上面一样。

需要注意的是:输入的 i 小于1(不合理的值)和P为NULL时返回-1

int GetElem(LinkNode* L, int i)
{
	LinkNode* P = L->next;//从第一个结点开始
	int count = 1;
	while (P && count < i)
	{
		P = P->next;
		count++;
	}
	if (!P || count > i)
	{
		//没找到,或者i的值不合理(小于1)则返回-1
		return -1;
	}
	//找到则返回对应的元素值
	return P->data;
}

5.  对链表进行“改”操作

(1),修改第i个结点的数据

理解上面的代码后,这个基本差不多,就不写了  :3

三,整体的实现和效果

下面代码中没有:1,头插法创建链表;2,尾插法创建链表;3,“查找元素e的位置”

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
	int data;			//数据域
	struct node* next;	//指针域
}LinkNode;

LinkNode* InitList()
{
	//初始化一个带头结点的链表
	LinkNode* temp = (LinkNode*)malloc(sizeof(LinkNode));
	temp->next = NULL;
	return temp;
}
int LinkEmpty(LinkNode* L)
{
	if (L)
	{
		return 1;
	}
	return 0;
}

int LinkInsert(LinkNode* L, int i, int e)
{
	//L为记录头结点的指针, i为插入位置, e为插入元素
	LinkNode* temp = L;
	int count = 0;		//默认长度为0
	while (temp->next && count < i - 1)		
	//确保 temp 指针移动到第 i-1 个结点的位置,并避免访问空指针导致的错误。
	{		
		//寻找第i个结点,并使temp指向第i-1个结点
		temp = temp->next;
		count++;
	}
	//上面循环中已经根据i对count的值进行计数,count最大时等于链表长度,
	//当i-1大于链表长度时,则无法访问i结点(没有i这个结点)
	if (!(temp) || count < i - 1)
	{
		///第i个位置不存在,则进行提示并返回0
		printf(">>>访问越界,请重试!\n");
		return 0;
	}
	//在链表的第i个位置插入新结点P
	LinkNode* P = (LinkNode*)malloc(sizeof(LinkNode));
	P->data = e;
	P->next = temp->next;		//将temp下一个结点给P的地址域
	temp->next = P;				//将P的地址赋值给temp的地址域
	return 1;					//成功插入则返回1
}

void LinkPrint(LinkNode* L)
{

	LinkNode* P = L->next;
	printf(">链表中的元素为:");
	while (P)
	{
		printf(" %d", P->data);
		P = P->next;
	}
	printf("\n");
}
int LinkLenght(LinkNode* L)
{
	LinkNode* temp = L;
	int len = 0;		//默认长度为0
	while (temp->next)
	{
		temp = temp->next;
		len++;	//遍历得到链表长度
	}
	return len;
}
int LinkDelect(LinkNode* L, int i) {
	LinkNode* temp = L;
	int count = 0;
	while (temp->next && count < i - 1)
	{
		//寻找第i个结点,并使temp指向第i-1个结点
		temp = temp->next;
		count++;
	}
	if (!(temp->next) || count < i - 1)
	{
		///第i个位置不存在,则进行提示并返回0
		printf(">删除位置不合理,请重试!\n");
		return 0;
	}
	LinkNode* P = temp->next;//临时存储要删除结点的地址,用于后续释放
	temp->next = P->next;
	free(P);	//释放被删除的地址
}
void LinkDestroy(LinkNode* L)
{
	LinkNode* P;
	while (L)//当L为NULL时停止
	{
		P = L;
		L = L->next;
		free(P);
	}
}

int main()
{
	//创建一个结构体变量指针
	LinkNode* L = InitList();
	printf("^链表初始化成功.\n");
	printf("\n");

	//判断链表是否为空
	int flag = LinkEmpty(L);
	flag ? printf(">>>链表不为空\n") : printf(">>>链表为空\n");
	printf("\n");

	//插入新元素 + 打印链表中的元素
	LinkInsert(L, 1, 11);//L,i,e
	LinkPrint(L);
	LinkInsert(L, 2, 12);
	LinkPrint(L);
	LinkInsert(L, 3, 13);
	LinkPrint(L);
	LinkInsert(L, 4, 14);
	LinkPrint(L);
	LinkInsert(L, 3, 3);
	LinkPrint(L);
	LinkInsert(L, 6, 5);
	LinkPrint(L);
	LinkInsert(L, 9, 5);//越界访问
	LinkPrint(L);
	printf("\n");

	//求链表中元素个数
	int len = LinkLenght(L);
	printf(">>>链表的元素个数为: %d\n", len);
	printf("\n");


	//从链表中删除第i个元素 并打印
	LinkDelect(L, 2);
	LinkPrint(L);	
	LinkDelect(L, 5);
	LinkPrint(L);
	printf("\n");

	//销毁单链表
	LinkDestroy(L);

	return 0;
}
1.单链表的基本操作及应用 ①创建 ②插入 ③删除 ④查找 ⑤显示,数据结构,算法,数据结构,链表,c语言,学习,visual studio,windows
上方代码实现效果

如果文章有错误的地方,请帮忙指出进行改正,谢谢!  

栈:链栈和顺序栈的实现https://blog.csdn.net/Mzyh_c/article/details/135180651?spm=1001.2014.3001.5501文章来源地址https://www.toymoban.com/news/detail-765347.html

到了这里,关于链表入门:“单链表“的基本操作详解(C语言)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】 循环单链表的基本操作 (C语言版)

    目录 一、循环单链表 1、循环单链表的定义: 2、循环单链表的优缺点: 二、循环单链表的基本操作算法(C语言)    1、宏定义  2、创建结构体 3、循环单链表的初始化  4、循环单链表的插入 5、求单链表长度 6、循环单链表的清空 7、循环单链表的销毁 8、循环单链表的取

    2024年01月22日
    浏览(60)
  • C语言单链表实现初始化、创建、增、删、查等基本操作(详细)

    提示:文章参考王道的课程,相当于课程笔记 目录 一、单链表的定义及初始化 1、定义   2、初始化  1)不带头结点的单链表  2)带头节的单链表  二、单链表插入和删除 1)插入 1、按位序插入(带头结点) 2、按位插入(不带头结点)  3、指定结点的后插操作  4、指定结点

    2023年04月08日
    浏览(65)
  • 链表的基本操作(c语言)

    目录 链式存储结构 代码实现 链表初始化 头插法(前插法)创建含k个结点的单链表 尾插法(后插法)创建含k个结点的单链表 取第i个节点的数据域 寻找数据域等于e的结点返回该结点序号 在第i个结点插入数据域为e的结点 删除第i个结点 遍历链表 求链表结点个数(链表长度) 销毁

    2024年02月08日
    浏览(42)
  • C语言实现链表基本操作

    目录 一、什么是链表 二、为什么要使用链表 三、链表相关知识 四、链表实现 1.定义结构体 2.创建链表 3.遍历链表 4.判断链表是否为空 5.计算链表长度 6.插入一个数据 7.删除数据 8.全部代码 如果把数据比喻成珠子,指针就是线,链表通过指针这条线就是把数据这些珠子串起

    2024年02月06日
    浏览(43)
  • 吐血整理 二叉树(链表实现)的基本操作详解!

    本文是对二叉树这种数据结构基本操作与部分练习题的总结,内容庞大、详细、易懂,是你学习路上不容错过的优质博客! 既然是 链式二叉树 ,那必须得有自己的结点类型,以下是链式二叉树结点类型的定义,为了避免过多重复的代码,下面的问题都统一使用该结点类型。

    2024年02月03日
    浏览(58)
  • c语言数据结构——链表的实现及其基本操作

    顺序表的问题及思考 问题: 中间/头部的插入删除,时间复杂度为O(N) 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到 200,我们再继续插入了5个数据,后面没有数据插

    2023年04月09日
    浏览(85)
  • C语言---数据结构实验---顺序表的合并---链表的基本操作---重点解析约瑟夫问题

    实验的写法多种多样,但本文并未采用 #define 定义容量的写法,这样写已经是很老旧过时的写法。所有实验主体采用均为动态开辟,后续如果利用 C++ 来写或许会应用更多语法… 本篇展示数据结构的两个实验 其中,重点分析约瑟夫问题 实验中代码的命名风格等均与下方博客

    2024年02月16日
    浏览(70)
  • 【C++】单链表——单链表的基本操作

     由于顺序表的插入删除操作需要移动大量的元素,影响了运行效率,因此引入了线性表的链式存储—— 单链表 。单链表通过一组任意的存储单元来存储线性表中的数据元素,不需要使用地址连续的存储单元,因此它不要求在逻辑上相邻的两个元素在物理位置上也相邻。 单

    2024年02月03日
    浏览(46)
  • 单链表的基本操作

    目录 一.链表的基本概念和结构 二.链表的分类 三.单链表的基本操作  1.创建一个节点 2.打印 3.尾插 4.头插 5.尾删 6.头删 7.查找 8.指定位置插入 9.指定位置删除 10.销毁         概念:链表是一种 物理存储结构上非连续 、非顺序的存储结构,数据元素的 逻辑顺序 是通过链表

    2024年01月22日
    浏览(47)
  • 单链表基本操作(java)

    节点类是链表类的内部类

    2024年02月16日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包