数据结构 - C/C++ - 链表

目录

结构特性

内存布局

结构样式

结构拓展

单链表

结构定义

节点关联

插入节点

删除节点

常见操作        

双链表

环链表

结构容器

结构设计

结构特性

  • 线性结构的存储方式

    • 顺序存储 - 数组

    • 链式存储 - 链表

  • 线性结构的链式存储是通过任意的存储单元来存储线性表当中的数据元素。

    • 存储单元可以是连续的也可以是不连续的。

    • 线性结构的顺序存储中每个元素只需要存储其元素数据即可。

    • 线性结构的链式存储除了存储元素数据外，还有存储后继元素的内存地址。

  • 结构概念

    • 节点(Node) - 链式存储结构中的元素单位为节点，通常由数据域和指针域共同组成。

    • 数据域(Data) - 存储节点值。

    • 指针域(Next) - 存储节点指向的下一个节点的内存地址。

    • 头节点(Head) - 链表头部节点。

    • 尾节点(Tail) - 链表的结束位置节点，其指针域指向NULL，表示了链表结束。

内存布局

  • 链式存储

  • 节点样式

结构样式

  • 单链表

    • 每个节点只有一个指针域，指向下一个节点。

  • 双向链表

    • 每个节点存在两个指针域，一个指向前节点，一个指向后节点。

  • 循环链表

    • 链表尾部节点指向头节点。

结构拓展

单链表

结构定义
typedef struct ListNode
{
	//数据域
	int value;

	//指针域
	ListNode* Next;

	//赋值域
	ListNode(int num) : value(num), Next(nullptr){}
};
节点关联
	ListNode* Node1 = new ListNode(1);
	ListNode* Node2 = new ListNode(2);
	ListNode* Node3 = new ListNode(3);
	ListNode* Node4 = new ListNode(4);
	ListNode* Node5 = new ListNode(5);

	Node1->Next = Node2;
	Node2->Next = Node3;
	Node3->Next = Node4;
	Node4->Next = Node5;
	Node5->Next = NULL;
插入节点
void Insert(ListNode* Cur, ListNode* Node)
{
    ListNode* Temp = Cur->Next;
	Cur->Next = Node;
	Node->Next = Temp;
}
删除节点
void Remove(ListNode* Cur)
{
	//当前节点.Next = 当前节点.下一个节点.下一个节点
	ListNode* Node6 = Cur->Next;
	ListNode* Node3 = Node6->Next;
	Cur->Next = Node3;
	delete Node6;
}
常见操作        
	//遍历节点
	int nIndex = 0;
	ListNode* pTemp = Node1;
	while (pTemp != NULL)
	{
		printf("Index -> [%d] -> Data -> [%d] \r\n", nIndex, pTemp->value);
		++nIndex;
		pTemp = pTemp->Next;
	}

双链表

#include <iostream>

class ListNode
{
public:
	//数据域
	int value;

	//指针域
	ListNode* Prev;
	ListNode* Next;

	//赋值域
	ListNode(int Num): value(Num), Prev(nullptr), Next(nullptr) {}
};

//追加节点
void Append(ListNode* Head , int val)
{
	ListNode* newNode = new ListNode(val);

	ListNode* tempNode = Head;

	while (tempNode->Next != NULL)
	{
		tempNode = tempNode->Next;
	}

	tempNode->Next = newNode;
	newNode->Prev = tempNode;
	newNode->Next = NULL;

}

//添加节点
void Insert(ListNode* Head, int val)
{
	ListNode* newNode = new ListNode(val);

	ListNode* HeadNext = Head->Next;

	Head->Next = newNode;

	newNode->Prev = Head;
	newNode->Next = HeadNext;

	HeadNext->Prev = newNode;

	/*
		
		Node2.Next = NodeCC;

		NodeCC.Prev = Node2;
		NodeCC.Next = Node3;

		Node3.Prev = NodeCC;
	
	*/

}

//移除节点
void Remove(ListNode* Head)
{
	ListNode* tempNode = Head;

	while (tempNode->Next != NULL)
	{
		tempNode = tempNode->Next;
	}

	tempNode->Prev->Next = NULL;

	delete tempNode;
}

//删除节点
void Erase(ListNode* Head)
{
	//当前节点.上一个.下一个 = 当前节点.下一个
	//当前节点.下一个.上一个 = 当前节点.上一个

	Head->Prev->Next = Head->Next;
	Head->Next->Prev = Head->Prev;
}

