【C++ 数据结构与算法 一站式备考指南】一文掌握 数据结构与算法课程 知识点（一）

int arr[10]; // 初始化一个大小为10的整数数组

#include <vector>
std::vector<int> vec;  // 初始化一个空的整数动态数组
std::vector<int> vec(10);  // 初始化一个大小为10的整数动态数组

int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int element = arr[5];  // 直接通过索引查找，element现在是6
std::vector<int> vec = {1, 2, 3, 4, 5};
int another_element = vec[2];  // another_element现在是3

std::vector<int> vec = {1, 2, 3};
vec.push_back(4);  // 在尾部插入元素，现在vector为 {1, 2, 3, 4}
vec.insert(vec.begin() + 1, 0);  // 在索引1的位置插入元素0，现在vector为 {1, 0, 2, 3, 4}

std::vector<int> vec = {1, 0, 2, 3, 4};
vec.erase(vec.begin() + 1);  // 删除索引1处的元素，现在vector为 {1, 2, 3, 4}
vec.pop_back();  // 删除最后一个元素，现在vector为 {1, 2, 3}

#include <iostream>
int main() {
    int arr[5] = {1, 2, 3, 4, 5};  // 初始化
    // 查找
    int element_to_find = 4;
    for (int i = 0; i < 5; ++i) {
        if (arr[i] == element_to_find) {
            std::cout << "Element found at index: " << i << std::endl;
            break;
        }
    }
    // 插入（在索引2插入元素6）
    for (int i = 4; i >= 2; --i) {
        arr[i] = arr[i - 1];
    }
    arr[2] = 6;
    // 删除（删除索引1的元素）
    for (int i = 1; i < 4; ++i) {
        arr[i] = arr[i + 1];
    }
    // 输出数组
    for (int i = 0; i < 5; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

#include <iostream>
#include <vector>
int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};  // 初始化
    // 查找
    int element_to_find = 4;
    for (size_t i = 0; i < vec.size(); ++i) {
        if (vec[i] == element_to_find) {
            std::cout << "Element found at index: " << i << std::endl;
            break;
        }
    }
    // 插入（在索引2插入元素6）
    vec.insert(vec.begin() + 2, 6);
    // 删除（删除索引1的元素）
    vec.erase(vec.begin() + 1);
    // 输出vector
    for (auto elem : vec) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    return 0;
}

struct Node {
    int data;
    Node* next;
};
Node* head = new Node();  // 创建一个空的头节点
head->next = nullptr;  // 初始化头节点的next指针为nullptr

Node* find(int value, Node* head) {
    Node* current = head->next;  // 从第一个数据节点开始
    while (current != nullptr) {
        if (current->data == value) {
            return current;  // 返回找到的节点
        }
        current = current->next;  // 移动到下一个节点
    }
    return nullptr;  // 如果没有找到，返回nullptr
}

void insert(int value, Node* prevNode) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

void deleteNode(Node* prevNode) {
    if (prevNode->next == nullptr) {
        return;  // 没有可删除的节点
    }
    Node* tempNode = prevNode->next;
    prevNode->next = tempNode->next;
    delete tempNode;  // 释放内存
}

#include <iostream>
struct Node {
    int data;
    Node* next;
};
// 初始化单链表
Node* initialize() {
    Node* head = new Node();
    head->next = nullptr;
    return head;
}
// 查找元素
Node* find(int value, Node* head) {
    Node* current = head->next;
    while (current != nullptr) {
        if (current->data == value) {
            return current;
        }
        current = current->next;
    }
    return nullptr;
}
// 插入元素
void insert(int value, Node* prevNode) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}
// 删除元素
void deleteNode(Node* prevNode) {
    if (prevNode->next == nullptr) {
        return;
    }
    Node* tempNode = prevNode->next;
    prevNode->next = tempNode->next;
    delete tempNode;
}
// 打印链表
void printList(Node* head) {
    Node* current = head->next;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}
