数据结构—链表

 链表结构-----“银行自助叫号”

        链表(Linked List)是一种常见的数据结构,用于存储一个序列的元素。它由一系列结点组成,每个结点包含两个部分:数据部分和指针部分。数据部分存储着当前结点的数据,而指针部分则存储着下一个结点的地址。

        链表可以分为单向链表、双向链表和循环链表等几种类型。其中单向链表每个结点只有一个指针指向下一个结点,而双向链表则每个结点有两个指针,一个指向前一个结点,一个指向后一个结点。循环链表与普通链表类似,只不过最后一个结点的指针指向链表的头结点。

        链表相对于数组来说,具有动态性,可以根据需要随时进行扩展或缩小,但是在访问链表中的某个元素时,需要从链表的头结点开始顺序遍历,因此访问效率较低。

一、链表的初始化

        链表的初始化是指创建一个空链表的过程,其中链表中没有任何节点。链表的初始化通常需要进行以下几个步骤:

1)、定义链表的结构:首先需要定义链表节点的结构。链表节点通常包含两个部分:数据域和指针域。数据域用于存储节点的数据,而指针域用于指向下一个节点。

struct LinkNode {
    int data;       // 数据域
    LinkNode* next;     // 指针域
};
链表节点

2)、创建头节点:链表的头节点是一个特殊的节点,它不存储实际的数据,只用于标识链表的起点。在初始化链表时,需要创建一个头节点。

LinkNode* head = new LinkNode();  // 创建头节点
head->next = nullptr;     // 头节点的指针域为空

 或使用 malloc 函数创建

// 初始化空链表
LinkNode* Init_Link() {
	/*该代码段将返回一个指向已初始化的空链表的头节点的指针,
	可以在其他函数中使用该指针进行链表操作。*/
	LinkNode* head = (LinkNode*)malloc(sizeof(LinkNode));
	head->next = nullptr;
	return head;
}

执行上述代码之后,则有: 

3)、设置尾节点:在初始化链表时,由于链表为空,头节点同时也是尾节点,因此需要将头节点的指针域设置为空。

head->next = nullptr;

4)、完成初始化:将链表的头节点作为链表的唯一标识,可以通过头节点找到整个链表。此时,链表的初始化就完成了。

完整的链表初始化代码示例:

#include<iostream>

struct LinkNode{
	int data; // 数据域
	LinkNode* next; // 指针域
};

// 初始化空链表
LinkNode* Init_Link() {
	/*该代码段将返回一个指向已初始化的空链表的头节点的指针,
	可以在其他函数中使用该指针进行链表操作。*/
	LinkNode* head = (LinkNode*)malloc(sizeof(LinkNode));
	head->next = nullptr;
	return head;
}

int main() {
	LinkNode* L1 = Init_Link(); // 调用Init_Link函数,获得一个指向已初始化的空链表的头节点的指针。


	// 输出链表头节点的指针
	std::cout << "链表L1的指针域:" << L1->next;
	free(L1); // 在不再需要链表时手动释放内存,确保没有内存泄漏
	return 0;
}

二、链表节点的插入

2.1 头部插入

链表头部插入节点结构图

        在上图中,我们首先创建了一个单链表,单链表的元素为1、2、3、4,该单链表包含头节点。接下来, 我们要完成头部插入新节点,即在头节点之后、第一个元素节点之前插入新节点,插入的步骤为:
第一步:让新节点与第一个元素的节点相连接,代码为:

New_head->next = head->next; // 新节点接到头部节点的后一个节点

第二步:让头节点与新节点相连接,代码为:

head->next = New_head; // 头部节点连接新节点

第三步: 链表头节点与原第一个元素的节点之间的连接自动断开。

完整代码实现:

