基于面向对象，C++实现双链表

双链表同单链表类似，由一个值和两个指针组成
在这里插入图片描述

Node.h节点头文件

#pragma once
class Node
{
public:
	int value;
	Node* prev;
	Node* next;

	Node(int value);
	~Node();
};

Node.cpp节点源文件

#include "Node.h"

Node::Node(int value)
{
	this->value = value;
	prev = nullptr;
	next = nullptr;
}

Node::~Node()
{
}

DoubleLinkList.h双链表头文件

#pragma once
#include "Node.h"
class DoubleLinkList
{public:
	Node* head;
	Node* tail;
	int length;

	DoubleLinkList(int val);//有参构造
	void PrintDoubleLinkList();//打印双链表
	void getLength();//获取双链表长度

	void append(int val);//尾部插入元素
	void prepend(int val);//头部插入元素
	void insert(int index, int val);//任意位置插入元素

	Node* removeLast();//删除最后一个元素
	Node* removeFirst();//删除第一个元素
	Node* remove(int index);//删除任意位置元素

	Node* get(int index);//获取元素
	bool change(int index, int val);//改变元素
	int search(int val);//查找元素
};

DoubleLinkList.cpp节点源文件

#include "DoubleLinkList.h"
#include<iostream>
using namespace std;


DoubleLinkList::DoubleLinkList(int val)
{
	Node* newNode = new Node(val);
	head = newNode;
	tail = newNode;
	length = 1;
}

//打印链表
void DoubleLinkList::PrintDoubleLinkList()
{
	Node* temp = head;
	while (temp!=nullptr) {
		cout << temp->value << " ";
		temp = temp->next;
	}
	cout << endl;
}
//获取双链表长度
void DoubleLinkList::getLength()
{
	cout << "双链表长度为：" << length << endl;
}

//尾部插入
void DoubleLinkList::append(int val)
{
	Node* newNode = new Node(val);
	if (length == 0) {
		head = newNode;
		tail = newNode;
	}
	else {
		tail->next = newNode;
		newNode->prev = tail;
		tail = newNode;
	}
	length++;
}

//头部插入
void DoubleLinkList::prepend(int val)
{
	Node* newNode = new Node(val);
	if (length == 0) {
		head = newNode;
		tail = newNode;
	}
	else {
		newNode->next = head;
		head->prev = newNode;
		head = newNode;
	}
	length++;
}

//任意位置插入
void DoubleLinkList::insert(int index, int val)
{
	if (index<0 || index>length) {
		cout << "error";
	}
	else if (index == 0) {
		prepend(val);
	}
	else if(index == length){
		append(val);
	}
	else {
		Node* p1 = head;
		for (int i = 0; i < index - 1; i++) {
			p1 = p1->next;
		}
		Node* p2 = p1->next;
		Node* newNode = new Node(val);
		newNode->prev = p1;
		newNode->next = p2;
		p1->next = newNode;
		p2->prev = newNode;
		length++;
	}
}

//删除尾部
Node* DoubleLinkList::removeLast()
{
	if (length == 0) {
		return nullptr;
	}
	Node* temp = tail;
	if (length == 1) {
		head = nullptr;
		tail = nullptr;
	}
	else {
		tail = tail->prev;
		tail->next = nullptr;
		temp->prev = nullptr;
	}
	length--;
	return temp;
}

//删除头部
Node* DoubleLinkList::removeFirst()
{
	if (length == 0) {
		return nullptr;
	}
	Node* temp = head;
	if (length == 1) {
		head = nullptr;
		tail = nullptr;
	}
	else {
		head = head->next;
		head->prev = nullptr;
		temp->next = nullptr;
	}
	length--;
	return temp;
}

//删除任意位置
Node* DoubleLinkList::remove(int index)
{
	if (index<0 || index>length) {
		return nullptr;
	}
	if (index == 0) {
		return removeFirst();
	}
	if (index == length - 1) {
		return removeLast();
	}
	Node* temp = head;
	for (int i = 0; i < index; i++) {
		temp = temp->next;
	}
	temp->next->prev = temp->prev;
	temp->prev->next = temp->next;
	temp->next = nullptr;
	temp->prev = nullptr;
	length--;
	return temp;
}

