数据结构是编程基石，选择与运用合适的数据结构能显著提升算法效能与资源使用效率。本文从基本数据类型与数组出发，深入探讨链表、栈与队列、树结构、图结构的核心概念及实现，旨在通过每种数据结构的基本知识与应用场景，帮助读者构建高效程序的基础。

基本数据类型与数组

数据类型

在编程语言中，数据类型决定了变量可以存储的数据的种类。常见的数据类型包括：

• 整型（int）：用于存储整数，如 int x = 10;
• 浮点型（float/double）：用于存储实数，如 double y = 3.14;
• 字符型（char）：用于存储单个字符，如 char z = 'A';

数组

数组是一种线性数据结构，由相同数据类型的多个元素组成，这些元素在内存中连续存储。数组的大小在创建时确定，其基本操作包括：

• 初始化：定义数组并初始化元素，如 int arr[] = {1, 2, 3};
• 访问：通过索引访问数组元素，如 int x = arr[0];，其中索引从 0 开始。
• 遍历：遍历数组元素并执行操作，如使用 for 循环。

示例代码：数组的遍历和求和

#include <iostream>
using namespace std;

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int sum = 0;

    for (int i = 0; i < 5; ++i) {
        sum += arr[i];
    }

    cout << "Sum of array elements: " << sum << endl;
    return 0;
}

链表

链表概述

链表是一种线性数据结构，其元素（称为节点）通过指针相互连接。与数组不同，链表的大小可以在运行时动态改变，且插入、删除操作较为高效。

实现

单链表

struct Node {
    int data;
    Node* next;
};

void insertAtEnd(Node*& head, int value) {
    Node* newNode = new Node{value, nullptr};
    if (head == nullptr) {
        head = newNode;
    } else {
        Node* current = head;
        while (current->next != nullptr) {
            current = current->next;
        }
        current->next = newNode;
    }
}

双向链表与循环链表

struct BiNode {
    int data;
    BiNode* prev;
    BiNode* next;
};

void insertAtEnd(BiNode*& head, int value) {
    BiNode* newNode = new BiNode{value, nullptr, nullptr};
    if (head == nullptr) {
        head = newNode;
        newNode->prev = newNode;
        newNode->next = newNode;
    } else {
        BiNode* current = head;
        while (current->next != head) {
            current = current->next;
        }
        current->next = newNode;
        newNode->prev = current;
        newNode->next = head;
        head->prev = newNode;
    }
}

栈与队列

栈

栈是一种线性数据结构，遵循后进先出（LIFO）原则。其基本操作包括：

• 入栈：在栈顶添加元素
• 出栈：从栈顶移除元素
• 顶元素访问：访问栈顶元素但不移除

实现

template <typename T>
class Stack {
    T* data;
    int top;
    int capacity;

public:
    Stack(int size) : data(new T[size]), capacity(size), top(-1) {}

    ~Stack() {
        delete[] data;
    }

    bool push(T value) {
        if (top == capacity - 1) {
            return false;
        }
        data[++top] = value;
        return true;
    }

    bool pop(T& value) {
        if (top == -1) {
            return false;
        }
        value = data[top];
        top--;
        return true;
    }
};

队列

队列遵循先进先出（FIFO）原则，包含：

• 入队：在队列尾部添加元素
• 出队：从队列头部移除元素
• 队头元素访问：访问队头元素但不移除

template <typename T>
class Queue {
    T* data;
    int head;
    int tail;
    int capacity;

public:
    Queue(int size) : data(new T[size]), capacity(size), head(0), tail(-1) {}

    ~Queue() {
        delete[] data;
    }

    bool enqueue(T value) {
        if (tail == capacity - 1) {
            return false;
        }
        tail++;
        data[tail] = value;
        return true;
    }

    bool dequeue(T& value) {
        if (head == tail) {
            return false;
        }
        value = data[head];
        head++;
        return true;
    }
};

树结构

二叉树

二叉树是一种节点结构，每个节点最多有两个子节点，通常称为左子节点和右子节点。

基本操作

• 插入：递归地找到插入位置并添加新节点
• 查找：递归地遍历树以查找给定值
• 删除：根据节点的子节点数量不同，采用不同的策略

示例代码：二叉树的遍历

struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;
};

void preorderTraversal(TreeNode* node) {
    if (node == nullptr) {
        return;
    }
    cout << node->value << " ";
    preorderTraversal(node->left);
    preorderTraversal(node->right);
}

void inorderTraversal(TreeNode* node) {
    if (node == nullptr) {
        return;
    }
    inorderTraversal(node->left);
    cout << node->value << " ";
    inorderTraversal(node->right);
}

void postorderTraversal(TreeNode* node) {
    if (node == nullptr) {
        return;
    }
    postorderTraversal(node->left);
    postorderTraversal(node->right);
    cout << node->value << " ";
}

图结构

示例代码：图的基本操作

class Graph {
    int numVertices;
    list<int>* adjLists;

public:
    Graph(int vertices) : numVertices(vertices), adjLists(new list<int>[vertices]) {}

    void addEdge(int src, int dest) {
        adjLists[src].push_back(dest);
        adjLists[dest].push_back(src); // 未优化的图，边双向存储
    }

    void dfs(int vertex) {
        bool* visited = new bool[numVertices];

        for (int i = 0; i < numVertices; i++) {
            visited[i] = false;
        }

        dfsUtil(vertex, visited);
    }

private:
    void dfsUtil(int v, bool* visited) {
        visited[v] = true;
        cout << v << " ";

        for (int i = 0; i < adjLists[v].size(); i++) {
            int n = adjLists[v][i];
            if (!visited[n]) {
                dfsUtil(n, visited);
            }
        }
    }
};

结语

数据结构是编程基础中的重要组成部分，理解并熟练掌握它们不仅可以提升编码效率，还能为解决复杂问题提供坚固的基石。从基本的数据类型与数组到链表、栈、队列、树和图，每一步都为更高级的算法设计和系统构建铺路。推荐进一步学习资源包括在线课程、书籍和实践项目，如慕课网，这些平台提供了丰富的教学资源和实际操作机会，帮助深入理解并应用数据结构。记住，实践是掌握数据结构的关键，尝试在实际项目中应用这些概念，将理论知识转化为解决问题的能力。