正文

C语言数据结构习题全解析，轻松掌握编程技能

/0 浏览量
0413

在编程的世界里，掌握数据结构是至关重要的。C语言作为一种高效、强大的编程语言，为我们提供了丰富的工具来实现各种数据结构。本文将带领大家深入解析C语言中的常见数据结构习题，帮助大家轻松掌握编程技能。

基础概念

在深入习题解析之前，让我们先回顾一下C语言中常见的数据结构：

  • 数组：一种基本的数据结构，用于存储固定大小的元素序列。
  • 链表：由节点组成的序列，每个节点包含数据和指向下一个节点的指针。
  • 栈：后进先出（LIFO）的数据结构。
  • 队列：先进先出（FIFO）的数据结构。
  • 树：由节点组成的层次结构，每个节点可以有零个或多个子节点。
  • 图：由节点和边组成，用于表示实体之间的关系。

习题解析

1. 数组操作

题目：编写一个C语言程序，实现两个整型数组的合并，并输出合并后的数组。

解析：首先，定义两个数组并初始化数据。然后，创建一个新的数组用于存放合并后的结果。遍历两个原数组，将元素依次添加到新数组中。

#include <stdio.h>

#define SIZE 5

void mergeArrays(int arr1[], int arr2[], int result[]) {
    for (int i = 0; i < SIZE; ++i) {
        result[i] = arr1[i];
    }
    for (int i = 0; i < SIZE; ++i) {
        result[SIZE + i] = arr2[i];
    }
}

int main() {
    int arr1[SIZE] = {1, 2, 3, 4, 5};
    int arr2[SIZE] = {6, 7, 8, 9, 10};
    int result[SIZE * 2];

    mergeArrays(arr1, arr2, result);

    for (int i = 0; i < SIZE * 2; ++i) {
        printf("%d ", result[i]);
    }
    printf("\n");

    return 0;
}

2. 链表操作

题目：实现一个单链表，包含插入、删除和查找功能。

解析：定义一个链表节点结构体，包含数据和指向下一个节点的指针。然后，编写插入、删除和查找函数。

#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));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 插入节点
void insertNode(Node** head, int data) {
    Node* newNode = createNode(data);
    newNode->next = *head;
    *head = 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);
}

// 查找节点
Node* searchNode(Node* head, int key) {
    Node* temp = head;
    while (temp != NULL) {
        if (temp->data == key) {
            return temp;
        }
        temp = temp->next;
    }
    return NULL;
}

3. 栈操作

题目：实现一个栈，支持入栈、出栈、判断栈空和获取栈顶元素功能。

解析：使用链表实现栈，维护一个指向栈顶节点的指针。根据栈的定义，入栈操作时新元素成为栈顶元素，出栈操作时删除栈顶元素。

#include <stdio.h>
#include <stdlib.h>

typedef struct Stack {
    int data;
    struct Stack* next;
} Stack;

Stack* createStack() {
    Stack* newStack = (Stack*)malloc(sizeof(Stack));
    newStack->next = NULL;
    return newStack;
}

void push(Stack** top, int data) {
    Stack* newNode = (Stack*)malloc(sizeof(Stack));
    newNode->data = data;
    newNode->next = *top;
    *top = newNode;
}

int pop(Stack** top) {
    if (*top == NULL) return -1;
    Stack* temp = *top;
    int data = temp->data;
    *top = temp->next;
    free(temp);
    return data;
}

int isEmpty(Stack* top) {
    return top == NULL;
}

int peek(Stack* top) {
    if (top == NULL) return -1;
    return top->data;
}

4. 队列操作

题目：实现一个循环队列，支持入队、出队、判断队列空和获取队头元素功能。

解析：使用数组实现循环队列，维护一个指向队头和队尾的指针。入队时，如果队尾指针未到达数组末尾，则直接添加到队尾；否则，将队头指针指向数组的起始位置。出队时，如果队头指针未到达队尾，则直接删除队头元素；否则，将队头指针指向数组的起始位置。

#include <stdio.h>
#include <stdlib.h>

#define QUEUE_SIZE 5

typedef struct Queue {
    int items[QUEUE_SIZE];
    int front;
    int rear;
} Queue;

Queue* createQueue() {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->front = 0;
    queue->rear = 0;
    return queue;
}

int isEmpty(Queue* queue) {
    return queue->front == queue->rear;
}

int isFull(Queue* queue) {
    return ((queue->rear + 1) % QUEUE_SIZE) == queue->front;
}

void enqueue(Queue* queue, int item) {
    if (isFull(queue)) {
        printf("Queue is full\n");
        return;
    }
    queue->items[queue->rear] = item;
    queue->rear = (queue->rear + 1) % QUEUE_SIZE;
}

int dequeue(Queue* queue) {
    if (isEmpty(queue)) {
        printf("Queue is empty\n");
        return -1;
    }
    int item = queue->items[queue->front];
    queue->front = (queue->front + 1) % QUEUE_SIZE;
    return item;
}

