正文

掌握数据结构，严蔚敏经典源码深度解析指南

/0 浏览量
0909

在计算机科学中，数据结构是构建高效算法的基石。严蔚敏老师的《数据结构（C语言版）》是一本深受广大计算机专业学生和开发者喜爱的教材。本书不仅深入浅出地介绍了各种基本数据结构，还提供了丰富的源代码，帮助读者理解和掌握数据结构的应用。本文将带你一起深入解析严蔚敏经典源码，帮助你更好地掌握数据结构。

1. 数据结构概述

1.1 数据结构与算法的关系

数据结构是指计算机中存储数据的方式，它决定了数据的组织、管理和访问效率。算法则是解决特定问题的步骤序列，它依赖于数据结构来实现。因此，掌握数据结构对于理解和设计高效算法至关重要。

1.2 常见数据结构

在严蔚敏的书中，介绍了以下常见数据结构：

  • 线性结构：顺序表、链表、栈、队列
  • 非线性结构：树、图

2. 顺序表

顺序表是一种线性结构，它使用一段连续的存储空间来存储数据元素。以下是顺序表的实现代码：

#include <stdio.h>
#include <stdlib.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) return;
    if (L->length >= MAXSIZE) 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) return;
    *e = L->data[i - 1];
    for (int j = i; j < L->length; j++) {
        L->data[j - 1] = L->data[j];
    }
    L->length--;
}

3. 链表

链表是一种非线性结构，它使用指针来存储数据元素。以下是单链表的实现代码：

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

typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

// 创建链表
LinkList CreateList() {
    LinkList L = (LinkList)malloc(sizeof(LNode));
    if (!L) return NULL;
    L->next = NULL;
    return L;
}

// 插入元素
void ListInsert(LinkList L, int i, int e) {
    LNode *p = L;
    for (int j = 1; j < i; j++) {
        p = p->next;
        if (!p) return;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (!s) return;
    s->data = e;
    s->next = p->next;
    p->next = s;
}

// 删除元素
void ListDelete(LinkList L, int i, int *e) {
    LNode *p = L;
    for (int j = 1; j < i; j++) {
        p = p->next;
        if (!p) return;
    }
    LNode *q = p->next;
    *e = q->data;
    p->next = q->next;
    free(q);
}

4. 栈与队列

栈和队列都是线性结构，它们遵循“后进先出”（栈）和“先进先出”（队列）的原则。

以下是栈的实现代码：

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

#define MAXSIZE 100

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

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

// 入栈
void Push(SeqStack *S, int e) {
    if (S->top >= MAXSIZE - 1) return;
    S->data[++S->top] = e;
}

// 出栈
int Pop(SeqStack *S, int *e) {
    if (S->top == -1) return 0;
    *e = S->data[S->top--];
    return 1;
}

以下是队列的实现代码：

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

#define MAXSIZE 100

typedef struct {
    int data[MAXSIZE];
    int front, rear;
} SeqQueue;

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

// 入队
void EnQueue(SeqQueue *Q, int e) {
    if ((Q->rear + 1) % MAXSIZE == Q->front) return;
    Q->data[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MAXSIZE;
}

// 出队
int DeQueue(SeqQueue *Q, int *e) {
    if (Q->front == Q->rear) return 0;
    *e = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAXSIZE;
    return 1;
}

5. 树与图

树和图是两种常见的非线性结构，它们在计算机科学中有着广泛的应用。

以下是二叉树的实现代码：

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

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

// 创建二叉树
BiTree CreateBiTree() {
    BiTNode *T = (BiTNode *)malloc(sizeof(BiTNode));
    if (!T) return NULL;
    printf("Enter data for root node: ");
    scanf("%d", &T->data);
    T->lchild = T->rchild = NULL;
    // 创建左子树
    printf("Enter data for left child of root node: ");
    T->lchild = CreateBiTree();
    // 创建右子树
    printf("Enter data for right child of root node: ");
    T->rchild = CreateBiTree();
    return T;
}

以下是图的实现代码：

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

#define MAXSIZE 100

typedef struct {
    int vexs[MAXSIZE];
    int arc[MAXSIZE][MAXSIZE];
    int vexnum, arcnum;
} ALGraph;

// 创建图
void CreateGraph(ALGraph *G) {
    printf("Enter number of vertices and edges: ");
    scanf("%d %d", &G->vexnum, &G->arcnum);
    for (int i = 0; i < G->vexnum; i++) {
        printf("Enter vertex %d: ", i + 1);
        scanf("%d", &G->vexs[i]);
    }
    for (int i = 0; i < G->vexnum; i++) {
        for (int j = 0; j < G->vexnum; j++) {
            G->arc[i][j] = 0;
        }
    }
    for (int i = 0; i < G->arcnum; i++) {
        printf("Enter edge %d: ", i + 1);
        int k, v1, v2;
        scanf("%d %d %d", &k, &v1, &v2);
        G->arc[v1][v2] = 1;
        G->arc[v2][v1] = 1;
    }
}

6. 总结

通过以上对严蔚敏经典源码的深度解析，相信你已经对数据结构有了更深入的理解。在实际应用中，数据结构的选择和优化对于提高程序性能至关重要。希望本文能帮助你更好地掌握数据结构，为你的编程之路打下坚实的基础。

-- 展开阅读全文 --