int main()
{
	ListNode* Node1 = new ListNode(1);
	ListNode* Node2 = new ListNode(2);
	ListNode* Node3 = new ListNode(3);
	ListNode* Node4 = new ListNode(4);
	ListNode* Node5 = new ListNode(5);

	Node1->Prev = NULL;
	Node1->Next = Node2;

	Node2->Prev = Node1;
	Node2->Next = Node3;

	Node3->Prev = Node2;
	Node3->Next = Node4;

	Node4->Prev = Node3;
	Node4->Next = Node5;

	Node5->Prev = Node4;
	Node5->Next = NULL;

	Append(Node1 ,0xCC);
	Insert(Node2 ,0xDD);

	Remove(Node1);
	Erase(Node3);

	return 0;
}

环链表

#include <iostream>

class ListNode
{
public:
	//数据域
	int value;

	//指针域
	ListNode* Next;

	//赋值域
	ListNode(int Num) : value(Num), Next(nullptr){}
};

int main()
{
	ListNode* Node1 = new ListNode(1);
	ListNode* Node2 = new ListNode(2);
	ListNode* Node3 = new ListNode(3);
	ListNode* Node4 = new ListNode(4);
	ListNode* Node5 = new ListNode(5);

	Node1->Next = Node2;
	Node2->Next = Node3;
	Node3->Next = Node4;
	Node4->Next = Node5;
	Node5->Next = Node1;

	ListNode* tempNode = Node1;
	
	do
	{
		printf("%d \r\n", tempNode->value);
		tempNode = tempNode->Next;

	} while (tempNode != Node1);


	return 0;
}

结构容器

  • std:list

  • 构造函数

    • 默认构造函数

    • 有参构造函数

    • 拷贝构造函数

    • 列表构造函数

    • 默认析构函数

  • 大小函数

    • 节点数量

    • 是否为空

    • 清空数据

  • 功能函数

    • 插入元素

    • 头部插入

    • 尾部插入

    • 指定插入

    • 删除元素

    • 修改元素

    • 访问元素

结构设计

#include <iostream>

class Node
{
public:
	//数据域
	int value;

	//指针域
	Node* Prev;
	Node* Next;

	//赋值域
	Node(int Num, Node* p = nullptr, Node* n = nullptr) : value(Num), Prev(p), Next(n) {}
};

class List
{
public:

	//头部节点
	Node* Head;

	//尾部节点
	Node* Tail;

	//节点数量
	size_t size;

public:

	//默认构造
	List();

	//有参构造
	List(int Count, int value);

	//拷贝构造
	List(const List& ref);

	//列表构造
	List(std::initializer_list<int> initList);

	//默认析构
	~List();

public:

	//是否为空
	bool IsEmpty();

	//节点数量
	size_t GetSize();

	//清空容器
	void Clear();

public:

	//尾部插入
	void Push_Back(int value);

	//头部插入
	void Push_Front(int value);

	//指定插入
	void Insert(int InsertValue, int value);

	//尾部移除
	void Pop_Back();

	//头部移除
	void Pop_Front();

	//按值匹配
	void Remove(int value);

	//查找节点
	bool Find(int value);

public:

	//赋值运算符
	List& operator=(const List & other);

	//下标运算符
	int& operator[](int Index);

};

std::ostream& operator<<(std::ostream& output, const List& obj);

List::List()
{
	this->Head = nullptr;
	this->Tail = nullptr;
	this->size = 0;
}

List::List(int Count, int value) : Head(nullptr), Tail(nullptr), size(0)
{
	while (Count--)
	{
		Push_Back(value);
	}
}

List::List(const List& ref) : Head(nullptr), Tail(nullptr), size(0)
{
	Node* node = ref.Head;
	while (node)
	{
		Push_Back(node->value);
		node = node->Next;
	}
}

List::List(std::initializer_list<int> initList) : Head(nullptr), Tail(nullptr), size(0)
{
	for (auto value : initList)
	{
		Push_Back(value);
	}
}

List::~List()
{
	Clear();
}

bool List::IsEmpty()
{
	return this->size == 0 ? true : false;
}

size_t List::GetSize()
{
	return this->size;
}

void List::Clear()
{
	if (IsEmpty()) return;

	Node* node = this->Head;
	while (node)
	{
		Node* Temp = node->Next;
		delete node;
		node = Temp;
	}
	Head = Tail = nullptr;
	size = 0;
}

