首页 > 其他分享 >基础数据结构【c语言版】之 “图” 详细讲述

基础数据结构【c语言版】之 “图” 详细讲述

时间：2024-11-12 12:18:46浏览次数：3  
标签：讲述 int graph VERTICES ++ MAX 顶点 数据结构 语言版

别忘了请点个赞+收藏+关注支持一下博主喵！！！

1. 图的定义和术语

1.1 图的定义

**图（Graph）**是由顶点（Vertex）和边（Edge）组成的一个集合，可以表示顶点之间的关系。通常，图可以表示为 G=(V,E)G = (V, E)G=(V,E)，其中：

  • VVV 是顶点集合，表示图中的所有顶点。
  • EEE 是边集合，表示图中顶点之间的连接关系。

图的类型：：：

根据边的不同特性，图可以分为以下几种常见类型：

  1. 无向图（Undirected Graph）：边没有方向，连接两个顶点的边可以双向访问。例如，表示朋友关系的社交网络图通常为无向图。

  2. 有向图（Directed Graph）：边具有方向，从一个顶点指向另一个顶点。通常用箭头表示边的方向，例如，表示课程的先修关系图。

  3. 带权图（Weighted Graph）：每条边上都有一个权重（Weight），表示从一个顶点到另一个顶点的“代价”，如距离、时间或费用。例如，道路图中可以用权重表示每条道路的长度。

1.2 图的术语

在学习图结构时，我们需要掌握一些常用的术语，以便更好地理解图的概念。

  1. 顶点（Vertex）：图中的基本单位，每个顶点用来表示一个对象，通常记为 VVV 或者用 V1,V2,…,VnV_1, V_2, \dots, V_nV1​,V2​,…,Vn​ 来表示多个顶点。

  2. 边（Edge）：顶点与顶点之间的连接，用来表示对象之间的关系，通常记为 EEE。在无向图中，边用无序对 (Vi,Vj)(V_i, V_j)(Vi​,Vj​) 表示，而在有向图中，边用有序对 (Vi,Vj)(V_i, V_j)(Vi​,Vj​) 表示，其中边的方向从 ViV_iVi​ 指向 VjV_jVj​。

  3. 度（Degree）：

    • 无向图的度：在无向图中，顶点的度是连接该顶点的边的数量。例如，一个度为3的顶点表示有3条边连接到该顶点。
    • 有向图的入度和出度：在有向图中，入度（In-degree）表示指向该顶点的边数，出度（Out-degree）表示从该顶点出发的边数。

  4. 路径（Path）：从一个顶点到另一个顶点所经过的顶点序列。路径的长度是路径上边的数目。

    • 简单路径：不包含重复顶点的路径。
    • 回路（Cycle）：起点和终点相同的路径称为回路。

  5. 连通图（Connected Graph）：在无向图中，如果任意两个顶点之间都存在路径，则称该图为连通图。否则称为非连通图。

  6. 强连通图（Strongly Connected Graph）：在有向图中，如果任意两个顶点之间都存在路径（即双向可达），则称该图为强连通图。

  7. 稀疏图（Sparse Graph）和稠密图（Dense Graph）：

    • 稀疏图：边数远小于顶点数的平方，常常用邻接表表示。
    • 稠密图：边数接近顶点数的平方，常常用邻接矩阵表示。

1.3 C语言中的图表示

在C语言中，我们通常使用邻接矩阵或邻接表来存储图。以下是用邻接矩阵表示无向图的简单示例代码：

#include <stdio.h>

#define MAX_VERTICES 5  // 假设顶点数量最大为5

void initializeGraph(int graph[MAX_VERTICES][MAX_VERTICES]) {
    for (int i = 0; i < MAX_VERTICES; i++) {
        for (int j = 0; j < MAX_VERTICES; j++) {
            graph[i][j] = 0;  // 初始化图中所有边为0（即无连接）
        }
    }
}