//获取元素
Node* DoubleLinkList::get(int index)
{
	
	if (index<0 || index>length) {
		return nullptr;
	}
	Node* temp = head;
	if (index < length / 2) {
		for (int i = 0; i < index; i++) {
			temp = temp->next;
		}
	}
	else {
		temp = tail;
		for (int i = length - 1; i > index; i--) {
			temp = temp->prev;
		}
	}
	return temp;
}

//改变元素
bool DoubleLinkList::change(int index, int val)
{
	Node* temp = get(index);
	if (temp) {
		temp -> value = val;
		return true;
	}
	return false;
}

//查找元素
int DoubleLinkList::search(int val)
{
	int index = 0;
	Node* temp = head;
	while (temp->value != val) {
		index++;
		temp = temp->next;
		if (temp == nullptr) {
			cout << "未找到！" << endl;
			return -1;
		}
	}
	cout << "找到了！元素索引为：";
	return index;
}

插入元素

1. 头部插入

1.新节点的next指向head节点
2.head节点的prev指向新节点
3.head移动至新节点
具体如下图所示：

在这里插入图片描述

//头部插入
void DoubleLinkList::prepend(int val)
{
	Node* newNode = new Node(val);
	if (length == 0) {
		head = newNode;
		tail = newNode;
	}
	else {
		newNode->next = head;
		head->prev = newNode;
		head = newNode;
	}
	length++;
}

2. 尾部插入

1.尾节点tail的next指向新节点
2.新节点的prev指向尾节点tail
3.tail节点移动到新节点

在这里插入图片描述

//尾部插入
void DoubleLinkList::append(int val)
{
	Node* newNode = new Node(val);
	if (length == 0) {
		head = newNode;
		tail = newNode;
	}
	else {
		tail->next = newNode;
		newNode->prev = tail;
		tail = newNode;
	}
	length++;
}

3. 任意位置插入

1.创建新节点p1指向头结点head，然后移动至插入节点前一个节点，并创建新节点p2指向p1的next节点
2.新节点的prev指向p1
3.新节点的next指向p2
4.p1节点的next指向新节点
5.p2节点的prev指向新节点

在这里插入图片描述

//任意位置插入
void DoubleLinkList::insert(int index, int val)
{
	if (index<0 || index>length) {
		cout << "error";
	}
	else if (index == 0) {
		prepend(val);
	}
	else if(index == length){
		append(val);
	}
	else {
		Node* p1 = head;
		for (int i = 0; i < index - 1; i++) {
			p1 = p1->next;
		}
		Node* p2 = p1->next;
		Node* newNode = new Node(val);
		newNode->prev = p1;
		newNode->next = p2;
		p1->next = newNode;
		p2->prev = newNode;
		length++;
	}
}

删除元素

1. 尾部删除

1.新建一个节点temp指向尾节点tail
2.尾节点tail移动至tail的prev节点
3.尾节点tail的next指向空
4.temp的prev指针指向空

在这里插入图片描述

//删除尾部
Node* DoubleLinkList::removeLast()
{
	if (length == 0) {
		return nullptr;
	}
	Node* temp = tail;
	if (length == 1) {
		head = nullptr;
		tail = nullptr;
	}
	else {
		tail = tail->prev;
		tail->next = nullptr;
		temp->prev = nullptr;
	}
	length--;
	return temp;
}

2. 头部删除

1.新建一个节点temp指向头结点head
2.head节点移动到head的next指针指向的节点
3.head的prev指针指向nullptr
4.temp节点的next指针指向nullptr

在这里插入图片描述

//删除头部
Node* DoubleLinkList::removeFirst()
{
	if (length == 0) {
		return nullptr;
	}
	Node* temp = head;
	if (length == 1) {
		head = nullptr;
		tail = nullptr;
	}
	else {
		head = head->next;
		head->prev = nullptr;
		temp->next = nullptr;
	}
	length--;
	return temp;
}

3. 任意位置删除

1.新建一个节点temp指向头结点head
2.temp移动到要删除的节点处
3.temp的next节点的prev指针指向temp的prev节点
4.temp的prev节点的next指针指向temp的next节点
5.temp的next节点指向nullptr
6.temp的prev节点指向nullptr

