嵌入式软件开发第三部分，各类常用的数据结构及扩展，良好的数据结构选择是保证程序稳定运行的关键，（1）部分包括数组，链表，栈，队列。（2）部分包括树，堆。（3）部分包括散列表，图。

七 散列表（哈希表）

散列表（Hash Table）是一种根据关键字直接访问存储位置的数据结构，它能够实现快速查找、插入和删除操作。散列表通过把关键字映射到表中一个位置来访问记录，以加快查找速度。这个映射函数叫作散列函数（Hash Function），存放记录的数组叫作散列表（Hash Table）。

散列表在计算机领域有着广泛的应用，下面介绍其中一些具体的应用：

  1. 数据库索引：数据库中的索引通常使用散列表实现。每个索引项包含一个键值和一个指向对应数据项的指针。当需要查找某个数据项时，首先从索引中找到对应的键值，然后通过指针快速访问该数据项。

  2. 缓存系统：缓存系统通常使用散列表来存储缓存数据。当需要访问某个数据时，先在散列表中查找对应的缓存项，如果存在则直接返回结果。如果不存在则从原始数据源中获取数据，并将其存储到散列表中。

  3. 字典：字典通常使用散列表来存储单词和对应的解释。当需要查找某个单词的解释时，可以通过散列表中的键值快速找到对应的解释。

  4. 文件系统：部分文件系统（如NTFS文件系统）使用散列表来加速文件查找。文件系统中的散列表保存了文件名和对应的磁盘块号，通过散列表可以快速定位到指定文件的存储位置。

  5. 哈希加密：密码学中的哈希函数被广泛应用于密码加密和校验。哈希函数把任意长度的输入消息通过运算转换成固定长度的输出值，这个输出值可以作为消息的数字指纹，能够验证消息的完整性和真实性。

总之，散列表作为一种快速、高效的数据结构，被广泛应用于各种场景中，如数据库索引、缓存系统、字典、文件系统等。

散列表的核心思想是通过哈希函数将关键字映射到散列表地址上，实现快速查找。具体来说，散列表的操作可以分为以下几个步骤：

  1. 哈希函数的设计：哈希函数用来将任意长度的输入（例如电话号码）映射为固定长度的输出（例如散列表的地址）。好的哈希函数能够尽可能地把输入均匀地映射到各个散列表地址上，避免散列冲突（即多个关键字映射到同一个散列表地址上）。

  2. 散列冲突的处理：由于哈希函数的输出值有限，不同的关键字可能会被映射到同一个散列表地址上。因此，需要在散列表中采用一些方法来处理散列冲突。常见的解决冲突的方法包括：链地址法、开放地址法、再哈希法等。

  3. 再哈希法：设定若干个哈希函数，如果冲突了就用备用函数计算。多个哈希函数计算出来的还是同一个地址的概率就很低了
    开放地址法：当发生冲突时，形成一个探查序列，从冲突的那个地址开始，沿着序列逐个探查，常用的探测再散列有线性再散列和二次再散列。以二次再散列来说，加如地址5冲突，则依次探测5+11=6，5+22=9。。。。。挺好理解的
    链地址法：链地址就是在数组上插入链表，发生冲突后就插在链表头上。所以不管有多少冲突都没有问题
     

  4. 添加元素：将（键，值）对存储到散列表中，需要先通过哈希函数计算出该键对应的散列表地址，然后把值存放在该地址上。

  5. 查找元素：查找指定键对应的值时，需要用哈希函数计算出该键对应的散列表地址，然后在该地址上查找相应的值。如果存在散列冲突，则按照冲突处理方法进行查找。

散列表的时间复杂度主要取决于哈希函数的设计和散列冲突的处理方式。通常情况下，在哈希函数均匀分布的情况下，散列表的查找、插入和删除的时间复杂度平均为 O(1)。因此，散列表是一种高效的数据结构，被广泛应用于各种场景中，如数据库索引、缓存系统、字典等。

基于链地址法构建散列表（利用链表）

1）向散列表中添加元素

