C++数据结构实验：实现和应用关键数据结构

宁南山

291人浏览 · 2025-08-11 15:39:00

宁南山 · 2025-08-11 15:39:00 发布

简介：数据结构是计算机科学的基础，它决定了程序的效率和性能。本实验重点讲解了四种核心数据结构：共享栈、链栈、循环队列和链队列。通过C++实现这些数据结构，学生将学习如何在多线程环境下保证线程安全，理解基于链表的动态扩展优势，掌握循环队列解决边界问题的方法，以及体验链队列的灵活内存使用。这些数据结构的实践加深了对栈和队列工作原理的理解，为未来学习和应用更高级数据结构打下基础。熟练掌握这些结构对于提升编程技能和解决实际问题至关重要。
C++数据结构实验_实现共享栈，链栈，循环队列，链队列

1. C++数据结构实验总览

在本章中，我们将探索 C++ 中数据结构的实验总览，特别是对于那些在 IT 行业中拥有 5 年以上经验的专业人员来说，本章旨在提供一个关于数据结构实验的完整概述。首先，我们会介绍数据结构实验的目的和重要性，接着会按照章节顺序概述本书的结构。本章的内容为读者在接下来的章节中深入探讨具体的实现和优化提供了必要的背景知识和框架。

1.1 数据结构实验的目的和重要性

数据结构是计算机科学的核心，它们对算法的性能有着直接的影响。数据结构实验的目的是为了理解各种数据结构的特性和应用场景，通过实际编写代码来加深对理论知识的理解。掌握数据结构不仅对软件开发至关重要，而且对于解决复杂的实际问题也具有指导意义。在这一章节中，我们将探索数据结构实验的基本原则及其在软件开发中的作用。

1.2 实验内容概览

本书将详细讨论栈和队列这两种基本数据结构的高级应用，这些内容对于那些希望提升软件设计和编程能力的 IT 专业人员特别有用。我们将从共享栈的线程安全实现开始，深入探讨线程同步、无锁编程和原子操作。随后，我们会探讨链栈的动态扩展特性，循环队列的边界问题解决方法以及链队列的内存使用灵活性。在本书的最后，我们将讨论数据结构与算法性能的关系，并介绍如何选择合适的数据结构以优化性能。

通过以下各章节的深入学习，读者将能够掌握如何在 C++ 中实现高效、安全的数据结构，并理解它们在解决实际问题中的应用。我们将使用代码示例、测试和性能分析，逐步揭开数据结构背后的秘密。

2. 共享栈的线程安全实现

2.1 线程安全的基本概念

2.1.1 线程安全的定义

线程安全是多线程编程中的一个重要概念，它指的是当多个线程访问某个类时，不管运行时环境采用何种调度方式或者这些线程如何交替执行，并且在主调代码中不需要额外的同步及协同，这个类都能表现出正确的行为。

具体来说，一个线程安全的数据结构，即使在多线程环境下使用，它也能够保证：

原子性（Atomicity）：单个操作是不可分割的，要么全部完成，要么全部不执行。
可见性（Visibility）：一个线程对共享变量的修改，能够及时被其他线程看到。
有序性（Ordering）：程序代码的执行顺序与指令序列一致。

2.1.2 线程同步机制

为了保证线程安全，多线程程序通常会使用一些同步机制来控制线程对共享资源的访问。常见的同步机制包括：

互斥锁（Mutex）：互斥锁是一种简单的同步机制，确保某一时刻只有一个线程能够访问共享资源。
读写锁（Read-Write Lock）：当多个线程并发读取时，读写锁允许多个线程同时读取，但在写入时必须独占。
信号量（Semaphore）：信号量是一种更通用的同步机制，可以用作互斥锁或实现复杂的同步模式。
条件变量（Condition Variable）：条件变量允许线程阻塞等待某个条件的发生，然后继续执行。

2.2 共享栈的线程安全设计

2.2.1 锁的使用策略

在共享栈的设计中，为了保证线程安全，我们可以使用锁来保证临界区的互斥访问。临界区是指访问共享资源的代码片段，这些代码在执行时不允许其他线程打断。

锁的策略包括：

