正文

掌握数据结构，C语言习题实战攻略全解析

/0 浏览量
0412

引言

在计算机科学领域，数据结构是理解和实现算法的基础。C语言作为一种经典的编程语言，因其高效和灵活性而被广泛应用于学习数据结构和算法。本文将深入解析C语言在数据结构学习中的应用，通过一系列实战习题，帮助你更好地掌握数据结构。

一、基础数据结构

1.1 数组

主题句：数组是C语言中最基本的数据结构，用于存储具有相同数据类型的元素序列。

实战习题：

#include <stdio.h>

int main() {
    int arr[5] = {1, 2, 3, 4, 5};
    printf("The third element is: %d\n", arr[2]);
    return 0;
}

1.2 链表

主题句：链表是一种动态数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

实战习题：

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

struct Node {
    int data;
    struct Node* next;
};

void insertAtBeginning(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

int main() {
    struct Node* head = NULL;
    insertAtBeginning(&head, 1);
    insertAtBeginning(&head, 2);
    insertAtBeginning(&head, 3);
    printf("The linked list is: ");
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    return 0;
}

1.3 栈

主题句：栈是一种后进先出（LIFO）的数据结构，常用于处理函数调用、递归等场景。

实战习题：

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

#define MAX_SIZE 100

struct Stack {
    int top;
    int items[MAX_SIZE];
};

void initializeStack(struct Stack* s) {
    s->top = -1;
}

int isEmpty(struct Stack* s) {
    return s->top == -1;
}

void push(struct Stack* s, int item) {
    if (s->top < MAX_SIZE - 1) {
        s->items[++s->top] = item;
    }
}

int pop(struct Stack* s) {
    if (!isEmpty(s)) {
        return s->items[s->top--];
    }
    return -1;
}

int main() {
    struct Stack s;
    initializeStack(&s);
    push(&s, 10);
    push(&s, 20);
    push(&s, 30);
    printf("Popped element is: %d\n", pop(&s));
    return 0;
}

1.4 队列

主题句：队列是一种先进先出（FIFO）的数据结构，常用于处理等待任务、打印队列等场景。

实战习题：

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

#define MAX_SIZE 100

struct Queue {
    int items[MAX_SIZE];
    int front;
    int rear;
};

void initializeQueue(struct Queue* q) {
    q->front = q->rear = -1;
}

int isEmpty(struct Queue* q) {
    return q->front == -1;
}

void enqueue(struct Queue* q, int item) {
    if ((q->rear + 1) % MAX_SIZE == q->front) {
        printf("Queue is full\n");
    } else {
        if (isEmpty(q)) {
            q->front = q->rear = 0;
        } else {
            q->rear = (q->rear + 1) % MAX_SIZE;
        }
        q->items[q->rear] = item;
    }
}

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

int main() {
    struct Queue q;
    initializeQueue(&q);
    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    printf("Dequeued element is: %d\n", dequeue(&q));
    return 0;
}

二、高级数据结构

2.1 树

主题句：树是一种非线性数据结构，由节点组成，每个节点有零个或多个子节点。

实战习题：

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

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

void insert(struct Node** root_ref, int data) {
    struct Node* node = newNode(data);
    if (*root_ref == NULL) {
        *root_ref = node;
    } else {
        struct Node* current = *root_ref;
        struct Node* parent = NULL;
        while (current != NULL) {
            parent = current;
            if (data < current->data) {
                current = current->left;
            } else {
                current = current->right;
            }
        }
        if (data < parent->data) {
            parent->left = node;
        } else {
            parent->right = node;
        }
    }
}

void inorderTraversal(struct Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}

int main() {
    struct Node* root = NULL;
    insert(&root, 50);
    insert(&root, 30);
    insert(&root, 20);
    insert(&root, 40);
    insert(&root, 70);
    insert(&root, 60);
    insert(&root, 80);
    printf("Inorder traversal of the given tree is: ");
    inorderTraversal(root);
    return 0;
}

2.2 图

主题句：图是一种复杂的数据结构，由节点（顶点）和边组成，用于表示实体之间的关系。

实战习题：

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

#define MAX_VERTICES 100

struct Graph {
    int num_vertices;
    int** adj_matrix;
};

struct Graph* createGraph(int num_vertices) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->num_vertices = num_vertices;
    graph->adj_matrix = (int**)malloc(num_vertices * sizeof(int*));
    for (int i = 0; i < num_vertices; i++) {
        graph->adj_matrix[i] = (int*)malloc(num_vertices * sizeof(int));
        for (int j = 0; j < num_vertices; j++) {
            graph->adj_matrix[i][j] = 0;
        }
    }
    return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {
    graph->adj_matrix[src][dest] = 1;
    graph->adj_matrix[dest][src] = 1;
}

void printGraph(struct Graph* graph) {
    for (int i = 0; i < graph->num_vertices; i++) {
        for (int j = 0; j < graph->num_vertices; j++) {
            printf("%d ", graph->adj_matrix[i][j]);
        }
        printf("\n");
    }
}

int main() {
    struct Graph* graph = createGraph(4);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);
    printf("The adjacency matrix of the graph is:\n");
    printGraph(graph);
    return 0;
}

三、总结

通过以上实战习题，你将能够更好地理解和应用C语言中的数据结构。记住，实践是学习的关键，不断尝试和解决问题将帮助你巩固所学知识。祝你学习顺利！

-- 展开阅读全文 --