数据结构与算法面试高频（基础算法）

基础算法

1 实现一个vector⭐⭐⭐⭐

#include <iostream>
#include <stdexcept>

template <typename T>
class MyVector {
private:
    T* data;  // 指向动态分配数组的指针
    size_t size_;  // 当前元素的数量
    size_t capacity_;  // 当前数组的容量

    // 重新分配内存，扩大容量
    void reserve(size_t newCapacity) {
        if (newCapacity <= capacity_) return;

        T* newData = new T[newCapacity];
        for (size_t i = 0; i < size_; ++i) {
            newData[i] = data[i];
        }
        delete[] data;
        data = newData;
        capacity_ = newCapacity;
    }

public:
    // 默认构造函数
    MyVector() : data(nullptr), size_(0), capacity_(0) {}

    // 析构函数
    ~MyVector() {
        delete[] data;
    }

    // 获取当前元素的数量
    size_t size() const {
        return size_;
    }

    // 获取当前数组的容量
    size_t capacity() const {
        return capacity_;
    }

    // 判断向量是否为空
    bool empty() const {
        return size_ == 0;
    }

    // 在向量末尾添加一个元素
    void push_back(const T& value) {
        if (size_ == capacity_) {
            if (capacity_ == 0) {
                reserve(1);
            } else {
                reserve(2 * capacity_);
            }
        }
        data[size_++] = value;
    }

    // 移除向量末尾的元素
    void pop_back() {
        if (size_ > 0) {
            --size_;
        }
    }

    // 访问指定位置的元素
    T& operator[](size_t index) {
        if (index >= size_) {
            throw std::out_of_range("Index out of range");
        }
        return data[index];
    }

    const T& operator[](size_t index) const {
        if (index >= size_) {
            throw std::out_of_range("Index out of range");
        }
        return data[index];
    }
};

// 测试代码
int main() {
    MyVector<int> vec;
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);

    std::cout << "Size: " << vec.size() << std::endl;
    std::cout << "Capacity: " << vec.capacity() << std::endl;

    for (size_t i = 0; i < vec.size(); ++i) {
        std::cout << vec[i] << " ";
    }
    std::cout << std::endl;

    vec.pop_back();
    std::cout << "Size after pop_back: " << vec.size() << std::endl;

    return 0;
}

2 来手写一个链表⭐⭐⭐⭐

#include <iostream>

// 定义链表节点类
template <typename T>
class Node {
public:
    T data;         // 节点存储的数据
    Node<T>* next;  // 指向下一个节点的指针

    // 构造函数
    Node(T value) : data(value), next(nullptr) {}
};

// 定义链表类
template <typename T>
class LinkedList {
private:
    Node<T>* head;  // 链表头指针

public:
    // 构造函数，初始化头指针为 nullptr
    LinkedList() : head(nullptr) {}

    // 析构函数，释放链表中所有节点的内存
    ~LinkedList() {
        while (head != nullptr) {
            Node<T>* temp = head;
            head = head->next;
            delete temp;
        }
    }

    // 在链表头部插入一个新节点
    void insertAtHead(T value) {
        Node<T>* newNode = new Node<T>(value);
        newNode->next = head;
        head = newNode;
    }

    // 在链表尾部插入一个新节点
    void insertAtTail(T value) {
        Node<T>* newNode = new Node<T>(value);
        if (head == nullptr) {
            head = newNode;
            return;
        }
        Node<T>* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
    }

    // 删除链表头部节点
    void deleteAtHead() {
        if (head == nullptr) {
            return;
        }
        Node<T>* temp = head;
        head = head->next;
        delete temp;
    }

    // 删除链表尾部节点
    void deleteAtTail() {
        if (head == nullptr) {
            return;
        }
        if (head->next == nullptr) {
            delete head;
            head = nullptr;
            return;
        }
        Node<T>* temp = head;
        while (temp->next->next != nullptr) {
            temp = temp->next;
        }
        delete temp->next;
        temp->next = nullptr;
    }