互斥锁（Mutex）：确保在任何时候只有一个线程能够执行临界区代码。
自旋锁（Spin Lock）：当锁不可用时，线程持续轮询锁的状态直到获得锁，适用于锁的预期占用时间短的情况。

2.2.2 无锁编程与原子操作

无锁编程是利用现代处理器提供的原子指令（如CAS，Compare And Swap）来实现的。原子操作是指不会被线程调度机制打断的操作，原子操作在执行完毕之前，不会被其他线程中断。

无锁编程的优势在于减少上下文切换和避免死锁，但是设计复杂度较高，容易出错。适用于高并发、低延时的场景。

2.3 实现共享栈的线程安全代码

2.3.1 C++11中的线程库应用

C++11标准库中提供了线程支持，我们可以使用 <thread> , <mutex> , <atomic> 等头文件中的类和函数来实现线程安全的共享栈。

例子中使用 std::mutex 和 std::lock_guard 来保证栈操作的线程安全：

#include <iostream>
#include <stack>
#include <mutex>

std::stack<int> stack;
std::mutex mtx;

void push(int value) {
    std::lock_guard<std::mutex> lock(mtx); // 构造函数中自动加锁
    stack.push(value);
}

int pop() {
    std::lock_guard<std::mutex> lock(mtx);
    if (stack.empty()) {
        throw std::out_of_range("Stack<>::pop(): empty stack");
    }
    int const res = stack.top();
    stack.pop();
    return res;
}

2.3.2 代码示例与测试

下面提供了一个简单的测试示例，用以演示如何多线程对共享栈进行操作：

#include <thread>
#include <vector>
#include <iostream>

void pushThread(std::stack<int>& stack, std::mutex& mtx, int num) {
    for (int i = 0; i < num; ++i) {
        std::lock_guard<std::mutex> lock(mtx);
        stack.push(i);
    }
}

void popThread(std::stack<int>& stack, std::mutex& mtx, int num) {
    for (int i = 0; i < num; ++i) {
        std::lock_guard<std::mutex> lock(mtx);
        if (!stack.empty()) {
            std::cout << "Popped: " << stack.top() << '\n';
            stack.pop();
        }
    }
}

int main() {
    const int num_pushes = 100;
    std::stack<int> shared_stack;
    std::mutex mtx;

    std::vector<std::thread> threads;

    // 创建多个线程，一部分用于push操作，一部分用于pop操作
    for (int i = 0; i < num_pushes; ++i) {
        threads.emplace_back(pushThread, std::ref(shared_stack), std::ref(mtx), 1);
    }
    for (int i = 0; i < num_pushes; ++i) {
        threads.emplace_back(popThread, std::ref(shared_stack), std::ref(mtx), 1);
    }

    // 等待所有线程完成
    for (auto& t : threads) {
        t.join();
    }

    return 0;
}

在上述示例中，我们创建了多线程进行push和pop操作，其中 std::lock_guard 会保证每次只有一个线程能够访问共享栈。通过这种方式，我们能够确保共享栈在多线程环境下的线程安全。

3. 链栈的动态扩展特性

链栈是一种通过链表实现的栈结构，它克服了普通数组栈在空间使用上的局限性，通过动态内存分配机制实现了栈空间的自动扩展。本章节将从栈的数据结构入手，深入探讨链栈的设计原理、动态扩展机制，并通过代码示例展示如何实现一个链栈。

3.1 栈的数据结构概述

3.1.1 栈的定义和操作

栈是一种后进先出（LIFO, Last In First Out）的数据结构，只允许在表的一端进行插入或删除操作。其中，插入操作称为“压栈”，删除操作称为“出栈”。在栈中，最后插入的元素总是最先被删除，这与现实生活中的堆叠物品相类似。

栈的操作通常包括以下几个：

push : 将元素压入栈顶。
pop : 移除栈顶元素。
top / peek : 查看栈顶元素而不移除。
isEmpty : 检查栈是否为空。

3.1.2 栈在C++中的实现

在C++标准模板库（STL）中， std::stack 提供了栈的基本实现。然而，为了探究链栈的动态扩展特性，我们将手动实现一个链栈。

3.2 链栈的数据结构和优势

3.2.1 链栈的定义和操作

