首页 > 编程语言 >数据结构与算法 - 链表

数据结构与算法 - 链表

时间:2023-06-30 09:04:10浏览次数:57  
标签:include 21 list 链表 算法 test 数据结构 ptr name

双链表的的基本结构

从 STL 源码抽出的基本双链表结构

代码

#ifndef _GRAVER_GLIB_LIST_H_
#define _GRAVER_GLIB_LIST_H_

#include <cstddef>

#include "graver/util/log_util.h"

namespace graver {

// 内部结构与方法放在 detail
namespace detail {

/**
 * @brief 链表结点
 * 
 * @tparam T 数据类型
 */
template <typename T>
class ListNode {
public:
    ListNode() {
        prev = nullptr;
        next = nullptr;
    }

    ListNode(T value) {
        prev = nullptr;
        next = nullptr;
        data = value;
    }

public:
    /**
     * @brief 前一个结点指针
     */
    ListNode<T>* prev;
    /**
     * @brief 后一个结点指针
     */
    ListNode<T>* next;
    /**
     * @brief 数据
     */
    T data;
};

/**
 * @brief 迭代器
 * 
 * @tparam T 数据类型
 */
template <typename T>
class ListIterator {
public:
    ListIterator(ListNode<T>* ptr = nullptr) : _ptr(ptr){};
    T& operator*() const {
        return *static_cast<T*>(static_cast<void*>(&_ptr->data));
    };
    T* operator->() const {
        return static_cast<T*>(static_cast<void*>(&_ptr->data));
    }
    ListIterator& operator++() {
        _ptr = _ptr->next;
        return *this;
    }
    ListIterator operator++(int) {
        auto tmp = *this;
        _ptr     = _ptr->next;
        return tmp;
    }
    bool operator==(const ListIterator& it) const {
        return _ptr == it._ptr;
    }
    bool operator!=(const ListIterator& it) const {
        return _ptr != it._ptr;
    }

private:
    ListNode<T>* _ptr;
};

}  // namespace detail

/**
 * @brief 链表
 * 
 * @tparam T 数据类型
 */
template <typename T>
class List {
private:
    typedef detail::ListNode<T> _Node;

public:
    typedef detail::ListIterator<T> iterator;

public:
    List() {
        dzlog_info("List constructor");
        _head = new _Node();
        _tail = new _Node();

        _head->prev = nullptr;
        _head->next = _tail;
        _tail->prev = _head;
        _tail->next = nullptr;

        _length = 0;
    }
    ~List() {
        dzlog_info("List destructor");
        clear();
        delete _head;
        delete _tail;
    }

public:
    // 返回指向起始的迭代器
    iterator begin() noexcept {
        return iterator(_head->next);
    }
    // 返回指向末尾的迭代器
    iterator end() {
        return iterator(_tail);
    }

public:
    // 是否为空
    bool empty() {
        return 0 == size();
    }
    // 元素数量
    size_t size() const {
        return _length;
    }

public:
    // 清空链表
    void clear() {
        while (!empty()) {
            pop_back();
        }
    }
    // 尾部追加元素
    void push_back(const T& value) {
        detail::ListNode<T>* node = new _Node();
        node->data                = value;

        _tail->prev->next = node;
        node->prev        = _tail->prev;
        node->next        = _tail;
        _tail->prev       = node;

        _length++;
    }

    // 尾部移除
    void pop_back() {
        if (empty()) {
            return;
        }

        auto removeNode = _tail->prev;
        _tail->prev     = removeNode->prev;
        delete removeNode;
        _length--;
    }

private:
    /**
     * @brief 头结点
     */
    _Node* _head;
    /**
     * @brief 尾结点
     */
    _Node* _tail;
    /**
     * @brief 链表长度
     */
    size_t _length;
};

}  // namespace graver

#endif

测试

测试数据定义

#ifndef _GRAVER_TEST_TEST_TYPE_H_
#define _GRAVER_TEST_TEST_TYPE_H_

#include <string>

#include "fmt/core.h"
#include "graver/util/log_util.h"

struct Person {
    std::string name;
    int         age;

    void print() const {
        dzlog_info(fmt::format("name:{}\tage:{}", name, age).c_str());
    }
};

#endif

STL list 测试

#include <list>
#include <memory>

#include "doctest/doctest.h"
#include "fmt/core.h"
#include "graver/util/log_util.h"
#include "test_type.hpp"

TEST_SUITE("test_common") {
    TEST_CASE("test_common_one") {
        auto list = std::make_unique<std::list<Person>>();
        dzlog_info("it++");
        list->push_back({"Thresh", 18});
        list->push_back({"Syndra", 16});
        list->push_back({"Maokai", 35});
        list->push_back({"Shaco", 25});
        for (auto it = list->begin(); it != list->end(); it++) {
            (*it).print();
        }
        dzlog_info("++it");
        for (auto it = list->begin(); it != list->end(); ++it) {
            it->print();
        }
        dzlog_info("foreach");
        for (const auto& p : *list) {
            p.print();
        }
    }
}

自定义双链表测试

#include <memory>

#include "doctest/doctest.h"
#include "fmt/core.h"
#include "graver/glib/glib.h"
#include "graver/util/log_util.h"
#include "test_type.hpp"

TEST_SUITE("test_list") {
    TEST_CASE("test_list_one") {
        auto list = std::make_unique<graver::List<Person>>();
        dzlog_info("it++");
        list->push_back({"Thresh", 18});
        list->push_back({"Syndra", 16});
        list->push_back({"Maokai", 35});
        list->push_back({"Shaco", 25});
        for (auto it = list->begin(); it != list->end(); it++) {
            (*it).print();
        }
        dzlog_info("++it");
        for (auto it = list->begin(); it != list->end(); ++it) {
            it->print();
        }
        dzlog_info("foreach");
        for (const auto& p : *list) {
            p.print();
        }
    }
}

