c++程序设计速学笔记2基础数据结构

基础数据结构

数组（Array）

数组是一种线性数据结构，它存储相同类型的元素的连续内存块。数组的每个元素都有一个索引，用于快速访问和操作数据。
特点：

• 随机访问：数组支持通过索引快速访问元素。
• 固定大小：静态数组的大小在声明时确定，动态数组（如C++中的std::vector）可以在运行时调整大小。
• 内存连续：数组元素在内存中存储是连续的，这使得访问速度快，但可能导致内存碎片。

vector 是一种动态数组容器，它封装了数组的功能，并允许在运行时动态地调整大小

#include <vector>
using namespace std;
vector<int> vec; // 创建一个存储整数的 vector
vector<std::string> strVec; // 创建一个存储字符串的 vector
//使用花括号 {} 来初始化 vector
vector<int> vec = {1, 2, 3, 4, 5};
vector<string> strVec = {"hello", "world"};
//使用 push_back() 方法向 vector 添加元素：
vec.push_back(6);
strVec.push_back("C++");
//使用下标 [] 访问 vector 中的元素：
int firstElement = vec[0]; // 获取第一个元素
string secondElement = strVec[1]; // 获取第二个元素bool isEmpty = vec.empty(); // 检查是否为空
int size = vec.size(); // 获取元素数量
int first = vec.front(); // 获取第一个元素
int last = vec.back(); // 获取最后一个元素for (int num : vec) {cout << num << " ";
}
cout << endl;vec[0] = 100; // 修改第一个元素vec.insert(vec.begin() + 1, 50); // 在第二个位置插入数字 50vec.erase(vec.begin() + 1); // 删除第二个位置的元素

string 是一个模板类，专门设计用来处理字符序列

1. 构造函数：可以创建空字符串或初始化为特定内容的字符串。
2. 赋值和修改：可以赋值、连接、插入和删除字符串中的字符。
3. 访问元素：可以使用下标操作符 [] 访问字符串中的单个字符。
4. 长度和容量：提供 size() 和 length() 来获取字符串的长度，以及 capacity() 来获取分配的存储空间。
5. 比较：提供比较操作符来比较两个字符串。
6. 查找和替换：提供方法在字符串中查找子串，并替换匹配的子串。
7. 子串：提供 substr() 方法来获取字符串的子串。
8. 迭代器：支持迭代器，可以遍历字符串中的每个字符。

#include <iostream>
#include <string>
using namespace std;
int main() {// 创建字符串string greeting = "Hello, World!";string name = "Kimi";// 输出字符串cout << greeting << std::endl;// 连接字符串string message = "My name is " + name + ".";cout << message << endl;// 访问特定字符char firstChar = message[0]; // 'M'cout << "The first character is: " << firstChar << endl;// 获取字符串长度cout << "The length of the message is: " << message.length() << endl;// 修改字符串message[0] = 'H'; // 修改第一个字符为 'H'cout << "Modified message: " << message << endl;return 0;
}

链表（Linked List）

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。
特点：

• 动态大小：链表的大小可以在运行时动态变化，适合不确定数量元素的情况。
• 非连续内存：链表的元素不需要在内存中连续存储，这使得它们在处理大量数据时更加灵活。
• 插入和删除：链表的插入和删除操作通常比数组更高效，因为不需要移动大量元素。

常见类型：

• 单链表：每个节点指向下一个节点。
• 双链表：每个节点指向前一个和后一个节点。
• 循环链表：最后一个节点指向第一个节点，形成一个循环。
  单链表

#include <iostream>
#include <forward_list>forward_list<int> fl;fl.push_front(1);fl.push_back(4);auto it = fl.before_begin(); // 获取逆向迭代器
std::advance(it, 2); // 移动到第三个元素之前
fl.insert_after(it, 5);fl.remove(3);//删除所有匹配的元素auto it = fl.begin();
std::advance(it, 2); // 移动到第三个元素
fl.erase_after(it); // 删除第三个元素//遍历 
for (int elem : fl) {std::cout << elem << " ";
}
std::cout << std::endl;//获取链表大小
std::cout << "Size of forward_list: " << fl.size() << std::endl;//清空
fl.clear();排序
std::sort(fl.begin(), fl.end());//反转
std::forward_list<int> reversed_fl;
for (auto it = fl.before_begin(); it != fl.end(); ++it) {reversed_fl.push_front(*it);
}
fl = std::move(reversed_fl);//查找元素
auto it = std::find(fl.begin(), fl.end(), 2);
if (it != fl.end()) {std::cout << "Found element 2 at position: " << std::distance(fl.begin(), it) << std::endl;
}

双向链表
需要频繁插入和删除元素的场景中非常有用。然而，由于它不支持随机访问，所以不适合需要频繁访问中间元素的场景。

#include <list>
std::list<int> lst;lst.push_front(1);
lst.push_back(2);auto it = std::find(lst.begin(), lst.end(), 1); // 找到元素1的位置
lst.insert(it, 3); // 在元素1之前插入3lst.remove(2);it = std::find(lst.begin(), lst.end(), 3); // 找到元素3的位置
lst.erase(it); // 删除元素3//遍历
for (const auto& elem : lst) {std::cout << elem << " ";
}
std::cout << std::endl;//排序
lst.sort(); // 默认使用 `<` 比较元素
//反转
lst.reverse();//查找元素
it = std::find(lst.begin(), lst.end(), 2); // 查找元素2
if (it != lst.end()) {std::cout << "Found element 2" << std::endl;
}//合并和分割列表
std::list<int> anotherList = {4, 5, 6};
lst.merge(anotherList); // 合并两个列表
anotherList.splice(anotherList.begin(), lst); // 将anotherList的元素移动到lst//插入范围
int arr[] = {7, 8, 9};
lst.insert(lst.end(), std::begin(arr), std::end(arr));