在这里插入图片描述

//删除任意位置
Node* DoubleLinkList::remove(int index)
{
	if (index<0 || index>length) {
		return nullptr;
	}
	if (index == 0) {
		return removeFirst();
	}
	if (index == length - 1) {
		return removeLast();
	}
	Node* temp = head;
	for (int i = 0; i < index; i++) {
		temp = temp->next;
	}
	temp->next->prev = temp->prev;
	temp->prev->next = temp->next;
	temp->next = nullptr;
	temp->prev = nullptr;
	length--;
	return temp;
}

获取元素

1.比较索引和链表长度的大小
2.若索引比length小，则在链表的前一半向后找
3.若索引比length大，则在链表的后一半向前找

在这里插入图片描述

//获取元素
Node* DoubleLinkList::get(int index)
{
	
	if (index<0 || index>length) {
		return nullptr;
	}
	Node* temp = head;
	if (index < length / 2) {
		for (int i = 0; i < index; i++) {
			temp = temp->next;
		}
	}
	else {
		temp = tail;
		for (int i = length - 1; i > index; i--) {
			temp = temp->prev;
		}
	}
	return temp;
}

改变元素

1.获取节点
2.将节点的值改为需要的值即可

在这里插入图片描述

//改变元素
bool DoubleLinkList::change(int index, int val)
{
	Node* temp = get(index);
	if (temp) {
		temp -> value = val;
		return true;
	}
	return false;
}

查找元素

1.新建一个节点temp指向头结点head
2.不断向后移动temp并判断temp是否威空
3.最终返回索引

//查找元素
int DoubleLinkList::search(int val)
{
	int index = 0;
	Node* temp = head;
	while (temp->value != val) {
		index++;
		temp = temp->next;
		if (temp == nullptr) {
			cout << "未找到！" << endl;
			return -1;
		}
	}
	cout << "找到了！元素索引为：";
	return index;
}

测试：新建一个main文件进行测试

#include<iostream>
#include"Node.h"
#include"DoubleLinkList.h"

using namespace std;

void test01() {
	DoubleLinkList* myList = new DoubleLinkList(1);
	myList->append(3);
	myList->append(5);
	myList->append(7);
	myList->append(9);
	myList->PrintDoubleLinkList();
	myList->getLength();
}

void test02() {
	DoubleLinkList* myList1 = new DoubleLinkList(1);
	myList1->append(3);
	myList1->append(5);
	myList1->append(7);
	myList1->append(9);
	//myList1->insert(5, 4);
	//myList1->removeLast();
	//myList1->remove(2);
	//cout<<myList1->get(4)->value<<endl;
	//myList1->change(2, 4);
	cout<<myList1->search(5)<<endl;
	myList1->PrintDoubleLinkList();
	myList1->getLength();
}

int main() {
	//test01();
	test02();
}

测试结果如下：
在这里插入图片描述

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

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

相关文章

深度学习笔记（六）——网络优化（2）：参数更新优化器SGD、SGDM、AdaGrad、RMSProp、Adam

深度学习笔记（六）——网络优化（2）：参数更新优化器SGD、SGDM、AdaGrad、RMSProp、Adam

文中程序以Tensorflow-2.6.0为例 部分概念包含笔者个人理解&#xff0c;如有遗漏或错误&#xff0c;欢迎评论或私信指正。 截图和程序部分引用自北京大学机器学习公开课 在前面的博文中已经学习了构建神经网络的基础需求&#xff0c;搭建了一个简单的双层网络结构来实现数据的分…
阅读更多...
【设计模式】什么场景可以考虑使用简单工厂模式

【设计模式】什么场景可以考虑使用简单工厂模式

1.概述 工厂模式是一种创建型模式&#xff0c;主要作用就是创建对象&#xff0c;将对象的创建过程和使用的过程进行解耦。我们平时说的工厂模式实际上是对三种不同类型的工厂模式的统称&#xff0c;简单工厂、工厂方法、抽象工厂&#xff0c;而在23种设计模式中&#xff0c;只…
阅读更多...
VSCode编写 C/C++ 程序

VSCode编写 C/C++ 程序