链栈由多个节点组成，每个节点包含数据部分和指向下一个节点的指针。链栈的操作与普通栈类似，但其内部结构允许动态地分配和释放内存。

链栈的操作包括：

push : 在链表头部插入一个节点。
pop : 移除链表头部的节点。
top / peek : 返回链表头部节点的数据部分。
isEmpty : 检查链表是否为空。

3.2.2 动态内存分配与释放

链栈的一个显著优势在于其动态内存分配能力。当栈空间不足时，链栈可以自动申请新的内存块来存储数据。同样，当栈中元素被弹出时，可以释放相应的内存块。

以下是简单的链栈节点定义和基本操作的伪代码实现：

struct StackNode {
    int data;          // 数据部分
    StackNode* next;   // 指向下一个节点的指针
};

class LinkedStack {
private:
    StackNode* top;    // 指向栈顶节点的指针

public:
    LinkedStack() : top(nullptr) {} // 构造函数

    ~LinkedStack() {
        while (!isEmpty()) {
            pop();
        }
    }

    void push(int value) {
        // 创建新节点，分配内存
        StackNode* newNode = new StackNode;
        newNode->data = value;
        // 链接新节点到原栈顶
        newNode->next = top;
        // 更新栈顶指针
        top = newNode;
    }

    int pop() {
        if (isEmpty()) {
            throw std::runtime_error("Stack is empty");
        }
        // 保存栈顶数据
        int value = top->data;
        // 获取新的栈顶节点
        StackNode* temp = top;
        top = top->next;
        // 释放原栈顶节点的内存
        delete temp;
        return value;
    }

    int top() const {
        if (isEmpty()) {
            throw std::runtime_error("Stack is empty");
        }
        return top->data;
    }

    bool isEmpty() const {
        return top == nullptr;
    }
};

3.3 链栈动态扩展的实现

3.3.1 链表节点的创建与链接

链栈的动态扩展依赖于对链表节点的创建和链接。每当需要压栈操作，而当前栈为空或栈顶节点已满时，将创建一个新的节点并将其链接到链表中。

3.3.2 栈满与栈空的判断

由于链栈使用动态内存，它本质上不存在“满”的情况，除非内存耗尽。不过，判断栈空的条件很简单，只需检查栈顶指针是否为 nullptr 。

3.3.3 代码示例与测试

测试代码如下：

int main() {
    LinkedStack stack;
    try {
        stack.push(1);
        stack.push(2);
        stack.push(3);
        std::cout << "Top element is: " << stack.top() << std::endl; // 输出栈顶元素
        std::cout << "Popping: " << stack.pop() << std::endl;
        std::cout << "Top element is now: " << stack.top() << std::endl;
        // 继续出栈直到栈空
        while (!stack.isEmpty()) {
            std::cout << "Popping: " << stack.pop() << std::endl;
        }
        std::cout << "Stack is now empty" << std::endl;
    } catch (const std::exception& e) {
        std::cerr << "Exception: " << e.what() << std::endl;
    }
    return 0;
}

上述代码演示了链栈的基本操作，包括压栈、查看栈顶、出栈以及判断栈空，并对可能出现的异常进行捕获处理。

通过本章节的介绍，我们已经深入了解了链栈的基本结构及其动态扩展特性。接下来的章节将继续探讨循环队列和链队列的数据结构特性，进一步揭示数据结构如何适应不同的应用场景以优化内存使用和提升性能。

4. 循环队列的边界问题解决

4.1 队列的数据结构概述

队列是另一种典型的数据结构，它遵循先进先出（First In First Out, FIFO）的原则。在计算机科学中，队列常用于任务调度、缓冲处理等场景。

4.1.1 队列的定义和操作

队列的操作主要包括入队（enqueue）和出队（dequeue）。入队操作是将一个元素添加到队列的末尾，而出队操作是移除队列头部的元素。除此之外，队列通常还支持查看队首元素（front）和队尾元素（rear）的操作，以及检查队列是否为空（isEmpty）或已满（isFull）。

4.1.2 队列在C++中的实现

在C++标准库中，队列通常通过容器适配器来实现，比如使用 std::queue 。这个容器适配器内部实际上使用了一个底层容器，例如 std::deque 或 std::list 。通过这些底层容器的接口， std::queue 提供了队列操作的标准实现。

