首页 书籍 深入浅出程序设计竞赛

# 数组

C++ 中的 vector 是一个非常重要且广泛使用的容器类，它是标准模板库（STL）的一部分。 vector 可以被理解为一个动态数组，其大小可以在运行时动态改变，提供了比普通数组更灵活的操作方式。

# 基本概念

  • 动态数组：与传统的数组不同， vector 可以根据需要动态地增加或减少元素，自动管理内存。
  • 模板类： vector 是一个模板类，可以存储任意类型的元素，例如 vector<int> , vector<string> 等。

# 主要特性

  • 自动管理内存： vector 在需要扩容时会自动重新分配内存，并将旧元素复制到新的内存地址，释放旧的内存空间。
  • 随机访问： vector 支持通过下标直接访问元素，时间复杂度为 O (1)。
  • 尾部操作高效：向 vector 的尾部添加或删除元素非常高效，但在头部或中间插入或删除元素可能会导致元素移动，因此效率较低。

# 常用操作

  • 创建：可以创建一个空的 vector ，或者指定初始大小和元素值。
    vector<int> v1; // 创建一个空的 vector
    vector<int> v2(5, 10); // 创建一个有 5 个元素，每个元素值为 10 的 vector
  • 访问元素：使用 at() 或者 [] 运算符访问元素。
    int value = v[0]; // 使用下标访问
    int value = v.at(0); // 使用 at () 访问，更安全，会检查下标越界
  • 添加元素：使用 push_back() 在尾部添加元素。
    v.push_back(20); // 在尾部添加一个值为 20 的元素
  • 删除元素：使用 pop_back() 删除尾部元素，使用 erase() 删除指定位置的元素。
    v.pop_back(); // 删除尾部元素
    v.erase(v.begin()); // 删除第一个元素
  • 大小操作：可以使用 size() 获取 vector 的元素个数， empty() 检查 vector 是否为空， resize() 改变 vector 的大小。

# 性能考虑

  • vector 的动态扩展会涉及到内存重新分配以及元素的拷贝，这可能是一个耗时的操作。因此，在知道大致容量需求时，使用 reserve() 预分配内存是一个好的实践。
  • 尽量避免在 vector 的头部或中间进行插入和删除操作，因为这会导致大量元素的移动。

# 题目：寄包柜

超市里有 n*(1≤n≤105) 个寄包柜。每个寄包柜格子数量不一，第 i 个寄包柜有 ai (1≤ai≤105) 个格子，不过我们并不知道各个 ai 的值。对于每个寄包柜，格子编号从 1 开始，一直到 ai。现在有 q*(1≤q≤105) 次操作：

  • 1 i j k ：在第 i 个柜子的第 j 个格子存入物品 k*(0≤k≤109)。当 k*=0 时说明清空该格子。
  • 2 i j ：查询第 i 个柜子的第 j* 个格子中的物品是什么，保证查询的柜子有存过东西。

已知超市里共计不会超过 107 个寄包格子 ai 是确定然而未知的，但是保证一定不小于该柜子存物品请求的格子编号的最大值。当然也有可能某些寄包柜中一个格子都没有。

# 分析

# 栈

栈是一种遵循后进先出（LIFO, Last In First Out）原则的数据结构。它只允许在栈顶进行添加或删除操作。栈可以用数组或链表实现

在 C++ 的 STL 中， std::stack 提供了以下几个主要的成员函数：

  • push(const T& value) ：将一个新元素添加到栈顶。
  • pop() ：移除栈顶元素。
  • top() ：返回栈顶元素的引用。
  • empty() ：检查栈是否为空，如果为空返回 true，否则返回 false。
  • size() ：返回栈中元素的个数

数组实现栈

#include <iostream>
using namespace std;
class Stack {
private:
    int* arr;
    int capacity;
    int top;
public:
    // 构造函数
    Stack(int size = 10) {  // 默认大小为 10
        arr = new int[size];
        capacity = size;
        top = -1;
    }
    // 析构函数
    ~Stack() {
        delete[] arr;
    }
    // 添加元素到栈顶
    void push(int x) {
        if (isFull()) {
            cout << "栈溢出\n";
            exit(EXIT_FAILURE);
        }
        arr[++top] = x;
    }
    // 移除栈顶元素
    int pop() {
        if (isEmpty()) {
            cout << "栈为空\n";
            exit(EXIT_FAILURE);
        }
        return arr[top--];
    }
    // 返回栈顶元素
    int peek() {
        if (!isEmpty()) {
            return arr[top];
        } else {
            cout << "栈为空\n";
            exit(EXIT_FAILURE);
        }
    }
    // 检查栈是否为空
    bool isEmpty() {
        return top == -1;
    }
    // 检查栈是否已满
    bool isFull() {
        return top == capacity - 1;
    }
    // 返回栈的大小
    int size() {
        return top + 1;
    }
};
int main() {
    Stack stack(3);
    stack.push(1);
    stack.push(2);
    stack.push(3);
    cout << "栈顶元素: " << stack.peek() << endl;
    stack.pop();
    cout << "移除栈顶元素后，新的栈顶元素: " << stack.peek() << endl;
    if (!stack.isEmpty()) {
        cout << "栈非空" << endl;
    }
    cout << "栈中元素数量: " << stack.size() << endl;
    return 0;
}
# 题目：后缀表达式


