c++数据结构

简介: c++数据结构

在C++中,数据结构是用于组织和存储数据的特定方式,以便有效地访问和修改这些数据。不同的数据结构适用于不同的场景,如数组、链表、栈、队列、树、图等。下面我将对其中一些常用的数据结构进行简要的讲解,并提供相关的编程示例。

1. 数组(Array)

数组是一种线性数据结构,用于存储相同类型的数据元素的集合。数组中的元素通过索引进行访问,索引从0开始。

编程示例

#include <iostream> 
using namespace std; 
int main() { 
int arr[5] = {1, 2, 3, 4, 5}; 
for (int i = 0; i < 5; i++) { 
cout << arr[i] << " "; 
} 
cout << endl; 
return 0; 
}

2. 链表(Linked List)

链表是一种动态数据结构,由一系列节点组成,每个节点包含数据元素和指向下一个节点的指针。与数组不同,链表在内存中的存储不是连续的。

编程示例(单向链表)

#include <iostream> 
using namespace std; 
struct Node { 
int data; 
Node* next; 
}; 
void printList(Node* head) { 
Node* temp = head; 
while (temp != nullptr) { 
cout << temp->data << " "; 
temp = temp->next; 
} 
cout << endl; 
} 
int main() { 
// 创建链表:1 -> 2 -> 3 
Node* head = new Node{1, nullptr}; 
head->next = new Node{2, nullptr}; 
head->next->next = new Node{3, nullptr}; 
printList(head); // 输出:1 2 3 
// ... (需要释放内存,这里略去) 
return 0; 
}

3. 栈(Stack)

栈是一种后进先出(LIFO)的数据结构,只允许在一端进行插入和删除操作,这一端被称为栈顶。

编程示例(使用数组实现)

#include <iostream> 
#include <stack> // 也可以使用STL中的stack 
using namespace std; 
const int MAX_SIZE = 100; 
int stack[MAX_SIZE]; 
int top = -1; // 栈顶指针初始化为-1 
void push(int x) { 
if (top == MAX_SIZE - 1) { 
cout << "Stack is full!" << endl; 
return; 
} 
stack[++top] = x; 
} 
int pop() { 
if (top == -1) { 
cout << "Stack is empty!" << endl; 
return -1; // 或者抛出一个异常 
} 
return stack[top--]; 
} 
int main() { 
push(1); 
push(2); 
push(3); 
cout << pop() << endl; // 输出:3 
cout << pop() << endl; // 输出:2 
// ... 
return 0; 
}

4. 队列(Queue)

队列是一种先进先出(FIFO)的数据结构,只允许在队尾进行插入操作(入队),在队头进行删除操作(出队)。

编程示例(使用STL中的queue)

#include <iostream> 
#include <queue> 
using namespace std; 
int main() { 
queue<int> q; 
q.push(1); 
q.push(2); 
q.push(3); 
cout << q.front() << endl; // 输出:1(队头元素) 
q.pop(); // 移除队头元素 
cout << q.front() << endl; // 输出:2(新的队头元素) 
// ... 
return 0; 
}

5. 树(Tree)

树是一种非线性的数据结构,由节点和边组成。每个节点可以有一个或多个子节点,但只有一个父节点(根节点除外)。常见的树有二叉树、AVL树、红黑树等。

编程示例(二叉树)

由于二叉树的实现较为复杂,这里仅展示一个简单的节点定义。

#include <iostream> 
using namespace std; 
struct TreeNode { 
int val; 
TreeNode* left; 
TreeNode* right; 
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} 
}; 
// ... (二叉树的插入、遍历等操作需要额外实现) 
int main() { 
// 创建一个简单的二叉树 
TreeNode* root = new TreeNode(1); 
root->left = new TreeNode(2); 
root->right = new TreeNode(3); 
root->left->left = new TreeNode(4); 
root->left->right = new TreeNode(5); 
// ... (需要遍历或操作树) 
return 0; 
}

由于篇幅限制,这里仅对每种数据结构进行了简要的讲解和编程示例的展示。在实际应用中,每种数据结构都有其适用的场景和优缺点,需要根据具体需求进行选择和使用。

相关文章
|
1月前
|
设计模式 算法 搜索推荐
C++数据结构设计:理解并选择策略模式与模板特化
C++数据结构设计:理解并选择策略模式与模板特化
54 2
|
1月前
|
存储 安全 数据管理
探索C++中回调函数的数据结构和封装的权衡以及示例
探索C++中回调函数的数据结构和封装的权衡以及示例
83 4
|
1月前
|
存储 编译器 数据库
【C/C++ 数据结构 】线索二叉树全解析:从数学原理到C++实现
【C/C++ 数据结构 】线索二叉树全解析:从数学原理到C++实现
66 0
|
1月前
|
存储 算法 C++
【C/C++ 数据结构 】无向图和有向图的差异
【C/C++ 数据结构 】无向图和有向图的差异
60 0
|
1月前
|
算法 C++ 开发者
【C/C++ 数据结构 】二叉树基本性质:对于任何一颗二叉树T,若其终端结点为n0 ,那么度数为2的结点数为n2。则n0=n2+1...
【C/C++ 数据结构 】二叉树基本性质:对于任何一颗二叉树T,若其终端结点为n0 ,那么度数为2的结点数为n2。则n0=n2+1...
29 0
|
6天前
|
存储 算法 程序员
【C++进阶】深入STL之 栈与队列:数据结构探索之旅
【C++进阶】深入STL之 栈与队列:数据结构探索之旅
15 4
|
1月前
|
算法 Go 数据库
数据结构/C++:位图 & 布隆过滤器
数据结构/C++:位图 & 布隆过滤器
17 0
|
1月前
|
存储 算法 C++
数据结构/C++:哈希表
数据结构/C++:哈希表
16 2
|
1月前
|
存储 算法 Java
数据结构/C++:红黑树
数据结构/C++:红黑树
20 3
|
1月前
|
存储 算法 C++
数据结构/C++:AVL树
数据结构/C++:AVL树
15 2

热门文章

最新文章