int main() {
    Node* head = initialize();
    insert(1, head);
    insert(2, head);
    insert(3, head);
    std::cout << "Original List: ";
    printList(head);
    Node* node = find(2, head);
    if (node != nullptr) {
        std::cout << "Element found: " << node->data << std::endl;
    } else {
        std::cout << "Element not found." << std::endl;
    }
    deleteNode(head);  // 删除头节点后的第一个元素
    std::cout << "List after deletion: ";
    printList(head);
    return 0;
}

#include <iostream>
#include <stack>
using namespace std;
void decimalToBinary(int n) {
    stack<int> s;
    while (n > 0) {
        s.push(n % 2);
        n = n / 2;
    }
    while (!s.empty()) {
        cout << s.top();
        s.pop();
    }
    cout << endl;
}
int main() {
    int n = 10;
    cout << "The binary representation of " << n << " is: ";
    decimalToBinary(n);
    return 0;
}

#include <iostream>
#include <stack>
using namespace std;
bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '{' || c == '[') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char top = st.top();
            st.pop();
            if ((c == ')' && top != '(') || 
                (c == '}' && top != '{') || 
                (c == ']' && top != '[')) {
                return false;
            }
        }
    }
    return st.empty();
}
int main() {
    string s = "{[()]}";
    if (isValid(s)) {
        cout << "The string is balanced." << endl;
    } else {
        cout << "The string is not balanced." << endl;
    }
    return 0;
}

#include <iostream>
#include <stack>
using namespace std;
int main() {
    stack<int> s;
    // Push elements into stack
    s.push(10);
    s.push(20);
    s.push(30);
    // Pop elements from stack
    s.pop();
    // Get the top element
    if (!s.empty()) {
        cout << "Top element: " << s.top() << endl;
    }
    return 0;
}

#include <iostream>
#include <stack>
#include <string>
using namespace std;
bool isPalindrome(string str) {
    stack<char> s;
    string reversedStr = "";
    // Push all characters of the string into stack
    for (char c : str) {
        s.push(c);
    }
    // Pop characters from stack to form the reversed string
    while (!s.empty()) {
        reversedStr += s.top();
        s.pop();
    }
    return str == reversedStr;
}
int main() {
    string str = "level";
    if (isPalindrome(str)) {
        cout << str << " is a palindrome." << endl;
    } else {
        cout << str << " is not a palindrome." << endl;
    }
    return 0;
}

#include <iostream>
#include <queue>
#include <string>
using namespace std;
void taskScheduler(queue<string> &tasks) {
    while (!tasks.empty()) {
        cout << "Processing task: " << tasks.front() << endl;
        tasks.pop();
    }
}
int main() {
    queue<string> tasks;
    // Adding tasks to the queue
    tasks.push("Task 1");
    tasks.push("Task 2");
    tasks.push("Task 3");
    // Process tasks
    taskScheduler(tasks);
    return 0;
}

#include <iostream>
#include <queue>
using namespace std;
double calculateAverage(queue<int> &data, int windowSize) {
    double sum = 0;
    if (data.size() < windowSize) return 0;
    queue<int> windowData;
    for (int i = 0; i < windowSize; ++i) {
        int value = data.front();
        sum += value;
        windowData.push(value);
        data.pop();
    }
    return sum / windowSize;
}
int main() {
    queue<int> data;
    data.push(1);
    data.push(2);
    data.push(3);
    data.push(4);
    data.push(5);
    int windowSize = 3;
    double average = calculateAverage(data, windowSize);
    cout << "The average of the last " << windowSize << " elements is: " << average << endl;
    return 0;
}

#include <iostream>
#include <deque>
using namespace std;
int main() {
    deque<int> dq;
    // Insert elements at the end
    dq.push_back(10);
    dq.push_back(20);
    // Insert elements at the beginning
    dq.push_front(30);
    dq.push_front(40);
    // Remove elements from the end
    dq.pop_back();
    // Remove elements from the beginning
    dq.pop_front();
    // Display elements
    for (int elem : dq) {
        cout << elem << " ";
    }
    cout << endl;
    return 0;
}

#include <iostream>
#include <queue>
using namespace std;
int main() {
    priority_queue<int> pq;
    // Insert elements
    pq.push(10);
    pq.push(30);
    pq.push(20);
    // Remove and display elements
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;
    return 0;
}