第三部分：数据结构与算法（概述）
C++中的数据结构与算法是程序设计的重要组成部分，以下是一些常见的数据结构和算法及其在C++中的实现与应用：
一、数据结构
1. 数组（Array）
数组是一种线性数据结构，它存储一组相同类型的元素，这些元素在内存中是连续存储的。
在C++中，可以使用原生数组或者std::vector（动态数组）来表示。
示例（使用原生数组）
#include <iostream>
int main() {
int arr[5] = {1, 2, 3, 4, 5};
for (int i = 0; i < 5; ++i) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}示例（使用std::vector）
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
for (int num : vec) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}2. 链表（Linked List）
链表是由一系列节点组成的数据结构，每个节点包含数据和指向下一个节点的指针。链表可以分为单链表、双链表和循环链表等。
单链表示例（节点定义和链表操作）
// 单链表节点定义
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
// 构建单链表
ListNode* createLinkedList() {
ListNode* head = new ListNode(1);
ListNode* node2 = new ListNode(2);
ListNode* node3 = new ListNode(3);
head->next = node2;
node2->next = node3;
return head;
}
// 遍历单链表
void traverseLinkedList(ListNode* head) {
ListNode* current = head;
while (current!= NULL) {
std::cout << current->val << " ";
current = current->next;
}
std::cout << std::endl;
}3. 栈（Stack）
栈是一种后进先出（LIFO）的数据结构。在C++中，可以使用std::stack来实现栈的操作。
示例（使用std::stack）
#include <stack>
#include <iostream>
int main() {
std::stack<int> s;
s.push(1);
s.push(2);
s.push(3);
while (!s.empty()) {
std::cout << s.top() << " ";
s.pop();
}
std::cout << std::endl;
return 0;
}4. 队列（Queue）
队列是一种先进先出（FIFO）的数据结构。在C++中，可以使用std::queue来实现队列的操作。
示例（使用std::queue）
#include <queue>
#include <iostream>
int main() {
std::queue<int> q;
q.push(1);
q.push(2);
q.push(3);
while (!q.empty()) {
std::cout << q.front() << " ";
q.pop();
}
std::cout << std::endl;
return 0;
}5. 树（Tree）
树是一种非线性的数据结构，由节点和边组成，有一个根节点，每个节点可以有零个或多个子节点。二叉树是树结构的一种特殊形式，其中每个节点最多有两个子节点（左子节点和右子节点）。
二叉树节点定义和简单遍历示例
// 二叉树节点定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 前序遍历二叉树
void preorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
std::cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}6. 图（Graph）
图是由顶点（节点）和边组成的数据结构，可以用来表示各种复杂的关系，如社交网络中的人际关系、交通网络中的道路连接等。图可以分为有向图和无向图。
简单的图表示（邻接矩阵）和深度优先搜索示例（针对无向图）
#include <iostream>
#include <vector>
// 使用邻接矩阵表示无向图
class Graph {
public:
Graph(int numVertices) : numVertices(numVertices) {
adjMatrix.resize(numVertices, std::vector<int>(numVertices, 0));
}
void addEdge(int src, int dest) {
adjMatrix[src][dest] = 1;
adjMatrix[dest][src] = 1;
}
void dfs(int startVertex) {
std::vector<bool> visited(numVertices, false);
dfsUtil(startVertex, visited);
}
private:
int numVertices;
std::vector<std::vector<int>> adjMatrix;
void dfsUtil(int vertex, std::vector<bool>& visited) {
visited[vertex] = true;
std::cout << vertex << " ";
for (int i = 0; i < numVertices; ++i) {
if (adjMatrix[vertex][i] == 1 &&!visited[i]) {
dfsUtil(i, visited);
}
}
}
};二、算法
1. 排序算法
冒泡排序（Bubble Sort）
冒泡排序是一种简单的排序算法，它通过反复比较相邻的元素并交换它们（如果它们的顺序错误），直到整个数组被排序。
#include <iostream>
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; ++i) {
for (int j = 0; j < n - i - 1; ++j) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int arr[] = {2, 1, 9, 8, 5};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}快速排序（Quick Sort）
快速排序是一种高效的排序算法，它采用分治策略。选择一个元素作为枢轴（pivot），将数组分为两部分，小于枢轴的元素和大于枢轴的元素，然后对这两部分递归地进行排序。
#include <iostream>
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; ++j) {
if (arr[j] <= pivot) {
++i;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main() {
int arr[] = {5, 4, 3, 2, 1};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}2. 搜索算法
线性搜索（Linear Search）
线性搜索是一种简单的搜索算法，它顺序地遍历数组中的元素，直到找到目标元素或者遍历完整个数组。
#include <iostream>
int linearSearch(int arr[], int n, int target) {
for (int i = 0; i < n; ++i) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 3;
int result = linearSearch(arr, n, target);
if (result!= -1) {
std::cout << "Element found at index: " << result << std::endl;
} else {
std::cout << "Element not found." << std::endl;
}
return 0;
}二分搜索（Binary Search）
二分搜索是一种用于有序数组的高效搜索算法。它每次比较中间元素与目标元素，然后根据比较结果决定在数组的左半部分还是右半部分继续搜索。
#include <iostream>
int binarySearch(int arr[], int low, int high, int target) {
while (low <= high) {
int mid = low+(high - low) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 3;
int result = binarySearch(arr, 0, n - 1, target);
if (result!= -1) {
std::cout << "Element found at index: " << result << std::endl;
} else {
std::cout << "Element not found." << std::endl;
}
return 0;
}
C++编程语言基础
第三部分：数据结构与算法（概述）
