随着计算机科学的不断发展，数据结构作为计算机科学的基础知识，已经成为程序员们必备的技能。在众多的编程语言中，C++因其高效的性能和丰富的库支持，成为了实现数据结构的首选语言。本文将深入剖析几种常见的数据结构源码，帮助读者更好地理解数据结构在编程中的应用。

一、线性表

线性表是数据结构中最基础的一种，它是一系列元素的有序集合。常见的线性表有数组、链表、栈和队列。

1.数组

数组是一种随机访问的数据结构，通过索引可以直接访问到任一元素。以下是一个简单的数组源码示例：

`cpp

include <iostream>

using namespace std;

int main() { int arr[10]; for (int i = 0; i < 10; i++) { arr[i] = i * 2; } for (int i = 0; i < 10; i++) { cout << arr[i] << " "; } return 0; } `

2.链表

链表是一种基于节点的数据结构，节点中包含数据和指向下一个节点的指针。以下是一个简单的单链表源码示例：

`cpp

include <iostream>

using namespace std;

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

ListNode createList(int arr[], int n) { ListNode head = new ListNode(arr[0]); ListNode *cur = head; for (int i = 1; i < n; i++) { cur->next = new ListNode(arr[i]); cur = cur->next; } return head; }

int main() { int arr[] = {1, 2, 3, 4, 5}; ListNode *list = createList(arr, 5); while (list) { cout << list->val << " "; list = list->next; } return 0; } `

3.栈

栈是一种后进先出（LIFO）的数据结构，常见的操作有入栈、出栈和判断栈空。以下是一个简单的栈源码示例：

`cpp

include <iostream>

using namespace std;

template <typename T> class Stack { private: T *elements; int top; int maxSize;

public: Stack(int size) : maxSize(size), top(-1) { elements = new T[maxSize]; }

~Stack() {
    delete[] elements;
}
void push(T data) {
    if (top < maxSize - 1) {
        elements[++top] = data;
    }
}
T pop() {
    if (top >= 0) {
        return elements[top--];
    }
    return T(); // 返回默认构造函数创建的对象
}
bool isEmpty() {
    return top == -1;
}

};

int main() { Stack<int> stack(5); for (int i = 0; i < 5; i++) { stack.push(i); } while (!stack.isEmpty()) { cout << stack.pop() << " "; } return 0; } `

4.队列

队列是一种先进先出（FIFO）的数据结构，常见的操作有入队、出队和判断队列空。以下是一个简单的队列源码示例：

`cpp

include <iostream>

using namespace std;

template <typename T> class Queue { private: T *elements; int front; int rear; int maxSize;

public: Queue(int size) : maxSize(size), front(0), rear(0) { elements = new T[maxSize]; }

~Queue() {
    delete[] elements;
}
void enqueue(T data) {
    if (rear < maxSize - 1) {
        elements[rear++] = data;
    }
}
T dequeue() {
    if (front < rear) {
        return elements[front++];
    }
    return T(); // 返回默认构造函数创建的对象
}
bool isEmpty() {
    return front == rear;
}

};

int main() { Queue<int> queue(5); for (int i = 0; i < 5; i++) { queue.enqueue(i); } while (!queue.isEmpty()) { cout << queue.dequeue() << " "; } return 0; } `

二、非线性表

非线性表是由多个线性表组成的，常见的非线性表有树和图。

1.树

树是一种层次结构，由节点组成，节点包含数据和指向子节点的指针。以下是一个简单的二叉树源码示例：

`cpp

include <iostream>

using namespace std;

struct TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} };

TreeNode createTree(int arr[], int n) { TreeNode root = new TreeNode(arr[0]); TreeNode *cur = root; for (int i = 1; i < n; i++) { if (arr[i] < cur->val) { if (cur->left == NULL) { cur->left = new TreeNode(arr[i]); cur = cur->left; } else { cur = cur->left; } } else { if (cur->right == NULL) { cur->right = new TreeNode(arr[i]); cur = cur->right; } else { cur = cur->right; } } } return root; }

int main() { int arr[] = {5, 3, 7, 2, 4, 6, 8}; TreeNode *root = createTree(arr, 7); // 遍历二叉树 // ... return 0; } `

2.图

图是一种由节点和边组成的数据结构，节点表示实体，边表示实体之间的关系。以下是一个简单的图源码示例：

`cpp

include <iostream>

using namespace std;

struct GraphNode { int val; int edges; GraphNode *next; GraphNode(int x) : val(x), edges(0), next(NULL) {} };

class Graph { private: int numVertices; GraphNode **nodes;

public: Graph(int numVertices) : numVertices(numVertices), nodes(new GraphNode*[numVertices]) { for (int i = 0; i < numVertices; i++) { nodes[i] = NULL; } }

~Graph() {
    for (int i = 0; i < numVertices; i++) {
        GraphNode *cur = nodes[i];
        while (cur) {
            GraphNode *temp = cur;
            cur = cur->next;
            delete temp;
        }
    }
    delete[] nodes;
}
void addEdge(int start, int end) {
    GraphNode *newEdge = new GraphNode(end);
    newEdge->next = nodes[start];
    nodes[start] = newEdge;
    nodes[end] = NULL;
}
void display() {
    for (int i = 0; i < numVertices; i++) {
        GraphNode *cur = nodes[i];
        while (cur) {
            cout << i << " -> " << cur->val << endl;
            cur = cur->next;
        }
    }
}

};

int main() { Graph graph(4); graph.addEdge(0, 1); graph.addEdge(0, 2); graph.addEdge(1, 3); graph.addEdge(2, 3); graph.display(); return 0; } `

总结

通过以上源码示例，我们可以看到数据结构在编程中的应用。掌握数据结构不仅有助于提高代码效率，还能使代码更加易于理解和维护。在实际开发过程中，我们需要根据具体问题选择合适的数据结构，以实现最佳性能。希望本文能帮助读者更好地理解数据结构及其源码。