正文

掌握数据结构，严蔚敏经典源码详解攻略

/0 浏览量
0901

在计算机科学的世界里，数据结构是构建高效算法的基石。严蔚敏先生的《数据结构》一书，作为国内计算机专业的经典教材，深受广大读者喜爱。本书不仅系统地介绍了各种基本数据结构，还提供了丰富的源码示例，帮助读者深入理解数据结构的原理和应用。本文将围绕严蔚敏经典源码，详细讲解如何进行有效的学习和掌握。

第一章：数据结构概述

1.1 数据结构的基本概念

数据结构是指计算机中存储、组织数据的方式。它不仅包括数据的存储形式，还包括数据的操作方法。掌握数据结构，有助于我们编写出高效、可维护的代码。

1.2 数据结构的分类

数据结构主要分为线性结构和非线性结构两大类。线性结构包括数组、链表、栈、队列等；非线性结构包括树、图等。

第二章：线性表

2.1 数组

数组是一种基本的数据结构，它使用连续的内存空间来存储元素。以下是使用C语言实现数组的基本操作：

#include <stdio.h>

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int length;
} Array;

void initArray(Array *a) {
    a->length = 0;
}

void insertArray(Array *a, int index, int value) {
    if (index < 0 || index > a->length) {
        return;
    }
    for (int i = a->length; i > index; i--) {
        a->data[i] = a->data[i - 1];
    }
    a->data[index] = value;
    a->length++;
}

void deleteArray(Array *a, int index) {
    if (index < 0 || index >= a->length) {
        return;
    }
    for (int i = index; i < a->length - 1; i++) {
        a->data[i] = a->data[i + 1];
    }
    a->length--;
}

2.2 链表

链表是一种使用指针连接元素的数据结构。以下是使用C语言实现单链表的基本操作：

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

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

Node* createNode(int value) {
    Node *node = (Node *)malloc(sizeof(Node));
    if (node == NULL) {
        return NULL;
    }
    node->data = value;
    node->next = NULL;
    return node;
}

void insertNode(Node **head, int value) {
    Node *newNode = createNode(value);
    if (newNode == NULL) {
        return;
    }
    newNode->next = *head;
    *head = newNode;
}

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

第三章：栈和队列

3.1 栈

栈是一种后进先出（LIFO）的数据结构。以下是使用C语言实现栈的基本操作：

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

#define MAX_SIZE 100

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

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

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

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

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

3.2 队列

队列是一种先进先出（FIFO）的数据结构。以下是使用C语言实现队列的基本操作：

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

#define MAX_SIZE 100

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

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

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

void enqueue(Queue *q, int value) {
    if ((q->rear + 1) % MAX_SIZE == q->front) {
        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;
}

第四章：树和图

4.1 树

树是一种非线性数据结构，由节点组成，每个节点有零个或多个子节点。以下是使用C语言实现二叉树的基本操作：

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

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

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

void insertNode(TreeNode **root, int value) {
    if (*root == NULL) {
        *root = createNode(value);
        return;
    }
    TreeNode *temp = *root;
    while (temp != NULL) {
        if (value < temp->data) {
            if (temp->left == NULL) {
                temp->left = createNode(value);
                return;
            }
            temp = temp->left;
        } else {
            if (temp->right == NULL) {
                temp->right = createNode(value);
                return;
            }
            temp = temp->right;
        }
    }
}

4.2 图

图是一种非线性数据结构，由节点和边组成。以下是使用C语言实现邻接矩阵表示的图的基本操作：

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

#define MAX_SIZE 100

typedef struct {
    int adjMatrix[MAX_SIZE][MAX_SIZE];
    int numVertices;
} Graph;

void initGraph(Graph *g, int numVertices) {
    g->numVertices = numVertices;
    for (int i = 0; i < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
            g->adjMatrix[i][j] = 0;
        }
    }
}

void addEdge(Graph *g, int start, int end) {
    g->adjMatrix[start][end] = 1;
    g->adjMatrix[end][start] = 1;
}

第五章：总结

通过以上对严蔚敏经典源码的详解，相信你已经对数据结构有了更深入的理解。在实际应用中，我们需要根据具体问题选择合适的数据结构，以达到最佳的性能。希望本文能帮助你更好地掌握数据结构，为你的编程之路打下坚实的基础。

-- 展开阅读全文 --