正文

数据结构C语言版第二版习题解析与答案全解析

/0 浏览量
0413

引言

在计算机科学中，数据结构是至关重要的组成部分。C语言作为一门基础且强大的编程语言，常常被用于实现复杂的数据结构。本书《数据结构C语言版第二版》详细介绍了各种数据结构及其在C语言中的实现。本文将针对本书中的习题进行解析，并提供详细的答案。

1. 链表

1.1 单链表的创建与遍历

题目：编写一个函数，用于创建一个单链表，并实现遍历链表的功能。

解析：首先定义链表节点结构体，然后创建节点，将这些节点连接成链表。遍历链表时，从头节点开始，依次访问每个节点。

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

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

Node* createList(int arr[], int size) {
    Node* head = NULL;
    Node* tail = NULL;
    for (int i = 0; i < size; i++) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = arr[i];
        newNode->next = NULL;
        if (head == NULL) {
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }
    return head;
}

void printList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

1.2 链表反转

题目：编写一个函数，实现单链表的反转。

解析：反转链表时，需要改变节点间的连接顺序。可以使用递归或迭代的方法实现。

Node* reverseList(Node* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    Node* rest = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;
    return rest;
}

2. 栈与队列

2.1 栈的创建与操作

题目：编写一个函数，实现栈的创建和基本操作（入栈、出栈、判断栈空）。

解析：栈可以使用数组或链表实现。以下为使用数组实现的栈。

#include <stdio.h>
#include <stdbool.h>

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

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

bool isFull(Stack* s) {
    return s->top == MAX_SIZE - 1;
}

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

void push(Stack* s, int value) {
    if (isFull(s)) {
        return;
    }
    s->data[++s->top] = value;
}

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

2.2 队列的创建与操作

题目：编写一个函数，实现队列的创建和基本操作（入队、出队、判断队列空）。

解析：队列可以使用数组或链表实现。以下为使用数组实现的队列。

#include <stdio.h>
#include <stdbool.h>

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
} Queue;

void initQueue(Queue* q) {
    q->front = q->rear = 0;
}

bool isFull(Queue* q) {
    return (q->rear + 1) % MAX_SIZE == q->front;
}

bool isEmpty(Queue* q) {
    return q->front == q->rear;
}

void enqueue(Queue* q, int value) {
    if (isFull(q)) {
        return;
    }
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % MAX_SIZE;
}

int dequeue(Queue* q) {
    if (isEmpty(q)) {
        return -1;
    }
    int value = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    return value;
}

3. 树与图

3.1 二叉树的创建与遍历

题目：编写一个函数，实现二叉树的创建和遍历（前序、中序、后序）。

解析：二叉树可以使用数组或链表实现。以下为使用链表实现的二叉树。

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

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

TreeNode* createNode(int value) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

void preOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->data);
    preOrder(root->left);
    preOrder(root->right);
}

void inOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inOrder(root->left);
    printf("%d ", root->data);
    inOrder(root->right);
}

void postOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    printf("%d ", root->data);
}

3.2 图的创建与遍历

题目：编写一个函数，实现图的创建和遍历（深度优先搜索、广度优先搜索）。

解析：图可以使用邻接矩阵或邻接表实现。以下为使用邻接表实现的图。

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

#define MAX_VERTICES 100

typedef struct Edge {
    int to;
    struct Edge* next;
} Edge;

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

Graph* createGraph(int numVertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = numVertices;
    graph->adjLists = (Edge**)malloc(numVertices * sizeof(Edge*));
    graph->visited = (int*)malloc(numVertices * sizeof(int));
    for (int i = 0; i < numVertices; i++) {
        graph->adjLists[i] = NULL;
        graph->visited[i] = 0;
    }
    return graph;
}

void addEdge(Graph* graph, int src, int dest) {
    Edge* newEdge = (Edge*)malloc(sizeof(Edge));
    newEdge->to = dest;
    newEdge->next = graph->adjLists[src];
    graph->adjLists[src] = newEdge;
}

void DFS(Graph* graph, int vertex) {
    Edge* adjList = graph->adjLists[vertex];
    Edge* temp = adjList;

    graph->visited[vertex] = 1;
    printf("%d ", vertex);

    while (temp != NULL) {
        int connectedVertex = temp->to;
        if (graph->visited[connectedVertex] == 0) {
            DFS(graph, connectedVertex);
        }
        temp = temp->next;
    }
}

void BFS(Graph* graph, int startVertex) {
    int* visited = (int*)malloc(graph->numVertices * sizeof(int));
    for (int i = 0; i < graph->numVertices; i++) {
        visited[i] = 0;
    }

    int* queue = (int*)malloc(graph->numVertices * sizeof(int));
    int front = 0;
    int rear = -1;

    visited[startVertex] = 1;
    queue[++rear] = startVertex;

    while (front <= rear) {
        int currentVertex = queue[front++];
        printf("%d ", currentVertex);

        for (int i = 0; i < graph->numVertices; i++) {
            Edge* adjList = graph->adjLists[currentVertex];
            while (adjList) {
                int adjVertex = adjList->to;
                if (visited[adjVertex] == 0) {
                    visited[adjVertex] = 1;
                    queue[++rear] = adjVertex;
                }
                adjList = adjList->next;
            }
        }
    }

    free(visited);
    free(queue);
}

总结

本文针对《数据结构C语言版第二版》中的习题进行了详细解析，并提供了相应的代码实现。通过学习这些习题，读者可以更好地理解数据结构及其在C语言中的实现。希望本文对大家的学习有所帮助。

-- 展开阅读全文 --