4.2 循环队列的数据结构和优势

循环队列是队列的一种扩展形式，它通过使用固定大小的数组来实现，并解决了普通队列在数组操作中可能出现的数组越界问题。

4.2.1 循环队列的定义和操作

循环队列在数组空间用完时，头部空间重新利用，形成环状结构。它维护两个指针，分别是头部指针front和尾部指针rear。入队操作是将新元素放在rear指向的位置，并将rear向前移动一位；出队操作是取出front指向的元素，并将front向前移动一位。

4.2.2 循环队列的优势与应用

循环队列的优点在于它可以有效利用数组空间，避免了线性队列在数组操作中的频繁复制问题。在实际应用中，如键盘缓冲区、内存管理等场景，循环队列可以提供更高效的解决方案。

4.3 循环队列边界问题的解决策略

4.3.1 前驱和后继的计算方法

在循环队列中，”前驱”和”后继”的概念非常重要，它们用于计算在数组中移动指针时的位置。由于是循环结构，前驱通常是指针向前移动一个位置，而当指针到达数组的开头时，它会循环回到数组的末尾。类似地，后继是指针向后移动一个位置，如果指针到达数组末尾，则会循环回到数组开头。

在C++中，计算前驱和后继的操作可以通过取模运算来实现，确保指针值始终在数组的有效范围内。

#define QUEUE_SIZE 5 // 假设队列大小为5
int front = 0, rear = 0;

// 计算后继位置
int nextPosition(int pos) {
    return (pos + 1) % QUEUE_SIZE;
}

// 计算前驱位置
int previousPosition(int pos) {
    return (pos - 1 + QUEUE_SIZE) % QUEUE_SIZE;
}

4.3.2 边界条件的处理代码

处理循环队列的边界条件时，需要特别注意当队列为空或队列已满的情况。当队列为空时，front和rear指针指向同一个位置；当队列已满时，队列中会有一个空位，即 (rear + 1) % QUEUE_SIZE 等于front。

为了避免死锁，我们需要在入队和出队操作中添加逻辑判断，确保不会出现队列已满仍然尝试入队，或队列为空仍然尝试出队的情况。

bool isQueueFull(int front, int rear) {
    return (rear + 1) % QUEUE_SIZE == front;
}

bool isQueueEmpty(int front, int rear) {
    return front == rear;
}

在每次进行入队或出队操作之前，都应当先调用这两个函数检查队列状态，以避免出现不可预期的错误。

通过上面的策略和代码实现，可以有效地解决循环队列在边界条件下的问题，确保队列操作的正确性和稳定性。

5. 链队列的内存使用灵活性

5.1 链队列的结构和特点

链队列是队列的一种实现方式，其特点在于它使用链表来存储队列中的元素。链队列可以有效地解决数组实现的队列存在的固定容量问题，提供了更灵活的内存使用方式。

5.1.1 链队列的定义和操作

链队列由一系列节点组成，每个节点包含数据域和指向下一个节点的指针域。链队列的操作主要包括入队（enqueue）、出队（dequeue）、获取队首元素（front）和检查队列是否为空（isEmpty）等。

在C++中，链队列的基本结构可以通过以下代码示例展示：

struct Node {
    int data; // 数据域
    Node* next; // 指针域，指向下一个节点
};

class LinkedQueue {
public:
    LinkedQueue() : head(nullptr), tail(nullptr) {} // 构造函数

    ~LinkedQueue() {
        // 析构函数，释放所有节点内存
        while (!isEmpty()) {
            dequeue();
        }
    }

    void enqueue(int value) {
        // 入队操作
        Node* newNode = new Node{value, nullptr};
        if (tail) {
            tail->next = newNode;
        } else {
            head = newNode;
        }
        tail = newNode;
    }

    int dequeue() {
        // 出队操作
        if (isEmpty()) throw std::runtime_error("Queue is empty");
        int value = head->data;
        Node* temp = head;
        head = head->next;
        if (!head) {
            tail = nullptr;
        }
        delete temp;
        return value;
    }

    int front() const {
        // 获取队首元素
        if (isEmpty()) throw std::runtime_error("Queue is empty");
        return head->data;
    }