    // 打印链表中的所有元素
    void printList() {
        Node<T>* temp = head;
        while (temp != nullptr) {
            std::cout << temp->data << " ";
            temp = temp->next;
        }
        std::cout << std::endl;
    }
};

int main() {
    LinkedList<int> list;

    // 在链表尾部插入元素
    list.insertAtTail(1);
    list.insertAtTail(2);
    list.insertAtTail(3);

    // 打印链表
    std::cout << "After inserting at tail: ";
    list.printList();

    // 在链表头部插入元素
    list.insertAtHead(0);

    // 打印链表
    std::cout << "After inserting at head: ";
    list.printList();

    // 删除链表头部元素
    list.deleteAtHead();

    // 打印链表
    std::cout << "After deleting at head: ";
    list.printList();

    // 删除链表尾部元素
    list.deleteAtTail();

    // 打印链表
    std::cout << "After deleting at tail: ";
    list.printList();

    return 0;
}
  • Node 类：定义了链表的节点，包含一个数据成员 data 和一个指向下一个节点的指针 next。
  • head：链表的头指针，指向链表的第一个节点。
  • 构造函数：初始化头指针为 nullptr。
  • 析构函数：释放链表中所有节点的内存，防止内存泄漏。
  • insertAtHead：在链表头部插入一个新节点。
  • insertAtTail：在链表尾部插入一个新节点。
  • deleteAtHead：删除链表头部节点。
  • deleteAtTail：删除链表尾部节点。
  • printList：打印链表中的所有元素。
  • main 函数：创建一个链表对象，进行插入和删除操作，并打印链表的内容。

通过上述代码，你可以了解如何使用 C++ 实现一个简单的链表，并对链表进行基本的操作。

3 用数组或链表来实现一个栈⭐⭐⭐⭐⭐

实现的原理都是类似的，用游标变量来控制元素的位置。

栈只需要设置一个游标变量来控制栈顶元素的位置

大家一定要掌握，面试很容易手撕代码。

使用数组实现栈

#include <iostream>
#include <stdexcept>

template <typename T, size_t MAX_SIZE>
class ArrayStack {
private:
    T data[MAX_SIZE];
    int topIndex;

public:
    ArrayStack() : topIndex(-1) {}

    // 判断栈是否为空
    bool empty() const {
        return topIndex == -1;
    }

    // 判断栈是否已满
    bool full() const {
        return topIndex == static_cast<int>(MAX_SIZE - 1);
    }

    // 入栈操作
    void push(const T& value) {
        if (full()) {
            throw std::overflow_error("Stack overflow");
        }
        data[++topIndex] = value;
    }

    // 出栈操作
    void pop() {
        if (empty()) {
            throw std::underflow_error("Stack underflow");
        }
        --topIndex;
    }

    // 获取栈顶元素
    T top() const {
        if (empty()) {
            throw std::underflow_error("Stack is empty");
        }
        return data[topIndex];
    }
};


int main() {
    ArrayStack<int, 5> stack;
    try {
        stack.push(1);
        stack.push(2);
        stack.push(3);
        std::cout << "Top element: " << stack.top() << std::endl;
        stack.pop();
        std::cout << "Top element after pop: " << stack.top() << std::endl;
    } catch (const std::exception& e) {
        std::cerr << "Exception: " << e.what() << std::endl;
    }
    return 0;
}
  • ArrayStack 类使用一个固定大小的数组 data 来存储栈中的元素，topIndex 表示栈顶元素的索引。
  • empty 方法通过检查 topIndex 是否为 -1 来判断栈是否为空。
  • full 方法通过检查 topIndex 是否达到数组的最大索引来判断栈是否已满。
  • push 方法在栈未满时将元素添加到栈顶，并更新 topIndex。
  • pop 方法在栈非空时将 topIndex 减 1，实现出栈操作。
  • top 方法在栈非空时返回栈顶元素。

使用链表实现栈

#include <iostream>
#include <stdexcept>

template <typename T>
class Node {
public:
    T data;
    Node<T>* next;