输出结果

2023-06-28 07:21:24.978 6716 INFO [test_type.hpp:14] - name:Thresh      age:18
2023-06-28 07:21:24.978 6716 INFO [test_type.hpp:14] - name:Syndra      age:16
2023-06-28 07:21:24.978 6716 INFO [test_type.hpp:14] - name:Maokai      age:35
2023-06-28 07:21:24.978 6716 INFO [test_type.hpp:14] - name:Shaco       age:25
2023-06-28 07:21:24.979 6716 INFO [test_list.cpp:20] - ++it
2023-06-28 07:21:24.979 6716 INFO [test_type.hpp:14] - name:Thresh      age:18
2023-06-28 07:21:24.979 6716 INFO [test_type.hpp:14] - name:Syndra      age:16
2023-06-28 07:21:24.979 6716 INFO [test_type.hpp:14] - name:Maokai      age:35
2023-06-28 07:21:24.979 6716 INFO [test_type.hpp:14] - name:Shaco       age:25
2023-06-28 07:21:24.980 6716 INFO [test_list.cpp:24] - foreach
2023-06-28 07:21:24.980 6716 INFO [test_type.hpp:14] - name:Thresh      age:18
2023-06-28 07:21:24.980 6716 INFO [test_type.hpp:14] - name:Syndra      age:16
2023-06-28 07:21:24.980 6716 INFO [test_type.hpp:14] - name:Maokai      age:35
2023-06-28 07:21:24.981 6716 INFO [test_type.hpp:14] - name:Shaco       age:25

leetcode 链表题目

21. 合并两个有序链表
解题过程记录: 【leetcode】【21】【合并两个有序链表】

标签:include,21,list,链表,算法,test,数据结构,ptr,name
From: https://www.cnblogs.com/khlbat/p/17515668.html

相关文章

  • prim算法
    #include<stdio.h>#defineN20#defineTRUE1#defineINF32766#defineINFIN32767typedefstruct{ intvexnum,arcnum; charvexs[N]; intarcs[N][N];}MGraph;voidcreateMGraph_w(MGraph*g);voidprim(MGraph*g,intu);//创建带权无向图的邻接矩阵void......
  • 数据结构和算法-2023.06.29
    斐波那契数列初衷......
  • 欧几里得(及其扩展算法)
    欧几里得算法算法内容计算两个数的最大公约数的算法,也叫辗转相除法。即:gcd(a,b)=gcd(b,a%b)。数学证明设gcd(a,b)=d,则必定有:d|a且d|b,则必定有d|(ax+by)而a%b=a-a/b*b,所以d|(a%b),则d必定为b和a%b的约数,并且a%b必定小于a则d必定为b和a%b的最大公约数。-代码实现优美,太优......
  • MATLAB代码:基于粒子群算法的储能优化配置 关键词:储能优化配置 粒子群 储能充放电优
    MATLAB代码:基于粒子群算法的储能优化配置关键词:储能优化配置粒子群 储能充放电优化 参考文档:无明显参考文档,仅有几篇文献可以适当参考仿真平台:MATLAB平台采用粒子群实现求解优势:代码注释详实,适合参考学习,非目前烂大街的版本,程序非常精品,请仔细辨识 主要内容:建立了储能的......
  • 电子凸轮追剪曲线生成算法
    电子凸轮追剪曲线生成算法。品牌:麦格米特(算法,理解后可转成其他品牌PLC或任何一种编程语言)只有程序原创文章,转载请说明出处,资料来源:http://imgcs.cn/5c/633554519425.html......
  • 音乐推荐系统 系统算法:基于用户的协同过滤推荐算法
    音乐推荐系统系统算法:基于用户的协同过滤推荐算法编程语言:python数据库:sqlite框架:MVCweb应用框架:Django解压就可以运行(自己需要有调试项目环境的能力),需要软件python和pycharm或者Anaconda项目有配套的文档原创文章,转载请说明出处,资料来源:http://imgcs.cn/5c/678695319073.......
  • 基于Matlab的主动配电网实时无功优化 考虑风电和光伏的接入,采用多目标粒子群算法,以网
    基于Matlab的主动配电网实时无功优化考虑风电和光伏的接入,采用多目标粒子群算法,以网损和电压偏差为目标,优化变压器分接头、无功补偿器实现24小时无功优化,算例采用IEEE33进行仿真分析,对优化前后的电压和网损进行了分析。这段程序主要是一个多目标粒子群优化算法(MOPSO),用于解决电力......
  • 【数据结构】选择排序 与 堆排序
    ☑️前言......
  • 基于粒子群算法的电力系统最优潮流 以IEEE30节点的六机为对象,建立考虑功率平衡、机组
    基于粒子群算法的电力系统最优潮流以IEEE30节点的六机为对象,建立考虑功率平衡、机组爬坡约束、出力限制约束的电力系统经济调度模型,采用粒子群算法对模型进行求解,得到六个机组的最优运行计划,确定系统最优运行成本。这段程序主要是一个基于粒子群优化算法(PSO)的电力系统调度程序。......
  • 文心一言 VS 讯飞星火 VS chatgpt (51)-- 算法导论6.2 3题
    三、当元素A[i]比其孩子的值都大时,调用MAX-HEAPIFY(A.i)会有什么结果?文心一言:当元素A[i]比其孩子的的值都大时,调用MAX-HEAPIFY(A,i)会将A[i]与其孩子中的最小值进行交换,并将A[i]视为新的根节点。这个操作会使得以A[i]为根节点的子树满足最大堆的性质,即根节点比其左......