// 链表头部插入节点
void Head_Insert_node(LinkNode* head) {
	/*
	  head:链表头指针
	  new_data:需要插入的元素
	*/
	int new_data;
	int num2;
	std::cout << "头插法插入元素个数:" << std::endl;
	std::cin >> num2;
	std::cout << "头插法插入元素:" << std::endl;
	for (int i = 0; i < num2; i++) {
		std::cin >> new_data;
		LinkNode* New_head = (LinkNode*)malloc(sizeof(LinkNode)); // 定义一个新节点NewNode(为新节点分配地址)
		if (New_head == nullptr) {
			std::cout << "内存分配失败!\n";
		}
		New_head->data = new_data; // 为新节点分配值
		// 头部插入新节点
		New_head->next = head->next; // 新节点接到头部节点的后一个节点
		head->next = New_head; // 头部节点连接新节点
	}
}

2.2 尾部插入

完整代码实现: 

// 链表尾部插入节点
void Tail_Insert_node(LinkNode* head) {
	
	int tail_new_data; // 定义尾部插入元素
	int tail_num; // 定义尾插法插入元素个数
	std::cout << "尾插法插入元素个数:" << std::endl;
	std::cin >> tail_num;
	std::cout << "尾插法插入元素:" << std::endl;
	LinkNode* each_current = head; // 定义遍历指针
	for (int i = 0; i < tail_num; i++) {
		std::cin >> tail_new_data;
		LinkNode* New_node = (LinkNode*)malloc(sizeof(LinkNode)); // 定义一个新节点NewNode(为新节点分配地址)
		if (New_node == nullptr) {
			std::cout << "内存分配失败!\n";
		}
		if (each_current->next == nullptr) { // 链表只有头节点,没有元素节点
			New_node->data = tail_new_data; // 为新节点分配值
			each_current->next = New_node;
			New_node->next = nullptr; // 若没有这句话 会报错 *****重要!!!
			each_current = each_current->next;
		}
		if (each_current->next != nullptr) { // 链表除头节点之外还有其他的元素节点
			New_node->data = tail_new_data; // 为新节点分配值
			while (each_current->next != nullptr) {
				each_current = each_current->next;
			}
			each_current->next = New_node;
			New_node->next = nullptr; // 若没有这句话 会报错 *****重要!!!
		}	
	}
}

 2.2.1 尾部插入时两种情况

2.2.1.1 非空链表时尾插

第一步:遍历指针找出链表尾部节点 。

过程分析:
        首先需要定义一个链表类型的遍历指针each_current, 该指针用于寻找链表的尾部节点,该指针初始位置指向第一个节点,随后开始遍历,若该指针指向的下一个节点内容不为空,则表明该指针指向的节点不是尾部节点,此时该指针自增,直到该指针指向的下一个节点的内容为nullptr,说明该指针指向的节点为尾部节点,此时退出while循环。

第二步:将新节点New_head接入尾部节点之后。

注意:新节点New_head的指针域要赋nullptr,即New_head->next=nullptr;否则程序报错! 

过程分析:

 接下来我们将新节点New_head接入到尾部节点的后面位置。

2.2.1.2 空链表时尾插

2.3 中间任意位置插入

代码实现: 

// 链表任意位置插入节点
void Insert_Node(LinkNode* head) {
	/*
	head:链表的头指针
	position:新节点插入的位置
	new_data:插入的元素
	*/
	LinkNode* each_current = head; // 定义遍历指针
	LinkNode* New_node = (LinkNode*)malloc(sizeof(LinkNode)); // 定义一个新节点NewNode(为新节点分配地址)

	int new_data; // 插入元素
	int position; // 插入位置
	if (each_current->next == nullptr) {
		std::cout << "链表中无元素,请先考虑使用头插法或尾插法创建链表!" << std::endl;
	}
	else {
		std::cout << "插入位置:" << std::endl;
		std::cin >> position;
		std::cout << "插入元素:" << std::endl;
		std::cin >> new_data;
		if (New_node == nullptr) {
			std::cout << "内存分配失败!\n";
		}
		New_node->data = new_data; // 为新节点分配值
		New_node->next = nullptr;

		int count_num = count_Linknum(head); // 获取链表元素个数,储存在变量count_num中

		if (position <= 0) {
			std::cout << "插入位置越下界!\n";
		}
		else if (position > count_num) {
			std::cout << "插入位置越上界!\n";
		}
		else {

			// 找到要插入位置的前一个节点
			int count = 1;
			while (each_current->next != nullptr && count != position) {
				each_current = each_current->next;
				count++;
			}
			// 在指定位置插入节点
			New_node->next = each_current->next;
			each_current->next = New_node;
		}
	}
}

 分析:

 

