引言
C++作为一门强大的编程语言，其数据结构是实现高效编程的关键。掌握合适的数据结构可以大大提高程序的执行效率和可维护性。本文将带您走进C++数据结构的世界，通过详细的代码实现和实例分析，帮助您轻松掌握高效编程技巧。
一、基本数据结构
1.1 数组
数组是C++中最基本的数据结构之一，用于存储具有相同数据类型的元素。以下是一个使用数组存储整数的示例：
#include
using namespace std;
int main() {
int arr[5] = {1, 2, 3, 4, 5};
for (int i = 0; i < 5; ++i) {
cout << arr[i] << " ";
}
return 0;
}
1.2 链表
链表是一种非线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。以下是一个简单的单向链表实现：
#include
using namespace std;
struct Node {
int data;
Node* next;
};
void insert(Node*& head, int value) {
Node* newNode = new Node;
newNode->data = value;
newNode->next = head;
head = newNode;
}
void display(Node* head) {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
int main() {
Node* head = nullptr;
insert(head, 5);
insert(head, 4);
insert(head, 3);
insert(head, 2);
insert(head, 1);
display(head);
return 0;
}
1.3 栈
栈是一种后进先出（LIFO）的数据结构。以下是一个简单的栈实现：
#include
using namespace std;
struct Stack {
int top;
int arr[100];
};
void push(Stack& s, int value) {
if (s.top == 99) {
cout << "Stack overflow" << endl;
return;
}
s.top++;
s.arr[s.top] = value;
}
int pop(Stack& s) {
if (s.top == -1) {
cout << "Stack underflow" << endl;
return -1;
}
int value = s.arr[s.top];
s.top--;
return value;
}
int main() {
Stack s;
s.top = -1;
push(s, 5);
push(s, 4);
push(s, 3);
cout << "Top element: " << pop(s) << endl;
return 0;
}
1.4 队列
队列是一种先进先出（FIFO）的数据结构。以下是一个简单的队列实现：
#include
using namespace std;
struct Queue {
int front, rear;
int arr[100];
};
void enqueue(Queue& q, int value) {
if (q.rear == 99) {
cout << "Queue overflow" << endl;
return;
}
q.arr[++q.rear] = value;
}
int dequeue(Queue& q) {
if (q.front == q.rear) {
cout << "Queue underflow" << endl;
return -1;
}
int value = q.arr[q.front++];
return value;
}
int main() {
Queue q;
q.front = q.rear = -1;
enqueue(q, 5);
enqueue(q, 4);
enqueue(q, 3);
cout << "Dequeued: " << dequeue(q) << endl;
return 0;
}
二、高级数据结构
2.1 树
树是一种非线性数据结构，由节点组成，每个节点有零个或多个子节点。以下是一个简单的二叉树实现：
#include
using namespace std;
struct Node {
int data;
Node* left, *right;
};
Node* createNode(int value) {
Node* newNode = new Node;
newNode->data = value;
newNode->left = newNode->right = nullptr;
return newNode;
}
void insert(Node*& root, int value) {
if (root == nullptr) {
root = createNode(value);
return;
}
if (value < root->data) {
insert(root->left, value);
} else {
insert(root->right, value);
}
}
void inorder(Node* root) {
if (root == nullptr) {
return;
}
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
int main() {
Node* root = nullptr;
insert(root, 8);
insert(root, 3);
insert(root, 10);
insert(root, 1);
insert(root, 6);
insert(root, 14);
inorder(root);
return 0;
}
2.2 图
图是一种复杂的数据结构，由节点（称为顶点）和边组成。以下是一个简单的邻接表实现：
#include
#include
using namespace std;
struct Graph {
int V;
list
};
Graph* createGraph(int V) {
Graph* graph = new Graph;
graph->V = V;
graph->adj = new list
return graph;
}
void addEdge(Graph* graph, int src, int dest) {
graph->adj[src].push_back(dest);
graph->adj[dest].push_back(src);
}
void displayGraph(Graph* graph) {
for (int v = 0; v < graph->V; ++v) {
cout << "Adjacency list of vertex " << v << ":\n";
for (int adj : graph->adj[v]) {
cout << adj << " ";
}
cout << "\n";
}
}
int main() {
Graph* graph = createGraph(5);
addEdge(graph, 0, 1);
addEdge(graph, 0, 4);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
displayGraph(graph);
return 0;
}
三、总结
本文详细介绍了C++中的基本和高级数据结构，并通过实例代码展示了如何实现它们。通过学习这些数据结构，您可以更好地理解如何高效地处理数据，从而提高编程技能。希望本文能帮助您解锁C++数据结构，迈向高效编程之路。