正文

数据结构第三章关键习题解析与答案全攻略

/0 浏览量
0403

1. 线性表

1.1 线性表的顺序存储结构

习题：给定一个线性表的顺序存储结构，实现一个函数，用于在表的末尾插入一个新元素。

解析：在顺序存储结构中，插入操作通常需要移动插入点之后的元素，以腾出空间。

代码示例：

void insertElement(int *array, int size, int element) {
    if (size >= MAX_SIZE) {
        return; // 表已满
    }
    for (int i = size - 1; i >= 0; i--) {
        array[i + 1] = array[i];
    }
    array[0] = element;
}

1.2 线性表的链式存储结构

习题：给定一个线性表的链式存储结构，实现一个函数，用于删除指定位置的元素。

解析：在链式存储结构中，删除操作需要找到要删除的元素的前一个节点，并更新它的指针。

代码示例：

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

void deleteElement(Node **head, int position) {
    if (*head == NULL) {
        return; // 表为空
    }
    Node *current = *head;
    Node *previous = NULL;
    int index = 0;
    while (current != NULL && index < position) {
        previous = current;
        current = current->next;
        index++;
    }
    if (current == NULL) {
        return; // 位置超出范围
    }
    if (previous == NULL) {
        *head = current->next; // 删除的是头节点
    } else {
        previous->next = current->next;
    }
    free(current);
}

2. 栈和队列

2.1 栈

习题：实现一个栈的逆序操作，即将栈中的元素顺序颠倒。

解析：可以使用另一个栈来辅助完成逆序操作。

代码示例：

void reverseStack(int *stack, int size) {
    int tempStack[MAX_SIZE];
    int top = -1;
    for (int i = 0; i < size; i++) {
        push(tempStack, &top, stack[i]);
    }
    for (int i = 0; i < size; i++) {
        pop(tempStack, &top, &stack[i]);
    }
}

void push(int *stack, int *top, int element) {
    stack[++(*top)] = element;
}

void pop(int *stack, int *top, int *element) {
    *element = stack[(*top)--];
}

2.2 队列

习题：实现一个循环队列，并实现入队和出队操作。

解析：循环队列使用一个数组，通过两个指针分别指向队列的头部和尾部。

代码示例：

#define MAX_SIZE 5
int queue[MAX_SIZE];
int front = 0;
int rear = 0;

void enqueue(int element) {
    if ((rear + 1) % MAX_SIZE == front) {
        return; // 队列已满
    }
    queue[rear] = element;
    rear = (rear + 1) % MAX_SIZE;
}

int dequeue() {
    if (front == rear) {
        return -1; // 队列为空
    }
    int element = queue[front];
    front = (front + 1) % MAX_SIZE;
    return element;
}

3. 树和二叉树

3.1 二叉树的遍历

习题：实现二叉树的先序、中序和后序遍历。

解析：遍历二叉树的方法有三种：递归和非递归。

代码示例：

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

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

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

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

3.2 二叉搜索树

习题：实现一个二叉搜索树，并实现插入、删除和查找操作。

解析：二叉搜索树是一种特殊的二叉树，其左子树上所有节点的值均小于它的根节点的值，右子树上所有节点的值均大于它的根节点的值。

代码示例：

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

TreeNode* insert(TreeNode *root, int value) {
    if (root == NULL) {
        root = (TreeNode*)malloc(sizeof(TreeNode));
        root->data = value;
        root->left = NULL;
        root->right = NULL;
        return root;
    }
    if (value < root->data) {
        root->left = insert(root->left, value);
    } else if (value > root->data) {
        root->right = insert(root->right, value);
    }
    return root;
}

TreeNode* minValueNode(TreeNode *node) {
    TreeNode *current = node;
    while (current->left != NULL) {
        current = current->left;
    }
    return current;
}

TreeNode* delete(TreeNode *root, int value) {
    if (root == NULL) {
        return root;
    }
    if (value < root->data) {
        root->left = delete(root->left, value);
    } else if (value > root->data) {
        root->right = delete(root->right, value);
    } 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 = delete(root->right, temp->data);
    }
    return root;
}

TreeNode* search(TreeNode *root, int value) {
    if (root == NULL || root->data == value) {
        return root;
    }
    if (value < root->data) {
        return search(root->left, value);
    }
    return search(root->right, value);
}

4. 图

4.1 图的邻接矩阵表示

习题：实现一个图的邻接矩阵表示，并实现图的深度优先遍历和广度优先遍历。

解析：图的邻接矩阵表示使用一个二维数组，其中元素matrix[i][j]表示顶点i和顶点j之间是否存在边。

代码示例：

#define MAX_SIZE 5
int matrix[MAX_SIZE][MAX_SIZE];

void createGraph(int numVertices) {
    for (int i = 0; i < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
            matrix[i][j] = 0;
        }
    }
}

void addEdge(int start, int end) {
    matrix[start][end] = 1;
    matrix[end][start] = 1; // 无向图
}

void dfs(int vertex) {
    visited[vertex] = true;
    printf("%d ", vertex);
    for (int i = 0; i < MAX_SIZE; i++) {
        if (matrix[vertex][i] == 1 && !visited[i]) {
            dfs(i);
        }
    }
}

void bfs(int start) {
    int queue[MAX_SIZE];
    int front = 0;
    int rear = 0;
    visited[start] = true;
    queue[rear++] = start;
    while (front < rear) {
        int vertex = queue[front++];
        printf("%d ", vertex);
        for (int i = 0; i < MAX_SIZE; i++) {
            if (matrix[vertex][i] == 1 && !visited[i]) {
                visited[i] = true;
                queue[rear++] = i;
            }
        }
    }
}

4.2 图的邻接表表示

习题：实现一个图的邻接表表示，并实现图的深度优先遍历和广度优先遍历。

解析：图的邻接表表示使用一个数组，其中每个元素是一个链表，链表中的节点表示与该顶点相邻的顶点。

代码示例：

#define MAX_SIZE 5
struct Node {
    int vertex;
    struct Node *next;
};

struct Graph {
    int numVertices;
    struct Node* *adjLists;
    int visited[MAX_SIZE];
};

struct Node* createNode(int v) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

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

void addEdge(struct Graph* graph, int src, int dest) {
    struct Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

void dfs(struct Graph* graph, int vertex) {
    struct Node* adjList = graph->adjLists[vertex];
    struct Node* temp = adjList;
    graph->visited[vertex] = true;
    printf("%d ", vertex);
    while (temp != NULL) {
        int connectedVertex = temp->vertex;
        if (!graph->visited[connectedVertex]) {
            dfs(graph, connectedVertex);
        }
        temp = temp->next;
    }
}

void bfs(struct Graph* graph, int start) {
    int queue[MAX_SIZE];
    int front = 0;
    int rear = 0;
    graph->visited[start] = true;
    queue[rear++] = start;
    while (front < rear) {
        int vertex = queue[front++];
        printf("%d ", vertex);
        struct Node* adjList = graph->adjLists[vertex];
        struct Node* temp = adjList;
        while (temp != NULL) {
            int connectedVertex = temp->vertex;
            if (!graph->visited[connectedVertex]) {
                graph->visited[connectedVertex] = true;
                queue[rear++] = connectedVertex;
            }
            temp = temp->next;
        }
    }
}

总结

本文详细解析了数据结构第三章的关键习题，包括线性表、栈和队列、树和二叉树以及图。通过这些习题的解析，可以帮助读者更好地理解和掌握数据结构的相关知识。希望本文对您有所帮助！

-- 展开阅读全文 --