三、链表元素的打印

        链表元素打印函数如下(带有头节点的链表):

// 打印链表元素
void printLinkNode(LinkNode* head) {
	LinkNode* each_current = head->next; // 定义遍历指针
	std::cout << "链表元素为:\n";
	while (each_current != nullptr){
		std::cout<< each_current->data << " ";
		each_current = each_current->next;
	}
}

上述代码段分析: 

        对于链表元素的打印,我们需要定义一个链表类型的遍历指针each_current,该指针首先指向头节点的后一个节点,即装第一个元素的节点。当遍历指针所指内容不为空时,输出遍历指针指向的当前节点的元素值,随后遍历指针递增,直到遍历指针指向nullptr,此时节点遍历完成,退出while循环。

四、统计链表元素个数

函数实现: 

// 统计链表元素个数
int count_Linknum(LinkNode* head) {
	/*
	 head:表示头指针
	*/
	LinkNode* each_current = head->next; // 定义遍历指针
	int count_num = 0;
	while (each_current != nullptr) {
		each_current = each_current->next;
		count_num++;
	}
	return count_num;
}

代码分析(以带头结点的四个元素节点为例): 

五、链表元素的删除

5.1 链表指定元素的删除

代码如下: 

// 删除链表指定元素
void Delete_element(LinkNode* head) {
	LinkNode* each_current = head->next; // 定义遍历指针
	LinkNode* pre_each_current = head;
	if (each_current == nullptr) {
		std::cout << "链表中无元素,请先创建链表!" << std::endl;
	}
	else {
		int delete_data;
		std::cout << "删除的元素:" << std::endl;
		std::cin >> delete_data;

	
		while (each_current != nullptr) {
			if ((each_current->data != delete_data) && (each_current->next == nullptr)) {
				std::cout << "链表中没有您想要删除的元素!" << std::endl;
			}
			if (each_current->data == delete_data) {
				pre_each_current->next = each_current->next;
				free(each_current); // 释放要删除的节点
				each_current = pre_each_current->next; // each_current指向删除节点的后一个节点
				std::cout << "元素" << delete_data << "已删除!" << std::endl;
			}
			else {
				// 当没有找到要删除的元素时,each_current和pre_each_current正常递增
				each_current = each_current->next;
				pre_each_current = pre_each_current->next;
			}
		}	
	}
}

5.2 链表指定位置上的元素的删除

代码如下:

// 删除链表指定位置上的元素
void Delete_position(LinkNode* head) {
	LinkNode* each_current = head->next; // 定义遍历指针
	LinkNode* pre_each_current = head;
	if (each_current == nullptr) {
		std::cout << "链表中无元素,请先创建链表!" << std::endl;
	}
	else {
		int delete_position;
		std::cout << "删除的位置:" << std::endl;
		std::cin >> delete_position;
		int linknum = count_Linknum(head); // 链表元素个数
		if (delete_position > linknum) {
			std::cout << "删除越上界!" << std::endl;
		}
		if (delete_position <= 0) {
			std::cout << "删除越下界!" << std::endl;
		}
		else {
			int element_position = 1; // 元素位置变量
			while (element_position != delete_position) {
				element_position++;
				each_current = each_current->next;
				pre_each_current = pre_each_current->next;
			}
			pre_each_current->next = pre_each_current->next->next; // 也可:pre_each_current->next = each_current->next;
			
			std::cout << "第" << delete_position << "位置上的元素" << each_current->data << "已删除!" << std::endl;
			free(each_current);
		}
	}		
}

六、查询链表元素

6.1 查询链表指定元素