所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。


本题中运算符仅包含 +-*/。保证对于 / 运算除数不为 0。特别地，其中 / 运算的结果需要向 0 取整（即与 C++  /  运算的规则一致）。


如：3*(5-2)+7 对应的后缀表达式为：3.5.2.-*7.+@。在该式中， @  为表达式的结束符号。 .  为操作数的结束符号。


输入一行一个字符串 s，表示后缀表达式。


输出一个整数，表示表达式的值。


# 分析


后缀表达式（也称为逆波兰表达式）的求值可以通过使用一个栈来实现。遍历整个表达式，对于每个遇到的元素执行以下操作：


    

  1. 操作数：如果是操作数（数字），则将其推入栈中。
    2. 

  2. 运算符：如果是运算符（+、-、*、/），则从栈中弹出两个操作数，先弹出的作为右操作数，后弹出的作为左操作数，执行相应的运算，并将结果推回栈中。
    3. 

  3. 结束符号：当遇到表达式的结束符号 @ 时，停止处理。
    4. 

  4. 操作数结束符号： .  用来分隔或标识操作数的结束，有助于区分多位数的操作数。
    5. 



# 代码


// 后缀表达式
#include <stack>
#include <cstdio>
using namespace std;
stack<int> n;
int s = 0, x,y;
int main(){
    char ch;
    do{
        ch = getchar();
        if(ch >= '0' && ch <= '9')
            s = s * 10 + ch - '0';
        else if(ch == '.')
            n.push(s),s = 0;
        else if(ch != '@'){
            x = n.top();n.pop();y = n.top();n.pop();
            switch (ch) {
                case '+': n.push(x + y); break;
                case '-': n.push(x - y); break;
                case '*': n.push(x * y); break;
                case '/': n.push(x / y); break;
            }
        }
    } while (ch != '@');
    printf("%d\n",n.top());
    return 0;
}
# 队列


队列是一种先进先出（FIFO, First In First Out）的数据结构，它允许在队列的一端（通常称为队尾 rear 或 back）添加元素，在队列的另一端（通常称为队头 front）移除元素。队列常用于任务调度、缓存实现等场景。


在 C++ 的 STL（Standard Template Library）中， std::queue  提供了以下几个主要的成员函数：


    

  • push(const T& value) ：向队尾添加一个新元素。
    • 

  • pop() ：移除队头的元素。
    • 

  • front() ：返回队头元素的引用。
    • 

  • back() ：返回队尾元素的引用。
    • 

  • empty() ：检查队列是否为空，如果为空返回 true，否则返回 false。
    • 

  • size() ：返回队列中元素的个数。
    • 



链表实现队列


#include <iostream>
using namespace std;
class Node {
public:
    int value;
    Node* next;
    Node(int value) : value(value), next(nullptr) {}
};
class Queue {
private:
    Node* front; // 队头指针
    Node* rear;  // 队尾指针
    int count;   // 队列中元素的数量
public:
    // 构造函数
    Queue() : front(nullptr), rear(nullptr), count(0) {}
    // 析构函数
    ~Queue() {
        while(!isEmpty()) {
            pop();
        }
    }
    // 向队尾添加元素
    void push(int value) {
        Node* newNode = new Node(value);
        if (isEmpty()) {
            front = rear = newNode;
        } else {
            rear->next = newNode;
            rear = newNode;
        }
        count++;
    }
    // 移除队头元素
    void pop() {
        if (isEmpty()) {
            cout << "队列为空\n";
            return;
        }
        Node* temp = front;
        front = front->next;
        delete temp;
        count--;
        if (isEmpty()) {
            rear = nullptr; // 如果队列变空，重置 rear 指针
        }
    }
    // 返回队头元素
    int peek() {
        if (!isEmpty()) {
            return front->value;
        } else {
            cout << "队列为空\n";
            exit(EXIT_FAILURE);
        }
    }
    // 检查队列是否为空
    bool isEmpty() {
        return count == 0;
    }
    // 返回队列的大小
    int size() {
        return count;
    }
};
int main() {
    Queue queue;
    queue.push(1);
    queue.push(2);
    queue.push(3);
    cout << "队头元素: " << queue.peek() << endl;
    queue.pop();
    cout << "移除队头元素后，新的队头元素: " << queue.peek() << endl;
    if (!queue.isEmpty()) {
        cout << "队列非空" << endl;
    }
    cout << "队列中元素数量: " << queue.size() << endl;
    return 0;
}
# 题目：约瑟夫问题


