1. Toy模板网首页
  2. > Toy博客

C++数据结构与算法详解：链表、栈、队列、树、二叉树和图结构的实现与应用

7月前 作者：格林希尔 分类：Toy博客 阅读(31) 违法举报

这篇具有很好参考价值的文章主要介绍了C++数据结构与算法详解：链表、栈、队列、树、二叉树和图结构的实现与应用。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、链表

1.1 定义

链表是一种常见的数据结构由一系列节点按顺序连接而成，一般每个节点包含一个数据元素和一个指向下一个节点的引用。
链表有多种类型：

  • 单向链表：每个节点只有一个指向下一个节点的引用
  • 双向链表：每个节点有一个指向前一个节点和一个指向后一个节点的引用
  • 循环链表：尾节点指向头节点形成循环
  • 双向循环链表：既是双向链表又是循环链表

1.2 实现

1.2.1 单向链表

单向链表是指每个节点包含一个指向下一个节点的指针，最后一个节点的指针为NULL。
以下是单向链表的基本结构：

struct ListNode 
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

1.2.2 双向链表

双向链表是在单向链表的基础上，每个节点还包含一个指向上一个节点的指针。
以下是双向链表的基本结构：

struct ListNode 
{
    int val;
    ListNode *prev;
    ListNode *next;
    ListNode(int x) : val(x), prev(NULL), next(NULL) {}
};

1.2.3 常见操作(反转 合并 查找)

/* 链表反转 */
Node* reverseLinkedList(Node* head) {
    Node* newHead = nullptr;
    while(head != nullptr) {
        Node* tmp = head->next;
        head->next = newHead;
        newHead = head;
        head = tmp;
    }
    return newHead;
}

/* 链表合并 */
Node* mergeLinkedList(Node* head1, Node* head2) {
    Node* dummy = new Node;
    Node* cur = dummy;
    while(head1 != nullptr && head2 != nullptr) {
        if(head1->data < head2->data) {
            cur->next = head1;
            head1 = head1->next;
        } else {
            cur->next = head2;
            head2 = head2->next;
        }
        cur = cur->next;
    }
    cur->next = (head1 != nullptr ? head1 : head2);
    return dummy->next;
}

/* 链表查找 */
Node* findNode(Node* head, int data) {
    Node* cur = head;
    while(cur != nullptr && cur->data != data) {
        cur = cur->next;
    }
    return cur;
}

1.3 应用

链表在程序中有着多种应用 例如：

  • 实现LRU缓存淘汰算法
  • 实现文件系统中的文件块分配
  • 链表作为数据流的缓冲区

使用双向循环链表实现的LRU缓存示例：

class LRUCache 
{
private:
    struct CacheNode 
    {
        int key;
        int value;
        CacheNode(int k, int v) : key(k), value(v) {}
    };

    int capacity;
    list<CacheNode> cacheList;
    unordered_map<int, list<CacheNode>::iterator> cacheMap;

public:
    LRUCache(int capacity) 
    {
        this->capacity = capacity;
    }

    int get(int key) 
    {
        if (cacheMap.find(key) == cacheMap.end()) 
        {
            return -1;
        }
        // 把当前节点移到链表头部
        cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
        return cacheMap[key]->value;
    }

    void put(int key, int value) 
    {
        if (cacheMap.find(key) == cacheMap.end()) 
        {
            if (cacheList.size() == capacity) 
            {
                // 删除链表最后一个节点
                int key = cacheList.back().key;
                cacheMap.erase(key);
                cacheList.pop_back();
            }
            cacheList.push_front(CacheNode(key, value));
            cacheMap[key] = cacheList.begin();
        } 
        else 
        {
            // 修改节点的值，并移到链表头部
            cacheMap[key]->value = value;
            cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
        }
    }
};

使用LRU缓存：

LRUCache cache = LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
cout << cache.get(1) << endl; // 输出 1
cache.put(3, 3);
cout << cache.get(2) << endl; // 输出 -1，因为键 2 已经被删除了
cache.put(4, 4);
cout << cache.get(1) << endl; // 输出 -1，因为键 1 已经被删除了
cout << cache.get(3) << endl; // 输出 3
cout << cache.get(4) << endl; // 输出 4

二、 栈-Stack 队列-Queue

1.1 定义

  • 栈(Stack)：后进先出(LIFO: Last In First Out)
  • 队列(Queue)：先进先出(FIFO: First In First Out)