// 向散列表中添加元素
void insert(HashTable* hashtable, char* key, int value) {
    // 计算关键字的哈希值，并定位到该位置
    int pos = hash(key);
    // 判断该位置上是否已经有节点
    ListNode* node = hashtable->data[pos];
    while (node != NULL && strcmp(node->key, key) != 0) {
        node = node->next;
    }
    // 如果该位置上没有节点，则创建一个新节点并插入到链表头部
    if (node == NULL) {
        ListNode* new_node = new_node(key, value);
        new_node->next = hashtable->data[pos];
        hashtable->data[pos] = new_node;
        hashtable->size++;
    }
    // 如果该位置上已经有节点，则更新该节点的值
    else {
        node->value = value;
    }
}

2）在散列表中查找元素

// 在散列表中查找元素，如果找到则返回其对应的值，否则返回-1
int search(HashTable* hashtable, char* key) {
    // 计算关键字的哈希值，并定位到该位置
    int pos = hash(key);
    // 遍历链表查找该元素
    ListNode* node = hashtable->data[pos];
    while (node != NULL && strcmp(node->key, key) != 0) {
        node = node->next;
    }
    // 找到了该元素，返回其对应的值
    if (node != NULL) {
        return node->value;
    }
    // 没找到该元素，返回-1
    else {
        return -1;
    }
}

3）从散列表中删除元素

// 从散列表中删除元素
void remove_node(HashTable* hashtable, char* key) {
    // 计算关键字的哈希值，并定位到该位置
    int pos = hash(key);
    // 遍历链表查找该元素
    ListNode* node = hashtable->data[pos];
    ListNode* prev = NULL;
    while (node != NULL && strcmp(node->key, key) != 0) {
        prev = node;
        node = node->next;
    }
    // 处理该位置上的节点
    if (node != NULL) {
        // 如果该节点是链表头部，则将下一个节点设置为新的链表头部
        if (prev == NULL) {
            hashtable->data[pos] = node->next;
        }
        // 否则，将该节点从链表中删除
        else {
            prev->next = node->next;
        }
        free(node);
        hashtable->size--;
    }
}

全部程序

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

// 最大的散列表大小
#define MAX_SIZE 100

// 定义一个结构体保存散列表节点的信息
typedef struct {
    char* key;  // 关键字
    int value;  // 存储的值
} ListNode;

// 定义散列表的结构体
typedef struct {
    ListNode* data[MAX_SIZE];  // 散列表的数据
    int size;                  // 散列表的大小
} HashTable;

// 哈希函数，将字符串映射成散列表地址
int hash(char* key) {
    int hash_code = 0;
    for (int i = 0; i < strlen(key); i++) {
        hash_code = hash_code * 31 + key[i];
    }
    return hash_code % MAX_SIZE;
}

// 创建新的节点并返回指针
ListNode* new_node(char* key, int value) {
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    node->key = (char*)malloc(sizeof(char) * strlen(key));
    strcpy(node->key, key);
    node->value = value;
    return node;
}

// 向散列表中添加元素
void insert(HashTable* hashtable, char* key, int value) {
    // 计算关键字的哈希值，并定位到该位置
    int pos = hash(key);
    // 判断该位置上是否已经有节点
    ListNode* node = hashtable->data[pos];
    while (node != NULL && strcmp(node->key, key) != 0) {
        node = node->next;
    }
    // 如果该位置上没有节点，则创建一个新节点并插入到链表头部
    if (node == NULL) {
        ListNode* new_node = new_node(key, value);
        new_node->next = hashtable->data[pos];
        hashtable->data[pos] = new_node;
        hashtable->size++;
    }
    // 如果该位置上已经有节点，则更新该节点的值
    else {
        node->value = value;
    }
}

// 在散列表中查找元素，如果找到则返回其对应的值，否则返回-1
int search(HashTable* hashtable, char* key) {
    // 计算关键字的哈希值，并定位到该位置
    int pos = hash(key);
    // 遍历链表查找该元素
    ListNode* node = hashtable->data[pos];
    while (node != NULL && strcmp(node->key, key) != 0) {
        node = node->next;
    }
    // 找到了该元素，返回其对应的值
    if (node != NULL) {
        return node->value;
    }
    // 没找到该元素，返回-1
    else {
        return -1;
    }
}

