2024年3月4日发(作者：)

数据结构(C语言)【经典题库】含答案

数据结构（C语言）【经典题库】含答案

数据结构是计算机科学中的重要基础，对于程序员和软件工程师来说，熟练掌握数据结构是必不可少的。在C语言中，有许多经典的数据结构题目，通过解答这些题目，可以深入理解数据结构的原理和应用。本文将介绍一些经典的数据结构题目，同时附上详细的答案。

一、数组题目

1. 给定一个整型数组arr和一个整数target，找出数组中两个数的和为target的所有组合。

```C

#include

void findPairs(int arr[], int n, int target) {

int i, j;

for (i = 0; i < n - 1; i++) {

for (j = i + 1; j < n; j++) {

if (arr[i] + arr[j] == target) {

printf("%d, %dn", arr[i], arr[j]);

}

}

}

}

int main() {

int arr[] = {2, 4, 6, 8, 10};

int target = 14;

int n = sizeof(arr) / sizeof(arr[0]);

findPairs(arr, n, target);

return 0;

}

```

答案解析：使用两层循环遍历数组中的每对元素，判断它们的和是否等于目标值target，如果是则输出。时间复杂度为O(n^2)。

2. 给定一个整型数组arr和一个整数k，求出数组中连续子数组的最大和。

```C

#include

int maxSubArraySum(int arr[], int n) {

int maxSum = arr[0];

int currentSum = arr[0];

for (int i = 1; i < n; i++) {

currentSum = (currentSum + arr[i] > arr[i]) ? currentSum + arr[i] :

arr[i];

if (currentSum > maxSum) {

maxSum = currentSum;

}

}

return maxSum;

}

int main() {

int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

int n = sizeof(arr) / sizeof(arr[0]);

int maxSum = maxSubArraySum(arr, n);

printf("最大和为：%dn", maxSum);

return 0;

}

```

答案解析：使用动态规划的思想，定义两个变量`maxSum`和`currentSum`，分别表示当前的最大和和累加和。遍历数组，如果当前

元素加上前面的最大和大于当前元素，说明最大和可以继续累加，否则更新最大和为当前元素。时间复杂度为O(n)。

二、链表题目

1. 给定一个链表的头节点head和一个目标值value，删除链表中所有值为value的节点。

```C

#include

typedef struct ListNode {

int val;

struct ListNode *next;

} ListNode;

ListNode* removeElements(ListNode* head, int value) {

ListNode *dummy = (ListNode *)malloc(sizeof(ListNode));

dummy->next = head;

ListNode *prev = dummy;

ListNode *curr = head;

while (curr) {

if (curr->val == value) {

prev->next = curr->next;

free(curr);

curr = prev->next;

} else {

prev = curr;

curr = curr->next;

}

}

head = dummy->next;

free(dummy);

return head;

}

void printList(ListNode *head) {

ListNode *curr = head;

while (curr) {

printf("%d ", curr->val);

curr = curr->next;

}

printf("n");

}

int main() {

ListNode *head = (ListNode *)malloc(sizeof(ListNode));

head->val = 1;

ListNode *node1 = (ListNode *)malloc(sizeof(ListNode));

node1->val = 2;

head->next = node1;

ListNode *node2 = (ListNode *)malloc(sizeof(ListNode));

node2->val = 3;

node1->next = node2;

ListNode *node3 = (ListNode *)malloc(sizeof(ListNode));

node3->val = 2;

node2->next = node3;

node3->next = NULL;

printf("原链表：");

printList(head);

int value = 2;

head = removeElements(head, value);

printf("删除值为%d的节点后的链表：", value);

printList(head);

return 0;

}

```

答案解析：使用双指针法遍历链表，当当前节点的值等于目标值时，将前一个节点的next指针指向当前节点的next指针，并释放当前节点的内存空间。时间复杂度为O(n)。

三、栈和队列题目

1. 实现一个栈，要求支持push、pop和getMin操作，其中getMin操作返回栈中最小的元素。

```C

#include

#include

typedef struct {

int val;

struct Node *next;

} Node;

typedef struct {

Node *top;

int min;

} MinStack;

MinStack* createStack() {

MinStack *stack = (MinStack *)malloc(sizeof(MinStack));

stack->top = NULL;

stack->min = INT_MAX;

return stack;

}

void push(MinStack *stack, int val) {

Node *newNode = (Node *)malloc(sizeof(Node));

newNode->val = val;

if (newNode->val < stack->min) {

stack->min = newNode->val;

}

newNode->next = stack->top;

stack->top = newNode;

}

void pop(MinStack *stack) {

if (stack->top == NULL) {

printf("栈为空！");

return;

}

Node *temp = stack->top;

stack->top = stack->top->next;

if (temp->val == stack->min) {

stack->min = INT_MAX;

Node *curr = stack->top;

while (curr) {

if (curr->val < stack->min) {

stack->min = curr->val;

}

curr = curr->next;

}

}

free(temp);

}

int getMin(MinStack *stack) {

return stack->min;

}

int main() {

MinStack *stack = createStack();

push(stack, 3);

push(stack, 5);

push(stack, 2);

push(stack, 1);

printf("最小元素：%dn", getMin(stack));

pop(stack);

pop(stack);

printf("最小元素：%dn", getMin(stack));

return 0;

}

```

答案解析：使用链表实现栈，并在栈结构体中增加一个min字段，用于保存栈中的最小元素。当push操作时，比较新的元素和当前最小值，如果新元素小于当前最小值，则将min更新为新元素；当pop操作时，并且弹出的元素等于当前最小值时，需要重新计算最小值。时间复杂度为O(1)。

四、树和图题目

1. 给定一个二叉树，判断它是否是平衡二叉树。

```C

#include

#include

#include

typedef struct TreeNode {

int val;

struct TreeNode *left;

struct TreeNode *right;

} TreeNode;

int max(int a, int b) {

return (a > b) ? a : b;

}

int height(TreeNode *root) {

if (root == NULL) {

return 0;

}

return max(height(root->left), height(root->right)) + 1;

}

bool isBalanced(TreeNode* root) {

if (root == NULL) {

return true;

}

int leftHeight = height(root->left);

int rightHeight = height(root->right);

if (abs(leftHeight - rightHeight) > 1) {

return false;

}

return isBalanced(root->left) && isBalanced(root->right);

}

TreeNode* createNode(int val) {

TreeNode* node = (TreeNode *)malloc(sizeof(TreeNode));

node->val = val;

node->left = NULL;

node->right = NULL;

return node;

}

int main() {

TreeNode* root = createNode(1);

root->left = createNode(2);

root->right = createNode(2);

root->left->left = createNode(3);

root->left->right = createNode(3);

root->left->left->left = createNode(4);

root->left->left->right = createNode(4);

bool isBalancedTree = isBalanced(root);

if (isBalancedTree) {

printf("该二叉树是平衡二叉树n");

} else {

printf("该二叉树不是平衡二叉树n");

}

return 0;

}

```

答案解析：使用递归的方法判断二叉树是否是平衡二叉树。先计算左子树的高度和右子树的高度，然后比较两者的差的绝对值是否大于1，

若大于1，则返回false；否则，递归判断左子树和右子树是否都是平衡二叉树。时间复杂度为O(nlogn)。

通过以上的经典数据结构题目的解析，可以加深对数据结构的理解和应用。掌握了这些经典题目的解题思路和方法，可以更好地应对日常开发中的问题，在算法和数据结构方面提升自己的能力。