VSCode 全称 Visual Studio Code&#xff0c;是微软出的一款轻量级代码编辑器&#xff0c;免费、开源而且功能强大。它支持几乎所有主流的程序语言的语法高亮、智能代码补全、自定义热键、括号匹配、代码片段、代码对比 Diff、GIT 等特性&#xff0c;支持插件扩展&#xff0c;并…
阅读更多...
SG-8101CGA 系列 (晶体振荡器 可编程 可用 +125°C )

SG-8101CGA 系列 (晶体振荡器 可编程 可用 +125°C )

SG-8101CGA是可编程晶体振荡器&#xff0c;具有CMOS输出&#xff0c;适用于汽车&#xff0c;同时&#xff0c;该系列还提供相同的频率和其他参数的轻松编程能力&#xff0c;符合AEC-Q100标准&#xff0c;具有出色的电磁兼容性和稳定性&#xff0c;可以在各种环境下使用。外部尺…
阅读更多...
Linux下编写zlg7290驱动(1)

Linux下编写zlg7290驱动(1)

大家好&#xff0c;今天给大家介绍Linux下编写zlg7290驱动(1)&#xff0c;文章末尾附有分享大家一个资料包&#xff0c;差不多150多G。里面学习内容、面经、项目都比较新也比较全&#xff01;可进群免费领取。 在智能仪表中&#xff0c;经常会用到键盘、数码管等外设。因此&…
阅读更多...
Windows Server 2012 R2部署项目

Windows Server 2012 R2部署项目

JDK 下载JDK 1.直接官网下载&#xff1a;http://www.oracle.com/&#xff1b; 2.我用的是1.8&#xff0c;阿里云盘分享地址&#xff1a;https://www.aliyundrive.com/s/u4V9x1AHL2r 安装jdk 双击安装点击下一步如果不改变路径就一直下一步 安装完成直接点击关闭即可&#x…
阅读更多...
高光谱分类论文解读分享之基于形态卷积神经网络的高光谱影像分类

高光谱分类论文解读分享之基于形态卷积神经网络的高光谱影像分类

IEEE TGRS 2021&#xff1a;基于形态卷积神经网络的高光谱影像分类 题目 Morphological Convolutional Neural Networks for Hyperspectral Image Classification 作者 Swalpa Kumar Roy; Ranjan Mondal; Mercedes E. Paoletti; Juan M. Haut; Antonio Plaza 关键词 Clas…
阅读更多...
鸿蒙开发基础-Web组件之cookie操作

鸿蒙开发基础-Web组件之cookie操作

使用ArkTS语言实现一个简单的免登录过程&#xff0c;向大家介绍基本的cookie管理操作。主要包含以下功能&#xff1a; 获取指定url对应的cookie的值。设置cookie。清除所有cookie。免登录访问账户中心。 cookie读写操作 首次打开应用时&#xff0c;应用首页的Web组件内呈现的…
阅读更多...
008定点小数、奇偶校验码

008定点小数、奇偶校验码

阅读更多...
【OJ】环形链表

【OJ】环形链表

目录 1. 环形链表||&#xff08;142&#xff09;1.1 题目描述1.2 题目分析1.3 代码 2. 环形链表&#xff08;141&#xff09;2.1 题目描述2.2 题目分析2.3 代码 1. 环形链表||&#xff08;142&#xff09; 1.1 题目描述 1.2 题目分析 带环链表&#xff1a;尾节点的next指向链…
阅读更多...
Windows之任意文件删除到提权

Windows之任意文件删除到提权

前言 ZDI 发表过从任意文件夹删除到提权的利用过程&#xff0c;还提供了任意文件删除到提权的利用过程&#xff0c;所以一字之差但是漏洞利用方式也是有细微偏差的。 这里把任意文件删除和任意文件夹删除漏洞提权结合起来分析&#xff0c;是因为其最后的利用过程是一样的&…
阅读更多...
第二节课 书生·浦语大模型趣味 Demo笔记及作业

第二节课 书生·浦语大模型趣味 Demo笔记及作业

文章目录 笔记作业基础作业&#xff1a;进阶作业&#xff1a; 笔记 书生浦语大模型InternLM-Chat-7B 智能对话 Demo&#xff1a;https://blog.csdn.net/m0_49289284/article/details/135412067书生浦语大模型Lagent 智能体工具调用 Demo&#xff1a;https://blog.csdn.net/m0_…
阅读更多...
k8s node节点加入集群，token过期

