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

🕗 发布于 2024-11-09 03:55 c++ 笔记 数据结构

基础数据结构

数组（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); // 在第二个位置插入数字 50

vec.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]; // '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之前插入3

lst.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 3

    return 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_map
    std::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;
}

原文地址：https://blog.csdn.net/Bulling_/article/details/143572000

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：05 SQL炼金术：深入探索与实战优化
下一篇：SGD学习器和Adam学习器之间的区别与关系

vue 版本升级
这个警告是说eslint-plugin-vue package支持 node 12.22或者 14.17 或者 16.0.0以上版本，但是当前你的版本是 12.19.0，版本太低了需要更新 node版
阅读更多2024-11-09
理解虚拟 DOM：Vue 的灵魂之处
虚拟 DOM（Virtual DOM）是一个轻量级的 JavaScript 对象，它是实际 DOM 的一个抽象表示。在 Vue 中，当我们对数据进行修改时，框架不会立即更新真实的 DOM，而是首先对虚
阅读更多2024-11-09
vue3 动态路由+动态组件+缓存应用
vue3 动态路由+动态组件+缓存应用
阅读更多2024-11-09
机器学习—训练细节
然后张量流会试图最小化均方误差，在这个表达式中，用大写的J(W,B)来表示成本函数，成本函数是神经网络中所有参数的函数，所以你可以把W，B看作包括整个神经网络中的所有的W，B参数，所以如果你优化关于w
阅读更多2024-11-09
解释Python中的装饰器的作用
装饰器接收两个参数：一个是要装饰的函数，另一个是可选的额外参数列表。装饰器可以返回一个新的函数，这个新函数是原始函数的增强版，或者保持和原始函数相同的行为。装饰器在Python中是一种特殊类型的函数，
阅读更多2024-11-09
我自己nodejs练手时常用的一些库基础用法
我自己使用node练手时常用的一些库的基本使用记录：有bcrypt,express,pg,config,jwt和pm2
阅读更多2024-11-09
EasyPlayer.js无插件H5播放器支持哪些浏览器？
为了确保用户无论在何种设备或浏览器上都能享受到最佳的观看体验，EasyPlayer.js流媒体播放器应运而生，它以其卓越的跨浏览器兼容性和功能丰富性，成为了视频播放解决方案的佼佼者。这种广泛的兼容性使
阅读更多2024-11-09
Java-I/O框架13：文件夹的递归遍历和递归删除
16.29 递归遍历和递归删除_哔哩哔哩_bilibili。1.文件夹的递归遍历。2.文件夹的递归删除。
阅读更多2024-11-09
github和Visual Studio
使用很简单，自己稍微琢磨下就明白了。
阅读更多2024-11-09
Python毕业设计选题：基于django+vue的网上购物系统的设计与实现
网上购物系统是在实际应用和软件工程的开发原理之上，运用Python语言以及Django框架进行开发。首先要进行需求分析，分析出网上购物系统的主要功能，然后设计了系统结构。整体设计包括系统的功能、系统总
阅读更多2024-11-09