    bool isEmpty() const {
        // 检查队列是否为空
        return head == nullptr;
    }

private:
    Node* head; // 队首指针
    Node* tail; // 队尾指针
};

5.1.2 链队列的内存管理

链队列的内存管理主要关注如何分配和回收节点内存。由于链队列的动态特性，其内存分配是在运行时根据需要进行的，这使得链队列可以有效地使用内存，避免浪费。

5.1.2.1 内存分配策略

链队列中的内存分配通常发生在入队操作时。当一个新元素需要加入队列时，会动态地在堆上创建一个新的节点。

5.1.2.2 内存回收策略

与内存分配相对应，内存回收发生在出队操作时。当节点被移出队列时，它所占用的内存需要被释放，以便其他操作可以重新使用这些内存。

5.2 链队列的内存使用效率

链队列的内存使用效率主要体现在其动态内存分配和回收的策略上。由于链队列的节点在入队和出队时被创建和销毁，因此需要特别注意如何高效地管理这些节点的内存。

5.2.1 链队列节点的动态分配

链队列节点的动态分配是通过 new 关键字实现的。每个入队操作都会创建一个新的节点，并将其加入到队列中。

5.2.2 链队列内存回收策略

链队列的内存回收是通过删除节点实现的。当节点被出队后，它所占的内存通过 delete 操作被释放，以便可以被其他节点再次使用。

5.3 链队列的灵活内存管理实现

5.3.1 内存池技术的应用

内存池是一种预分配和管理内存的技术，它可以提高内存分配和回收的效率。链队列可以通过使用内存池来优化节点的创建和销毁过程。

5.3.1.1 内存池的基本概念

内存池通过预先分配一大块内存，并将其分割成固定大小的块来使用。这些块可以被快速地分配和回收，从而减少内存碎片和提高性能。

5.3.1.2 内存池在链队列中的应用

在链队列中，内存池可以用来预先分配一定数量的节点。当需要进行入队操作时，可以从内存池中快速地取出一个节点来使用，而当节点出队时，则可以将节点返回给内存池，而不是直接销毁。

class MemoryPool {
private:
    int nodeSize;
    int capacity;
    Node** freeList;
    int freeCount;

public:
    MemoryPool(int size, int cap) : nodeSize(size), capacity(cap), freeList(nullptr), freeCount(0) {
        freeList = new Node*[capacity];
        for (int i = 0; i < capacity; ++i) {
            freeList[i] = new Node;
        }
        freeCount = capacity;
    }

    ~MemoryPool() {
        for (int i = 0; i < capacity; ++i) {
            delete freeList[i];
        }
        delete[] freeList;
    }

    Node* getNode() {
        if (freeCount == 0) {
            throw std::bad_alloc();
        }
        --freeCount;
        Node* node = freeList[freeCount];
        node->next = nullptr;
        return node;
    }

    void releaseNode(Node* node) {
        if (freeCount < capacity) {
            freeList[freeCount++] = node;
        } else {
            delete node;
        }
    }
};

// 在链队列中使用内存池
class LinkedQueueWithPool {
public:
    LinkedQueueWithPool(int nodeSize, int poolCapacity) : pool(nodeSize, poolCapacity) {}

    void enqueue(int value) {
        Node* newNode = pool.getNode();
        newNode->data = value;
        if (tail) {
            tail->next = newNode;
        } else {
            head = newNode;
        }
        tail = newNode;
    }

    int dequeue() {
        if (isEmpty()) throw std::runtime_error("Queue is empty");
        int value = head->data;
        Node* temp = head;
        head = head->next;
        if (!head) {
            tail = nullptr;
        }
        pool.releaseNode(temp);
        return value;
    }

private:
    MemoryPool pool;
    Node* head;
    Node* tail;
};

5.3.2 代码实现与性能分析

通过上述代码实现，我们可以看到链队列与内存池结合后的优化效果。内存池的使用可以显著减少动态内存分配和释放的次数，从而提高链队列的整体性能。

5.3.2.1 性能测试

性能测试可以对比使用内存池和未使用内存池的链队列，在入队和出队操作中的性能差异。测试结果可以使用表格形式展示，比较两者在执行同样数量的操作时的耗时和内存使用情况。

5.3.2.2 性能分析