void addEdge(int graph[MAX_VERTICES][MAX_VERTICES], int u, int v) {
    graph[u][v] = 1;
    graph[v][u] = 1;  // 无向图，边(u, v) 和 (v, u) 都需设置为1
}

void printGraph(int graph[MAX_VERTICES][MAX_VERTICES]) {
    for (int i = 0; i < MAX_VERTICES; i++) {
        for (int j = 0; j < MAX_VERTICES; j++) {
            printf("%d ", graph[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int graph[MAX_VERTICES][MAX_VERTICES];
    initializeGraph(graph);

    // 添加边
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    printf("图的邻接矩阵表示：\n");
    printGraph(graph);

    return 0;
}
  1. initializeGraph：初始化邻接矩阵，将所有元素设为0，表示无边。
  2. addEdge：在无向图中添加边。由于是无向图，边(u,v)(u, v)(u,v) 和 (v,u)(v, u)(v,u) 都设置为1。
  3. printGraph：输出邻接矩阵，方便观察图的结构。

运行上述代码会输出邻接矩阵，通过该矩阵可以查看每个顶点之间是否有边连接。

2. 图的存储结构

图的存储结构影响图的操作效率和存储空间。具体的存储结构包括：

2.1 数组表示法（邻接矩阵）

邻接矩阵是一种顺序存储结构，使用二维数组来表示顶点之间的连接关系。适合用于稠密图（边数接近于顶点数平方）。

  • 定义：假设图有 VVV 个顶点，用一个 V×VV \times VV×V 的二维数组 graph 表示图的邻接矩阵。
  • 有向图：若存在从顶点 iii 到顶点 jjj 的边，则 graph[i][j] = 1。
  • 无向图：如果 iii 和 jjj 之间有边，则 graph[i][j] = graph[j][i] = 1。
  • 加权图：若有边权重，则使用权重值代替 1。
#include <stdio.h>

#define MAX_VERTICES 4

void printGraph(int graph[MAX_VERTICES][MAX_VERTICES]) {
    for (int i = 0; i < MAX_VERTICES; i++) {
        for (int j = 0; j < MAX_VERTICES; j++) {
            printf("%d ", graph[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int graph[MAX_VERTICES][MAX_VERTICES] = { {0, 1, 0, 0}, {1, 0, 1, 1}, {0, 1, 0, 1}, {0, 1, 1, 0} };
    printf("邻接矩阵表示的图：\n");
    printGraph(graph);
    return 0;
}

2.2 邻接表

邻接表使用链表来存储顶点的邻接关系，适合用于稀疏图（边数较少）。

  • 定义：用数组 graph 存储每个顶点的邻接链表。graph[i] 指向顶点 iii 的链表，链表中包含所有与顶点 iii 相连的顶点。
  • 优点：节省空间，适合边较少的图。
#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 4

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

Node* createNode(int vertex) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = vertex;
    newNode->next = NULL;
    return newNode;
}

void addEdge(Node* graph[], int u, int v) {
    Node* newNode = createNode(v);
    newNode->next = graph[u];
    graph[u] = newNode;

    newNode = createNode(u);
    newNode->next = graph[v];
    graph[v] = newNode;
}

void printGraph(Node* graph[]) {
    for (int i = 0; i < MAX_VERTICES; i++) {
        Node* temp = graph[i];
        printf("顶点 %d:", i);
        while (temp) {
            printf(" -> %d", temp->vertex);
            temp = temp->next;
        }
        printf("\n");
    }
}

int main() {
    Node* graph[MAX_VERTICES] = {NULL};
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);

    printf("邻接表表示的图：\n");
    printGraph(graph);
    return 0;
}

2.3 十字链表

十字链表是一种用于存储有向图的结构，每条边包含指向起点和终点的两个指针，适合于表示入度和出度。

  • 定义：每个顶点包含两个链表，一个存储出边，一个存储入边。
  • 适用场景：用于需要频繁操作边的有向图。
typedef struct ArcNode {
    int tailvex, headvex;
    struct ArcNode *hlink, *tlink;
} ArcNode;

typedef struct VNode {
    int data;
    ArcNode *firstin, *firstout;
} VNode;

VNode graph[MAX_VERTICES];

2.4 邻接多重表

邻接多重表适合用于存储无向图，特别是在边的操作频繁时。每条边的节点结构包括两个顶点及其各自的相邻边指针。

  • 定义：每条边包含两个指针，分别指向两个顶点的邻接表节点。
  • 适用场景：用于表示无向图的连通性。
typedef struct EdgeNode {
    int ivex, jvex;
    struct EdgeNode *ilink, *jlink;
} EdgeNode;

typedef struct VertexNode {
    int data;
    EdgeNode *firstedge;
} VertexNode;

VertexNode graph[MAX_VERTICES];

 3. 图的遍历

图的遍历是指从一个顶点出发，沿着边遍历每一个顶点。常用的图的遍历方法有两种：深度优先搜索和广度优先搜索。

3.1 深度优先搜索（DFS）

深度优先搜索是一种尽可能“深入”访问图中顶点的遍历方法。其特点是沿着路径深入到某一分支的末端，然后回溯到上一个节点再遍历其他分支。

DFS 实现代码

以下是一个使用邻接矩阵表示图，并实现DFS的C语言示例代码：

#include <stdio.h>

#define MAX_VERTICES 10  // 定义最大顶点数
#define TRUE 1
#define FALSE 0

// 定义图结构
typedef struct {
    int vertices[MAX_VERTICES][MAX_VERTICES];  // 邻接矩阵
    int vertex_count;  // 顶点数量
} Graph;

// 初始化图
void initGraph(Graph *g, int vertex_count) {
    g->vertex_count = vertex_count;
    for (int i = 0; i < vertex_count; i++) {
        for (int j = 0; j < vertex_count; j++) {
            g->vertices[i][j] = 0;
        }
    }
}

// 添加边
void addEdge(Graph *g, int start, int end) {
    g->vertices[start][end] = 1;
    g->vertices[end][start] = 1;  // 如果是无向图，则双向连接
}

// 深度优先搜索
void DFS(Graph *g, int v, int visited[]) {
    visited[v] = TRUE;  // 标记顶点为已访问
    printf("%d ", v);   // 输出当前访问的顶点

    for (int i = 0; i < g->vertex_count; i++) {
        if (g->vertices[v][i] == 1 && !visited[i]) {  // 找到未访问的相邻顶点
            DFS(g, i, visited);  // 递归访问相邻顶点
        }
    }
}

// 调用DFS遍历整个图
void depthFirstSearch(Graph *g) {
    int visited[MAX_VERTICES] = {FALSE};  // 初始化访问标记
    printf("深度优先搜索遍历结果: ");
    for (int i = 0; i < g->vertex_count; i++) {
        if (!visited[i]) {
            DFS(g, i, visited);  // 对未访问的顶点进行DFS
        }
    }
    printf("\n");
}

3.2 广度优先搜索（BFS）

广度优先搜索是一种“逐层”访问图中顶点的遍历方法，使用队列存储待访问的顶点。先访问当前层的所有顶点，再逐层深入，适合查找最短路径。

BFS 实现代码

以下代码使用邻接矩阵表示图，并实现BFS算法：

#include <stdbool.h>

#define QUEUE_SIZE MAX_VERTICES

typedef struct {
    int items[QUEUE_SIZE];
    int front, rear;
} Queue;

// 初始化队列
void initQueue(Queue *q) {
    q->front = 0;
    q->rear = -1;
}

// 入队
void enqueue(Queue *q, int value) {
    if (q->rear < QUEUE_SIZE - 1) {
        q->items[++q->rear] = value;
    }
}

// 出队
int dequeue(Queue *q) {
    if (q->front <= q->rear) {
        return q->items[q->front++];
    }
    return -1;
}

// 判断队列是否为空
bool isEmpty(Queue *q) {
    return q->front > q->rear;
}

// 广度优先搜索
void breadthFirstSearch(Graph *g, int start) {
    int visited[MAX_VERTICES] = {FALSE};
    Queue q;
    initQueue(&q);

    printf("广度优先搜索遍历结果: ");
    enqueue(&q, start);   // 起点入队
    visited[start] = TRUE;

    while (!isEmpty(&q)) {
        int v = dequeue(&q);  // 获取队首顶点
        printf("%d ", v);

        for (int i = 0; i < g->vertex_count; i++) {
            if (g->vertices[v][i] == 1 && !visited[i]) {
                enqueue(&q, i);   // 相邻未访问顶点入队
                visited[i] = TRUE;  // 标记为已访问
            }
        }
    }
    printf("\n");
}

主函数调用示例

在主函数中初始化图、添加边并调用DFS和BFS函数进行遍历：

int main() {
    Graph g;
    initGraph(&g, 5);  // 假设图中有5个顶点

    // 添加一些边
    addEdge(&g, 0, 1);
    addEdge(&g, 0, 2);
    addEdge(&g, 1, 3);
    addEdge(&g, 2, 4);

    depthFirstSearch(&g);  // 执行深度优先搜索
    breadthFirstSearch(&g, 0);  // 从顶点0执行广度优先搜索

    return 0;
}

4 图的连通性问题

图的连通性问题在很多算法中是重要的基础。连通性问题主要涉及图的连通分量、生成树、强连通分量、最小生成树等。

4.1 无向图的连通分量和生成树

无向图的连通分量是一个最大连通子图。一个无向图可能包含多个连通分量。生成树是一个连通分量中包含所有顶点的最小边集合，且不包含环。

4.1.1 连通分量的DFS实现

可以通过深度优先搜索（DFS）找到所有连通分量。

#include <stdio.h>

#define MAX_VERTICES 10

typedef struct {
    int vertices[MAX_VERTICES][MAX_VERTICES];  // 邻接矩阵
    int vertex_count;  // 顶点数
} Graph;

void DFS(Graph *g, int v, int visited[]) {
    visited[v] = 1;
    printf("%d ", v);

    for (int i = 0; i < g->vertex_count; i++) {
        if (g->vertices[v][i] == 1 && !visited[i]) {
            DFS(g, i, visited);
        }
    }
}

void findConnectedComponents(Graph *g) {
    int visited[MAX_VERTICES] = {0};
    printf("连通分量:\n");
    for (int i = 0; i < g->vertex_count; i++) {
        if (!visited[i]) {
            DFS(g, i, visited);  // 每找到一个未访问顶点即代表一个连通分量
            printf("\n");
        }
    }
}

4.1.2 最小生成树的Kruskal算法

Kruskal算法通过对所有边进行排序并逐步选择权值最小的边来构造最小生成树。

4.2 有向图的强连通分量

在有向图中，强连通分量是一个子图，其中任意两个顶点都是互相可达的。通常可以使用Kosaraju算法实现，它包含两次DFS遍历。

// 示例：通过Kosaraju算法找出强连通分量
void kosarajuSCC(Graph *g) {
    // 1. 执行第一次DFS，记录顶点的完成时间
    // 2. 反转图
    // 3. 按照完成时间降序执行第二次DFS，找出所有强连通分量
}

4.3 最小生成树

最小生成树（MST）是一个加权连通图的子图，它连接了所有顶点并且总权值最小。常用的算法有Kruskal和Prim。

4.3.1 Kruskal算法

Kruskal算法基于边的排序实现MST。主要步骤是将图中的边按权重排序，从小到大依次选择，如果加入一条边不构成环，则将其加入MST中。

// Kruskal算法代码示例
void kruskalMST(Graph *g) {
    // 对所有边按权重排序
    // 依次选择权重最小且不构成环的边
}

4.4 关节点和重连通分量

关节点（Articulation Point）是指在无向图中去掉该顶点后，图的连通性减少的点。可以通过DFS和时间戳的递归算法（Tarjan算法）找到关节点。

#include <limits.h>

void articulationPoints(Graph *g) {
    int visited[MAX_VERTICES] = {0}, parent[MAX_VERTICES], disc[MAX_VERTICES], low[MAX_VERTICES];
    for (int i = 0; i < g->vertex_count; i++) {
        if (!visited[i]) {
            dfsArticulation(g, i, visited, disc, low, parent);
        }
    }
}

void dfsArticulation(Graph *g, int u, int visited[], int disc[], int low[], int parent[]) {
    static int time = 0;
    visited[u] = 1;
    disc[u] = low[u] = ++time;
    int children = 0;

    for (int v = 0; v < g->vertex_count; v++) {
        if (g->vertices[u][v]) {  // 如果u和v之间有边
            if (!visited[v]) {  // v未访问
                parent[v] = u;
                children++;
                dfsArticulation(g, v, visited, disc, low, parent);

                low[u] = (low[u] < low[v]) ? low[u] : low[v];

                if (parent[u] == -1 && children > 1) {
                    printf("关节点: %d\n", u);
                }
                if (parent[u] != -1 && low[v] >= disc[u]) {
                    printf("关节点: %d\n", u);
                }
            } else if (v != parent[u]) {
                low[u] = (low[u] < disc[v]) ? low[u] : disc[v];
            }
        }
    }
}

 5. Dijkstra算法求最短路径

Dijkstra算法用于解决有权图中的单源最短路径问题。该算法通过维护一个优先队列来选择当前距离最小的未访问节点作为下一个访问节点，从而逐步构建从源节点到其他所有节点的最短路径树。

Dijkstra 算法按阶段进行，正像无权最短路径算法一样。在每个阶段，Dijkstra 算法选择一个顶点 v，它在所有 unknown 顶点中具有最小的 dv，同时算法声明从 s 到 v 的最短路径是 known 的。阶段的其余部分由 dw 值的更新工作组成。

Dijkstra算法原理

  1. 初始化：

    • 将源节点的距离设为0，其他所有节点的距离设为无穷大。
    • 创建一个集合来记录已经确定最短路径的节点。

  2. 迭代过程：

    • 从尚未确定最短路径的节点中选择一个距离最小的节点，标记为已确定最短路径。
    • 更新该节点的所有邻居节点的距离。如果通过当前节点到达邻居节点的距离比已知的距离更短，则更新邻居节点的距离和前驱节点。

  3. 终止条件：

    • 当所有节点都已确定最短路径时，算法结束。
#include <stdio.h>
#include <stdlib.h>
#include <limits.h> // 包含 INT_MAX，等同于无穷大

#define NUM_VERTICES 100 // 定义图中的顶点数量

typedef struct {
    int dist;       // 从源顶点的距离
    int known;      // 是否已经确定最短路径
    int path;       // 路径上的前驱顶点
} Vertex;

// 邻接矩阵表示图
int graph[NUM_VERTICES][NUM_VERTICES];

// 初始化图
void initializeGraph(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) {
                graph[i][j] = 0; // 自环距离为0
            } else {
                graph[i][j] = INT_MAX; // 未连接的边距离设为无穷大
            }
        }
    }
}

// 添加边
void addEdge(int u, int v, int weight) {
    graph[u][v] = weight;
    // 如果是无向图，还需要添加反向边
    // graph[v][u] = weight;
}

// Dijkstra算法
void dijkstra(Vertex *vertices, int n, int start) {
    // 初始化所有顶点
    for (int i = 0; i < n; i++) {
        vertices[i].dist = INT_MAX; // 初始距离设为无穷大
        vertices[i].known = 0;      // 初始状态为未知
        vertices[i].path = -1;      // 初始前驱顶点为 -1
    }

    // 设置起始顶点的距离为 0
    vertices[start].dist = 0;

    // 主循环：直到所有顶点都已确定最短路径
    while (1) {
        int minDist = INT_MAX;
        int u = -1;

        // 选择一个距离最小且未确定最短路径的顶点
        for (int i = 0; i < n; i++) {
            if (!vertices[i].known && vertices[i].dist < minDist) {
                minDist = vertices[i].dist;
                u = i;
            }
        }

        // 如果找不到这样的顶点，算法结束
        if (u == -1) {
            break;
        }

        // 标记该顶点为已确定最短路径
        vertices[u].known = 1;

        // 更新该顶点的所有邻居节点的距离
        for (int v = 0; v < n; v++) {
            if (graph[u][v] != INT_MAX && !vertices[v].known) { // 如果存在边且邻居节点未确定最短路径
                int newDist = vertices[u].dist + graph[u][v];
                if (newDist < vertices[v].dist) {
                    vertices[v].dist = newDist; // 更新距离
                    vertices[v].path = u;       // 更新前驱顶点
                }
            }
        }
    }
}

// 打印最短路径
void printShortestPaths(Vertex *vertices, int n, int start) {
    for (int i = 0; i < n; i++) {
        if (i == start) {
            continue; // 跳过起始顶点
        }
        printf("从顶点 %d 到顶点 %d 的最短路径为: ", start, i);
        if (vertices[i].dist == INT_MAX) {
            printf("不可达\n");
        } else {
            printf("%d ", vertices[i].dist);
            int path = i;
            while (path != -1) {
                printf("%d <- ", path);
                path = vertices[path].path;
            }
            printf("\b\b\b\n"); // 删除最后一个 "<-"
        }
    }
}

int main() {
    int n = 5; // 顶点数量
    initializeGraph(n); // 初始化图

    // 添加边
    addEdge(0, 1, 10);
    addEdge(0, 4, 5);
    addEdge(1, 2, 1);
    addEdge(1, 4, 2);
    addEdge(2, 3, 4);
    addEdge(3, 2, 6);
    addEdge(4, 1, 3);
    addEdge(4, 2, 9);
    addEdge(4, 3, 2);

    Vertex vertices[n];
    int startVertex = 0; // 起始顶点

    dijkstra(vertices, n, startVertex); // 计算最短路径

    printShortestPaths(vertices, n, startVertex); // 打印最短路径

    return 0;
}

代码分析

  1. 初始化图：

    • initializeGraph 函数将图初始化为一个邻接矩阵，其中对角线元素为0（表示自环），其他元素为 INT_MAX（表示无穷大）。

  2. 添加边：

    • addEdge 函数用于向图中添加边。对于有向图，只需设置 graph[u][v]；对于无向图，还需设置 graph[v][u]。

  3. Dijkstra算法：

    • dijkstra 函数实现Dijkstra算法。
    • 初始化所有顶点的距离为 INT_MAX，已知状态为 0，前驱顶点为 -1。
    • 将起始顶点的距离设为0。
    • 在主循环中，选择一个距离最小且未确定最短路径的顶点，标记为已确定最短路径。
    • 更新该顶点的所有邻居节点的距离，如果通过当前顶点到达邻居节点的距离更短，则更新邻居节点的距离和前驱顶点。

  4. 打印最短路径：

    • printShortestPaths 函数用于打印从起始顶点到其他所有顶点的最短路径及其路径信息。

运行示例

假设图中有5个顶点，边的权重如下：

  • (0, 1): 10
  • (0, 4): 5
  • (1, 2): 1
  • (1, 4): 2
  • (2, 3): 4
  • (3, 2): 6
  • (4, 1): 3
  • (4, 2): 9
  • (4, 3): 2

运行程序后，输出如下：

从顶点 0 到顶点 1 的最短路径为: 8 1 <- 4 <- 0
从顶点 0 到顶点 2 的最短路径为: 9 2 <- 1 <- 4 <- 0
从顶点 0 到顶点 3 的最短路径为: 7 3 <- 4 <- 0
从顶点 0 到顶点 4 的最短路径为: 5 4 <- 0

别忘了请点个赞+收藏+关注支持一下博主喵！！！

标签：讲述,int,graph,VERTICES,++,MAX,顶点,数据结构,语言版
From： https://blog.csdn.net/Asuna666w/article/details/143695390

相关文章

  • 【初阶数据结构与算法】线性表之链表的分类以及双链表的定义与实现
    文章目录一、链表的分类二、双链表的实现1.双链表结构的定义2.双链表的初始化和销毁初始化函数1初始化函数2销毁函数3.双链表的打印以及节点的申请打印函数节点的申请4.双链表的头插和尾插头插函数尾插函数5.双链表的查找和判空查找函数判空函数6.双链表的头删和尾......
  • 数据结构——快速排序
    目录一、排序思想二、代码实现（一）hoare版1、原版——固定选key2、随机选key、三数取中选key（二）挖坑法（三）前后指针法（四）小区间优化（五）非递归写法一、排序思想任取待排序元素序列中的某元素作为基准值，按照该基准值将待排序集合分割成两子序列，左子序列中所有元素均小于基......
  • C++数据结构实验题目解析
    目录题目:考点分析：难点1：就地逆置步骤：代码实现：核心代码详细解释：难点2：①非递减链表，②删除相同元素代码详解①：代码详解②：完整代码：大家好，今天我就来给大家分析一下我上期分享的题目的详细解析，编程的能力都是逐步提升的，但是思维的锻炼可以提前进行，这样有助于我们以后自......
  • 郝玩的数据结构1——单调栈，单调队列
    栈和队列是很郝咏的Stl，那么，我们手搓——用数组模拟故事背景：辣鸡老o在学单调栈&单调队列——我栈top为栈顶，易得出出栈即top--，入栈++top=(ovo)......——完全不会讲，那么上马：点击查看代码#include<bits/stdc++.h>usingnamespacestd;constintN=114514;intstk[N],top=0;......
  • 力扣 170. 两数之和 III - 数据结构设计 two-sum III
    数组系列力扣数据结构之数组-00-概览力扣.53最大子数组和maximum-subarray力扣.128最长连续序列longest-consecutive-sequence力扣.1两数之和N种解法two-sum力扣.167两数之和IItwo-sum-ii力扣.170两数之和IIItwo-sum-iii力扣.653两数之和IVtwo-sum-IV力......
  • C++ 数据结构详解
    目录C++数据结构详解引言1.数组(Array)示例代码2.向量(Vector)示例代码3.链表(List)示例代码4.栈(Stack)示例代码5.队列(Queue)示例代码6.集合(Set)示例代码7.映射(Map)示例代码C++数据结构详解引言数据结构是计算机科学中的一个重要概念......
  • python中常见的8种数据结构之一字典及其使用方法
    字典（Dictionary）是Python中常见的数据结构之一，用于存储一组配对的键(key)和值(value)。字典是可变的、无序的，并且键必须是唯一的。创建字典的方法有两种：使用花括号{}或使用内置的dict()函数。下面是一些常见的字典操作和方法：1.创建字典：my_dict={'key1':'value1','key2'......
  • 数据结构 ——— 链式二叉树oj题：对称二叉树
    目录题目要求手搓一个对称二叉树代码实现 题目要求给你一个二叉树的根节点 root ，检查它是否轴对称手搓一个对称二叉树代码演示：//数据类型typedefintBTDataType;//二叉树节点的结构typedefstructBinaryTreeNode{ BTDataTypedata;//每个节点的数据......
  • 数据结构[2016]
    一、设有二维数组A[6][8],每个元素占6个字节存储，实现存放，A[0][0]的起始地址为1000,计算：(10分)(1)数组最后一个元素A[5][7]的起始地址；(2)按行优先存放时，元素A[1][4]的起始地址；(3)按列优先存放时，元素A[4][7]的起始地址。二、若有一棵二叉树，左右子树均有三个结点，其左子树的前......
  • 数据结构大作业-计算机实践课程
    目录源码数据结构报告系统功能框图及说明开发环境系统主要功能运行效果截图创建一条含整数节点的无序链表链表节点的输出链表节点的升序排序分别计算链表中奇数和偶数点之和并输出释放链表源码#include<iostream>#include<string>usingnamespacestd;ty......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99