int peek(Queue* queue) {
    if (isEmpty(queue)) {
        printf("Queue is empty\n");
        return -1;
    }
    return queue->items[queue->front];
}

5. 树操作

题目：实现一个二叉树，包含创建节点、插入节点、查找节点、删除节点和遍历功能。

解析：定义一个二叉树节点结构体，包含数据和指向左右子节点的指针。根据二叉树的操作要求，实现插入、查找、删除和遍历等功能。

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 创建新节点
TreeNode* createNode(int data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 插入节点
TreeNode* insertNode(TreeNode* root, int data) {
    if (root == NULL) {
        return createNode(data);
    }
    if (data < root->data) {
        root->left = insertNode(root->left, data);
    } else if (data > root->data) {
        root->right = insertNode(root->right, data);
    }
    return root;
}

// 查找节点
TreeNode* searchNode(TreeNode* root, int data) {
    if (root == NULL || root->data == data) {
        return root;
    }
    if (data < root->data) {
        return searchNode(root->left, data);
    }
    return searchNode(root->right, data);
}

// 删除节点
TreeNode* deleteNode(TreeNode* root, int data) {
    if (root == NULL) {
        return root;
    }
    if (data < root->data) {
        root->left = deleteNode(root->left, data);
    } else if (data > root->data) {
        root->right = deleteNode(root->right, data);
    } else {
        if (root->left == NULL) {
            TreeNode* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            TreeNode* temp = root->left;
            free(root);
            return temp;
        }
        TreeNode* temp = minValueNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

// 获取最小值节点
TreeNode* minValueNode(TreeNode* node) {
    TreeNode* current = node;
    while (current->left != NULL) {
        current = current->left;
    }
    return current;
}

// 中序遍历
void inorderTraversal(TreeNode* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}

6. 图操作

题目：实现一个邻接表表示的图，包含添加边、删除边、查找节点和遍历功能。

解析：定义一个图节点结构体，包含数据和指向下一个邻接节点的指针。使用邻接表实现图，根据图的定义，实现添加边、删除边、查找节点和遍历等功能。

#include <stdio.h>
#include <stdlib.h>

typedef struct GraphNode {
    int vertex;
    struct GraphNode* next;
} GraphNode;

typedef struct Graph {
    int numVertices;
    GraphNode** adjLists;
    int* visited;
} Graph;

// 创建新节点
GraphNode* createNode(int v) {
    GraphNode* newNode = (GraphNode*)malloc(sizeof(GraphNode));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// 创建图
Graph* createGraph(int vertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = vertices;
    graph->adjLists = (GraphNode**)malloc(vertices * sizeof(GraphNode*));
    graph->visited = (int*)malloc(vertices * sizeof(int));

    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
        graph->visited[i] = 0;
    }
    return graph;
}

// 添加边
void addEdge(Graph* graph, int src, int dest) {
    // 添加从src到dest的边
    GraphNode* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // 添加从dest到src的边（无向图）
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

// 删除边
void removeEdge(Graph* graph, int src, int dest) {
    // 删除从src到dest的边
    GraphNode* temp = graph->adjLists[src], *prev = NULL;
    while (temp) {
        if (temp->vertex == dest) {
            if (prev == NULL) {
                graph->adjLists[src] = temp->next;
                free(temp);
                break;
            } else {
                prev->next = temp->next;
                free(temp);
                break;
            }
        }
        prev = temp;
        temp = temp->next;
    }

    // 删除从dest到src的边（无向图）
    temp = graph->adjLists[dest], prev = NULL;
    while (temp) {
        if (temp->vertex == src) {
            if (prev == NULL) {
                graph->adjLists[dest] = temp->next;
                free(temp);
                break;
            } else {
                prev->next = temp->next;
                free(temp);
                break;
            }
        }
        prev = temp;
        temp = temp->next;
    }
}

// 查找节点
GraphNode* searchNode(Graph* graph, int vertex) {
    for (int i = 0; i < graph->numVertices; i++) {
        GraphNode* temp = graph->adjLists[i];
        while (temp) {
            if (temp->vertex == vertex) {
                return temp;
            }
            temp = temp->next;
        }
    }
    return NULL;
}

// 深度优先搜索
void DFS(Graph* graph, int vertex) {
    GraphNode* adjList = searchNode(graph, vertex);
    graph->visited[vertex] = 1;
    printf("%d ", vertex);

    while (adjList) {
        int connectedVertex = adjList->vertex;
        if (graph->visited[connectedVertex] == 0) {
            DFS(graph, connectedVertex);
        }
        adjList = adjList->next;
    }
}

总结

通过以上解析，相信大家对C语言中的常见数据结构习题有了更深入的了解。在编程实践中，不断练习和总结是提高编程技能的关键。希望本文能帮助大家轻松掌握C语言数据结构，为成为一名优秀的程序员打下坚实基础。

-- 展开阅读全文 --