分析性能测试结果，我们可以得出结论，内存池技术在处理大量频繁的入队和出队操作时，能够提供更稳定的性能表现。通过减少内存碎片和提高内存的重用率，链队列的性能得到了有效提升。

以上是链队列内存使用灵活性的详细介绍，结合了内存池技术，我们进一步提升了链队列在内存使用上的效率和稳定性。这为处理大规模数据提供了更为可靠的内存管理方案。

6. 数据结构与算法性能的关系

6.1 数据结构与算法概述

6.1.1 数据结构对算法的影响

数据结构是算法的逻辑基础，算法的效率往往受到其操作的数据结构的显著影响。简单来说，数据结构定义了数据元素之间的逻辑关系，而算法则是在这些逻辑关系之上进行操作的一种过程。选择合适的数据结构可以大幅提高算法的效率。例如，使用二叉搜索树（BST）可以实现快速的查找操作，但如果数据分布不均匀，可能退化为链表，其查找效率会大幅度下降。

6.1.2 算法效率的度量标准

算法效率主要通过时间复杂度和空间复杂度来衡量。时间复杂度是指算法执行时间随输入规模增长的变化趋势，通常用大O表示法表达，如O(n)表示线性时间复杂度，O(n^2)表示二次时间复杂度。空间复杂度则描述了算法在执行过程中临时占用存储空间的大小。算法的时间和空间效率往往是需要权衡的，有时候为了获得更快的速度，可能需要消耗更多的存储空间，反之亦然。

6.2 数据结构的选择对性能的影响

6.2.1 不同数据结构的性能比较

不同数据结构的性能比较需要在特定的应用场景下进行。例如，对于需要频繁插入删除元素的场景，链表往往比数组更加高效；而如果需要快速随机访问，数组或者基于数组实现的动态数组（如C++的 std::vector ）则更为合适。堆（heap）结构则适用于实现优先队列等场景。

6.2.2 实例分析：栈和队列的应用

栈和队列是两种基本的数据结构，它们在算法性能优化中扮演着重要角色。栈是后进先出（LIFO）的数据结构，适合用于需要逆序处理的算法，如递归算法的调用栈，或者浏览器的后退功能。队列则是先进先出（FIFO）的数据结构，适合实现任务调度，如操作系统中的进程调度。

6.3 算法优化与数据结构的结合

6.3.1 算法优化策略

算法优化可以从多个维度进行，包括但不限于：
- 减少不必要的计算，利用已有结果避免重复计算（动态规划）。
- 优化数据结构以减少操作时间，如使用平衡二叉搜索树（如AVL树）代替普通二叉搜索树。
- 减少内存访问次数，利用缓存局部性原理提高效率。
- 利用特定算法消除冗余操作，如在排序算法中使用快速排序而不是冒泡排序。

6.3.2 数据结构优化的实践案例

以散列表（哈希表）为例，其性能优化涉及到冲突解决策略。常见的冲突解决方法有链表法和开放寻址法。链表法下，当哈希冲突发生时，可以将所有具有相同哈希值的元素通过链表连接起来。如果冲突较少，则性能接近常数时间复杂度O(1)。在开放寻址法中，若发生冲突，则在数组中寻找下一个空位，该方法在数据量不大的情况下效率较高，但随着数据量增大，性能可能会下降。

#include <iostream>
#include <unordered_map>

int main() {
    // 示例：使用C++的unordered_map作为散列表的应用
    std::unordered_map<int, std::string> myMap;

    // 插入数据
    myMap[1] = "Item1";
    myMap[2] = "Item2";
    myMap[3] = "Item3";

    // 查询数据
    std::cout << "Key 2: " << myMap[2] << std::endl;

    return 0;
}

在上述代码中， unordered_map 是C++标准库中提供的一种散列表实现，它通过哈希表存储键值对，使得平均时间复杂度为O(1)的插入和查找操作成为可能。

以上是关于数据结构与算法性能关系的探讨，分析了数据结构选择如何影响算法的性能，并举例说明了优化策略的具体实现。然而，对于程序员来说，理解不同数据结构的内在特性及其在不同算法中的应用，是进行性能优化和高效编程的关键所在。

本文还有配套的精品资源，点击获取