基于面向对象编程，C++实现单链表

链表：在内存空间中是非连续存储

组成：链表是由一个个节点组成的，每个节点都包含两个元素：数据和指针
在这里插入图片描述

节点头文件：

建立一个ListNode.h头文件

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

	ListNode(int val);
	~ListNode();
};

节点源文件：

建立一个ListNode.cpp源文件

#include "ListNode.h"

ListNode::ListNode(int val)
{
	this->value = val;
	next = nullptr;
}

ListNode::~ListNode()
{
}

单链表：由一个个节点组成：

在这里插入图片描述

链表头文件：

建立一个ListNode.h头文件，将需要的API函数写入其中

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

	LinkList();//默认构造
	~LinkList();//默认析构
	LinkList(int val);//有参构造

	void GetLength();//获取长度
	void PrintList();//打印链表
	ListNode* get(int index);//获取元素
	void append(int val);//尾部添加元素
	void prepend(int val);//头部添加元素
	void insert(int index, int val);//插入元素
	ListNode* removeFirst();//移除头部元素
	ListNode* removeLast();//移除尾部元素
	ListNode* remove(int index);//移除元素
	void reverse();//链表翻转
	bool set(int index, int val);//修改元素
	int search(int val);//查找元素
};

链表源文件

建立LinkList.cpp源文件，实现具体的API

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

LinkList::LinkList()
{
}

LinkList::~LinkList()
{
}
                                                                                                                                                       
LinkList::LinkList(int val)
{
    ListNode* newNode = new ListNode(val);
    head = newNode;
    tail = newNode;
    length = 1;
}

void LinkList::GetLength()
{
    cout << "链表长度为：" << length << endl;
}

//打印链表
void LinkList::PrintList()
{
    ListNode* temp = head;
    while (temp != nullptr) {
        cout << temp->value << " ";
        temp = temp->next;
    }
    cout << endl;
}

//获取元素
ListNode* LinkList::get(int index)
{
    if (index < 0 || index >= length) {
        return nullptr;
    }
    ListNode* temp = head;
    for (int i = 0; i < index; i++) {
        temp = temp->next;
    }
    return temp;
}

//尾部增加元素
void LinkList::append(int val)
{
    ListNode* newNode = new ListNode(val);
    if (length == 0) {
        head = newNode;
        tail = newNode;
    }
    else {
        tail->next = newNode;
        tail = newNode;
    }
    length++;
}

//头部增加元素
void LinkList::prepend(int val)
{
    ListNode* newNode = new ListNode(val);
    if (length == 0) {
        head = newNode;
        tail = newNode;
    }
    else {
        newNode->next = head;
        head = newNode;
    }
    length++;
}

//插入元素
void LinkList::insert(int index, int val)
{
    if (index<0 || index>length) {
        cout << "error";
    }
    else if (index == 0) {
        prepend(val);
    }
    else if (index == length - 1) {
        append(val);
    }
    else {
        ListNode* pre = head;
        for (int i = 0; i < index - 1; i++) {
            pre = pre->next;
        }
        ListNode* aft = pre->next;
        ListNode* newNode = new ListNode(val);
        newNode->next = aft;
        pre->next = newNode;
        length++;
    }
}

//尾部移除元素
ListNode* LinkList::removeLast()
{
    if (length == 0) {
        return nullptr;
    }

    ListNode* temp = head;
    ListNode* prev = head;
    while (temp->next) {
        prev = temp;
        temp = temp->next;
    }
    tail = prev;
    tail->next = nullptr;
    length--;

    if (length == 0) {//链表只有一个节点，删除后为空
        head = nullptr;
        tail = nullptr;
    }
    return temp;
}

//头部移除元素
ListNode* LinkList::removeFirst()
{
    if (length == 0) {
        return nullptr;
    }

    ListNode* temp = head;
    head = head->next;
    temp->next = nullptr;
    length--;

    if (length == 0) {
        tail = nullptr;
    }
    return temp;
}

