C++ 语言数据结构面试题详解
在C++面试中，数据结构是一个非常重要的考察点。掌握常见的数据结构及其应用，对于面试官来说是一个基本要求。本文将围绕C++语言中的常见数据结构，结合面试题进行详细解析，帮助读者在面试中更好地展示自己的技术实力。
一、线性表
1.1 线性表的定义
线性表是数据结构中最基本的结构之一，它是由有限个元素组成的序列，每个元素都有一个前驱和后继。
1.2 线性表的面试题
题目1：实现一个单链表
cpp
include
// 定义链表节点
struct ListNode {
int val;
ListNode next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 创建单链表
ListNode createList(int arr[], int n) {
if (n == 0) return nullptr;
ListNode head = new ListNode(arr[0]);
ListNode current = head;
for (int i = 1; i next = new ListNode(arr[i]);
current = current->next;
}
return head;
}
// 打印单链表
void printList(ListNode head) {
ListNode current = head;
while (current != nullptr) {
std::cout <val <next;
}
std::cout << std::endl;
}
// 主函数
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
ListNode list = createList(arr, n);
printList(list);
return 0;
}
题目2：实现一个循环链表
cpp
include
// 定义循环链表节点
struct CircularListNode {
int val;
CircularListNode next;
CircularListNode(int x) : val(x), next(nullptr) {}
};
// 创建循环链表
CircularListNode createCircularList(int arr[], int n) {
if (n == 0) return nullptr;
CircularListNode head = new CircularListNode(arr[0]);
CircularListNode current = head;
for (int i = 1; i next = new CircularListNode(arr[i]);
current = current->next;
}
current->next = head; // 使链表成环
return head;
}
// 打印循环链表
void printCircularList(CircularListNode head) {
if (head == nullptr) return;
CircularListNode current = head;
do {
std::cout <val <next;
} while (current != head);
std::cout << std::endl;
}
// 主函数
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
CircularListNode list = createCircularList(arr, n);
printCircularList(list);
return 0;
}
二、栈和队列
2.1 栈的定义
栈是一种后进先出（LIFO）的数据结构，它只允许在表的一端进行插入和删除操作。
2.2 队列的定义
队列是一种先进先出（FIFO）的数据结构，它只允许在表的一端进行插入操作，在另一端进行删除操作。
2.3 栈和队列的面试题
题目3：实现一个栈
cpp
include
include
// 定义栈
class Stack {
private:
std::vector data;
public:
void push(int value) {
data.push_back(value);
}
int pop() {
if (data.empty()) return -1;
return data.back();
}
int top() {
if (data.empty()) return -1;
return data.back();
}
bool isEmpty() {
return data.empty();
}
};
// 主函数
int main() {
Stack stack;
stack.push(1);
stack.push(2);
stack.push(3);
std::cout << "Top element: " << stack.top() << std::endl;
std::cout << "Popped element: " << stack.pop() << std::endl;
std::cout << "Top element: " << stack.top() << std::endl;
return 0;
}
题目4：实现一个队列
cpp
include
include
// 主函数
int main() {
std::queue queue;
queue.push(1);
queue.push(2);
queue.push(3);
std::cout << "Front element: " << queue.front() << std::endl;
std::cout << "Rear element: " << queue.back() << std::endl;
std::cout << "Dequeued element: " << queue.pop() << std::endl;
std::cout << "Front element: " << queue.front() << std::endl;
return 0;
}
三、树和二叉树
3.1 树的定义
树是一种非线性数据结构，由节点组成，每个节点有零个或多个子节点。
3.2 二叉树的定义
二叉树是一种特殊的树，每个节点最多有两个子节点。
3.3 树和二叉树的面试题
题目5：实现一个二叉树
cpp
include
// 定义二叉树节点
struct TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 创建二叉树
TreeNode createBinaryTree(int arr[], int n) {
if (n == 0) return nullptr;
TreeNode root = new TreeNode(arr[0]);
TreeNode current = root;
int i = 1;
while (i < n) {
if (i 2 left = new TreeNode(arr[i 2]);
current = current->left;
}
if (i 2 + 1 right = new TreeNode(arr[i 2 + 1]);
current = current->right;
}
i++;
}
return root;
}
// 打印二叉树
void printBinaryTree(TreeNode root) {
if (root == nullptr) return;
std::cout <val <left);
printBinaryTree(root->right);
}
// 主函数
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
TreeNode tree = createBinaryTree(arr, n);
printBinaryTree(tree);
return 0;
}
四、图
4.1 图的定义
图是一种复杂的数据结构，由节点和边组成，节点之间可以是任意连接。
4.2 图的面试题
题目6：实现一个图
cpp
include
include
// 定义图节点
struct GraphNode {
int val;
std::vector neighbors;
GraphNode(int x) : val(x) {}
};
// 创建图
void createGraph(GraphNode nodes, int n) {
for (int i = 0; i neighbors.push_back(nodes[1]);
nodes[1]->neighbors.push_back(nodes[0]);
}
// 打印图
void printGraph(GraphNode nodes, int n) {
for (int i = 0; i < n; ++i) {
std::cout << "Node " << i <neighbors) {
std::cout <val << " ";
}
std::cout << std::endl;
}
}
// 主函数
int main() {
int n = 2;
GraphNode nodes = new GraphNode[n];
createGraph(nodes, n);
printGraph(nodes, n);
return 0;
}
总结
本文详细解析了C++语言中常见的数据结构及其面试题。通过学习这些内容，读者可以在面试中更好地展示自己的技术实力。在实际开发中，熟练掌握这些数据结构对于提高代码质量和效率具有重要意义。
Comments NOTHING