void List::Push_Back(int value)
{
	//创建对象时关联前后节点对象
	Node* node = new Node(value, Tail, nullptr);

	//当前容器是否存在尾节点
	if (Tail != nullptr)
	{
		Tail->Next = node;
	}

	//修正尾部节点
	Tail = node;

	//判断头部节点
	if (Head == nullptr)
	{
		Head = node;
	}

	++this->size;
}

void List::Push_Front(int value)
{
	Node* node = new Node(value, nullptr, Head);

	if (Head != nullptr)
	{
		Head->Prev = node;
	}

	Head = node;

	if (Tail == nullptr)
	{
		Tail = node;
	}

	++this->size;
}

void List::Insert(int InsertValue, int value)
{
	Node* node = Head;
	while (node != nullptr && node->value != InsertValue)
	{
		node = node->Next;
	}

	if (node != nullptr)
	{
		Node* InsertNode = new Node(value, node, node->Next);
		if (node->Next != nullptr)
		{
			node->Next->Prev = InsertNode;
		}
		else
		{
			Tail = InsertNode;
		}

		node->Next = InsertNode;

		++this->size;
	}

}

void List::Pop_Back()
{
	if (Tail == nullptr)
	{
		return;
	}

	//保存尾节点
	Node* temp = Tail;

	//修正尾节点
	Tail = Tail->Prev;

	if (Tail == nullptr)
	{
		Head = nullptr;
	}
	else
	{
		Tail->Next = nullptr;
	}

	delete temp;

	--this->size;
}

void List::Pop_Front()
{
	if (Head == nullptr)
	{
		return;
	}

	Node* temp = Head;
	Head = Head->Next;
	if (Head == nullptr)
	{
		Tail = nullptr;
	}
	else
	{
		Head->Prev = nullptr;
	}

	delete temp;

	--this->size;
}

void List::Remove(int value)
{
	Node* node = Head;
	while (node != nullptr && node->value != value)
	{
		node = node->Next;
	}

	if (node != nullptr)
	{
		if (node == Head) Pop_Front();
		else if (node == Tail) Pop_Back();
		else
		{
			node->Prev->Next = node->Next;
			node->Next->Prev = node->Prev;
			delete node;
			--this->size;
		}
	}

}

bool List::Find(int value)
{
	Node* node = Head;

	while (node != nullptr)
	{
		if (node->value == value) return true;
		node = node->Next;
	}

	return false;
}

List& List::operator=(const List& other)
{
	if (this != &other)
	{
		//删除默认数据
		Clear();

		Node* node = other.Head;
		while (node)
		{
			Push_Back(node->value);
			node = node->Next;
		}
	}

	return *this;
}

int& List::operator[](int Index)
{
	Node* node = Head;
	int Count = 0;
	while (node != nullptr && Count < Index)
	{
		node = node->Next;
		++Count;
	}

	if (node != nullptr)
	{
		return node->value;
	}
}

std::ostream& operator<<(std::ostream& output, const List& obj)
{
	Node* node = obj.Head;

	while (node != nullptr)
	{
		output << node->value;

		if (node->Next != nullptr)
		{
			output << " | ";
		}

		node = node->Next;
	}

	return output;
}

int main()
{
	//默认构造函数
	List myList1;
	
	//有参构造函数
	List myList3(3, 0xCC);

	//列表构造函数
	List myList4 = { 1,2,3,4,5 };

	//拷贝构造函数
	List myList5 = myList4;

	//赋值运算符
	List myList6;
	myList6 = myList5;

	std::cout << myList6 << std::endl;

	return 0;
}

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

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

相关文章

制氢厂氢气泄漏安全监测：氢气传感器守护“氢”安全

制氢厂氢气泄漏安全监测：氢气传感器守护“氢”安全

随着全球能源结构的转型和清洁能源的需求日益增长&#xff0c;氢能作为一种高效、清洁的能源载体&#xff0c;受到了广泛关注。制氢厂作为氢能产业的重要组成部分&#xff0c;其安全问题也日益凸显。在制氢过程中&#xff0c;氢气泄漏是潜在的安全隐患之一&#xff0c;因此&…
阅读更多...
Python容器 之 字符串--下标和切片

Python容器 之 字符串--下标和切片

1.下标&#xff08;索引&#xff09; 一次获取容器中的一个数据 1, 下标(索引), 是数据在容器(字符串, 列表, 元组)中的位置, 编号 2, 一般来说,使用的是正数下标, 从 0 开始 3, 作用: 可以通过下标来获取具体位置的数据. 4, 语法&#xff1a; 容器[下标] 5, Python 中是支持…
阅读更多...
猫冻干可以天天喂吗？喂冻干前要了解的必入主食冻干榜单