//移除元素
ListNode* LinkList::remove(int index)
{
    if (index<0 || index>length) {
        return nullptr;
    }
    if (index == 0) {
        return removeFirst();
    }
    if (index == length - 1) {
        return removeLast();
    }
    ListNode* prev = head;
    for (int i = 0; i < index-1; i++) {
        prev = prev->next;
    }
    ListNode* temp = prev->next;
    prev->next = temp->next;
    temp->next = nullptr;
    length--;
    return temp;
}

//反转
void LinkList::reverse()
{
    ListNode* temp = head;
    head = tail;
    tail = temp;
    ListNode* after = temp->next;
    ListNode* before = nullptr;
    for (int i = 0; i < length; i++) {
        after = temp->next;
        temp->next = before;
        before = temp;
        temp = after;
    }
}
//修改元素
bool LinkList::set(int index, int val)
{
    ListNode* temp = get(index);
    if (temp) {
        temp->value = val;
        return true;
    }
    return false;
}

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

测试文件：

建一个单链表.cpp文件，用一个例子进行测试

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

void test() {
	LinkList* myList1 = new LinkList(1);
	myList1->append(3);
	myList1->append(5);
	myList1->append(7);
	myList1->append(9);
	myList1->PrintList();
	myList1->search(4);
}

int main() {
	test();
}

插入元素：

对于下面的单链表，可以进行头插，尾插，中间任意位置插入
在这里插入图片描述

  1. 头部插入：

由图可以知道，在头部插入时，先将新节点的next指向头结点，然后再将头结点移动到新节点处：

在这里插入图片描述

//头部增加元素
void LinkList::prepend(int val)
{
    ListNode* newNode = new ListNode(val);//创建新节点
    if (length == 0) {//如果单链表为空，就将单链表的头结点和尾节点都指向新节点
        head = newNode;
        tail = newNode;
    }
    else {
        newNode->next = head;
        head = newNode;
    }
    length++;
}
  1. 尾部插入：

在进行尾插时，先将尾节点的next指向新节点，然后尾节点移动到新节点上

在这里插入图片描述

//尾部增加元素
void LinkList::append(int val)
{
    ListNode* newNode = new ListNode(val);
    if (length == 0) {
        head = newNode;
        tail = newNode;
    }
    else {
        tail->next = newNode;
        tail = newNode;
    }
    length++;
}
  1. 其他位置插入：

在任意位置插入节点时，有以下几种情况：
1.如果插入的位置不合法要求，返回false
2.如果index=0，头插法
3.如果index=length-1，尾插法
4.其他情况下，
（1）先创建一个临时节点pre令其指向头结点head，
（2）然后移动pre指向index处前的一个节点
（3）在创建一个节点aft指向index
（4）让新节点的next指向aft
（5）让pre节点的next指向新节点

在这里插入图片描述

//插入元素
void LinkList::insert(int index, int val)
{
    if (index<0 || index>length) {
        cout << "error";
    }
    else if (index == 0) {
        prepend(val);
    }
    else if (index == length - 1) {
        append(val);
    }
    else {
        ListNode* pre = head;
        for (int i = 0; i < index - 1; i++) {
            pre = pre->next;
        }
        ListNode* aft = pre->next;
        ListNode* newNode = new ListNode(val);
        newNode->next = aft;
        pre->next = newNode;
        length++;
    }
}

删除元素：

同样，删除节点也可以分为头删，尾删，任意位置删除
在这里插入图片描述

  1. 头部节点删除

（1）创建一个新节点指向head
（2）让head向后移一个，即head指向head的next节点
（3）然让temp的next指向head

在这里插入图片描述

2. 尾部节点删除

（1）先创建两个节点：tmp和pre指向head
（2）依次向后移动temp和pre
（3）tail节点指向pre所指的节点
（4）tail的next指向nullptr