栈和队列是C++提供的两种基本数据类型，定义如下：

// 栈的定义
template <class T> class Stack {
public:
    Stack();                // 构造函数
    void push(const T&);    // 将元素加入栈顶，返回 void
    void pop();             // 移除栈顶的元素，返回 void
    T& top();               // 返回栈顶元素的引用，不移除该元素
    const T& top() const;   // 返回常量栈顶元素的引用，不移除该元素
    bool empty() const;     // 判断栈是否为空，返回 bool
    int size() const;       // 返回栈中元素的个数
};

// 队列的定义
template<class T> class Queue {
public:
    Queue();                // 构造函数
    void push(const T&);    // 将元素加入队尾，返回 void
    void pop();             // 移除队头的元素，返回 void
    T& front();             // 返回队头元素的引用，不移除该元素
    const T& front() const; // 返回常量队头元素的引用，不移除该元素
    bool empty() const;     // 判断队是否为空，返回 bool
    int size() const;       // 返回队中元素的个数
};

1.2 实现

栈和队列的实现方法比较简单可以使用数组或链表来实现

1.2.1 数组实现 栈和队列 示例：

// 数组实现的栈
template <class T> class Stack {
    T* a;
    int n;              // 栈的大小
    int t;              // 栈顶元素的下标
public:
    Stack(int maxn) {
        a = new T[maxn];
        n = maxn;
        t = -1;
    }
    bool empty() const {
        return t == -1;
    }
    void push(const T& x) {
        a[++t] = x;
    }
    void pop() {
        --t;
    }
    T top() const {
        return a[t];
    }
};

// 数组实现的队列
template<class T> class Queue {
    T* a;               
    int n;              // 队列的大小
    int head, tail;     // 队头和队尾的下标
public:
    Queue(int maxn) {
        a = new T[maxn];
        n = maxn;
        head = 0;
        tail = -1;
    }
    bool empty() const {
        return head > tail;
    }
    void push(const T& x) {
        a[++tail] = x;
    }
    void pop() {
        ++head;
    }
    T front() const {
        return a[head];
    }
};

1.2.3链表实现 栈和队列 示例：

// 链表实现的栈
template <class T> class Stack {
    // 定义链表节点
    struct node {
        T data;
        node* next;
        node(const T& d, node* n = nullptr): data(d), next(n) {}
    };
    node* t;            // 栈顶节点
public:
    Stack() : t(nullptr) {}    // 默认构造函数
    bool empty() const {
        return t == nullptr;
    }
    void push(const T& x) {
        t = new node(x, t);
    }
    void pop() {
        node* tmp = t;
        t = t->next;
        delete tmp;
    }
    T& top() const {
        return t->data;
    }
};

// 链表实现的队列
template <class T> class Queue {
    // 定义链表节点
    struct node {
        T data;
        node* next;
        node(const T& d, node* n = nullptr) : data(d), next(n) {}
    };
    node* head;         // 队头节点
    node* tail;         // 队尾节点
public:
    Queue() : head(nullptr), tail(nullptr) {}    // 默认构造函数
    bool empty() const {
        return head == nullptr;
    }
    void push(const T& x) {
        if (tail != nullptr) {
            tail->next = new node(x);
            tail = tail->next;
        } else {
            head = tail = new node(x);
        }
    }
    void pop() {
        node* tmp = head;
        head = head->next;
        delete tmp;
        if (head == nullptr) {
            tail = nullptr;
        }
    }
    T& front() const {
        return head->data;
    }
};

1.3 应用

栈和队列是常用的数据结构在程序中的应用广泛，例如：

  • 表达式求值
  • 函数调用
  • 网络请求处理
  • 路径搜索

如下使用栈来实现表达式求值示例：

// 使用栈来实现表达式求值
double calc(const string& s) {
    Stack<double> stk;
    for (int i = 0; i < s.size(); ++i) {
        if (isdigit(s[i])) {
            int j = i;
            while (j < s.size() && (isdigit(s[j]) || s[j] == '.')) ++j;
            stk.push(stod(s.substr(i, j - i)));
            i = j - 1;
        } else if (s[i] == '+') {
            double b = stk.top(); stk.pop();
            double a = stk.top(); stk.pop();
            stk.push(a + b);
        } else if (s[i] == '-') {
            double b = stk.top(); stk.pop();
            double a = stk.top(); stk.pop();
            stk.push(a - b);
        } else if (s[i] == '*') {
            double b = stk.top(); stk.pop();
            double a = stk.top(); stk.pop();
            stk.push(a * b);
        } else if (s[i] == '/') {
            double b = stk.top(); stk.pop();
            double a = stk.top(); stk.pop();
            stk.push(a / b);
        }
    }
    return stk.top();
}