猫冻干可以天天喂吗？喂冻干前要了解的必入主食冻干榜单

近年来&#xff0c;冻干猫粮因其高品质而备受喜爱&#xff0c;吸引了无数猫主人的目光&#xff0c;对于像我这样的养猫达人来说&#xff0c;早已尝试并认可了冻干喂养。然而&#xff0c;对于初入养猫行列的新手们来说&#xff0c;可能会有疑问&#xff1a;什么是冻干猫粮&#…
阅读更多...
通过容器启动QAnything知识库问答系统

通过容器启动QAnything知识库问答系统

QAnything (Question and Answer based on Anything) 是致力于支持任意格式文件或数据库的本地知识库问答系统&#xff0c;可断网安装使用。目前已支持格式&#xff1a;PDF(pdf)&#xff0c;Word(docx)&#xff0c;PPT(pptx)&#xff0c;XLS(xlsx)&#xff0c;Markdown(md)&…
阅读更多...
操作配置文件保存方式（上位机）

操作配置文件保存方式（上位机）

上位机:(Supervisor Control) 指的是用于监视和控制其他设备或者系统的计算机&#xff0c;在工业自动化和过程控制领域 上位机典型就是一台PC或者服务器&#xff0c;用于语各种下位机进行通信的&#xff0c;收集数据&#xff0c;并且根据收集的数据发送一些数据。 典型的设备…
阅读更多...
一文讲懂npm link

一文讲懂npm link

前言 在本地开发npm模块的时候&#xff0c;我们可以使用npm link命令&#xff0c;将npm 模块链接到对应的运行项目中去&#xff0c;方便地对模块进行调试和测试 用法 包链接是一个两步过程&#xff1a; 1.为依赖项创建全局软链npm link。一个符号链接&#xff0c;简称软链&a…
阅读更多...
为什么127.0.0.1和localhost之间算跨域？

为什么127.0.0.1和localhost之间算跨域？

原文&#xff1a;https://mp.weixin.qq.com/s/4zJBMNEntwjqAfN6A6diUA 什么是同源策略、跨域 跨域问题是指在浏览器中&#xff0c;当一个网页向不同域名、不同端口或不同协议的资源发起请求时&#xff0c;会受到限制。这是由浏览器的**同源策略&#xff08;Same-Origin Policy…
阅读更多...
沉浸感拉满的三模游戏外设神器！谷粒金刚3 Pro游戏手柄开箱试玩

沉浸感拉满的三模游戏外设神器！谷粒金刚3 Pro游戏手柄开箱试玩

沉浸感拉满的三模游戏外设神器&#xff01;谷粒金刚3 Pro游戏手柄开箱试玩 哈喽小伙伴们好&#xff0c;我是Stark-C~ 对于喜欢打游戏的玩家来说&#xff0c;一款得力的游戏外设绝对是提升游戏体验&#xff0c;增加游戏乐趣的重要神器&#xff01;而在众多的外设中&#xff0c…
阅读更多...
Redis基础教程（六）：redis 哈希(Hash)

Redis基础教程（六）：redis 哈希(Hash)

&#x1f49d;&#x1f49d;&#x1f49d;首先&#xff0c;欢迎各位来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里不仅可以有所收获&#xff0c;同时也能感受到一份轻松欢乐的氛围&#xff0c;祝你生活愉快&#xff01; &#x1f49d;&#x1f49…
阅读更多...
tkinter实现进度条

tkinter实现进度条

