江苏外贸型网站制作,微平台网站支持html5实现游戏,品牌网站建设解决,网站建设唯地带基础数据结构
数组#xff08;Array#xff09;
数组是一种线性数据结构#xff0c;它存储相同类型的元素的连续内存块。数组的每个元素都有一个索引#xff0c;用于快速访问和操作数据。 特点#xff1a;
随机访问#xff1a;数组支持通过索引快速访问元素。固定大小…基础数据结构
数组Array
数组是一种线性数据结构它存储相同类型的元素的连续内存块。数组的每个元素都有一个索引用于快速访问和操作数据。 特点
随机访问数组支持通过索引快速访问元素。固定大小静态数组的大小在声明时确定动态数组如C中的std::vector可以在运行时调整大小。内存连续数组元素在内存中存储是连续的这使得访问速度快但可能导致内存碎片。
vector 是一种动态数组容器它封装了数组的功能并允许在运行时动态地调整大小
#include vector
using namespace std;
vectorint vec; // 创建一个存储整数的 vector
vectorstd::string strVec; // 创建一个存储字符串的 vector
//使用花括号 {} 来初始化 vector
vectorint vec {1, 2, 3, 4, 5};
vectorstring 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 是一个模板类专门设计用来处理字符序列
构造函数可以创建空字符串或初始化为特定内容的字符串。赋值和修改可以赋值、连接、插入和删除字符串中的字符。访问元素可以使用下标操作符 [] 访问字符串中的单个字符。长度和容量提供 size() 和 length() 来获取字符串的长度以及 capacity() 来获取分配的存储空间。比较提供比较操作符来比较两个字符串。查找和替换提供方法在字符串中查找子串并替换匹配的子串。子串提供 substr() 方法来获取字符串的子串。迭代器支持迭代器可以遍历字符串中的每个字符。
#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]; // Mcout The first character is: firstChar endl;// 获取字符串长度cout The length of the message is: message.length() endl;// 修改字符串message[0] H; // 修改第一个字符为 Hcout Modified message: message endl;return 0;
}链表Linked List
链表是一种线性数据结构由一系列节点组成每个节点包含数据部分和指向下一个节点的指针。 特点
动态大小链表的大小可以在运行时动态变化适合不确定数量元素的情况。非连续内存链表的元素不需要在内存中连续存储这使得它们在处理大量数据时更加灵活。插入和删除链表的插入和删除操作通常比数组更高效因为不需要移动大量元素。
常见类型
单链表每个节点指向下一个节点。双链表每个节点指向前一个和后一个节点。循环链表最后一个节点指向第一个节点形成一个循环。 单链表
#include iostream
#include forward_listforward_listint 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_listint 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::listint 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::listint 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 listint main() {std::listint循环链表 {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 iostreamclass 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是一种后进先出LIFOLast In First Out的数据结构。
压栈Push在栈顶添加一个元素。弹栈Pop从栈顶移除一个元素。查看栈顶Top获取栈顶的元素但不移除它。
栈常用于处理需要回溯的场景如函数调用栈、撤销操作、括号匹配等 stack 容器适配器和 array 或 vector 作为底层容器的栈。
#include iostream
#include stack
using namespace std;int main() {// 创建一个整数类型的栈stackint 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() {// 创建一个整数类型的队列queueint 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 stringint main() {// 创建一个 unordered_mapstd::unordered_mapstd::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 Alices age is it-second std::endl;} else {std::cout Alice not found std::endl;}try {std::cout Alices 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;
}
