正文

数据结构宝典：严蔚敏经典源码深度解析

/0 浏览量
0901

引言

数据结构是计算机科学中的基础课程，对于理解计算机如何处理和组织数据至关重要。严蔚敏教授是中国数据结构领域的权威，他的经典教材《数据结构（C语言版）》至今仍被广大读者推崇。本文将深入解析严蔚敏教授的源码，带您领略数据结构的精髓。

第一章：线性表

1.1 线性表的定义

线性表是一种基本的数据结构，它由有限个元素组成，每个元素都有一个唯一的序号。线性表中的元素按一定的顺序排列，可以使用数组或链表来实现。

1.2 数组实现线性表

以下是一个使用数组实现的线性表的示例代码：

#include <stdio.h>

#define MAXSIZE 100 // 定义线性表的最大长度

typedef struct {
    int data[MAXSIZE]; // 存储线性表元素的数组
    int length;        // 线性表的当前长度
} SeqList;

// 初始化线性表
void InitList(SeqList *L) {
    L->length = 0;
}

// 向线性表中插入元素
void ListInsert(SeqList *L, int i, int e) {
    if (i < 1 || i > L->length + 1 || L->length == MAXSIZE) {
        printf("插入位置不合理或线性表已满\n");
        return;
    }
    for (int j = L->length; j >= i; j--) {
        L->data[j] = L->data[j - 1];
    }
    L->data[i - 1] = e;
    L->length++;
}

// 删除线性表中的元素
void ListDelete(SeqList *L, int i, int *e) {
    if (i < 1 || i > L->length) {
        printf("删除位置不合理\n");
        return;
    }
    *e = L->data[i - 1];
    for (int j = i; j < L->length; j++) {
        L->data[j - 1] = L->data[j];
    }
    L->length--;
}

1.3 链表实现线性表

链表是一种更为灵活的线性表实现方式，它使用节点来存储数据。以下是一个使用链表实现的线性表的示例代码：

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

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

// 创建节点
Node* CreateNode(int e) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = e;
    newNode->next = NULL;
    return newNode;
}

// 向链表中插入元素
void ListInsert(Node *L, int i, int e) {
    Node *pre = L;
    for (int j = 1; j < i; j++) {
        if (pre->next == NULL) {
            printf("插入位置不合理\n");
            return;
        }
        pre = pre->next;
    }
    Node *newNode = CreateNode(e);
    newNode->next = pre->next;
    pre->next = newNode;
}

// 删除链表中的元素
void ListDelete(Node *L, int i, int *e) {
    Node *pre = L;
    for (int j = 1; j < i; j++) {
        if (pre->next == NULL) {
            printf("删除位置不合理\n");
            return;
        }
        pre = pre->next;
    }
    Node *temp = pre->next;
    *e = temp->data;
    pre->next = temp->next;
    free(temp);
}

第二章：栈和队列

2.1 栈的定义

栈是一种后进先出（LIFO）的数据结构，元素只能从一端添加或删除。

2.2 栈的数组实现

以下是一个使用数组实现的栈的示例代码：

#include <stdio.h>

#define MAXSIZE 100 // 定义栈的最大长度

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

// 初始化栈
void InitStack(Stack *S) {
    S->top = -1;
}

// 入栈操作
void Push(Stack *S, int e) {
    if (S->top == MAXSIZE - 1) {
        printf("栈满\n");
        return;
    }
    S->data[++S->top] = e;
}

// 出栈操作
int Pop(Stack *S, int *e) {
    if (S->top == -1) {
        printf("栈空\n");
        return 0;
    }
    *e = S->data[S->top--];
    return 1;
}

2.3 队列的定义

队列是一种先进先出（FIFO）的数据结构，元素只能从一端添加，从另一端删除。

2.4 队列的链表实现

以下是一个使用链表实现的队列的示例代码：

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

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

typedef struct {
    Node *front;
    Node *rear;
} Queue;

// 创建节点
Node* CreateNode(int e) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = e;
    newNode->next = NULL;
    return newNode;
}