三、树和二叉树

1.1 定义

1.1.1 树的定义

树是一种非线性的数据结构，它由n个节点组成的有限集合，其中每个节点是一个具有唯一标识的对象，且节点之间存在着一些特定的关系。通常这些关系可以用父子关系来描述。每个节点可以有多个子节点，但是一个节点只有一个父节点，树中有且仅有一个无父节点的节点这个节点被称为根节点。

1.1.2 树的特点

  1. 树中的每个节点都有唯一的标识
  2. 树中每个节点至少有一个子节点
  3. 树中节点之间的关系是“父子”关系
  4. 树中有且仅有一个无父节点的节点这个节点被称为根节点
  5. 树中任意两个节点之间都存在一条唯一的路径

1.1.3 二叉树的定义

二叉树是一种特殊的树结构，每个节点最多有两个子节点，它的左子节点和右子节点分别称为左子树和右子树

1.1.4 二叉树的特点

  1. 二叉树中的每个节点都有唯一的标识
  2. 一个节点最多只有两个子节点
  3. 二叉树中节点之间的关系是“父子”关系
  4. 如果二叉树中任意一个节点（除了叶子节点），其左子树不为空则左子树中的所有节点的值都小于这个节点的值.如果其右子树不为空则右子树中所有节点的值都大于这个节点的值。

1.2 实现

1.2.1 实现方法

树和二叉树可以通过结构体和指针实现，使用链式结构来描述。节点包括一个数据域和两个指针域分别指向左右子树。

// 定义树节点结构体
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

1.2.2 常用算法

  1. 先序遍历：遍历顺序为根结点、左子树、右子树。
  2. 中序遍历：遍历顺序为左子树、根结点、右子树。
  3. 后序遍历：遍历顺序为左子树、右子树、根结点。
  4. 层序遍历：按层遍历二叉树。

先序遍历的代码示例：

void preorder_traversal(TreeNode *node) {
    if (node) {
        cout << node->val << " ";
        preorder_traversal(node->left);
        preorder_traversal(node->right);
    }
}

中序遍历的代码示例：

void inorder_traversal(TreeNode *node) {
    if (node) {
        inorder_traversal(node->left);
        cout << node->val << " ";
        inorder_traversal(node->right);
    }
}

后序遍历的代码示例：

void postorder_traversal(TreeNode *node) {
    if (node) {
        postorder_traversal(node->left);
        postorder_traversal(node->right);
        cout << node->val << " ";
    }
}

层序遍历的代码示例：

void level_order_traversal(TreeNode *node) {
    queue<TreeNode *> q;
    q.push(node);
    while (!q.empty()) {
        TreeNode *temp = q.front();
        q.pop();
        cout << temp->val << " ";
        if (temp->left) {
            q.push(temp->left);
        }
        if (temp->right) {
            q.push(temp->right);
        }
    }
}

1.3 应用

在程序中的应用有：

  1. 堆排序算法
  2. 哈夫曼编码
  3. 字典树
  4. AVL树（自平衡二叉搜索树）
  5. B树和B+树（多路搜索树）

四、 图结构

1.1 定义

1.1.1 图的定义