    Node(const T& value) : data(value), next(nullptr) {}
};

template <typename T>
class LinkedStack {
private:
    Node<T>* topNode;

public:
    LinkedStack() : topNode(nullptr) {}

    ~LinkedStack() {
        while (!empty()) {
            pop();
        }
    }

    // 判断栈是否为空
    bool empty() const {
        return topNode == nullptr;
    }

    // 入栈操作
    void push(const T& value) {
        Node<T>* newNode = new Node<T>(value);
        newNode->next = topNode;
        topNode = newNode;
    }

    // 出栈操作
    void pop() {
        if (empty()) {
            throw std::underflow_error("Stack underflow");
        }
        Node<T>* temp = topNode;
        topNode = topNode->next;
        delete temp;
    }

    // 获取栈顶元素
    T top() const {
        if (empty()) {
            throw std::underflow_error("Stack is empty");
        }
        return topNode->data;
    }
};


int main() {
    LinkedStack<int> stack;
    try {
        stack.push(1);
        stack.push(2);
        stack.push(3);
        std::cout << "Top element: " << stack.top() << std::endl;
        stack.pop();
        std::cout << "Top element after pop: " << stack.top() << std::endl;
    } catch (const std::exception& e) {
        std::cerr << "Exception: " << e.what() << std::endl;
    }
    return 0;
}
  • Node 类表示链表中的节点，包含一个数据成员 data 和一个指向下一个节点的指针 next。
  • LinkedStack 类使用 topNode 指向栈顶节点。
  • empty 方法通过检查 topNode 是否为 nullptr 来判断栈是否为空。
  • push 方法创建一个新节点，将其插入到链表头部，成为新的栈顶节点。
  • pop 方法在栈非空时删除栈顶节点，并释放其内存。
  • top 方法在栈非空时返回栈顶节点的数据。
  • 析构函数在对象销毁时会依次调用 pop 方法，释放所有节点的内存。

4 用数组或链表来实现一个队列⭐⭐⭐⭐

使用数组实现队列

#include <iostream>
#include <stdexcept>

template <typename T, size_t MAX_SIZE>
class ArrayQueue {
private:
    T data[MAX_SIZE];
    int frontIndex;
    int rearIndex;
    int count;

public:
    ArrayQueue() : frontIndex(0), rearIndex(0), count(0) {}

    // 判断队列是否为空
    bool empty() const {
        return count == 0;
    }

    // 判断队列是否已满
    bool full() const {
        return count == MAX_SIZE;
    }

    // 入队操作
    void enqueue(const T& value) {
        if (full()) {
            throw std::overflow_error("Queue is full");
        }
        data[rearIndex] = value;
        rearIndex = (rearIndex + 1) % MAX_SIZE;
        ++count;
    }

    // 出队操作
    void dequeue() {
        if (empty()) {
            throw std::underflow_error("Queue is empty");
        }
        frontIndex = (frontIndex + 1) % MAX_SIZE;
        --count;
    }

    // 获取队首元素
    T front() const {
        if (empty()) {
            throw std::underflow_error("Queue is empty");
        }
        return data[frontIndex];
    }
};


int main() {
    ArrayQueue<int, 5> queue;
    try {
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        std::cout << "Front element: " << queue.front() << std::endl;
        queue.dequeue();
        std::cout << "Front element after dequeue: " << queue.front() << std::endl;
    } catch (const std::exception& e) {
        std::cerr << "Exception: " << e.what() << std::endl;
    }
    return 0;
}
  • ArrayQueue 类使用一个固定大小的数组 data 来存储队列中的元素。
  • frontIndex 指向队首元素的位置，rearIndex 指向队尾元素的下一个位置，count 记录队列中元素的数量。
  • empty 方法通过检查 count 是否为 0 来判断队列是否为空。
  • full 方法通过检查 count 是否达到数组的最大容量来判断队列是否已满。
  • enqueue 方法在队列未满时将元素添加到队尾，并更新 rearIndex 和 count。使用取模运算 % 实现循环数组，以充分利用数组空间。
  • dequeue 方法在队列非空时更新 frontIndex 和 count，实现出队操作。
  • front 方法在队列非空时返回队首元素。