// 初始化队列
void InitQueue(Queue *Q) {
    Q->front = Q->rear = CreateNode(0);
    Q->front->next = NULL;
}

// 入队操作
void EnQueue(Queue *Q, int e) {
    Node *newNode = CreateNode(e);
    newNode->next = NULL;
    Q->rear->next = newNode;
    Q->rear = newNode;
}

// 出队操作
int DeQueue(Queue *Q, int *e) {
    if (Q->front->next == NULL) {
        printf("队列空\n");
        return 0;
    }
    Node *temp = Q->front->next;
    *e = temp->data;
    Q->front->next = temp->next;
    if (Q->front->next == NULL) {
        Q->rear = Q->front;
    }
    free(temp);
    return 1;
}

第三章：串

3.1 串的定义

串是由零个或多个字符组成的有限序列。

3.2 串的数组实现

以下是一个使用数组实现的串的示例代码：

#include <stdio.h>
#include <string.h>

#define MAXSIZE 100 // 定义串的最大长度

typedef struct {
    char data[MAXSIZE];
    int length;
} String;

// 初始化串
void InitString(String *S) {
    memset(S->data, 0, sizeof(S->data));
    S->length = 0;
}

// 连接串
void Concat(String *S1, String *S2, String *S3) {
    strcpy(S3->data, S1->data);
    strcat(S3->data, S2->data);
    S3->length = S1->length + S2->length;
}

// 子串
int SubString(String *S1, String *S2, int pos, int len) {
    if (pos < 1 || pos > S1->length - len + 1) {
        printf("子串位置不合理\n");
        return 0;
    }
    strncpy(S2->data, S1->data + pos - 1, len);
    S2->data[len] = '\0';
    S2->length = len;
    return 1;
}

第四章：树和二叉树

4.1 树的定义

树是一种非线性的数据结构，由若干节点组成，每个节点有零个或多个子节点。

4.2 二叉树的定义

二叉树是树的一种特殊情况，每个节点最多有两个子节点。

4.3 二叉树的数组实现

以下是一个使用数组实现的二叉树的示例代码：

#include <stdio.h>

#define MAXSIZE 100 // 定义二叉树的最大长度

typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode;

// 创建二叉树
BiTNode* CreateBiTree(BiTNode *T, int data) {
    if (data == -1) {
        return NULL;
    }
    T = (BiTNode *)malloc(sizeof(BiTNode));
    T->data = data;
    T->lchild = CreateBiTree(T->lchild, data);
    T->rchild = CreateBiTree(T->rchild, data);
    return T;
}

// 中序遍历二叉树
void InOrder(BiTNode *T) {
    if (T == NULL) {
        return;
    }
    InOrder(T->lchild);
    printf("%d ", T->data);
    InOrder(T->rchild);
}

第五章：图

5.1 图的定义

图是一种复杂的数据结构，由若干节点和连接这些节点的边组成。

5.2 图的邻接矩阵实现

以下是一个使用邻接矩阵实现的图的示例代码：

#include <stdio.h>

#define MAXSIZE 100 // 定义图的最大长度

typedef struct {
    int edges[MAXSIZE][MAXSIZE]; // 邻接矩阵
    int numVertexes, numEdges;
} MGraph;

// 创建图
void CreateMGraph(MGraph *G) {
    G->numVertexes = 4;
    G->numEdges = 6;
    int i, j, k;
    for (i = 0; i < G->numVertexes; i++) {
        for (j = 0; j < G->numVertexes; j++) {
            G->edges[i][j] = 0;
        }
    }
    // 添加边
    G->edges[0][1] = 1;
    G->edges[0][2] = 1;
    G->edges[1][2] = 1;
    G->edges[1][3] = 1;
    G->edges[2][3] = 1;
    G->edges[3][0] = 1;
}

总结

本文深入解析了严蔚敏教授的经典教材《数据结构（C语言版）》中的源码，涵盖了线性表、栈和队列、串、树和二叉树以及图等基本数据结构。通过对这些源码的分析，读者可以更好地理解数据结构的原理和应用，为编程实践打下坚实的基础。

-- 展开阅读全文 --