k8s node节点加入集群，token过期

1、master01节点执行 kubeadm token create --print-join-command 2、执行命令 kubeadm join 192.168.0.236:16443 --token qucd8q.hsfq4a1afluzaky3 --discovery-token-ca-cert-hash sha256:92175a356db070deb2ddd3823e288e3005a4baeec9b68580dcc11ce4d3767195 3、查看node02…
阅读更多...
C++学习笔记——SLT六大组件及头文件

C++学习笔记——SLT六大组件及头文件

目录 一、C中STL&#xff08;Standard Template Library&#xff09; 二、 Gun源代码开发精神 三、 实现版本 四、GNU C库的头文件分布 bits目录 ext目录 backward目录 iostream目录 stdexcept目录 string目录 上一篇文章&#xff1a; C标准模板库&#xff08;STL&am…
阅读更多...
光猫（无限路由器）插入可移动硬盘搭建简易版的NAS

光猫（无限路由器）插入可移动硬盘搭建简易版的NAS

1.场景分析 最近查询到了许多有关NAS的资料&#xff0c;用来替代百度云盘等确实有很多优势&#xff0c;尤其是具有不限速&#xff08;速度看自己配置&#xff09;、私密性好、一次投入后续只需要电费即可等优势。鉴于手上没有可以用的资源-cpu、机箱、内存等&#xff0c;查询到…
阅读更多...
ISO11898-闭环高速CAN网络 (125K~1Mbps)

ISO11898-闭环高速CAN网络 (125K~1Mbps)

ISO11898 标准的物理框图如下图 可理解为一个高速闭环 CAN 总线网络&#xff1b;CAN 闭环总线网络允许总线最大长度为 40m;最高速度为 1Mbps;可以看到总线的两端各有一个 120Ω 的电阻&#xff0c;此电阻作为阻抗匹配功能&#xff0c;以减少回波反射;节点就是不同的设备&#…
阅读更多...
Embeddings: What they are and why they matter

Embeddings: What they are and why they matter

embeddings 是什么意思https://simonwillison.net/2023/Oct/23/embeddings/推荐原因&#xff1a;GPT 模型的基础是一种叫做 embeddings 的技术&#xff0c;用来将文本转换成向量&#xff0c;从而可以计算出文本之间的相似度。这篇文章详细地介绍了embeddings及应用 Embeddings…
阅读更多...
HTML--CSS--边框、列表、表格样式

HTML--CSS--边框、列表、表格样式

边框样式 属性&#xff1a; border-width 边框宽度 border-style 边框外观 border-color 边框颜色 需要同时设定三个属性 border-width 边框宽度 取值为像素值 border-style 边框样式 none 无样式 dashed 虚线 solid 实线 border-color 边框颜色 如示例&#xff1a; 为div设…
阅读更多...
NLP论文阅读记录 - 2021 | WOS 使用深度强化学习及其他技术进行自动文本摘要

NLP论文阅读记录 - 2021 | WOS 使用深度强化学习及其他技术进行自动文本摘要

文章目录 前言0、论文摘要一、Introduction1.1目标问题1.2相关的尝试1.3本文贡献 二.相关工作2.1. Seq2seq 模型2.2.强化学习和序列生成2.3.自动文本摘要 三.本文方法四 实验效果4.1数据集4.2 对比模型4.3实施细节4.4评估指标4.5 实验结果4.6 细粒度分析 五 总结思考 前言 Auto…
阅读更多...
Python Matplotlib 动画教程：提高可视化吸引力的强大工具【第24篇—python：Matplotlib】

Python Matplotlib 动画教程：提高可视化吸引力的强大工具【第24篇—python：Matplotlib】

文章目录 &#x1f356; 方法一&#xff1a;使用pause()函数&#x1f680; 方法二&#xff1a;使用FuncAnimation()函数&#x1f94b; 线性图动画&#xff1a;&#x1f3bb; Python中的条形图追赶动画&#x1f30c; Python中的散点图动画&#xff1a;&#x1f6f9; 条形图追赶的…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站