n 个人围成一圈，从第一个人开始报数，数到 m 的人出列，再由下一个人重新从 1 开始报数，数到 m 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。


# 分析


    

  1. 初始化一个队列，将所有人的编号按顺序入队。
    2. 

  2. 开始报数，进行循环，每次循环中：

      

    • 从队头取出一个元素（即一个人的编号）。
      • 

    • 如果这次是第 m 次报数，这个人就 “出圈”（即不再将其编号放回队列），同时记录或输出这个人的编号。
      • 

    • 如果不是第 m 次报数，这个人继续参与下一轮报数，即将其编号放回队尾。
      • 

    

    3. 

  3. 当队列为空时，所有人都已经出圈，程序结束。
    4. 



# 代码


#include <iostream>
#include <queue>
using namespace std;
void josephus(int n, int m) {
    queue<int> q;
    // 初始化，将所有人的编号入队
    for (int i = 1; i <= n; ++i) {
        q.push(i);
    }
    cout << "出圈顺序: ";
    while (!q.empty()) {
        // 每次报数到 m-1 的人会被放回队尾，第 m 个人出圈
        for (int count = 1; count < m; ++count) {
            q.push(q.front()); // 报数不到 m 的，重新放回队尾
            q.pop();
        }
        // 第 m 个人出圈
        cout << q.front();
        if (q.size() > 1) {
            cout << ", ";
        }
        q.pop();
    }
    cout << endl;
}
int main() {
    int n, m;
    cout << "请输入总人数n: ";
    cin >> n;
    cout << "请输入报数m: ";
    cin >> m;
    josephus(n, m);
    return 0;
}
# 链表


链表是一种常见的基础数据结构，它是由一系列节点组成的集合。每个节点包含两部分：一部分存储数据元素，另一部分存储指向下一个节点的指针（在单链表中）。这种结构允许有效地在序列中的任何位置插入或删除元素，而无需重新排列数据。


链表主要有以下几种类型：


    

  • 单向链表：每个节点只包含指向下一个节点的指针。
    • 

  • 双向链表：每个节点包含两个指针，分别指向前一个节点和后一个节点。
    • 

  • 循环链表：链表的尾部指向头部，形成一个环。
    • 



#include <stdio.h>
#include <stdlib.h>
// 定义链表节点的结构体
typedef struct Node {
    int data;
    struct Node* next;
} Node;
// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
// 在链表末尾添加新节点
void appendNode(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node* temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}
// 删除链表中的节点
void deleteNode(Node** head, int key) {
    Node *temp = *head, *prev = NULL;
    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) return;
    prev->next = temp->next;
    free(temp);
}
// 打印链表
void printList(Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}
int main() {
    Node* head = NULL;
    appendNode(&head, 1);
    appendNode(&head, 2);
    appendNode(&head, 3);
    printList(head);
    
    deleteNode(&head, 2);
    printList(head);
    
    return 0;
}
# 题目：约瑟夫问题


n 个人围成一圈，从第一个人开始报数，数到 m 的人出列，再由下一个人重新从 1 开始报数，数到 m 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。


# 分析


创建一个包含 n 个节点的循环链表，每个节点代表一个人。然后，从头节点开始遍历链表，进行报数。每次数到 m，就移除当前节点（即该人出列）。重复这个过程，直到链表为空。


# 代码


#include <iostream>
using namespace std;
// 定义链表节点结构体
struct Node {
    int data;
    Node* next;
    //// 构造函数
    Node(int data): data(data), next(nullptr) {}
};
// 创建一个含有 n 个节点的循环链表
Node* createCircularList(int n) {
    if (n <= 0) return nullptr;
    Node* head = new Node(1);
    Node* prev = head;
    for (int i = 2; i <= n; ++i) {
        Node* curr = new Node(i);
        prev->next = curr;
        prev = curr;
    }
    prev->next = head; // 形成循环
    return head;
}
// 解决约瑟夫问题
void josephus(int n, int m) {
    Node* head = createCircularList(n);
    Node* curr = head;
    Node* prev = nullptr;
    while (curr->next != curr) { // 当链表中不止一个节点时
        int count = 1;
        while (count < m) {
            prev = curr;
            curr = curr->next;
            ++count;
        }
        // 删除第 m 个节点
        cout << curr->data << " ";
        prev->next = curr->next;
        delete curr;
        curr = prev->next;
    }
    cout << curr->data << endl; // 输出最后一个出列的人
    delete curr; // 清理内存
}
int main() {
    int n, m;
    cout << "请输入总人数n: ";
    cin >> n;
    cout << "请输入报数m: ";
    cin >> m;
    josephus(n, m);
    return 0;
}

      

          
          
      

  


   


    

  
    
      
    
    更新于