在这里插入图片描述

3. 任意位置删除

1.判断index是否合法，不合法返回false
2.如果index=0，则头结点删除法
3.如果index=length-1，则尾节点删除法
4.如果任意位置，则：
（1）创建一个节点prev指向头结点head
（2）移动pre节点至index的前一个节点
（3）创建一个节点temp指向prev的next节点即index指向的节点
（4）让prev的next节点指向temp的next节点
（5）temp的next指向空

在这里插入图片描述

修改元素：

（1）获取该节点
（2）如果该节点不为空，将新值赋给该节点的值

//修改元素
bool LinkList::set(int index, int val)
{
    ListNode* temp = get(index);
    if (temp) {
        temp->value = val;
        return true;
    }
    return false;
}

查找元素：

（1）创建一个临时节点temp，指向头结点head
（2）依次移动temp，并判断temp是否为空
（3）找到节点并返回相应的索引

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

链表反转：

1.创建一个节点temp，指向头结点head
2.头结点和尾节点互换位置
3.创建两个节点：p1指向空，p2指向temp的下一个节点
4.在整个单链表上进行如下操作：
（1）p2指向temp的下一个节点
（2）然后temp的next指向p1
（3）p1移动至temp
（4）temp移动至p2
在这里插入图片描述

//链表反转
void LinkList::reverse()
{
    ListNode* temp = head;
    head = tail;
    tail = temp;
    ListNode* after = temp->next;
    ListNode* before = nullptr;
    for (int i = 0; i < length; i++) {
        after = temp->next;
        temp->next = before;
        before = temp;
        temp = after;
    }
}

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

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

相关文章

web前端算法简介之队列

web前端算法简介之队列

队列 队列基本操作 入队&#xff08;enqueue&#xff09;&#xff1a;将元素添加到队列的尾部。出队&#xff08;dequeue&#xff09;&#xff1a;从队列的头部移除元素。队首&#xff08;front&#xff09;&#xff1a;获取队列头部的元素&#xff0c;但不移除它。队尾&#x…
阅读更多...
【机器学习300问】5、什么是强化学习？

【机器学习300问】5、什么是强化学习？

我将从三个方面为大家简明阐述什么是强化学习&#xff0c;首先从强化学习的定义大家的了解强化学习的特点&#xff0c;其次学习强化学习里特殊的术语加深对强化学习的理解&#xff0c;最后通过和监督学习与无监督学习的比较&#xff0c;通过对比学习来了解强化学习。 一、强化…
阅读更多...
canvasdrawer 微信原生小程序生成海报图片

canvasdrawer 微信原生小程序生成海报图片

在小程序中生成海报是一种非常有效的推广方式 用户可以使用小程序的过程中生成小程序海报并分享给他人 通过海报的形式&#xff0c;用户可以直观地了解产品或服务的特点和优势 常见绘制海报方式 目前&#xff0c;小程序海报有两种常见的实现方式&#xff1a; canvas 绘制…
阅读更多...
Hive基础知识（十）：Hive导入数据的五种方式

Hive基础知识（十）：Hive导入数据的五种方式

1. 向表中装载数据&#xff08;Load&#xff09; 1&#xff09;语法 hive> load data [local] inpath 数据的 path[overwrite] into table student [partition (partcol1val1,…)]; &#xff08;1&#xff09;load data:表示加载数据 &#xff08;2&#xff09;local:表示…
阅读更多...
视频SDK的技术架构优势和价值

视频SDK的技术架构优势和价值

为了满足企业对于高质量视频的需求&#xff0c;美摄科技推出了一款强大的视频SDK&#xff08;软件开发工具包&#xff09;&#xff0c;旨在帮助企业轻松实现高效、稳定的视频功能&#xff0c;提升用户体验&#xff0c;增强企业竞争力。 一、美摄视频SDK的技术实现方式 美摄视…
阅读更多...
【软件测试】学习笔记-静态测试方法