// 从散列表中删除元素
void remove_node(HashTable* hashtable, char* key) {
    // 计算关键字的哈希值，并定位到该位置
    int pos = hash(key);
    // 遍历链表查找该元素
    ListNode* node = hashtable->data[pos];
    ListNode* prev = NULL;
    while (node != NULL && strcmp(node->key, key) != 0) {
        prev = node;
        node = node->next;
    }
    // 处理该位置上的节点
    if (node != NULL) {
        // 如果该节点是链表头部，则将下一个节点设置为新的链表头部
        if (prev == NULL) {
            hashtable->data[pos] = node->next;
        }
        // 否则，将该节点从链表中删除
        else {
            prev->next = node->next;
        }
        free(node);
        hashtable->size--;
    }
}

// 打印散列表中的内容
void print_hashtable(HashTable* hashtable) {
    printf("Size of hashtable: %d\n", hashtable->size);
    for (int i = 0; i < MAX_SIZE; i++) {
        ListNode* node = hashtable->data[i];
        if (node != NULL) {
            printf("Pos: %d\n", i);
            while (node != NULL) {
                printf("%s : %d\n", node->key, node->value);
                node = node->next;
            }
        }
    }
}

int main() {
    // 创建一个新的散列表
    HashTable* hashtable = (HashTable*)malloc(sizeof(HashTable));
    hashtable->size = 0;
    for (int i = 0; i < MAX_SIZE; i++) {
        hashtable->data[i] = NULL;
    }

    // 向散列表中添加元素
    insert(hashtable, "apple", 10);
    insert(hashtable, "banana", 20);
    insert(hashtable, "orange", 30);
    insert(hashtable, "grape", 40);

    // 在散列表中查找元素
    int value = search(hashtable, "banana");
    printf("The value of 'banana' is %d\n", value);

    // 从散列表中删除元素
    remove_node(hashtable, "grape");

    // 打印散列表中的内容
    print_hashtable(hashtable);

    // 释放散列表所占用的内存
    for (int i = 0; i < MAX_SIZE; i++) {
        ListNode* node = hashtable->data[i];
        while (node != NULL) {
            ListNode* temp = node;
            node = node->next;
            free(temp->key);
            free(temp);
        }
    }
    free(hashtable);

    return 0;
}

八 图

图是一种非线性的数据结构，它由节点（顶点）和边组成。节点之间的连线称为边，它们可以用来表示各种复杂的现实世界中的关系，例如社交网络、电路等。

以下是图的基本概念：

  1. 顶点：也称为节点，表示图中的一个元素。

  2. 边：表示两个顶点之间的关系。

  3. 有向图：如果边有方向，则称该图为有向图。

  4. 无向图：如果边没有方向，则称该图为无向图。

  5. 权：表示边的重要程度或代价。

  6. 路径：是通过一系列边连接在一起的顶点序列，用来描述从一个顶点到另一个顶点的路线。

  7. 环：是指至少含有一个顶点的路径，其中第一个顶点与最后一个顶点是相同的。

  8. 连通：如果图中每两个顶点之间都存在至少一条路径，则称该图为连通图。

  9. 强连通：如果图是有向图，且对于任意两个顶点 u 和 v，都存在一条从 u 到 v 和一条从 v 到 u 的路径，则称该图为强连通图。

 图的类型

图有两种类型：有向图和无向图。在有向图中，边是有方向的，表示从一个顶点到另一个顶点有一个单向的路径；而在无向图中，边是没有方向的，表示两个顶点之间的路径是双向的。

常用的图的存储结构有以下几种：

  1. 邻接矩阵：使用一个二维数组来表示图中顶点之间的关系，其中数组的行和列分别表示图中的顶点，用 0 或 1 来表示是否存在边。当然，在带权图中，可以用数组元素的值来表示边的权值。

  2. 邻接表：使用一个链表数组来表示图中顶点之间的关系，每个链表表示一个顶点的邻接点集。链表中的节点包含两部分信息：邻接点的编号和这条边的权值（如果是带权图）。

  3. 关联矩阵：使用一个二维数组来表示图中顶点和边之间的关系，其中数组的行表示顶点，列表示边，用 0 或 1 表示该顶点与该边是否相关。当然，在带权图中，可以用数组元素的值来表示边的权值。

