正文

数据结构C语言版（第二版）课后习题解答详解

/0 浏览量
0413

1. 数组

1.1 数组的定义和初始化

数组是一种基本的数据结构，用于存储具有相同数据类型的元素序列。在C语言中，数组的定义如下：

类型 数组名[长度] = {元素1, 元素2, ..., 元素n};

例如，定义一个整型数组arr，长度为5，并初始化为{1, 2, 3, 4, 5}：

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

1.2 数组的访问和操作

数组可以通过索引访问和操作其元素。索引从0开始，例如，访问arr中的第二个元素：

int secondElement = arr[1];

还可以对数组进行操作，如排序、查找等。

2. 链表

2.1 链表的定义和初始化

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

typedef struct Node {
    类型 数据;
    struct Node *next;
} Node;

例如，定义一个整型链表节点：

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

初始化一个空链表：

Node *head = NULL;

2.2 链表的插入和删除

链表的基本操作包括插入和删除。以下是一个插入操作示例：

void insert(Node **head, int data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = *head;
    *head = newNode;
}

删除操作如下：

void delete(Node **head, int data) {
    Node *temp = *head, *prev = NULL;
    while (temp != NULL && temp->data != data) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) return;
    if (prev == NULL) {
        *head = temp->next;
    } else {
        prev->next = temp->next;
    }
    free(temp);
}

3. 栈和队列

3.1 栈的定义和操作

栈是一种后进先出（LIFO）的数据结构。以下是一个栈的定义和基本操作：

typedef struct Stack {
    类型 *array;
    int top;
    int capacity;
} Stack;

void initStack(Stack *s, int capacity) {
    s->array = (类型 *)malloc(capacity * sizeof(类型));
    s->top = -1;
    s->capacity = capacity;
}

void push(Stack *s, 类型 data) {
    if (s->top == s->capacity - 1) {
        return; // 栈满
    }
    s->array[++s->top] = data;
}

类型 pop(Stack *s) {
    if (s->top == -1) {
        return 0; // 栈空
    }
    return s->array[s->top--];
}

3.2 队列的定义和操作

队列是一种先进先出（FIFO）的数据结构。以下是一个队列的定义和基本操作：

typedef struct Queue {
    类型 *array;
    int front, rear, size, capacity;
} Queue;

void initQueue(Queue *q, int capacity) {
    q->array = (类型 *)malloc(capacity * sizeof(类型));
    q->front = q->size = 0;
    q->rear = capacity - 1;
    q->capacity = capacity;
}

int isFull(Queue *q) {
    return q->size == q->capacity;
}

int isEmpty(Queue *q) {
    return q->size == 0;
}

void enqueue(Queue *q, 类型 data) {
    if (isFull(q)) {
        return; // 队列满
    }
    q->rear = (q->rear + 1) % q->capacity;
    q->array[q->rear] = data;
    q->size++;
}

类型 dequeue(Queue *q) {
    if (isEmpty(q)) {
        return 0; // 队列空
    }
    类型 data = q->array[q->front];
    q->front = (q->front + 1) % q->capacity;
    q->size--;
    return data;
}

4. 树和图

4.1 树的定义和操作

树是一种非线性数据结构，由节点组成，每个节点包含数据和指向子节点的指针。以下是一个二叉树节点的定义和基本操作：

typedef struct TreeNode {
    类型 data;
    struct TreeNode *left, *right;
} TreeNode;

TreeNode *createNode(类型 data) {
    TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

void insertLeft(TreeNode *root, TreeNode *node) {
    root->left = node;
}

void insertRight(TreeNode *root, TreeNode *node) {
    root->right = node;
}

4.2 图的定义和操作

图是一种复杂的数据结构，由节点和边组成。以下是一个图的定义和基本操作：

typedef struct Graph {
    int numVertices;
    struct Edge *edges;
} Graph;

typedef struct Edge {
    int src, dest;
    struct Edge *next;
} Edge;

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

5. 总结

本文详细介绍了数据结构C语言版（第二版）课后习题中常见的几种数据结构，包括数组、链表、栈、队列、树和图。通过本文的学习，读者可以更好地理解和掌握这些数据结构，并在实际编程中灵活运用。

-- 展开阅读全文 --