tkinter实现进度条 效果代码解析导入需要的模块定义进度条 代码 效果 代码解析 导入需要的模块 import tkinter as tk from tkinter import ttk定义进度条 def start_progress():progress[value] 0max_value 100step 10for i in range(0, max_value, step):progress[valu…
阅读更多...
基于大数据架构的情感分析

基于大数据架构的情感分析

1 项目介绍 1.1 研究目的和意义 随着大数据时代的到来&#xff0c;电影产业积累了海量的用户评论数据&#xff0c;这些数据中蕴含着观众的情感倾向与偏好信息&#xff0c;为电影推荐和市场策略制定提供了宝贵资源。然而&#xff0c;如何高效地从这浩瀚的数据海洋中提炼出有价…
阅读更多...
Linux高并发服务器开发（八）Socket和TCP

Linux高并发服务器开发（八）Socket和TCP

文章目录 1 IPV4套接字结构体2 TCP客户端函数 3 TCP服务器流程函数代码粘包 4 三次握手5 四次挥手6 滑动窗口 1 IPV4套接字结构体 2 TCP客户端 特点&#xff1a;出错重传 每次发送数据对方都会回ACK&#xff0c;可靠 tcp是打电话的模型&#xff0c;建立连接 使用连接 关闭连接…
阅读更多...
论文阅读《U-KAN Makes Strong Backbone for MedicalImage Segmentation and Generation》

论文阅读《U-KAN Makes Strong Backbone for MedicalImage Segmentation and Generation》

Abstract U-Net 已成为图像分割和扩散概率模型等各种视觉应用的基石。虽然通过结合transformer或 MLP&#xff0c;U-Net 已经引入了许多创新设计和改进&#xff0c;但仍然局限于线性建模模式&#xff0c;而且可解释性不足。为了应对这些挑战&#xff0c;我们的直觉受到了 Kolm…
阅读更多...
PCL 基于点云RGB颜色的区域生长算法

PCL 基于点云RGB颜色的区域生长算法

RGB颜色的区域生长算法 一、概述1.1 算法定义1.2 算法特点1.3 算法实现二、代码示例三、运行结果🙋 结果预览 一、概述 1.1 算法定义 点云RGB区域生长算法: 是一个基于RGB颜色信息的区域生长算法，用于点云分割。该算法利用了点云中相邻点之间的颜色相似性来将点云分割成…
阅读更多...
WCCI 2024开幕，横滨圣地巡礼，畅游动漫与美食的世界

WCCI 2024开幕，横滨圣地巡礼，畅游动漫与美食的世界

惊喜&#xff01;WCCI 2024开幕&#xff0c;横滨圣地巡礼&#xff01;畅游动漫与美食的世界 会议之眼 快讯 会议介绍 IEEE WCCI&#xff08;World Congress on Computational Intelligence&#xff09;2024&#xff0c;即2024年IEEE世界计算智能大会&#xff0c;于6月30日至…
阅读更多...
力扣53. 最大子数组和（动态规划）

力扣53. 最大子数组和（动态规划）

Problem: 53. 最大子数组和 文章目录 题目描述思路及解法复杂度Code 题目描述 思路及解法 1.定义dp数组&#xff1a;dp[i]表示以nums[i]为结尾的子序列的最大子序列和&#xff1b; 2.状态初始化&#xff1a;dp[0] nums[0],表示以nums[0]为结尾的子序列的最大子序列和为nums[0]…
阅读更多...
linux配置ssh免密登录

linux配置ssh免密登录

1、准备工作 操作系统版本&#xff1a;UnionTech OS Server 20 1050e 内核版本&#xff1a;Linux 4.19.90-2201.4.0.0135.up1.uel20.x86_64 x86_64 使用root用户分别修改每台机器的hosts&#xff0c;添加每台机器所对应的IP和主机名 vi /etc/hosts添加如下内容 172.16.100.1…
阅读更多...
Redis-分布式锁（基本原理和不同实现方式对比）

Redis-分布式锁（基本原理和不同实现方式对比）

文章目录 1、基本原理2、不同实现方式 1、基本原理 分布式锁&#xff1a;满足分布式系统或集群模式下多进程可见并且互斥的锁。 分布式锁的核心思想就是让大家都使用同一把锁&#xff0c;只要大家使用的是同一把锁&#xff0c;那么我们就能锁住线程&#xff0c;不让线程进行&am…
阅读更多...
生命在于学习——Python人工智能原理（3.1.1）

生命在于学习——Python人工智能原理（3.1.1）

Python部分结束了&#xff0c;开始概率论部分 一、概率基本知识 1.1 事件与概率 1.1.1 事件的运算与关系 &#xff08;一&#xff09;基本概念 定义1 随机试验 如果一个试验满足如下条件&#xff1a; 在试验前不能断定其将发生什么结果&#xff0c;但可明确指出或说明试验…
阅读更多...
Hugging Face发布重量级版本：Transformer 4.42

Hugging Face发布重量级版本：Transformer 4.42

Hugging Face 宣布发布Transformer 4.42&#xff0c;该版本为流行的机器学习库带来了许多新功能和增强功能。此版本引入了几个高级模型&#xff0c;支持新工具和检索增强生成 &#xff08;RAG&#xff09;&#xff0c;提供 GGUF 微调&#xff0c;并整合了量化的 KV 缓存&#x…
阅读更多...
最新文章

Copyright @ 2022~2023