常用的图算法有以下几种：

  1. 深度优先搜索（DFS）：从一个起点开始，依次遍历所有与之相邻的顶点，并不断深入直到无法继续为止。在进行搜索的过程中，需要使用一个栈来记录已经访问的顶点。

  2. 广度优先搜索（BFS）：从一个起点开始，先访问其所有相邻的顶点，然后再访问这些相邻顶点的相邻顶点，依次类推。在进行搜索的过程中，需要使用一个队列来记录已经访问的顶点。

  3. 最短路径算法：用于找出图中两个顶点之间的最短路径，其中常用的算法包括 Dijkstra 算法和 Floyd-Warshall 算法。

  4. 最小生成树算法：用于找出图中的一棵生成树，使得该生成树的所有边权值之和最小。其中常用的算法包括 Prim 算法和 Kruskal 算法。

基于邻接表存储结构的深度优先搜索（DFS）

在下面的代码中，我们使用邻接表存储图，并采用递归的方式实现深度优先搜索。具体来说，我们使用一个 visited 数组来记录每个顶点是否被访问过，然后从某个未被访问的顶点开始，依次遍历其所有邻接点，并对每个未被访问的邻接点递归调用 DFS 函数。在 DFS 函数中，我们首先将当前顶点标记为已经被访问过，然后输出当前顶点的信息，并遍历它的所有邻接点。如果某个邻接点还没有被访问过，就递归调用 DFS 函数。最后，在主函数中，我们通过 InsertVertex 和 InsertArc 函数构造了一个简单的图，并对它进行深度优先遍历。

#define MAX_VERTEX_NUM 100   // 定义最大顶点数
#define FALSE 0
#define TRUE 1

// 邻接表中每个链表结点的定义
typedef struct ArcNode {
    int adjvex;              // 邻接点的编号
    struct ArcNode *nextarc; // 指向下一个邻接点的指针
} ArcNode;

