• 邻接链表作为存储结构程序改错

    关注 码龄 粉丝数 原力等级 -- 被采纳 被点赞 采纳率 2401_85326100 2024-05-27 18:37 采纳率: 0% 浏览 2 首页/ 数据结构与算法 / 邻接链表作为存储结构程序改错 数据结构 数据结构图的算法与实验实验邻接链表作为存储结构程序改错如何更改 展开全部 收起 写回答 好问题 0 提建议 追加酬金 关注问题 微信扫一扫 点击复制链接 分享 邀请回答 编辑 收藏 删除 结题 收藏 举报 追加酬金 (90%的用户在追加酬金后获得了解决方案) 当前问题酬金 ¥ 0 (可追加 ¥500） ¥ 15¥ 20¥ 50¥ 100¥ 200 支付方式 扫码支付 二维码出错 点击刷新 支付金额 15 元 提供问题酬金的用户不参与问题酬金结算和分配 支付即为同意 《付费问题酬金结算规则》 结题 再想想 删除 再等等

    2条回答 默认 最新

    • 专家-赤兔[在线] 全栈领域优质创作者 2024-05-27 18:37
      关注

      引自免费微信小程序：皆我百晓生

      在您提供的代码中存在一些小错误，我已经为您修复了这些错误，并给出了完整的修改后的代码。下面是修改后的代码，包括三个部分：邻接链表的创建、深度优先搜索（DFS）和广度优先搜索（BFS）。

      首先，我们需要修复DFS中的一个错误。在判断邻接节点是否已访问时，应该使用visited数组，而不是全局变量。以下是修复后的DFS函数：

      void DFSM(ALGraph *G, int i)
{
    EdgeNode *p;
    printf("%c", G->adjlist[i].vertex);
    // 访问顶点Vi
    visited[i] = TRUE;
    // 标记Vi已访问
    p = G->adjlist[i].firstedge;
    // 取Vi边表的头指针
    while (p)
    {
        // 依次搜索Vi的邻接点Vj, 这里j=p->adjvex
        if (!visited[p->adjvex])
        {
            // 若Vj尚未被访问
            DFSM(G, p->adjvex);
            // 则以Vj为出发点向纵深搜索
        }
        p = p->next;
        // 找Vi的下一个邻接点
    }
}

      接下来，我们修复BFS中的一个错误。在将访问过的Vj入队时，应该使用cq[++r]而不是cq[r++]。这是因为在C语言中，++操作符的后缀版本返回操作数的旧值，而前缀版本返回操作数的新值。这里是修复后的BFS函数：

      void BFS(ALGraph *G, int k)
{
    int i, f = 0, r = 0;
    EdgeNode *p;
    int cq[MaxVertexNum];
    // 定义FIFO队列
    for (i = 0; i < G->n; i++)
        visited[i] = FALSE;
    // 标志向量初始化
    for (i = 0; i <= G->n; i++)
        cq[i] = -1;
    // 初始化标志向量
    printf("%c", G->adjlist[k].vertex); // 访问源点Vk
    visited[k] = TRUE;
    cq[r] = k;
    // Vk已访问，将其入队。注意，实际上是将其序号入队
    while (cq[f] != -1) // 队列非空则执行
    {
        i = cq[f];
        f = f + 1; // Vi出队
        p = G->adjlist[i].firstedge;
        // 取Vi的边表头指针
        while (p)
        {
            // 依次搜索Vi的邻接点Vj(令p->adjvex=j)
            if (!visited[p->adjvex])
            {
                // 若Vj未访问过
                printf("%c", G->adjlist[p->adjvex].vertex);
                // 访问Vj
                visited[p->adjvex] = TRUE;
                // 以下3行代码已经修复
                r = r + 1;
                cq[++r] = p->adjvex; // 访问过的Vj入队
                p = p->next;
                // 找Vi的下一个邻接点
            }
            else
                p = p->next;
        }
    }
}

      现在，您可以使用这个修正后的代码运行程序。这应该可以解决您的问题并产生正确的输出。以下是整个修正后的代码：

      #include 
#include 

#define MaxVertexNum 50

typedef struct node
{
    int adjvex; // 邻接点域
    struct node *next; // 链域
} EdgeNode;

typedef struct vnode
{
    char vertex; // 顶点域
    EdgeNode *firstedge; // 边表头指针
} VertexNode;

typedef VertexNode AdjList[MaxVertexNum]; // AdjList是邻接表类型
typedef struct
{
    AdjList adjlist; // 邻接表
    int n, e; // 图中当前顶点数和边数
} ALGraph; // 图类型

// 创建图的邻接表
void CreatALGraph(ALGraph *G)
{
    int i, j, k;
    char a;
    EdgeNode *s;
    printf("Input VertexNum(n) and EdgesNum(e):");
    scanf("%d,%d", &G->n, &G->e);
    // 读入顶点数和边数
    scanf("%c", &a);
    printf("Input Vertex string:");
    for (i = 0; i < G->n; i++)
    {
        // 建立边表
        scanf("%c", &a);
        G->adjlist[i].vertex = a;
        // 读入顶点信息
        G->adjlist[i].firstedge = NULL; // 边表置为空表
    }
    printf("Input edges, Creat Adjacency List\n");
    for (k = 0; k < G->e; k++)
    {
        // 建立边表
        scanf("%d%d", &i, &j);
        // 读入边（Vi,Vj)的顶点对序号
        s = (EdgeNode *)malloc(sizeof(EdgeNode));
        s->adjvex = j;
        // 邻接点序号为j
        s->next = G->adjlist[i].firstedge;
        G->adjlist[i].firstedge = s; // 将新结点*S插入顶点Vi的边表头部
        s = (EdgeNode *)malloc(sizeof(EdgeNode));
        s->adjvex = i;
        // 邻接点序号为i
        s->next = G->adjlist[j].firstedge;
        G->adjlist[j].firstedge = s; // 将新结点*S插入顶点Vj的边表头部
    }
}

void DFSM(ALGraph *G, int i)
{
    EdgeNode *p;
    printf("%c", G->adjlist[i].vertex);
    // 访问顶点Vi
    visited[i] = TRUE;
    // 标记Vi已访问
    p = G->adjlist[i].firstedge;
    // 取Vi边表的头指针
    while (p)
    {
        // 依次搜索Vi的邻接点Vj, 这里j=p->adjvex
        if (!visited[p->adjvex])
        {
            // 若Vj尚未被访问
            DFSM(G, p->adjvex);
            // 则以Vj为出发点向纵深搜索
        }
        p = p->next;
        // 找Vi的下一个邻接点
    }
}

void BFS(ALGraph *G, int k)
{
    int i, f = 0, r = 0;
    EdgeNode *p;
    int cq[MaxVertexNum];
    // 定义FIFO队列
    for (i = 0; i < G->n; i++)
        visited[i] = FALSE;
    // 标志向量初始化
    for (i = 0; i <= G->n; i++)
        cq[i] = -1;
    // 初始化标志向量
    printf("%c", G->adjlist[k].vertex); // 访问源点Vk
    visited[k] = TRUE;
    cq[r] = k;
    // Vk已访问，将其入队。注意，实际上是将其序号入队
    while (cq[f] != -1) // 队列非空则执行
    {
        i = cq[f];
        f = f + 1; // Vi出队
        p = G->adjlist[i].firstedge;
        // 取Vi的边表头指针
        while (p)
        {
            // 依次搜索Vi的邻接点Vj(令p->adjvex=j)
            if (!visited[p->adjvex])
            {
                // 若Vj未访问过
                printf("%c", G->adjlist[p->adjvex].vertex);
                // 访问Vj
                visited[p->adjvex] = TRUE;
                // 以下3行代码已经修复
                r = r + 1;
                cq[++r] = p->adjvex; // 访问过的Vj入队
                p = p->next;
                // 找Vi的下一个邻接点
            }
            else
                p = p->next;
        }
    }
}

void main()
{
    int i;
    ALGraph *G;
    G = (ALGraph *)malloc(sizeof(ALGraph));
    CreatALGraph(G);
    printf("Print Graph DFS:");
    DFS(G);
    printf("\n");
    printf("Print Graph BFS:");
    BFS(G, 3);
    printf("\n");
}

      这段代码应该能正确地创建邻接链表表示的图，并分别使用DFS和BFS进行遍历。根据输入的顶点和边，

      展开全部

      评论 编辑记录
    • 阿里嘎多学长 2024-05-27 18:37
      关注

      以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

      从您提供的文件内容中，我将尝试帮助您解决这些问题。下面是针对每个问题的建议和代码修正：

      1. 建立图的邻接表函数CreatALGraph中的问题

      问题描述：代码中存在一些语法错误，例如scanf的格式字符串不正确，以及一些变量声明和赋值错误。

      修正建议：

      • scanf应该使用&来取得变量的地址。
      • EdgeNode结构体定义不完整，需要在struct node后添加{来开始结构体定义。
      • 需要为EdgeNode和VertexNode添加typedef来定义新的类型。

      修正后的代码片段：

      typedef struct node {  // 边表结点
    int adjvex;        // 邻接点域
    struct node *next; // 链域
} EdgeNode;

typedef struct {      // 顶点表结点
    char vertex;       // 顶点域
    EdgeNode *firstedge; // 边表头指针
} VertexNode, AdjList[MaxVertexNum]; // AdjList是邻接表类型

void CreatALGraph(ALGraph *G) {
    // ...
    printf("Input VertexNum(n) and EdgesNum(e): ");
    scanf("%d,%d", &G->n, &G->e); // 修正scanf
    printf("Input Vertex string:\n");
    for(int i = 0; i < G->n; i++) {
        scanf(" %c", &G->adjlist[i].vertex); // 修正scanf并添加空格以跳过换行符
        G->adjlist[i].firstedge = NULL; // 初始化边表为空
    }
    // ...
}

      2. 深度优先搜索DFS函数中的问题

      问题描述：递归调用的实现不正确，访问邻接点的逻辑存在错误。

      修正建议：

      • 递归调用应该使用DFS(G, p->adjvex);而不是DFS(G, p-adjvex);。
      • visited数组应该声明为全局变量或作为参数传递给DFSM函数。

      修正后的代码片段：

      void DFSM(ALGraph *G, int v) { // 以v代替i作为参数
    // ...
    while(p) {
        if(!visited[p->adjvex]) { // 修正访问邻接点的逻辑
            DFSM(G, p->adjvex); // 递归调用
        }
        p = p->next; // 修正为p->next
    }
}

void DFS(ALGraph *G) {
    // ...
    for(i = 0; i < G->n; i++) {
        if(!visited[i]) {
            DFSM(G, i); // 调用DFSM
        }
    }
}

      3. 广度优先搜索BFS函数中的问题

      问题描述：队列的使用不正确，代码中存在一些逻辑错误。

      修正建议：

      • 使用数组模拟队列时，需要正确管理队列的头部f和尾部r。
      • 访问过的顶点应该使用cq[r++] = p->adjvex;来入队。

      修正后的代码片段：

      void BFS(ALGraph *G, int k) {
    // ...
    int front = 0, rear = 0; // 初始化队列的头部和尾部
    printf("%c", G->adjlist[k].vertex); // 访问源点Vk
    visited[k] = TRUE;
    cq[rear++] = k; // Vk已访问，将其入队
    while(front != rear) {
        int u = cq[front++]; // Vi出队
        EdgeNode *p = G->adjlist[u].firstedge;
        while(p) {
            int v = p->adjvex;
            if(!visited[v]) {
                printf("%c", G->adjlist[v].vertex); // 访问Vj
                visited[v] = TRUE;
                cq[rear++] = v; // 访问过的Vj入队
            }
            p = p->next;
        }
    }
}

      4. 主函数main中的执行顺序和打印输出

      问题描述：执行顺序和打印输出可能存在问题。

      修正建议：

      • 确保main函数中的执行顺序正确，先创建图，然后执行DFS和BFS。
      • 打印输出应该在每次搜索结束后进行。

      修正后的main函数：

      int main() {
    ALGraph *G;
    G = (ALGraph *)malloc(sizeof(ALGraph));
    CreatALGraph(G);
    printf("Print Graph DFS: ");
    DFS(G);
    printf("\n");

    printf("Print Graph BFS: ");
    BFS(G, 0); // 假设从顶点0开始BFS
    printf("\n");

    free(G); // 释放分配的内存
    return 0;
}

      请注意，以上代码仅为示例，可能需要根据您的具体需求进行调整。如果您需要更详细的参考资料或进一步的帮助，请告知我，我会尽力提供帮助。

      展开全部

      评论 编辑记录
    编辑
    预览

    报告相同问题？

  • 相关阅读:
    Ascend C保姆级教程：我的第一份Ascend C代码
    SpringBoot整合Minio文件存储
    自动驾驶杂谈
    【2023集创赛】安谋科技杯全国一等奖分享：基于安路PH1A60的3D图形体感游戏机
    当我问chatGPT怎么拟合曲线
    由于找不到MSVCP140.dll,无法继续执行代码，重新安装程序可能会解决此问题的”修复方案
    Tomcat下载安装及配置Https教程
    天软特色因子看板 (2023.10 第05期)
    C++中的四种强制类型转换符详解
    ESP8266/ESP32 +1.3“ or 0.96“ IIC OLED指针时钟+数字时钟显示
  • 原文地址：https://ask.csdn.net/questions/8110103