C++ 语言 数据结构面试题详解示例

// 定义链表节点
struct ListNode {
int val;
ListNode next;
ListNode(int x) : val(x), next(nullptr) {}
};

// 插入节点
void insertNode(ListNode &head, int val) {
ListNode newNode = new ListNode(val);
if (head == nullptr) {
head = newNode;
} else {
ListNode current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = newNode;
}
}

// 删除节点
void deleteNode(ListNode &head, int val) {
if (head == nullptr) return;
if (head->val == val) {
ListNode temp = head;
head = head->next;
delete temp;
return;
}
ListNode current = head;
while (current->next != nullptr && current->next->val != val) {
current = current->next;
}
if (current->next != nullptr) {
ListNode temp = current->next;
current->next = temp->next;
delete temp;
}
}

// 查找节点
ListNode findNode(ListNode head, int val) {
ListNode current = head;
while (current != nullptr) {
if (current->val == val) {
return current;
}
current = current->next;
}
return nullptr;
}

// 遍历链表
void traverseList(ListNode head) {
ListNode current = head;
while (current != nullptr) {
std::cout <val <next;
}
std::cout << std::endl;
}

// 定义栈
class Stack {
private:
std::vector data;

public:
// 入栈
void push(int val) {
data.push_back(val);
}

// 出栈
int pop() {
if (data.empty()) {
throw std::runtime_error("Stack is empty");
}
return data.back();
}

// 查看栈顶元素
int top() {
if (data.empty()) {
throw std::runtime_error("Stack is empty");
}
return data.back();
}

// 判断栈是否为空
bool isEmpty() {
return data.empty();
}
};

// 定义队列
class Queue {
private:
std::vector data;

public:
// 入队
void enqueue(int val) {
data.push_back(val);
}

// 出队
int dequeue() {
if (data.empty()) {
throw std::runtime_error("Queue is empty");
}
return data.front();
}

// 查看队首元素
int front() {
if (data.empty()) {
throw std::runtime_error("Queue is empty");
}
return data.front();
}

// 判断队列是否为空
bool isEmpty() {
return data.empty();
}
};

// 定义二叉树节点
struct TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 插入节点
TreeNode insertNode(TreeNode root, int val) {
if (root == nullptr) {
return new TreeNode(val);
}
if (val val) {
root->left = insertNode(root->left, val);
} else if (val > root->val) {
root->right = insertNode(root->right, val);
}
return root;
}

// 查找节点
TreeNode findNode(TreeNode root, int val) {
if (root == nullptr) {
return nullptr;
}
if (root->val == val) {
return root;
}
TreeNode left = findNode(root->left, val);
if (left != nullptr) {
return left;
}
return findNode(root->right, val);
}

// 前序遍历
void preorderTraversal(TreeNode root) {
if (root != nullptr) {
std::cout <val <left);
preorderTraversal(root->right);
}
}

// 中序遍历
void inorderTraversal(TreeNode root) {
if (root != nullptr) {
inorderTraversal(root->left);
std::cout <val <right);
}
}

// 后序遍历
void postorderTraversal(TreeNode root) {
if (root != nullptr) {
postorderTraversal(root->left);
postorderTraversal(root->right);
std::cout <val << " ";
}
}

// 删除节点
TreeNode deleteNode(TreeNode root, int val) {
if (root == nullptr) {
return root;
}
if (val val) {
root->left = deleteNode(root->left, val);
} else if (val > root->val) {
root->right = deleteNode(root->right, val);
} else {
if (root->left == nullptr) {
TreeNode temp = root->right;
delete root;
return temp;
} else if (root->right == nullptr) {
TreeNode temp = root->left;
delete root;
return temp;
}
TreeNode minNode = findMin(root->right);
root->val = minNode->val;
root->right = deleteNode(root->right, minNode->val);
}
return root;
}

// 查找最小值节点
TreeNode findMin(TreeNode root) {
while (root->left != nullptr) {
root = root->left;
}
return root;
}

// 主函数
int main() {
TreeNode root = nullptr;
root = insertNode(root, 5);
root = insertNode(root, 3);
root = insertNode(root, 7);
root = insertNode(root, 2);
root = insertNode(root, 4);
root = insertNode(root, 6);
root = insertNode(root, 8);

std::cout << "Preorder traversal: ";
preorderTraversal(root); // 输出: 5 3 2 4 1 7 6 8
std::cout << std::endl;

std::cout << "Inorder traversal: ";
inorderTraversal(root); // 输出: 2 3 4 5 6 7 8
std::cout << std::endl;

std::cout << "Postorder traversal: ";
postorderTraversal(root); // 输出: 2 4 3 6 8 7 5
std::cout << std::endl;

root = deleteNode(root, 3);
std::cout << "Inorder traversal after deleting 3: ";
inorderTraversal(root); // 输出: 2 4 5 6 7 8
std::cout << std::endl;

// 定义图
class Graph {
private:
std::vector<#std::list> adjList;

public:
// 添加边
void addEdge(int src, int dest) {
adjList[src].push_back(dest);
adjList[dest].push_back(src); // 无向图
}

// 删除边
void removeEdge(int src, int dest) {
auto it = adjList[src].begin();
while (it != adjList[src].end()) {
if (it == dest) {
adjList[src].erase(it);
break;
}
++it;
}
it = adjList[dest].begin();
while (it != adjList[dest].end()) {
if (it == src) {
adjList[dest].erase(it);
break;
}
++it;
}
}

// 查找路径（深度优先搜索）
void dfs(int src, int dest) {
std::vector visited(adjList.size(), false);
std::vector parent(adjList.size(), -1);
dfsUtil(src, dest, visited, parent);
}

// 查找路径（广度优先搜索）
void bfs(int src, int dest) {
std::vector visited(adjList.size(), false);
std::queue queue;
queue.push(src);
visited[src] = true;
while (!queue.empty()) {
int current = queue.front();
queue.pop();
if (current == dest) {
break;
}
for (int neighbor : adjList[current]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.push(neighbor);
}
}
}
}

private:
// 深度优先搜索辅助函数
void dfsUtil(int src, int dest, std::vector &visited, std::vector &parent) {
if (src == dest) {
std::cout << src << " ";
return;
}
visited[src] = true;
for (int neighbor : adjList[src]) {
if (!visited[neighbor]) {
parent[neighbor] = src;
dfsUtil(neighbor, dest, visited, parent);
}
}
if (parent[src] != -1) {
std::cout << parent[src] << " ";
}
}
};

// 主函数
int main() {
Graph graph;
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 5);
graph.addEdge(3, 6);
graph.addEdge(4, 6);

std::cout << "DFS from 0 to 6: ";
graph.dfs(0, 6); // 输出: 0 1 3 6
std::cout << std::endl;

std::cout << "BFS from 0 to 6: ";
graph.bfs(0, 6); // 输出: 0 1 2 3 4 5 6
std::cout << std::endl;