// 邻接表中每个头结点的定义
typedef struct VNode {
    char data;               // 顶点的数据域
    ArcNode *firstarc;       // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];

// 图的定义
typedef struct {
    AdjList vertices;        // 邻接表
    int vexnum, arcnum;      // 顶点数和边数
} ALGraph;

int visited[MAX_VERTEX_NUM]; // 记录每个顶点是否被访问过

// 初始化图
void InitGraph(ALGraph *G) {
    G->vexnum = G->arcnum = 0;
    for (int i = 0; i < MAX_VERTEX_NUM; i++) {
        G->vertices[i].data = '\0';
        G->vertices[i].firstarc = NULL;
    }
}

// 插入一个顶点，返回该顶点在邻接表中的位置
int InsertVertex(ALGraph *G, char v) {
    if (G->vexnum >= MAX_VERTEX_NUM) {
        printf("Error: Too many vertices\n");
        return -1;
    } else {
        G->vertices[G->vexnum].data = v;
        G->vertices[G->vexnum].firstarc = NULL;
        return G->vexnum++;
    }
}

// 插入一条边 (vi, vj)
void InsertArc(ALGraph *G, int vi, int vj) {
    ArcNode *p = (ArcNode*)malloc(sizeof(ArcNode)); // 分配一个新的链表结点
    p->adjvex = vj;
    p->nextarc = G->vertices[vi].firstarc; // 将新结点插入到链表的头部
    G->vertices[vi].firstarc = p;
    G->arcnum++;
}

// 深度优先搜索算法
void DFS(ALGraph *G, int v) {
    visited[v] = TRUE; // 标记当前顶点已被访问
    printf("%c ", G->vertices[v].data);
    ArcNode *p = G->vertices[v].firstarc;
    while (p != NULL) { // 遍历 v 的所有邻接点
        if (!visited[p->adjvex]) {
            DFS(G, p->adjvex); // 对每个未被访问的邻接点递归调用 DFS
        }
        p = p->nextarc;
    }
}

// 对图进行深度优先遍历
void DFSTraverse(ALGraph *G) {
    memset(visited, FALSE, sizeof(visited)); // 初始化 visited 数组
    for (int i = 0; i < G->vexnum; i++) {
        if (!visited[i]) {
            DFS(G, i); // 对每个未被访问的顶点进行 DFS
        }
    }
}

int main() {
    ALGraph G;
    InitGraph(&G);
    int v1 = InsertVertex(&G, 'A');
    int v2 = InsertVertex(&G, 'B');
    int v3 = InsertVertex(&G, 'C');
    int v4 = InsertVertex(&G, 'D');
    InsertArc(&G, v1, v2);
    InsertArc(&G, v2, v3);
    InsertArc(&G, v3, v4);
    InsertArc(&G, v4, v1);
    DFSTraverse(&G);
    return 0;
}

基于邻接表存储结构的广度优先搜索（BFS）（基于队列）

在下面的代码中，我们使用邻接表存储图，并采用队列的方式实现广度优先搜索。具体来说，我们使用一个 visited 数组来记录每个顶点是否被访问过，然后从某个未被访问的顶点开始，依次遍历其所有邻接点，并将每个未被访问的邻接点加入队列中。在队列非空的情况下，依次取出队首元素，并遍历它的所有邻接点，将未访问的邻接点加入队列中。直到队列为空为止。

在 BFS 函数中，我们首先初始化队列，将起始顶点加入队列中，并标记其已被访问。然后在队列非空的情况下，依次取出队首元素 u，并输出该顶点的信息。接着，我们遍历 u 的所有邻接点，如果某个邻接点 v 还没有被访问过，就将它加入队列，并标记 visited[v] 为 1。

在 BFSTraverse 函数中，我们对图中每个未访问的顶点分别调用 BFS 函数即可。

总之，广度优先搜索算法是一种基于队列的搜索方式，可以在无权图中找到从起始顶点到其他所有顶点的最短路径。

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

#define MAX_VERTEX_NUM 100   // 定义最大顶点数

// 邻接表中每个链表结点的定义
typedef struct ArcNode {
    int adjvex;              // 邻接点的编号
    struct ArcNode *nextarc; // 指向下一个邻接点的指针
} ArcNode;

// 邻接表中每个头结点的定义
typedef struct VNode {
    char data;               // 顶点的数据域
    ArcNode *firstarc;       // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];

// 图的定义
typedef struct {
    AdjList vertices;        // 邻接表
    int vexnum, arcnum;      // 顶点数和边数
} ALGraph;

int visited[MAX_VERTEX_NUM]; // 记录每个顶点是否被访问过

// 初始化图
void InitGraph(ALGraph *G) {
    G->vexnum = G->arcnum = 0;
    for (int i = 0; i < MAX_VERTEX_NUM; i++) {
        G->vertices[i].data = '\0';
        G->vertices[i].firstarc = NULL;
    }
}

// 插入一个顶点，返回该顶点在邻接表中的位置
int InsertVertex(ALGraph *G, char v) {
    if (G->vexnum >= MAX_VERTEX_NUM) {
        printf("Error: Too many vertices\n");
        return -1;
    } else {
        G->vertices[G->vexnum].data = v;
        G->vertices[G->vexnum].firstarc = NULL;
        return G->vexnum++;
    }
}

// 插入一条边 (vi, vj)
void InsertArc(ALGraph *G, int vi, int vj) {
    ArcNode *p = (ArcNode*)malloc(sizeof(ArcNode)); // 分配一个新的链表结点
    p->adjvex = vj;
    p->nextarc = G->vertices[vi].firstarc; // 将新结点插入到链表的头部
    G->vertices[vi].firstarc = p;
    G->arcnum++;
}

// 广度优先搜索算法
void BFS(ALGraph *G, int v) {
    // 初始化队列
    int head = 0, tail = 0;
    int queue[MAX_VERTEX_NUM];
    queue[tail++] = v;
    visited[v] = 1;

    while (head != tail) { // 队列非空时
        int u = queue[head++]; // 取出队首元素
        printf("%c ", G->vertices[u].data);
        ArcNode *p = G->vertices[u].firstarc;
        while (p != NULL) { // 遍历 u 的所有邻接点
            if (!visited[p->adjvex]) {
                queue[tail++] = p->adjvex; // 将未访问的邻接点入队
                visited[p->adjvex] = 1; // 标记邻接点已被访问过
            }
            p = p->nextarc;
        }
    }
}

// 对图进行广度优先遍历
void BFSTraverse(ALGraph *G) {
    memset(visited, 0, sizeof(visited)); // 初始化 visited 数组
    for (int i = 0; i < G->vexnum; i++) {
        if (!visited[i]) {
            BFS(G, i); // 对每个未被访问的顶点进行 BFS
        }
    }
}

int main() {
    ALGraph G;
    InitGraph(&G);
    int v1 = InsertVertex(&G, 'A');
    int v2 = InsertVertex(&G, 'B');
    int v3 = InsertVertex(&G, 'C');
    int v4 = InsertVertex(&G, 'D');
    InsertArc(&G, v1, v2);
    InsertArc(&G, v1, v4);
    InsertArc(&G, v2, v3);
    InsertArc(&G, v3, v4);
    BFSTraverse(&G);
    return 0;
}

基于邻接矩阵存储结构的 Dijkstra 算法（计算最短路径）

在下面的代码中，我们使用邻接矩阵存储图，并采用 Dijkstra 算法计算单源最短路径。具体来说，我们需要维护三个数组：dist 数组、path 数组和 visited 数组。其中，dist[i] 表示从起始点到顶点 i 的最短距离，path[i] 表示从起始点到顶点 i 的最短路径上的前驱结点，visited[i] 记录每个顶点是否已确定最短路径。

Dijkstra 算法的基本思想是，将所有顶点分成两个集合：已确定最短路径的顶点集合 S 和未确定最短路径的顶点集合 T（初始时，S 只包括起始点）。然后每次从 T 中找出距离起始点最近的一个顶点 u，并将 u 加入 S 集合中，标记为已确定最短路径。然后用 u 松弛其邻接点，更新其它顶点的最短路径长度和前驱结点。依次进行 n 次这样的过程（n 为顶点数），直到所有顶点的最短路径都已确定。

在 Dijkstra 函数中，我们首先初始化 dist 数组和 path 数组，将起始点到各顶点的距离初始化为边的权值，前驱结点初始化为起始点（如果有边相连）。然后将起始点加入 S 集合中，标记为已确定最短路径。接着，在 T 集合中找出距离起始点最近的那个顶点 min_v，将其加入 S 集合中，标记为已确定最短路径。然后用 min_v 松弛其邻接点，更新其他顶点的最短路径长度和前驱结点。重复上述步骤，直到所有顶点的最短路径都已确定。

在 PrintPath 函数中，我们采用递归的方式输出从起始点到终点的最短路径。首先判断是否已到达起始点，如果是则直接输出；否则递归输出终点的前驱结点，最后再输出终点。

总之，Dijkstra 算法是一种贪心算法，能够求解单源最短路径问题。它的时间复杂度为 O(n^2)，比较适用于稠密图。

#include <stdio.h>
#include <limits.h>

#define MAX_VERTEX_NUM 100   // 定义最大顶点数

// 邻接矩阵的定义
typedef struct {
    int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边的权值
    int vexnum, arcnum;                         // 顶点数和边数
} MGraph;

// 初始化图
void InitGraph(MGraph *G) {
    G->vexnum = G->arcnum = 0;
    for (int i = 0; i < MAX_VERTEX_NUM; i++) {
        for (int j = 0; j < MAX_VERTEX_NUM; j++) {
            G->edges[i][j] = INT_MAX;           // 初始化为无穷大
        }
    }
}

// 添加一条边 (vi, vj)，权值为 w
void AddArc(MGraph *G, int vi, int vj, int w) {
    G->edges[vi][vj] = w;
    G->arcnum++;
}

// Dijkstra 算法求单源最短路径
void Dijkstra(MGraph *G, int start, int dist[], int path[]) {
    int visited[MAX_VERTEX_NUM] = {0}; // 记录每个顶点是否已确定最短路径
    for (int i = 0; i < G->vexnum; i++) {
        dist[i] = G->edges[start][i];   // 初始化 dist 数组为起始点到各顶点的距离
        if (G->edges[start][i] < INT_MAX) {
            path[i] = start; // 如果起始点到该顶点有边，则将其前驱为起始点
        } else {
            path[i] = -1;    // 如果起始点到该顶点没有边，则将其前驱置为 -1
        }
    }
    dist[start] = 0;              // 起始点到自身距离为 0
    visited[start] = 1;           // 起始点已确定最短路径
    for (int i = 1; i < G->vexnum; i++) { // 其余 n-1 个顶点依次进入 S 集合
        int min_dist = INT_MAX;
        int min_v = -1;
        for (int j = 0; j < G->vexnum; j++) { // 找出当前未确定最短路径的顶点中距离最小的那个
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                min_v = j;
            }
        }
        if (min_v == -1) break;      // 如果找不到这样的顶点，说明剩下的顶点都不连通
        visited[min_v] = 1;          // 将该顶点加入 S 集合中，标记为已确定最短路径
        for (int j = 0; j < G->vexnum; j++) { // 更新其他顶点的最短路径
            if (!visited[j] && G->edges[min_v][j] < INT_MAX && dist[min_v] + G->edges[min_v][j] < dist[j]) {
                dist[j] = dist[min_v] + G->edges[min_v][j]; // 通过 min_v 松弛 j
                path[j] = min_v; // 更新 j 的前驱为 min_v
            }
        }
    }
}

// 输出从起始点到终点的最短路径
void PrintPath(MGraph *G, int start, int end, int path[]) {
    if (end == start) { // 如果已到达起始点，直接输出
        printf("%d ", start);
        return;
    }
    if (path[end] == -1) { // 如果终点没有前驱，说明不连通
        printf("Error: Not connected\n");
        return;
    }
    PrintPath(G, start, path[end], path); // 递归输出前驱
    printf("%d ", end);
}

int main() {
    MGraph G;
    InitGraph(&G);
    int v0 = 0, v1 = 1, v2 = 2, v3 = 3, v4 = 4;
    AddArc(&G, v0, v1, 10);
    AddArc(&G, v0, v3, 30);
    AddArc(&G, v0, v4, 100);
    AddArc(&G, v1, v2, 50);
    AddArc(&G, v2, v4, 10);
    AddArc(&G, v3, v2, 20);
    AddArc(&G, v3, v4, 60);
    int dist[MAX_VERTEX_NUM] = {0}; // 存储起始点到各顶点的最短距离
    int path[MAX_VERTEX_NUM] = {-1}; // 存储各顶点到起始点的最短路径上的前驱结点
    Dijkstra(&G, v0, dist, path);
    for (int i = 0; i < G.vexnum; i++) {
        printf("%d ", dist[i]);
    }
    printf("\n");
    PrintPath(&G, v0, v4, path);
    return 0;
}

基于邻接矩阵存储结构的 Prim 算法（最小生成树）

在下面的代码中，我们使用邻接矩阵存储图，并采用 Prim 算法计算最小生成树。具体来说，我们需要维护两个数组：dist 数组和 path 数组。其中，dist[i] 表示顶点 i 到最小生成树的最短距离，path[i] 表示顶点 i 到最小生成树上的前驱结点。visited 数组用于记录每个顶点是否已加入生成树。

Prim 算法的基本思想是，将所有顶点分成两个集合：已加入生成树的顶点集合 S 和未加入生成树的顶点集合 T（初始时，S 只包括起始点）。然后每次从 T 中找出距离 S 最近的一个顶点 u，并将 u 加入 S 集合中。然后用 u 松弛其邻接点，更新 T 中的顶点到生成树的距离和前驱结点。重复上述步骤，直到所有顶点都已加入生成树。

在 Prim 函数中，我们首先初始化 dist 数组和 path 数组，将起始点到各顶点的距离初始化为边的权值，前驱结点初始化为起始点（如果有边相连）。然后将起始点加入生成树中，标记为已访问。接着，在 T 集合中找出距离 S 最近的那个顶点 min_v，将其加入 S 集合中。然后用 min_v 松弛其邻接点，更新其他顶点到生成树的距离和前驱结点。重复上述步骤，直到所有顶点都已加入生成树。

总之，Prim 算法是一种贪心算法，能够求解最小生成树问题。它的时间复杂度为 O(n^2)，比较适用于稠密图。

#include <stdio.h>
#include <limits.h>

#define MAX_VERTEX_NUM 100   // 定义最大顶点数

// 邻接矩阵的定义
typedef struct {
    int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边的权值
    int vexnum, arcnum;                         // 顶点数和边数
} MGraph;

// 初始化图
void InitGraph(MGraph *G) {
    G->vexnum = G->arcnum = 0;
    for (int i = 0; i < MAX_VERTEX_NUM; i++) {
        for (int j = 0; j < MAX_VERTEX_NUM; j++) {
            G->edges[i][j] = INT_MAX;           // 初始化为无穷大
        }
    }
}

// 添加一条边 (vi, vj)，权值为 w
void AddArc(MGraph *G, int vi, int vj, int w) {
    G->edges[vi][vj] = w;
    G->edges[vj][vi] = w; // 无向图需要添加两条边
    G->arcnum++;
}

// Prim 算法求最小生成树
void Prim(MGraph *G, int start, int dist[], int path[]) {
    int visited[MAX_VERTEX_NUM] = {0}; // 记录每个顶点是否已加入生成树
    for (int i = 0; i < G->vexnum; i++) {
        dist[i] = G->edges[start][i];   // 初始化 dist 数组为起始点到各顶点的距离
        if (G->edges[start][i] < INT_MAX) {
            path[i] = start; // 如果起始点到该顶点有边，则将其前驱为起始点
        } else {
            path[i] = -1;    // 如果起始点到该顶点没有边，则将其前驱置为 -1
        }
    }
    visited[start] = 1;           // 将起始点加入生成树中，标记为已访问
    for (int i = 1; i < G->vexnum; i++) { // 其余 n-1 个顶点依次加入生成树
        int min_dist = INT_MAX;
        int min_v = -1;
        for (int j = 0; j < G->vexnum; j++) { // 找出当前未加入生成树的顶点中距离最小的那个
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                min_v = j;
            }
        }
        if (min_v == -1) break;      // 如果找不到这样的顶点，说明剩下的顶点都不连通
        visited[min_v] = 1;          // 将该顶点加入生成树中，标记为已访问
        for (int j = 0; j < G->vexnum; j++) { // 更新其他顶点到生成树的距离
            if (!visited[j] && G->edges[min_v][j] < dist[j]) {
                dist[j] = G->edges[min_v][j]; // 通过 min_v 更新 j 的到生成树的距离
                path[j] = min_v; // 更新 j 的前驱为 min_v
            }
        }
    }
}