循环链表

#include <iostream>
#include <list>int main() {std::list<int>循环链表 = {1, 2, 3, 4, 5};// 遍历循环链表for (auto it = 循环链表.begin(); it != 循环链表.end(); ++it) {std::cout << *it << " ";}std::cout << std::endl;// 将迭代器移动到末尾，并获取下一个元素，实现循环auto it = 循环链表.end();--it; // 移动到最后一个元素std::cout << "最后一个元素: " << *it << std::endl;// 模拟循环链表的下一个元素std::cout << "下一个元素: " << *(it++) << std::endl;return 0;
}

#include <iostream>class Node {
public:int data;Node* next;Node(int val) : data(val), next(nullptr) {}
};class CircularLinkedList {
private:Node* head;Node* tail;public:CircularLinkedList() : head(nullptr), tail(nullptr) {}~CircularLinkedList() {while (head) {Node* temp = head;head = head->next;delete temp;}}void append(int value) {Node* newNode = new Node(value);if (!head) {head = tail = newNode;head->next = head; // 使链表循环} else {tail->next = newNode;tail = newNode;tail->next = head; // 使链表循环}}void display() {if (!head) return;Node* current = head;do {std::cout << current->data << " ";current = current->next;} while (current != head);std::cout << std::endl;}
};int main() {CircularLinkedList cll;cll.append(1);cll.append(2);cll.append(3);cll.display(); // 输出: 1 2 3return 0;
}

栈（Stack）

栈（Stack）是一种后进先出（LIFO，Last In First Out）的数据结构。

• 压栈（Push）：在栈顶添加一个元素。
• 弹栈（Pop）：从栈顶移除一个元素。
• 查看栈顶（Top）：获取栈顶的元素，但不移除它。

栈常用于处理需要回溯的场景，如函数调用栈、撤销操作、括号匹配等
stack 容器适配器和 array 或 vector 作为底层容器的栈。

#include <iostream>
#include <stack>
using namespace std;int main() {// 创建一个整数类型的栈stack<int> s;// 向栈中压入元素s.push(1);s.push(2);s.push(3);// 查看栈是否为空cout << "Stack is empty: " << (s.empty() ? "Yes" : "No") << std::endl;// 查看栈顶元素std::cout << "Top element: " << s.top() << std::endl;// 弹出栈顶元素std::cout << "Popping top element..." << std::endl;s.pop();// 再次查看栈是否为空std::cout << "Stack is empty after pop: " << (s.empty() ? "Yes" : "No") << std::endl;// 再次查看栈顶元素std::cout << "Top element after pop: " << s.top() << std::endl;return 0;
}

队列

先进先出（FIFO, First-In-First-Out）

• 入队（Enqueue）：在队列的末尾添加一个元素。
• 出队（Dequeue）：从队列的开头移除一个元素。
• 查看队首（Front）：获取队列开头的元素，但不移除它。
• 查看队尾（Back/Rear）：获取队列末尾的元素。

队列常用于处理需要保持元素顺序的场景，如打印任务队列、消息队列等。

#include <iostream>
#include <queue>
using namespace std;int main() {// 创建一个整数类型的队列queue<int> q;// 向队列中添加元素q.push(1);q.push(2);q.push(3);// 检查队列是否为空cout << "Queue is empty: " << (q.empty() ? "Yes" : "No") << endl;// 获取队列的大小cout << "Queue size: " << q.size() << endl;// 获取队列的第一个元素（队首）cout << "Front element: " << q.front() << endl;// 移除队列的第一个元素q.pop();// 再次检查队列是否为空和大小cout << "Queue is empty after one pop: " << (q.empty() ? "Yes" : "No") << endl;cout << "Queue size after one pop: " << q.size() << endl;// 再次获取队列的第一个元素cout << "Front element after one pop: " << q.front() << endl;return 0;
}

哈希表（Hash Table）

unordered_map来实现，它是基于哈希表的关联容器
注意线程安全问题

#include <iostream>
#include <unordered_map>
#include <string>int main() {// 创建一个 unordered_mapstd::unordered_map<std::string, int> ageMap;// 插入元素ageMap.insert({"Alice", 30});ageMap.insert(std::make_pair("Bob", 25));ageMap["Charlie"] = 35;// 查找元素auto it = ageMap.find("Alice");if (it != ageMap.end()) {std::cout << "Alice's age is " << it->second << std::endl;} else {std::cout << "Alice not found" << std::endl;}try {std::cout << "Alice's age is " << ageMap.at("Alice") << std::endl;} catch (const std::out_of_range& e) {std::cout << "Alice not found" << std::endl;}// 删除元素ageMap.erase("Bob");// 清空容器ageMap.clear();// 获取容器大小std::cout << "Number of elements: " << ageMap.size() << std::endl;// 检查容器是否为空if (ageMap.empty()) {std::cout << "The map is empty" << std::endl;} else {std::cout << "The map is not empty" << std::endl;}// 重新插入元素ageMap.insert({"Alice", 30});ageMap.insert({"Bob", 25});ageMap.insert({"Charlie", 35});// 遍历所有元素for (const auto& pair : ageMap) {std::cout << pair.first << " is " << pair.second << " years old." << std::endl;}// 桶相关操作std::cout << "Number of buckets: " << ageMap.bucket_count() << std::endl;std::cout << "Maximum number of buckets: " << ageMap.max_bucket_count() << std::endl;for (size_t i = 0; i < ageMap.bucket_count(); ++i) {std::cout << "Bucket " << i << " contains " << ageMap.bucket_size(i) << " elements." << std::endl;}std::string key = "Alice";std::cout << "Key " << key << " is in bucket " << ageMap.bucket(key) << std::endl;return 0;
}