图是一种数据结构，它由节点/顶点 (vertex）和边（edge）组成。
节点表示图中的元素而边描述它们之间的关系
在图中元素间的关系不再是父子关系而是一个相关的关系

// 定义图结构体
struct Graph {
    int V; // 节点个数
    vector<int> *adj; // 指向相邻顶点列表的指针
    Graph(int V) {
        this->V = V;
        adj = new vector<int>[V];
    }
    void addEdge(int v, int w) { // 添加一条边
        adj[v].push_back(w); // 无向图，边为双向，v->w 和 w->v 都需加入 adj 中 
        adj[w].push_back(v);
    }
};

1.1.2 图的类型

在图论中重点讨论无向图和有向图，以及它们的变种:

  1. 无向图：由节点和无向边组成的图结构，边没有方向，节点间的关系是双向的
  2. 有向图：由节点和有向边组成的图结构，边有方向，节点间的关系是单向的
  3. 带权图：除了节点和边之外还有一些权重信息
  4. 多重图：允许多个节点之间有多条边
// 定义带权图结构体
struct WeightedGraph {
    int V; // 节点个数
    vector<pair<int, int>> *adj; // pair中的第一个值表示相邻顶点，第二个值表示权重
    WeightedGraph(int V) {
        this->V = V;
        adj = new vector<pair<int, int>>[V];
    }
    void addEdge(int v, int w, int weight) { // 添加一条带权边
        adj[v].push_back(make_pair(w, weight));
        adj[w].push_back(make_pair(v, weight)); // 无向图，边为双向，v->w 和 w->v 都需加入 adj 中 
    }
};

1.2 实现

1.2.1 实现方法

  1. 邻接矩阵：使用一个二维数组表示节点与边之间的关系可以表示带权图
  2. 邻接表：使用一个数组+链表的方式表示节点与边之间的关系可以表示带权图
// 用邻接表实现的广度优先遍历算法
void bfs(Graph graph, int start) {
    bool *visited = new bool[graph.V]; // 标记节点是否被访问
    for (int i = 0; i < graph.V; ++i) {
        visited[i] = false;
    }
    queue<int> q;
    visited[start] = true; // 标记起始节点被访问
    q.push(start);
    while (!q.empty()) {
        int curr = q.front();
        cout << curr << " "; // 输出访问顺序
        q.pop();
        for (auto i = graph.adj[curr].begin(); i != graph.adj[curr].end(); ++i) {
            if (!visited[*i]) { // 如果该节点未被访问
                visited[*i] = true; // 标记该节点被访问
                q.push(*i); // 将该节点加入队列中，等待遍历
            }
        }
    }
}

1.2.2 常用算法

  1. 深度优先遍历（DFS）：以深度为优先级，沿着路径遍历，可以通过递归或栈实现
  2. 广度优先遍历（BFS）：以广度为优先级，按照“就近原则”，先遍历与起点直接相邻的节点，再遍历距离起点稍远的节点，可以使用队列实现
  3. 最短路径算法：解决两个节点之间的最短路径问题
  4. 最小生成树算法：解决连通图中，权值最小的生成树问题
// 用邻接矩阵实现的深度优先遍历算法
void dfs(int v, bool visited[], int **graph, int size) {
    visited[v] = true; // 标记该节点被访问
    cout << v << " "; // 输出访问顺序
    for (int i = 0; i < size; ++i) {
        if (graph[v][i] && !visited[i]) { // 如果该节点未被访问且与 v 有连接
            dfs(i, visited, graph, size); // 递归遍历该节点
        }
    }
}

1.3 应用

图作为一种重要的数据结构在程序中的应用有：

  1. 最短路径问题：GPS 导航
  2. 网络问题：路由算法
  3. 社交网络：朋友推荐
  4. 游戏策略：国际象棋
  5. 电路设计：电路布线

五、小结回顾

链表是一种常用的线性数据结构，它可以动态的添加或删除元素并且没有固定大小
链表是由节点组成的每个节点包含一个数据元素和一个指向下一个节点的指针

栈是一种后进先出的数据结构所有元素都在栈顶，可以理解为一种特殊的列表。
栈的基本操作包括入栈和出栈有时会使用压入和弹出这样的类比来描述这些操作。

队列是一种先进先出的数据结构所有元素被放置在队列的末尾并从队列的开头移除。
队列是一种有限制的列表它仅允许在列表的前面进行插入而仅允许在列表的后面进行删除

树是一种非线性数据结构由由节点组成，并且节点之间有特定的关系（如父节点、子节点等）
每个节点可以包含一个数据元素，还可以连接到其他节点。树被广泛应用于各种算法和数据结构中

图是一种非线性的数据结构由一个或多个节点组成并且节点之间有关联
图是由边和节点组成的每个边连接两个节点
图在计算机科学和算法中被广泛应用，例如网络路由、图像处理、算法设计等。文章来源地址https://www.toymoban.com/news/detail-442206.html

到了这里，关于C++数据结构与算法详解：链表、栈、队列、树、二叉树和图结构的实现与应用的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 《数据结构与算法》之队列与链表复习

    《数据结构与算法》之队列与链表复习

    我们在上一次学习了堆栈的数据结构以后，可以了解到它是受限制的操作，比如我们操作只能在栈顶，现在我们要学习的东西叫做队列，它也是受限制的一种数据结构，它的特点是队头只出数据，而队尾只入数据， 它的结构就和它的名字，像我们平时排队一样先来的人肯定要

    2024年02月08日
    浏览(29)
  • AcWing 算法基础课二 数据结构 链表 栈 队列 并查集 哈希表

    AcWing 算法基础课二 数据结构 链表 栈 队列 并查集 哈希表

    链表题目：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 AcWing. 826.单链表 双链表 AcWing 827.双链表 AcWing 828.模拟栈 AcWing 3302.表达式求值 AcWing 829. 模拟队列 AcWing 830.单调栈 AcWing 154.滑动窗口 AcWing 831. KMP字符串 AcWing 835. Trie字符串统计 AcWing 143. 最大异或对 AcWing 836.合并集合

    2024年02月15日
    浏览(30)
  • 数据结构三叉链表与线索二叉树的思路与实现详解

    数据结构三叉链表与线索二叉树的思路与实现详解

    ❤️作者主页：微凉秋意 ✅作者简介：后端领域优质创作者🏆，CSDN内容合伙人🏆，阿里云专家博主🏆 我们知道最常见的链式存储二叉树的结构体中有数据域、左孩子指针以及右孩子指针，通过递归来创建二叉树。显而易见的是，想找到二叉树中任意一个结点的 前驱 或 后

    2024年02月02日
    浏览(38)

  • 合肥工业大学 宣城校区 数据结构与算法实验 队列、二叉树、查找和排序

    1.实验目标 熟练掌握队列的顺序存储结构和链式存储结构。 熟练掌握队列的有关算法设计，并在循环顺序队列和链队列上实现。 根据具体给定的需求，合理设计并实现相关结构和算法。 2.实验内容和要求 循环顺序队列的实验要求 循环顺序队列结构和运算定义，算法的实现以

    2024年02月11日
    浏览(35)
  • C++数据结构之队列详解

    C++数据结构之队列详解

    队头填充进四个元素 此时思考一个问题，当删除元素时（元素出队列时）会出现假饱和的情况，如上图m_data[0]和m_data[1]再进行出队列操作之后，这两个位置可以容纳新的元素，但m_rear没有回到原本的m_data[0]位置，因此需要引入一个新的队列结构，环形队列，m_rear这个位置可以

    2024年02月05日
    浏览(29)

  • 数据结构——优先队列c++详解

    百度百科定义 优先队列是0个或多个元素的集合,每个元素都有一个优先权或值,对优先队列执行的操作有1) 查找;2) 插入一个新元素;3) 删除.在最小优先队列(min priority queue)中,查找操作用来搜索优先权最小的元素,删除操作用来删除该元素;对于最大优先队列(max priority queue),查找操

    2024年02月09日
    浏览(25)
  • C++数据结构之链表（详解）

    C++数据结构之链表（详解）

    主要参考文章地址 01.链表基础知识 | 算法通关手册 (itcharge.cn)） 本次内容是对链表的总结，可以看了上面的文章之后。 在看我下面的内容，做一个简短的复习，且本内容的代码均用C++实现，而参考资料的代码则为python。 每一个标题都有一个完整的链接，也可以点击下面的链

    2024年02月15日
    浏览(55)

  • 链表综合算法设计（c++数据结构）

      一、设计内容 已知简单的人事信息系统中职工记录包含职工编号（no）、职工姓名(name)、部门名称（depname）、职称(title)和工资数（salary）等信息（可以增加其他信息），设计并完成一个简单的人事信息管理系统，要求完成但不限于以下功能： （1）    增加一个职工信息

    2024年02月02日
    浏览(41)
  • C++数据结构与算法——栈与队列

    C++数据结构与算法——栈与队列

    C++第二阶段——数据结构和算法，之前学过一点点数据结构，当时是基于Python来学习的，现在基于C++查漏补缺，尤其是树的部分。这一部分计划一个月，主要利用代码随想录来学习，刷题使用力扣网站，不定时更新，欢迎关注！ 请你仅使用两个栈实现先入先出队列。队列应当

    2024年02月20日
    浏览(36)
  • 数据结构与算法之《二叉树》详解

    数据结构与算法之《二叉树》详解

    文章目录 一、树的概念及结构 二、二叉树的概念及结构 2、1 二叉树的概念 2、2 二叉树的特点 2、3 二叉树的结构（图片） 2、4 特殊的二叉树 三、二叉树的代码及思路实现 3、1 二叉树的存储结构 3、1、1 二叉树的顺序存储结构 3、1、2 二叉树的链式存储结构 3、2 二叉树链式

    2024年02月01日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包