正文

严蔚敏经典数据结构源码解读：从入门到精通

/0 浏览量
0831

在计算机科学领域，数据结构是至关重要的基础知识。严蔚敏教授的《数据结构》一书，作为中国计算机教育领域的经典教材，深受广大读者喜爱。本书不仅系统地介绍了各种基本数据结构，还提供了丰富的源代码示例。本文将带领读者从入门到精通，深入解读严蔚敏经典数据结构源码。

一、数据结构概述

1.1 数据结构定义

数据结构是计算机存储、组织数据的方式。它不仅影响程序的性能，还决定了程序的可读性和可维护性。

1.2 数据结构分类

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

二、线性结构源码解读

2.1 数组

数组是一种基本的数据结构，它使用连续的内存空间存储元素。以下是一个简单的数组实现示例：

#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;
}

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

2.2 链表

链表是一种使用指针存储数据的线性结构。以下是一个简单的单向链表实现示例：

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;
}

int deleteNode(Node **head, int value) {
    Node *current = *head;
    Node *previous = NULL;
    while (current != NULL && current->data != value) {
        previous = current;
        current = current->next;
    }
    if (current == NULL) {
        return -1;
    }
    if (previous == NULL) {
        *head = current->next;
    } else {
        previous->next = current->next;
    }
    free(current);
    return 0;
}

2.3 栈和队列

栈和队列都是特殊的线性结构，分别遵循后进先出（LIFO）和先进先出（FIFO）的原则。以下是一个简单的栈实现示例：

#define MAX_SIZE 100

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

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

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

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

三、非线性结构源码解读

3.1 树

树是一种重要的非线性结构，由节点组成，每个节点有零个或多个子节点。以下是一个简单的二叉树实现示例：

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 *current = *root;
    while (current != NULL) {
        if (value < current->data) {
            if (current->left == NULL) {
                current->left = createNode(value);
                return;
            }
            current = current->left;
        } else {
            if (current->right == NULL) {
                current->right = createNode(value);
                return;
            }
            current = current->right;
        }
    }
}

3.2 图

图是一种由节点和边组成的数据结构，用于表示实体之间的关系。以下是一个简单的邻接表实现示例：

#define MAX_SIZE 100

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

typedef struct Vertex {
    int data;
    Edge *edges;
} Vertex;

typedef struct Graph {
    int numVertices;
    Vertex *vertices;
} Graph;

Graph* createGraph(int numVertices) {
    Graph *graph = (Graph *)malloc(sizeof(Graph));
    if (graph == NULL) {
        return NULL;
    }
    graph->numVertices = numVertices;
    graph->vertices = (Vertex *)malloc(numVertices * sizeof(Vertex));
    for (int i = 0; i < numVertices; ++i) {
        graph->vertices[i].data = i;
        graph->vertices[i].edges = NULL;
    }
    return graph;
}

void addEdge(Graph *graph, int from, int to) {
    Edge *newEdge = (Edge *)malloc(sizeof(Edge));
    if (newEdge == NULL) {
        return;
    }
    newEdge->to = to;
    newEdge->next = graph->vertices[from].edges;
    graph->vertices[from].edges = newEdge;
}

四、总结

本文从入门到精通，详细解读了严蔚敏经典数据结构源码。通过学习这些源码，读者可以更好地理解数据结构的基本原理和应用。在实际编程过程中，灵活运用这些数据结构，可以编写出高效、可读性强的程序。希望本文对读者有所帮助。

-- 展开阅读全文 --