数据结构 - 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;
}


http://www.niftyadmin.cn/n/5536559.html

相关文章

【数据结构】（C语言）：堆（二叉树的应用）

【数据结构】（C语言）：堆（二叉树的应用）

堆&#xff1a; 此处堆为二叉树的应用&#xff0c;不是计算机中用于管理动态内存的堆。形状是完全二叉树。堆分两种&#xff1a;最大堆&#xff0c;最小堆。最大堆&#xff1a;每个节点比子树所有节点的数值都大&#xff0c;根节点为最大值。最小堆&#xff1a;每个节点比子树…
阅读更多...
C语言 指针和数组——指针的算术运算

C语言 指针和数组——指针的算术运算

目录 指针的算术运算 指针加上一个整数 指针减去一个整数 指针相减 指针的关系比较运算 小结 指针的算术运算 指针加上一个整数 指针减去一个整数 指针相减 指针的关系比较运算 小结  指针变量 – 指针类型的变量&#xff0c;保存地址型数据  指针变量与其他类型…
阅读更多...
ubuntu软件源的两种格式和环境变量

ubuntu软件源的两种格式和环境变量

1. ubuntu的/etc是什么目录&#xff1f; 在Ubuntu操作系统中&#xff0c;/etc/是一个特殊的目录&#xff0c;它包含系统的配置文件。这些配置文件用于设置各种系统和应用程序的参数和选项。 一般来说&#xff0c;用户可以在这个目录下找到各种重要的配置文件&#xff0c;如网络…
阅读更多...
Java增加线程后kafka仍然消费很慢

Java增加线程后kafka仍然消费很慢

文章目录 一、问题分析二、控制kafka消费速度属性三、案例描述 一、问题分析 Java增加线程通常是为了提高程序的并发处理能力&#xff0c;但如果Kafka仍然消费很慢&#xff0c;可能的原因有&#xff1a; 网络延迟较大&#xff1a;如果网络延迟较大&#xff0c;即使开启了多线…
阅读更多...
腾讯课堂即将停止服务？来试试这款开源的知识付费系统

腾讯课堂即将停止服务？来试试这款开源的知识付费系统

项目介绍 本系统基于ThinkPhp5.0layuiVue开发,功能包含在线直播、付费视频、付费音频、付费阅读、会员系统、分销系统、拼团活动、直播带货、直播打赏、商城系统等。能够快速积累客户、会员数据分析、智能转化客户、有效提高销售、吸引流量、网络营销、品牌推广的一款应用&…
阅读更多...
【Linux】Linux常用指令合集精讲，一篇让你彻底掌握(万字真言)

【Linux】Linux常用指令合集精讲，一篇让你彻底掌握(万字真言)

文章目录 一、文件与目录操作1.1 ls - 列出目录内容1.2 cd - 切换目录1.3 pwd - 显示当前目录1.4 mkdir - 创建目录1.5 rmdir - 删除空目录1.6 rm - 删除文件或目录1.7 cp - 复制文件或目录1.8 mv - 移动或重命名文件或目录1.9 touch - 创建空文件或更新文件时间戳 二、文件内容…
阅读更多...
Java 项目的构建工具 Maven

Java 项目的构建工具 Maven

Maven 一、Maven 简介二、Maven 安装配置1、Maven 下载安装2、Maven 配置 三、IDEA 集成 Maven四、Maven 依赖管理1、依赖配置2、依赖传递3、依赖范围4、生命周期 五、Maven 高级特性1、分模块设计与开发2、Maven 继承3、Maven 版本管理4、Maven 聚合5、私服 一、Maven 简介 M…
阅读更多...
R迅速切换目录 -R语言002

R迅速切换目录 -R语言002

实用小操作系列 R定位当前目录 getwd() [1] "/data/Rprofile1" #当前工作目录&#xff0c;因为他读取文件都是相对路径&#xff0c;进当前目录&#xff0c;一般不考虑绝对路径&#xff0c;写代码容易乱呀&#xff0c;切目录最简单完善 R切换工作目录 setwd(&q…
阅读更多...
最新文章

Copyright @ 2022~2023