// 查询链表指定元素
void search_element(LinkNode* head) {

	int element_position = 1; // 元素位置变量
	LinkNode* each_current = head->next; // 定义遍历指针
	if (each_current == nullptr) {
		std::cout << "链表中无元素,请先创建链表!" << std::endl;
	}
	else {
		int search_data;
		std::cout << "查找元素:" << std::endl;
		std::cin >> search_data;

		while (each_current != nullptr) {
			if (each_current->data == search_data) {
				std::cout << "元素:{" << search_data << "}" << "-" << "所在位置:" << element_position << std::endl;
			}
			else {
				std::cout << "链表中不存在此元素!" << std::endl;
				break;
			}
			each_current = each_current->next;
			element_position++;
		}
	}
}

6.2 查询链表指定位置上面的元素

// 查询链表指定位置上面的元素
void search_position(LinkNode* head) {
	int element_position = 1; // 元素位置变量
	LinkNode* each_current = head->next; // 定义遍历指针
	int linknum = count_Linknum(head);; // 链表元素个数
	if (each_current == nullptr) {
		std::cout << "链表中无元素,请先创建链表!" << std::endl;
	}
	else {
		int Sposition;
		std::cout << "查找的位置为:" << std::endl;
		std::cin >> Sposition;

		if (Sposition > linknum) {
			std::cout << "查询越上界!" << std::endl;
		}
		if (Sposition <= 0) {
			std::cout << "查询越下界!" << std::endl;
		}
		else {
			while (each_current != nullptr) {
				if (element_position == Sposition) {
					std::cout << "位置:" << Sposition << "所对应的元素为:" << each_current->data << std::endl;
				}
				each_current = each_current->next;
				element_position++;
			}
		}
	}
	
}

七、主函数

int main() {
	LinkNode* L1 = Init_Link(); // 调用Init_Link函数,获得一个指向已初始化的空链表的头节点的指针。
	int choice; // 选择变量
	
	while (true) {
		system("pause");
		system("cls");
		std::cout << "请选择要执行的操作:" << std::endl;
		std::cout << "---------------------------------------" << std::endl;
		std::cout << "1:退出" << std::endl;
		std::cout << "2:链表节点头插法" << std::endl;
		std::cout << "3:链表节点尾插法" << std::endl;
		std::cout << "4:链表节点任意位置插法" << std::endl;
		std::cout << "5:查询链表指定元素" << std::endl;
		std::cout << "6:查询链表指定位置上的元素" << std::endl;
		std::cout << "7:删除链表指定元素" << std::endl;
		std::cout << "8:删除链表指定位置上的元素" << std::endl;
		std::cout << "9:统计链表元素个数" << std::endl;
		std::cout << "10:打印链表元素" << std::endl;
		std::cout << "---------------------------------------" << std::endl;

		std::cin >> choice;
		
		switch (choice) {
		case 1:
			exit(0);
			break;
		case 2:
			Head_Insert_node(L1);
			break;
		case 3:
			Tail_Insert_node(L1);
			break;
		case 4:
			Insert_Node(L1);
			break;
		case 5: // 查询链表指定元素
			search_element(L1);
			break;
		case 6:
			search_position(L1);
			break;
		case 7:
			
			Delete_element(L1);
			break;
		case 8:
			Delete_position(L1);
			break;
		case 9:
			int count_num;
			count_num = count_Linknum(L1);
			std::cout << "链表中现存元素个数为:" << count_num << std::endl;
			break;
		case 10:
			printLinkNode(L1);
			break;
		}
	}
	

	/*Head_Insert_node(L1, 4);
	Head_Insert_node(L1, 3);
	Head_Insert_node(L1, 2);
	Head_Insert_node(L1, 1);
	Tail_Insert_node(L1, 5);
	Insert_Node(L1, 3, 3);
	printLinkNode(L1);
	search_element(L1, 3);
	search_position(L1, 5);
	Delete_position(L1, 2);
	printLinkNode(L1);*/
	// int count_num = count_Linknum(L1);
	// std::cout << "链表元素个数为:\n" << count_num;

	// 输出链表头节点的指针
	// std::cout << "链表L1的指针域:" << L1->next;
	free(L1); // 在不再需要链表时手动释放内存,确保没有内存泄漏
	return 0;

}

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

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

相关文章