int main() {
    MGraph G;
    InitGraph(&G);
    int v0 = 0, v1 = 1, v2 = 2, v3 = 3, v4 = 4;
    AddArc(&G, v0, v1, 10);
    AddArc(&G, v0, v3, 30);
    AddArc(&G, v0, v4, 100);
    AddArc(&G, v1, v2, 50);
    AddArc(&G, v2, v4, 10);
    AddArc(&G, v3, v2, 20);
    AddArc(&G, v3, v4, 60);
    int dist[MAX_VERTEX_NUM] = {0}; // 存储每个顶点到最小生成树的最短距离
    int path[MAX_VERTEX_NUM] = {-1}; // 存储每个顶点到最小生成树上的前驱结点
    Prim(&G, v0, dist, path);
    for (int i = 0; i < G.vexnum; i++) {
        printf("%d ", path[i]);
    }
    printf("\n");
    return 0;
}

# 数据结构 # 哈希算法 # c语言
Logo
乐奇 Rokid 开放社区

更多推荐

cover

国庆文旅安保上新！AR智能眼镜守护景区，黑科技护航假期出游

avatar 乐奇 Rokid 开放社区
cover

2027中国深圳智能穿戴产业链展览会

avatar 乐奇 Rokid 开放社区
cover

AR巡检哪家好

avatar 乐奇 Rokid 开放社区