使用链表实现队列

#include <iostream>
#include <stdexcept>

template <typename T>
class Node {
public:
    T data;
    Node<T>* next;

    Node(const T& value) : data(value), next(nullptr) {}
};

template <typename T>
class LinkedQueue {
private:
    Node<T>* frontNode;
    Node<T>* rearNode;

public:
    LinkedQueue() : frontNode(nullptr), rearNode(nullptr) {}

    ~LinkedQueue() {
        while (!empty()) {
            dequeue();
        }
    }

    // 判断队列是否为空
    bool empty() const {
        return frontNode == nullptr;
    }

    // 入队操作
    void enqueue(const T& value) {
        Node<T>* newNode = new Node<T>(value);
        if (empty()) {
            frontNode = rearNode = newNode;
        } else {
            rearNode->next = newNode;
            rearNode = newNode;
        }
    }

    // 出队操作
    void dequeue() {
        if (empty()) {
            throw std::underflow_error("Queue is empty");
        }
        Node<T>* temp = frontNode;
        frontNode = frontNode->next;
        if (frontNode == nullptr) {
            rearNode = nullptr;
        }
        delete temp;
    }

    // 获取队首元素
    T front() const {
        if (empty()) {
            throw std::underflow_error("Queue is empty");
        }
        return frontNode->data;
    }
};


int main() {
    LinkedQueue<int> queue;
    try {
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        std::cout << "Front element: " << queue.front() << std::endl;
        queue.dequeue();
        std::cout << "Front element after dequeue: " << queue.front() << std::endl;
    } catch (const std::exception& e) {
        std::cerr << "Exception: " << e.what() << std::endl;
    }
    return 0;
}
  • Node 类表示链表中的节点，包含一个数据成员 data 和一个指向下一个节点的指针 next。
  • LinkedQueue 类使用 frontNode 指向队首节点，rearNode 指向队尾节点。
  • empty 方法通过检查 frontNode 是否为 nullptr 来判断队列是否为空。
  • enque

剩余60%内容，订阅专栏后可继续查看/也可单篇购买

嵌入式/C++面试八股文 文章被收录于专栏

#承诺提供免费技术答疑# 本专栏主要是介绍嵌入式开发岗位相关知识和学习攻略。“C/C++软件开发岗位”也可以参考。 该专栏覆盖了嵌入式求职过程中99%常见面试题，详细讲解了嵌入式软件开发岗位、学习攻略、项目经验分享、面试心得，从技术面，HR面，主管面，谈薪一站式服务。订阅即赠送简历模板、内推机会，需要的同学点击我头像私信即可！

全部评论

相关推荐