CSDN最新最全pytest系列——pytest-base-url插件之配置可选的项目系统UR

前言 ①当我们的自动化代码完成之后&#xff0c;通常期望可以在不同的环境进行测试&#xff0c;此时可以将项目系统的URL单独拿出来&#xff0c;并且可以通过pytest.ini配置文件和支持pytest命令行方式执行。 ② pytest-base-url 是一个简单的pytest插件&#xff0c;它通过命…

12-25v转3.3v高清水下钓鱼摄像头电源供电芯片方案

高清水下钓鱼摄像头电源芯片方案&#xff1a;12-25V转3.3V&#xff0c;支持超宽电压输入范围和30米长线视频放大 在水下钓鱼摄像头设计中&#xff0c;为了实现高清画质和稳定的电源供应&#xff0c;需要一款能够将12-25V转换为3.3V输出的高效电源芯片。这款电源芯片不仅支持高…

【电路笔记】-电流源

电流源 文章目录 电流源1、概述1.1 理想电流源1.2 实际电流源1.3 连接规则 2、依赖电流2.1 压控电流源2.2 电流控制电流源 3、总结 本文为前面文章 电压源的延续&#xff0c;我们将在本文介绍电流源。 与电压源的情况类似&#xff0c;我们将首先介绍理想电流源的概念&#xff…

第二十章:多线程

进程 线程的特点 1.进程是资源分配的最小单位&#xff0c;线程是最小的执行单位 2.一个进程可以有多个线程 3.线程共享进程资源 package twentyth; public class ThreadTest extends Thread { public void run() { for (int i 1; i < 10; i) {//继承重…

Shell判断:模式匹配:case(三)

系统管理工具箱 1、需求&#xff1a;Linux提供的丰富的管理命令&#xff0c;用户管理&#xff0c;内存管理&#xff0c;磁盘管理&#xff0c;进程管理&#xff0c;日志管理&#xff0c;文件管理&#xff0c;软件管理&#xff0c;网络管理等等数十个工具包。如果你能通过shell编…

二十、虚拟机网络配置

1、Linux网络配置原理 我自己Linux虚拟机的IP地址是&#xff1a;192.168.159.131 vmnet8&#xff1a;192.168.159.1 无线网卡&#xff1a;192.168.159.1 2、查看网络IP和网关 查看虚拟网络编辑器和修改IP地址 如果把这个位置的子网IP换成&#xff1a;192.168.8.0的话重启虚拟机…

【兔子王赠书第8期】AI短视频制作一本通: 文本生成视频+图片生成视频+视频生成视频

文章目录 写在前面推荐图书关键点内容简介作者简介推荐理由写在后面 写在前面 1本书精通AI短视频制作&#xff0c;文本生成视频图片生成视频视频生成视频AI短视频应用&#xff01;高效视频制作技巧&#xff0c;助你快速成长为行业大咖&#xff01; 推荐图书 《AI短视频制作一…

Java小游戏之飞翔的小鸟

创建三个包&#xff0c;存放代码。把图片放进文件中 APP包&#xff08;运行&#xff09; GameApp类 package APP; import mian.GameFrame;public class GameApp {public static void main(String[] args) {new GameFrame();} } mian包&#xff08;主内容&#xff09; Barrie…

SQL基础理论篇(九):存储过程

文章目录 简介存储过程的形式定义一个存储过程使用delimiter定义语句结束符存储过程中的三种参数类型流控制语句 存储过程的优缺点参考文献 简介 存储过程Stored Procedure&#xff0c;SQL中的另一个重要应用。 前面说的视图&#xff0c;只能勉强跟编程中的函数相似&#xff…

2023年危险化学品生产单位安全生产管理人员证模拟考试题库及危险化学品生产单位安全生产管理人员理论考试试题

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2023年危险化学品生产单位安全生产管理人员证模拟考试题库及危险化学品生产单位安全生产管理人员理论考试试题是由安全生产模拟考试一点通提供&#xff0c;危险化学品生产单位安全生产管理人员证模拟考试题库是根据危…

Unsupervised MVS论文笔记

