正文

掌握数据结构精髓，严蔚敏源码解析攻略大全

/0 浏览量
0908

在计算机科学的世界里，数据结构是构建高效算法的基石。严蔚敏先生的《数据结构》一书，作为中国计算机科学教育的重要教材，其影响力遍及大江南北。本书不仅深入浅出地介绍了各种数据结构，还提供了丰富的源码示例，帮助读者更好地理解和掌握数据结构的精髓。本文将带你深入解析严蔚敏源码，助你成为数据结构的高手。

一、数据结构概述

数据结构是计算机存储、组织数据的方式。它不仅决定了数据的存储形式，还影响了数据处理的效率。常见的几种数据结构包括：

  • 线性结构：如数组、链表、栈、队列等。
  • 非线性结构：如树、图等。
  • 特殊结构：如散列表、堆等。

每种数据结构都有其独特的应用场景和操作方法。

二、严蔚敏源码解析攻略

1. 线性结构

数组

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

#include <stdio.h>

#define MAX_SIZE 100

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

void initArray(Array *a, int size) {
    a->length = size;
    for (int i = 0; i < size; i++) {
        a->data[i] = 0;
    }
}

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

链表

链表是一种动态的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。以下是链表的基本操作：

#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) {
        return NULL;
    }
    node->data = value;
    node->next = NULL;
    return node;
}

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

2. 非线性结构

树

树是一种重要的非线性数据结构，它由节点组成，每个节点有零个或多个子节点。以下是二叉树的基本操作：

#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) {
        return NULL;
    }
    node->data = value;
    node->left = NULL;
    node->right = NULL;
    return node;
}

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

图

图是一种由节点和边组成的数据结构，它表示了节点之间的关系。以下是图的基本操作：

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

typedef struct Graph {
    int numVertices;
    int **adjMatrix;
} Graph;

Graph* createGraph(int numVertices) {
    Graph *graph = (Graph *)malloc(sizeof(Graph));
    if (!graph) {
        return NULL;
    }
    graph->numVertices = numVertices;
    graph->adjMatrix = (int **)malloc(numVertices * sizeof(int *));
    for (int i = 0; i < numVertices; i++) {
        graph->adjMatrix[i] = (int *)malloc(numVertices * sizeof(int));
        for (int j = 0; j < numVertices; j++) {
            graph->adjMatrix[i][j] = 0;
        }
    }
    return graph;
}

void addEdge(Graph *graph, int src, int dest) {
    graph->adjMatrix[src][dest] = 1;
    graph->adjMatrix[dest][src] = 1;
}

3. 特殊结构

散列表

散列表是一种基于散列函数将数据存储在数组中的数据结构。以下是散列表的基本操作：

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

#define HASH_TABLE_SIZE 100

typedef struct HashNode {
    int key;
    int value;
    struct HashNode *next;
} HashNode;

HashNode* createHashNode(int key, int value) {
    HashNode *node = (HashNode *)malloc(sizeof(HashNode));
    if (!node) {
        return NULL;
    }
    node->key = key;
    node->value = value;
    node->next = NULL;
    return node;
}

int hashFunction(int key) {
    return key % HASH_TABLE_SIZE;
}

void insertHashTable(HashNode **hashTable, int key, int value) {
    int index = hashFunction(key);
    HashNode *node = createHashNode(key, value);
    node->next = hashTable[index];
    hashTable[index] = node;
}

堆

堆是一种特殊的树形数据结构，它满足堆的性质。以下是堆的基本操作：

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

#define MAX_SIZE 100

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

void initHeap(Heap *h) {
    h->length = 0;
}

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heapify(Heap *h, int index) {
    int largest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    if (left < h->length && h->data[left] > h->data[largest]) {
        largest = left;
    }
    if (right < h->length && h->data[right] > h->data[largest]) {
        largest = right;
    }
    if (largest != index) {
        swap(&h->data[index], &h->data[largest]);
        heapify(h, largest);
    }
}

void insertHeap(Heap *h, int value) {
    h->data[h->length] = value;
    int index = h->length;
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (h->data[parent] < h->data[index]) {
            swap(&h->data[parent], &h->data[index]);
            index = parent;
        } else {
            break;
        }
    }
    h->length++;
}

三、总结

通过以上对严蔚敏源码的解析，相信你已经对数据结构有了更深入的了解。在今后的学习和工作中，请不断实践和总结，将数据结构运用到实际项目中，为计算机科学的发展贡献自己的力量。

-- 展开阅读全文 --