【软件测试】学习笔记-静态测试方法

这篇文章详细讨论人工静态测试方法和自动静态测试方法&#xff0c;来帮你理解研发流程上是如何保证代码质量的&#xff0c;以及如何搭建自己的自动静态代码扫描方案&#xff0c;并且应用到项目的日常开发工作中去。 人工静态方法本质上属于流程上的实践&#xff0c;实际能够发…
阅读更多...
详解Java多线程之循环栅栏技术CyclicBarrier

详解Java多线程之循环栅栏技术CyclicBarrier

第1章&#xff1a;引言 大家好&#xff0c;我是小黑&#xff0c;工作中&#xff0c;咱们经常会遇到需要多个线程协同工作的情况。CyclicBarrier&#xff0c;直译过来就是“循环屏障”。它是Java中用于管理一组线程&#xff0c;并让它们在某个点上同步的工具。简单来说&#xf…
阅读更多...
[AutoSar]BSW_OS 01 Autosar OS入门（一）

[AutoSar]BSW_OS 01 Autosar OS入门（一）

目录 关键词平台说明一、Autosar OS 的位置二、Autosar OS 与OSEK三、TASK 关键词 嵌入式、C语言、autosar、OS、BSW 平台说明 项目ValueOSautosar OSautosar厂商vector芯片厂商TI编程语言C&#xff0c;C编译器HighTec (GCC) 一、Autosar OS 的位置 如在[AutoSar]基础部分 a…
阅读更多...
imgaug库指南（19）：从入门到精通的【图像增强】之旅

imgaug库指南（19）：从入门到精通的【图像增强】之旅

引言 在深度学习和计算机视觉的世界里&#xff0c;数据是模型训练的基石&#xff0c;其质量与数量直接影响着模型的性能。然而&#xff0c;获取大量高质量的标注数据往往需要耗费大量的时间和资源。正因如此&#xff0c;数据增强技术应运而生&#xff0c;成为了解决这一问题的…
阅读更多...
教程-右键用vscode(新窗口)打开文件或目录

教程-右键用vscode(新窗口)打开文件或目录

通过本文可以提高效率&#xff0c;用起来更爽更高效。 本文实现了&#xff08;windows系统&#xff09;&#xff1a; 右键-用vscode(当前窗口)打开文件或目录右键-用vscode-新窗口打开文件或目录 注意&#xff1a; 下面的安装路径要更改为您实际的路径 具体配置步骤&#x…
阅读更多...
案例117:基于微信小程序的新闻资讯系统设计与实现

案例117:基于微信小程序的新闻资讯系统设计与实现

文末获取源码 开发语言&#xff1a;Java 框架&#xff1a;springboot JDK版本&#xff1a;JDK1.8 数据库&#xff1a;mysql 5.7 开发软件&#xff1a;eclipse/myeclipse/idea Maven包&#xff1a;Maven3.5.4 小程序框架&#xff1a;uniapp 小程序开发软件&#xff1a;HBuilder …
阅读更多...
使用ArduinoMqttClient库连接阿里云，并实现发送接收数据（ESP8266）

使用ArduinoMqttClient库连接阿里云，并实现发送接收数据（ESP8266）

文章目录 引言一、MQTT理论部分二、使用MQTT.fx接入物联网设备三、使用ESP8266连接阿里云四、参考例程 引言 阿里云物联网平台的接入方式有很多种&#xff0c;从阿里云提供的开发文档可以看到&#xff0c;支持的接入协议有MQTT、HTTPS、CoAP、JT/808、GB/32960协议等等&#x…
阅读更多...
算法学习系列（十九）：DFS、BFS

算法学习系列（十九）：DFS、BFS