Unsupervised MVS论文笔记 摘要1 引言2 相关工作3 实现方法 Tejas Khot and Shubham Agrawal and Shubham Tulsiani and Christoph Mertz and Simon Lucey and Martial Hebert. Tejas Khot and Shubham Agrawal and Shubham Tulsiani and Christoph Mertz and Simon Lucey and …

【java】想要限制每次查询的结果集不能超过10000行,该如何实现?

文章目录 前言 前言 对于一些Saas化软件&#xff0c;当某个租户在执行查询SQL时&#xff0c;如果查询条件出现了BUG&#xff0c;导致去查了所有租户的数据&#xff0c;这种情况是非常严重的&#xff0c;此时就需要在架构层面做限制&#xff0c;禁止一些特殊SQL的执行&#xff…

Axios 请求响应结果的结构

发送请求 this.$axios.get(https://apis.jxcxin.cn/api/title?urlhttps://apis.jxcxin.cn/,{params: {id: 10}}).then(res > {console.log(res)})输出返回结果 confing 请求时的配置对象&#xff0c;如果请求的url&#xff0c;请求的方法&#xff0c;请求的参数&#xff0c…

数字孪生助力污水处理升级

随着科技的发展&#xff0c;数字孪生技术在各行各业中得到了广泛应用。在污水处理领域&#xff0c;数字孪生技术为流程监控、效率提升、问题诊断等提供了强有力的支持。本文就借用山海鲸可视化软件的污水处理解决方案为大家介绍数字孪生在污水处理领域的作用。 一、实时监控 …

MAX/MSP SDK学习04:Messages selector的使用

其实消息选择器在simplemax示例中就接触到了&#xff0c;但这文档非要讲那么抽象。目前为止对消息选择器的理解是&#xff1a;可判断接收过来的消息是否符合本Object的处理要求&#xff0c;比如加法对象只可接收数值型的消息以处理&#xff0c;但不能接收t_symbol型的消息&…

【华为OD题库-032】数字游戏-java

题目 小明玩一个游戏。系统发1n张牌&#xff0c;每张牌上有一个整数。第一张给小明&#xff0c;后n张按照发牌顺序排成连续的一行。需要小明判断&#xff0c;后n张牌中&#xff0c;是否存在连续的若干张牌&#xff0c;其和可以整除小明手中牌上的数字. 输入描述: 输入数据有多组…

DB2—03(DB2中常见基础操作)

DB2—03&#xff08;DB2中常见基础操作&#xff09; 1. 前言1.1 oracle和mysql相关 2. db2中的"dual"2.1 SYSIBM.SYSDUMMY12.2 使用VALUES2.3 SYSIBM.SYSDUMMY1 "变" dual 3. db2中常用函数3.1 nvl()、value()、COALESCE()3.2 NULLIF() 函数3.3 LISTAGG() …

成为AI产品经理——AI产品经理工作全流程

一、业务背景 背景&#xff1a;日常排球训练&#xff0c;中考排球项目和排球体测项目耗费大量人力成本和时间成本。 目标&#xff1a;开发一套用于实时检测排球运动并进行排球垫球计数和姿势分析的软件。 二、产品工作流程 我们这里对于产品工作流程的关键部分进行讲解&…

SQL 中的 MIN 和 MAX 以及常见函数详解及示例演示

SQL MIN() 和 MAX() 函数 SQL中的MIN()函数和MAX()函数用于查找所选列的最小值和最大值&#xff0c;分别。以下是它们的用法和示例&#xff1a; MIN() 函数 MIN()函数返回所选列的最小值。 示例&#xff1a; 查找Products表中的最低价格&#xff1a; SELECT MIN(Price) F…

Vue 重写push和replace方法,解决:Avoided redundant navigation to current location

当我们使用编程式路由导航跳转路径时&#xff0c;如果我们两次携带同样的参数进行跳转&#xff0c;会进行页面报错&#xff1a; 那产生这个问题的原因是什么呢&#xff1f; 我们接收并输出调用push方法返回的结果&#xff1a; 会发现这是一个Promise对象 我们都知道&#xff…