头像
12-01 11:23
西安邮电大学 后端工程师
到底要不要逃课学习技术？
一句话总结：这个问题并不是“要不要”的问题，而是“值不值”的问题。关键看哪一种方式更有利于你的目标，以及你是否能够承受逃课所带来的代价。线上或者线下只是学习形式而已，真正要关注的点是是否在有效学习，而不是一直死扣形式本身。1.你的目标到底是什么？就业OR考研逃课的前提是你有清晰的发展目标。而且这个目标的价值远超课堂所带来的价值内容。若你的目标是就业&nbsp;/&nbsp;项目实战：面对纯理论堆砌、内容重复（比如已通过线上课吃透）或老师照本宣科的&nbsp;“水课”，逃课去深耕岗位所需技术（如后端的&nbsp;Spring&nbsp;框架、前端的&nbsp;React&nbsp;实战），或做能落地的项目，性价比更高。若你的目标是保研&nbsp;/&nbsp;考研：专业课（数据结构、...
代码之外的生存之道
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
11-28 21:27
半导体fab or 🌸为
bg双9但是没有实习现在比较中意的offer要么回家（二线城市）要么去上海1、半导体fab厂：n*14，it岗，做cim系统（在招聘软件上粗略看了下能跳一些制造业的it岗），不倒班2、🌸为：n*(14-16)，通软，做鸿蒙系统但不是鸿蒙开发（不太了解如果跳槽能跳到哪里），加班猛其中fab厂的n是月基本工资，🌸为的n中包含绩效。另外这两家公司都额外有加班费主要纠结的点是fab厂离家近薪资在当地高，但是平台和风评较差；🌸为平台大，但是在上海这薪资有点低了（总包不到35，感觉是13a）另外也想了解一下两种职业未来个人发展方向（比如能跳槽到哪里去，哪个职业更好跳槽，抛开公司哪个职业未来更稳定一些...
点赞 评论 收藏
分享
10-22 03:28
湖南人文科技学院 Java
26届&nbsp;双非&nbsp;秋招&nbsp;0&nbsp;OC&nbsp;目前在亚信科技实习，部门老总说转正简单不难，一直在干bug自测&nbsp;只能边实习边秋招&nbsp;求各位大佬拷打指点简历和建议
激昂墓志铭_终章：亚新经典实习3300，转正7k外包。去那干啥，还要加班
投递亚信科技（中国）有限公司等公司6个岗位
点赞 评论 收藏
分享
头像
11-29 20:26
蚌埠坦克学院 嵌入式软件开发
打工人的破防时刻
有时候，并不是任务有多难、事情有多多，而是那一瞬间突然觉得自己撑不住了。明明已经忙了一整天，邮件却还是一封接一封；明明已经加班到深夜，群里却又跳出一句“这个再顺便改一下”；明明憋着一口气想把活干完，结果电脑突然死机、文档没保存、流程又要重走一遍。最让人破防的不是压力本身，而是那种&nbsp;“我已经很努力了，却还是不够”&nbsp;的无力感。努力没被看见、付出没人记得、委屈不能说、情绪不能崩，只能深吸一口气，继续做一个“成熟的职场人”。等到夜深了，路灯只剩你影子的时候，那句憋了一整天的话会突然冒出来：“好累啊，只是想被理解一下。”但第二天早上闹钟一响，我们还是会爬起来，继续打一场名叫生活的仗。因为哪怕再累，还是想...
哪一瞬间让你觉得工作好累
点赞 评论 收藏
分享
评论
点赞
1
分享

招聘动态

查看更多

成方金融科技有限公司

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 为了去实习，我赌上了___ #
15893次浏览 172人参与
# 摸鱼被leader发现了怎么办 #
70358次浏览 402人参与
# uu们，春招你还来吗？ #
8034次浏览 63人参与
# 2025年终总结 #
8490次浏览 158人参与
# 十二月请对我好一点 #
21200次浏览 291人参与
# 父母对你找工作是助力还是阻力？ #
10920次浏览 176人参与
# 一人推荐一个值得做的项目 #
7432次浏览 103人参与
# 运营每日一题 #
112438次浏览 885人参与
# 哪一瞬间让你觉得“这班不如不上” #
8385次浏览 124人参与
# 降低公积金和取消房补怎么选 #
23062次浏览 78人参与
# 高薪高压 vs 低薪wlb，你怎么选？ #
8183次浏览 92人参与
# 工作前VS工作后，你的心态变化 #
10769次浏览 139人参与
# 工作中出现了XX情况正常吗 #
26774次浏览 197人参与
# 公司福利里最没用的一项是啥 #
5477次浏览 87人参与
# 晒一晒你收到的礼盒 #
87626次浏览 428人参与
# 回顾今年你干过的最“勇”的一件事 #
11087次浏览 148人参与
# 如果可以，你希望哪个公司来捞你 #
154269次浏览 649人参与
# 第一份工作能做外包吗？ #
85092次浏览 569人参与
# 工作中哪个瞬间让你想离职 #
109024次浏览 770人参与
# 一人一道大厂面试题 #
108024次浏览 1239人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务