目录 引言一、DFS1.排列数字2.n-皇后问题 二、BFS1.走迷宫2.八数码问题 引言 关于这个DFS与BFS的问题非常的常见&#xff0c;其实这两个就是搜索的方式不一样而已&#xff0c;核心思想非常容易懂&#xff0c;题目的话也是做一道记一道&#xff0c;还是要针对题来看&#xff0c…
阅读更多...
Asp .Net Core 系列： 集成 CORS跨域配置

Asp .Net Core 系列： 集成 CORS跨域配置

文章目录 什么是CORS?Asp .Net Core 中如何配置CORS?CorsPolicyBuilder类详解注册以及使用策略三种方式EnableCors 和 DisableCors 特性关于带证书与不带证书代码的实现跨源&#xff08;cross-origin&#xff09;不带请求证书(Credentials)跨源&#xff08;cross-origin&…
阅读更多...
InternLM第3次课作业

InternLM第3次课作业

部署 参考github教程&#xff1a;https://github.com/InternLM/tutorial/tree/main/langchain 问题1&#xff1a; windows端口映射过程命令 ssh -i C:\\Users\\breat/.ssh/id_rsa.pub -CNg -L 7860:127.0.0.1:7860 rootssh.intern-ai.org.cn -p 3 4145 中&#xff0c;提示找不…
阅读更多...
哈希-力扣350. 两个数组的交集Ⅱ

哈希-力扣350. 两个数组的交集Ⅱ

题目 给你两个整数数组 nums1 和 nums2 &#xff0c;请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数&#xff0c;应与元素在两个数组中都出现的次数一致&#xff08;如果出现次数不一致&#xff0c;则考虑取较小值&#xff09;。可以不考虑输出结果的顺序。 示…
阅读更多...
详细分析Java中的@JsonSerialize注解

详细分析Java中的@JsonSerialize注解

目录 前言1. 核心知识2. 基本知识3. Demo3.1 jsontest13.2 jsontest2 4. 总结 前言 对应序列化的相关知识可看我之前的文章&#xff1a;详解Java中的serialVersionUID概念以及作用&#xff08;附上Demo&#xff09; 通过理解核心知识&#xff0c;再去品味总结的基本知识&#…
阅读更多...
聚对苯二甲酸乙二醇酯PET的特性有哪些？UV胶水能够粘接聚对苯二甲酸乙二醇酯PET吗？又有哪些优势呢？

聚对苯二甲酸乙二醇酯PET的特性有哪些？UV胶水能够粘接聚对苯二甲酸乙二醇酯PET吗？又有哪些优势呢？

聚对苯二甲酸乙二醇酯&#xff08;Polyethylene Terephthalate&#xff0c;PET&#xff09;是一种常见的塑料材料&#xff0c;具有许多特性&#xff0c;包括&#xff1a; 1.化学式&#xff1a; PET的化学式为 (C10H8O4)n&#xff0c;其中n表示重复单元的数量。 2.透明度&#…
阅读更多...
Redis-redis事务、乐观锁、Jedis、SpringBoot整合Redis

Redis-redis事务、乐观锁、Jedis、SpringBoot整合Redis

五、事务 1、事务 ①开启事务、执行事务 127.0.0.1:6379> multi # 开启事务 OK # 入队 127.0.0.1:6379> set k1 v1 QUEUED 127.0.0.1:6379> set k2 v2 QUEUED 127.0.0.1:6379> get k2 QUEUED 127.0.0.1:6379> set k3 v3 QUEUED 127.0.0.1:6379> …
阅读更多...
PyCharm连接服务器（利用PyCharm实现远程开发）

PyCharm连接服务器（利用PyCharm实现远程开发）

利用PyCharm实现远程开发 注&#xff1a;该功能只有在PyCharm专业版下才可以使用&#xff0c;并且必须是官方的正版许可&#xff0c;破解版的是不可以使用的&#xff01;&#xff01;&#xff01;可以通过免费教育许可申请使用权限&#xff08;申请流程&#xff09;。 pycharm…
阅读更多...
最新文章

Copyright @ 2022~2023