设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 技术交流 › C\C++交流 › 有没有大佬帮忙看看我的程序哪里出错了
12下一页
返回列表 发新帖
查看: 1237|回复: 28

[已解决]有没有大佬帮忙看看我的程序哪里出错了

[复制链接]
1613551
发表于 2023-12-11 19:40:34 | 显示全部楼层 |阅读模式
60鱼币

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef int ElemType;
typedef struct graph
{
    ElemType *v;  // 通过入栈的方式判断结点是否有被遍历
    ElemType **p; // 邻接表矩阵
    ElemType *stack;
} graph;
void Initialization(graph *ch, ElemType n)
{
    ch->p = (ElemType **)malloc(sizeof(ElemType *) * pow((n + 1), 2));
    for (int i = 1; i <= n; i++)
    {
        ch->p[i] = (ElemType *)malloc(sizeof(ElemType) * (n + 1));
    }
    ch->v = (ElemType *)malloc(sizeof(ElemType) * (n + 1));
    ch->stack = (ElemType *)malloc(sizeof(ElemType) * n);
}
void create(graph *ch, ElemType n)
{
    printf("请输入邻接表矩阵\n");
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            scanf("%d", &(ch->p[i][j]));
        }
    }
}
void visit(graph *ch, ElemType nn, ElemType n)
{
    int node = nn, j = 1, top = 0;
    ch->v[nn] = 1;
    ch->stack[top++] = nn;
    printf("%d", nn);
    while (1)
    {
        if (ch->p[node][j] == 1 && ch->v[j] == 0)
        {
            ch->v[j] = 1;
            ch->stack[top++] = j;
            printf("->%d", j);
            node = j;
            j = 1;
        };
        if (j == n + 1)
        {
            if (ch->stack[top] == nn)
            {
                break;
            }
            ch->stack[top--] = 0;
            node = ch->stack[top];
            j = 1;
        }
        j++;
    }
}
int main(void)
{
    int n, nn;
    graph p;
    do
    {

        printf("请输入结点数：");
        scanf("%d", &n);
        if (n <= 0)
        {
            printf("结点数不得小于等于0！\n");
        }
    } while (n <= 0);
    Initialization(&p, n);
    create(&p, n);
    do
    {

        printf("请选择从哪个结点开始遍历:");
        scanf("%d", &nn);
        if (nn < 0 || nn > n)
        {
            printf("您的输入不正确！\n");
        }
    } while (nn < 0 || nn > n);
    visit(&p, nn, n);
    system("pause");
    return 0;
}
最佳答案
月排行榜 / 总排行榜
人造人
2023-12-11 19:40:35
嗯，对于图来说，确实需要一个vector来标记已经访问过的节点，不然会死循环，因为有多条路径
改成这样，非递归的版本
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

typedef int ElemType;

typedef struct {
    ElemType e;
    size_t status;
} stack_elem_t;

typedef struct {
    stack_elem_t *data;
    size_t size, top;
} stack_t;

stack_t *stack_init(void) {
    stack_t *stack = malloc(sizeof(*stack));
    stack->data = NULL;
    stack->size = stack->top = 0;
    return stack;
}

void stack_deinit(stack_t *stack) {
    free(stack->data);
    free(stack);
}

size_t stack_size(const stack_t *stack) {
    return stack->top;
}

bool stack_empty(const stack_t *stack) {
    return stack_size(stack) == 0;
}

void stack_push(stack_t *stack, stack_elem_t e) {
    if(stack->top == stack->size)
        stack->data = realloc(stack->data, sizeof(stack_elem_t) * (stack->size += 10));
    stack->data[stack->top++] = e;
}

void stack_pop(stack_t *stack) {
    if(stack_empty(stack)) return;
    --stack->top;
}

stack_elem_t stack_top(const stack_t *stack) {
    if(stack_empty(stack)) abort();
    return stack->data[stack->top - 1];
}

typedef ElemType vector_elem_t;

typedef struct {
    vector_elem_t *data;
    size_t size;
} vector_t;

vector_t *vector_init(void) {
    vector_t *vector = malloc(sizeof(*vector));
    vector->data = NULL;
    vector->size = 0;
    return vector;
}

void vector_deinit(vector_t *vector) {
    free(vector->data);
    free(vector);
}

size_t vector_size(const vector_t *vector) {
    return vector->size;
}

size_t vector_empty(const vector_t *vector) {
    return vector_size(vector) == 0;
}

void vector_set(vector_t *vector, size_t index, vector_elem_t e) {
    if(index >= vector->size)
        vector->data = realloc(vector->data, sizeof(vector_elem_t) * (vector->size = index + 1));
    vector->data[index] = e;
}

vector_elem_t vector_get(const vector_t *vector, size_t index) {
    if(index >= vector->size) abort();
    return vector->data[index];
}

void vector_append(vector_t *vector, vector_elem_t e) {
    vector_set(vector, vector_size(vector), e);
}

bool vector_find(const vector_t *vector, vector_elem_t e) {
    for(size_t i = 0; i < vector_size(vector); ++i) {
        if(vector_get(vector, i) == e) return true;
    }
    return false;
}

typedef struct {
    ElemType **p;
    size_t n;
} graph;

void Initialization(graph *ch, size_t n) {
    ch->p = malloc(sizeof(ElemType *) * n);
    for(int i = 0; i < n; i++) {
        ch->p[i] = malloc(sizeof(ElemType) * n);
    }
    ch->n = n;
}

void graph_deinit(graph *graph) {
    for(size_t i = 0; i < graph->n; ++i) free(graph->p[i]);
    free(graph->p);
}

void create(graph *ch) {
    printf("请输入邻接表矩阵\n");
    for(int i = 0; i < ch->n; i++) {
        for(int j = 0; j < ch->n; j++) {
            scanf("%d", &ch->p[i][j]);
        }
    }
}

void visit(graph *ch, ElemType n) {
    stack_t *stack = stack_init();
    vector_t *vector = vector_init();
    stack_elem_t se = {n, 0};
    stack_push(stack, se);
    while(!stack_empty(stack)) {
        se = stack_top(stack);
        switch(se.status) {
            case 0:
                printf("%d\n", se.e);
                stack_pop(stack);
                stack_push(stack, (stack_elem_t){se.e, 1});
                vector_append(vector, se.e);
                for(size_t i = 0; i < ch->n; ++i) {
                    if(ch->p[se.e][i] && !vector_find(vector, i)) stack_push(stack, (stack_elem_t){i, 0});
                }
                break;
            case 1:
                stack_pop(stack);
        }
    }
    vector_deinit(vector);
    stack_deinit(stack);
}

int main(void) {
    unsigned int n, nn;
    graph p;
    printf("请输入结点数：");
    scanf("%u", &n);
    Initialization(&p, n);
    create(&p);
    do {
        printf("请选择从哪个结点开始遍历:");
        scanf("%d", &nn);
        if(nn > n) printf("您的输入不正确！\n");
    } while(nn > n);
    visit(&p, nn - 1);
    graph_deinit(&p);
    return 0;
}

最佳答案

人造人

查看完整内容

嗯，对于图来说，确实需要一个vector来标记已经访问过的节点，不然会死循环，因为有多条路径 改成这样，非递归的版本
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

人造人
发表于 2023-12-11 19:40:35 | 显示全部楼层    本楼为最佳答案   
嗯，对于图来说，确实需要一个vector来标记已经访问过的节点，不然会死循环，因为有多条路径
改成这样，非递归的版本
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

typedef int ElemType;

typedef struct {
    ElemType e;
    size_t status;
} stack_elem_t;

typedef struct {
    stack_elem_t *data;
    size_t size, top;
} stack_t;

stack_t *stack_init(void) {
    stack_t *stack = malloc(sizeof(*stack));
    stack->data = NULL;
    stack->size = stack->top = 0;
    return stack;
}

void stack_deinit(stack_t *stack) {
    free(stack->data);
    free(stack);
}

size_t stack_size(const stack_t *stack) {
    return stack->top;
}

bool stack_empty(const stack_t *stack) {
    return stack_size(stack) == 0;
}

void stack_push(stack_t *stack, stack_elem_t e) {
    if(stack->top == stack->size)
        stack->data = realloc(stack->data, sizeof(stack_elem_t) * (stack->size += 10));
    stack->data[stack->top++] = e;
}

void stack_pop(stack_t *stack) {
    if(stack_empty(stack)) return;
    --stack->top;
}

stack_elem_t stack_top(const stack_t *stack) {
    if(stack_empty(stack)) abort();
    return stack->data[stack->top - 1];
}

typedef ElemType vector_elem_t;

typedef struct {
    vector_elem_t *data;
    size_t size;
} vector_t;

vector_t *vector_init(void) {
    vector_t *vector = malloc(sizeof(*vector));
    vector->data = NULL;
    vector->size = 0;
    return vector;
}

void vector_deinit(vector_t *vector) {
    free(vector->data);
    free(vector);
}

size_t vector_size(const vector_t *vector) {
    return vector->size;
}

size_t vector_empty(const vector_t *vector) {
    return vector_size(vector) == 0;
}

void vector_set(vector_t *vector, size_t index, vector_elem_t e) {
    if(index >= vector->size)
        vector->data = realloc(vector->data, sizeof(vector_elem_t) * (vector->size = index + 1));
    vector->data[index] = e;
}

vector_elem_t vector_get(const vector_t *vector, size_t index) {
    if(index >= vector->size) abort();
    return vector->data[index];
}

void vector_append(vector_t *vector, vector_elem_t e) {
    vector_set(vector, vector_size(vector), e);
}

bool vector_find(const vector_t *vector, vector_elem_t e) {
    for(size_t i = 0; i < vector_size(vector); ++i) {
        if(vector_get(vector, i) == e) return true;
    }
    return false;
}

typedef struct {
    ElemType **p;
    size_t n;
} graph;

void Initialization(graph *ch, size_t n) {
    ch->p = malloc(sizeof(ElemType *) * n);
    for(int i = 0; i < n; i++) {
        ch->p[i] = malloc(sizeof(ElemType) * n);
    }
    ch->n = n;
}

void graph_deinit(graph *graph) {
    for(size_t i = 0; i < graph->n; ++i) free(graph->p[i]);
    free(graph->p);
}

void create(graph *ch) {
    printf("请输入邻接表矩阵\n");
    for(int i = 0; i < ch->n; i++) {
        for(int j = 0; j < ch->n; j++) {
            scanf("%d", &ch->p[i][j]);
        }
    }
}

void visit(graph *ch, ElemType n) {
    stack_t *stack = stack_init();
    vector_t *vector = vector_init();
    stack_elem_t se = {n, 0};
    stack_push(stack, se);
    while(!stack_empty(stack)) {
        se = stack_top(stack);
        switch(se.status) {
            case 0:
                printf("%d\n", se.e);
                stack_pop(stack);
                stack_push(stack, (stack_elem_t){se.e, 1});
                vector_append(vector, se.e);
                for(size_t i = 0; i < ch->n; ++i) {
                    if(ch->p[se.e][i] && !vector_find(vector, i)) stack_push(stack, (stack_elem_t){i, 0});
                }
                break;
            case 1:
                stack_pop(stack);
        }
    }
    vector_deinit(vector);
    stack_deinit(stack);
}

int main(void) {
    unsigned int n, nn;
    graph p;
    printf("请输入结点数：");
    scanf("%u", &n);
    Initialization(&p, n);
    create(&p);
    do {
        printf("请选择从哪个结点开始遍历:");
        scanf("%d", &nn);
        if(nn > n) printf("您的输入不正确！\n");
    } while(nn > n);
    visit(&p, nn - 1);
    graph_deinit(&p);
    return 0;
}
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

1613551
 楼主| 发表于 2023-12-11 19:41:08 | 显示全部楼层
不知道为什么无法实现遍历
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

1613551
 楼主| 发表于 2023-12-11 19:46:48 | 显示全部楼层
只能输出第一个结点
1702295170028.png
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

人造人
发表于 2023-12-11 23:51:50 | 显示全部楼层 
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

typedef int ElemType;

typedef struct {
    ElemType **p; // 邻接表矩阵
    size_t n;
    bool *flag;
    /*
    ElemType *v;  // 通过入栈的方式判断结点是否有被遍历
    ElemType *stack;
    */
} graph;

void Initialization(graph *ch, size_t n) {
    ch->p = malloc(sizeof(ElemType *) * n);
    // 要习惯了从0开始
    for(int i = 0; i < n; i++) {
        ch->p[i] = malloc(sizeof(ElemType) * n);
    }
    ch->flag = malloc(sizeof(bool) * n);
    memset(ch->flag, false, sizeof(bool) * n);
    ch->n = n;

    /*
    ch->v = (ElemType *)malloc(sizeof(ElemType) * (n + 1));
    ch->stack = (ElemType *)malloc(sizeof(ElemType) * n);
    */
}

// 释放内存的函数呢？
void graph_deinit(graph *graph) {
    for(size_t i = 0; i < graph->n; ++i) free(graph->p[i]);
    free(graph->p);
    free(graph->flag);
}

void create(graph *ch) {
    printf("请输入邻接表矩阵\n");
    for(int i = 0; i < ch->n; i++) {
        for(int j = 0; j < ch->n; j++) {
            scanf("%d", &ch->p[i][j]);
        }
    }
}

void visit(graph *ch, ElemType n) {
    if(ch->flag[n]) return;
    ch->flag[n] = true;
    printf("visit: %d\n", n);
    for(size_t i = 0; i < ch->n; ++i) {
        if(ch->p[n][i]) visit(ch, i);
    }
    ch->flag[n] = false;

    // 没看懂
    /*
    int node = n - 1, j = 1, top = 0;
    ch->v[n] = 1;
    ch->stack[top++] = n;
    printf("%zu", n);
    while(1) {
        if(ch->p[node][j] == 1 && ch->v[j] == 0) {
            ch->v[j] = 1;
            ch->stack[top++] = j;
            printf("->%d", j);
            node = j;
            j = 1;
        };
        if(j == ch->n + 1) {
            if(ch->stack[top] == n) {
                break;
            }
            ch->stack[top--] = 0;
            node = ch->stack[top];
            j = 1;
        }
        j++;
    }
    */
}

int main(void) {
    unsigned int n, nn;
    graph p;
    printf("请输入结点数：");
    scanf("%u", &n);
    Initialization(&p, n);
    create(&p);
    do {
        printf("请选择从哪个结点开始遍历:");
        scanf("%d", &nn);
        if(nn > n) printf("您的输入不正确！\n");
    } while(nn > n);
    visit(&p, nn - 1);
    graph_deinit(&p);
    return 0;
}

评分

参与人数 1荣誉 +5 贡献 +3 收起 理由
1613551 + 5 + 3

查看全部评分

想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

人造人
发表于 2023-12-11 23:59:40 | 显示全部楼层
本帖最后由 人造人 于 2023-12-12 00:37 编辑

递归返回后会清除当前节点的访问标志，如果有多条路径的话，感觉会出问题，还是这样吧
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

typedef int ElemType;

typedef struct {
    ElemType **p; // 邻接表矩阵
    size_t n;
    bool *flag;
} graph;

void Initialization(graph *ch, size_t n) {
    ch->p = malloc(sizeof(ElemType *) * n);
    for(int i = 0; i < n; i++) {
        ch->p[i] = malloc(sizeof(ElemType) * n);
    }
    ch->flag = malloc(sizeof(bool) * n);
    ch->n = n;
}

void graph_deinit(graph *graph) {
    for(size_t i = 0; i < graph->n; ++i) free(graph->p[i]);
    free(graph->p);
    free(graph->flag);
}

void create(graph *ch) {
    printf("请输入邻接表矩阵\n");
    for(int i = 0; i < ch->n; i++) {
        for(int j = 0; j < ch->n; j++) {
            scanf("%d", &ch->p[i][j]);
        }
    }
}

void visit_sub(graph *ch, ElemType n) {
    if(ch->flag[n]) return;
    ch->flag[n] = true;
    printf("visit: %d\n", n);
    for(size_t i = 0; i < ch->n; ++i) {
        if(ch->p[n][i]) visit_sub(ch, i);
    }
}

void visit(graph *ch, ElemType n) {
    memset(ch->flag, false, sizeof(bool) * ch->n);
    visit_sub(ch, n);
}

int main(void) {
    unsigned int n, nn;
    graph p;
    printf("请输入结点数：");
    scanf("%u", &n);
    Initialization(&p, n);
    create(&p);
    do {
        printf("请选择从哪个结点开始遍历:");
        scanf("%d", &nn);
        if(nn > n) printf("您的输入不正确！\n");
    } while(nn > n);
    visit(&p, nn - 1);
    graph_deinit(&p);
    return 0;
}

评分

参与人数 1荣誉 +5 贡献 +3 收起 理由
1613551 + 5 + 3

查看全部评分

想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

1613551
 楼主| 发表于 2023-12-12 14:44:38 | 显示全部楼层
人造人 发表于 2023-12-11 23:59
递归返回后会清除当前节点的访问标志，如果有多条路径的话，感觉会出问题，还是这样吧

不好意思，还没时间仔细看，但是我昨天其实自己弄出来一个了
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct graph
{
    ElemType *v;
    ElemType **p;
    ElemType *stack;
} graph;
void Initialization(graph *ch, ElemType n)
{
    ch->p = (ElemType **)malloc(sizeof(ElemType *) * (n + 1));
    for (int i = 0; i <= n; i++)
    {
        ch->p[i] = (ElemType *)malloc(sizeof(ElemType) * (n + 1));
    }
    ch->v = (ElemType *)malloc(sizeof(ElemType) * (n + 1));
    ch->stack = (ElemType *)malloc(sizeof(ElemType) * (n + 1));
    for (int i = 0; i <= n; i++)
    {
        ch->v[i] = 0;
        ch->stack[i] = 0;
    }
}
void create(graph *ch, ElemType n)
{
    printf("请输入邻接表矩阵\n");
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            scanf("%d", &(ch->p[i][j]));
        }
    }
}
void visit(graph *ch, ElemType nn, ElemType n)
{
    int node = nn, j = 1, top = 0;
    ch->v[nn] = 1;
    ch->stack[top++] = nn;
    printf("%d", nn);
    while (1)
    {
        if (ch->p[node][j] == 1 && ch->v[j] == 0)
        {
            ch->v[j] = 1;
            ch->stack[top++] = j;
            printf("->%d", j);
            node = j;
            j = 1;
        }
        if (j > n)
        {
            if (nn == ch->stack[top])
            {
                break;
            }
            ch->stack[top--] = 0;
            node = ch->stack[top];
            j = 1;
        }
        j++;
    }
}
int main(void)
{
    int n, nn;
    graph p;
    do
    {
        printf("请输入结点数：");
        scanf("%d", &n);

        if (n <= 0)
        {
            printf("结点数不得小于等于0！\n");
        }
    } while (n <= 0);
    Initialization(&p, n);
    create(&p, n);
    do
    {
        printf("请选择从哪个结点开始遍历:");
        scanf("%d", &nn);

        if (nn < 1 || nn > n)
        {
            printf("您的输入不正确！\n");
        }
    } while (nn < 1 || nn > n);
    visit(&p, nn, n);
    system("pause");
    for (int i = 0; i <= n; i++)
    {
        free(p.p[i]);
    }
    free(p.p);
    free(p.v);
    free(p.stack);
    return 0;
}
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

人造人
发表于 2023-12-12 17:46:43 | 显示全部楼层
1613551 发表于 2023-12-12 14:44
不好意思，还没时间仔细看，但是我昨天其实自己弄出来一个了

没看懂visit函数
说一下思路
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

1613551
 楼主| 发表于 2023-12-12 20:53:49 | 显示全部楼层
人造人 发表于 2023-12-12 17:46
没看懂visit函数
说一下思路

那个有点问题，我是模仿这位老哥的
https://fishc.com.cn/thread-206094-1-1.html
1702385559481.png
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

1613551
 楼主| 发表于 2023-12-12 20:54:32 | 显示全部楼层
人造人 发表于 2023-12-12 17:46
没看懂visit函数
说一下思路

我没改出来他那种效果，于是我自己又重新写了一个
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct Queue
{
    ElemType data;
    Queue *Qnode;
} Queue;
typedef struct graph
{
    ElemType *v;
    ElemType **p;
    ElemType *stack;
    Queue *Qhead;
    Queue *Qtail;
} graph;
void Initialization(graph *ch, ElemType n);
void create(graph *ch, ElemType n);
void enqueue(graph *ch, int nn);
int outqueue(graph *ch);
void widevisit(graph *ch, ElemType nn, ElemType n);
void depthvisit(graph *ch, ElemType nn, ElemType n);
void input(int *n, int *nn, int *option);
void freeG(graph *ch, int n);
int main(void)
{
    int n, nn, option;
    graph p;
    input(&n, &nn, &option);
    Initialization(&p, n);
    create(&p, n);
    option ? widevisit(&p, nn, n) : depthvisit(&p, nn, n);
    freeG(&p, n);
    system("pause");
    return 0;
}
void Initialization(graph *ch, ElemType n)
{
    ch->p = (ElemType **)malloc(sizeof(ElemType *) * (n + 1));
    for (int i = 0; i <= n; i++)
    {
        ch->p[i] = (ElemType *)malloc(sizeof(ElemType) * (n + 1));
    }
    ch->v = (ElemType *)malloc(sizeof(ElemType) * (n + 1));
    ch->stack = (ElemType *)malloc(sizeof(ElemType) * (n + 1));
    for (int i = 0; i <= n; i++)
    {
        ch->v[i] = 0;
        ch->stack[i] = 0;
    }
    ch->Qhead = ch->Qtail = NULL;
}
void create(graph *ch, ElemType n)
{
    printf("请输入邻接矩阵\n");
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            scanf("%d", &(ch->p[i][j]));
        }
    }
}
void enqueue(graph *ch, int nn)
{
    Queue *p = (Queue *)malloc(sizeof(Queue));
    p->Qnode = NULL;
    p->data = nn;
    if (ch->Qhead == NULL)
    {
        ch->Qhead = ch->Qtail = p;
    }
    else
    {
        ch->Qtail->Qnode = p;
        ch->Qtail = p;
    }
}
int outqueue(graph *ch)
{
    if (ch->Qhead == NULL)
    {
        return -1;
    }
    Queue *Q = ch->Qhead;
    int temp = Q->data;
    ch->Qhead = ch->Qhead->Qnode;
    if (ch->Qhead == NULL)
    {
        ch->Qtail = NULL;
    }
    free(Q);
    return temp;
}
void widevisit(graph *ch, ElemType nn, ElemType n)
{
    printf("下面进行图的广度优先遍历\n");
    int node = nn;
    ch->v[nn] = 1;
    enqueue(ch, nn);
    while (ch->Qhead != NULL)
    {
        node = outqueue(ch);
        if (node != nn)
        {
            printf("->");
        }
        printf("%c", 'A' + node - 1);
        for (int i = 1; i <= n; i++)
        {
            if (ch->p[node][i] == 1 && ch->v[i] == 0)
            {
                ch->v[i] = 1;
                enqueue(ch, i);
            }
        }
    }
    putchar('\n');
}
void depthvisit(graph *ch, ElemType nn, ElemType n)
{
    printf("下面进行图的深度优先遍历\n");
    int node = nn, j = 1, top = 0, found;
    ch->v[nn] = 1;
    ch->stack[top++] = nn;
    printf("%c", 'A' + nn - 1);

    while (top > 0)
    {
        found = 0;
        while (j <= n)
        {
            if (ch->p[node][j] == 1 && ch->v[j] == 0)
            {
                ch->v[j] = 1;
                ch->stack[top++] = j;
                printf("->%c", 'A' + j - 1);
                node = j;
                found = 1;
                break;
            }
            j++;
        }
        j = 1;
        if (!found)
        {
            top--;
            if (top > 0)
            {
                node = ch->stack[top - 1];
                j = ch->stack[top];
            }
        }
    }
    putchar('\n');
}

void input(int *n, int *nn, int *option)
{
    while (1)
    {
        printf("下面将进行图的遍历，请选择深度优先遍历（输入0）或广度优先遍历（输入1）：");
        scanf("%d", &(*option));
        if (*option == 0 || *option == 1)
        {
            break;
        }
        else
        {
            printf("您的输入有误！\n\n");
        }
    }
    do
    {
        printf("请输入结点数：");
        scanf("%d", &(*n));

        if (*n <= 0)
        {
            printf("结点数不得小于等于0！\n");
        }
    } while (*n <= 0);
    do
    {
        printf("请选择从哪个结点开始遍历:");
        scanf("%d", &(*nn));

        if (*nn < 1 || *nn > *n)
        {
            printf("您的输入不正确！\n");
        }
    } while (*nn < 1 || *nn > *n);
}
void freeG(graph *ch, int n)
{
    Queue *current = ch->Qhead;
    Queue *next;
    while (current != NULL)
    {
        next = current->Qnode;
        free(current);
        current = next;
    }
    for (int i = 0; i <= n; i++)
    {
        free(ch->p[i]);
    }
    free(ch->p);
    free(ch->v);
    free(ch->stack);
}
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

1613551
 楼主| 发表于 2023-12-12 20:57:09 | 显示全部楼层
人造人 发表于 2023-12-12 17:46
没看懂visit函数
说一下思路

我给你说一下最新的visit的思路
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

1613551
 楼主| 发表于 2023-12-12 21:07:15 | 显示全部楼层
本帖最后由 1613551 于 2023-12-12 21:08 编辑
人造人 发表于 2023-12-12 17:46
没看懂visit函数
说一下思路


具体思路就是，n是结点总数，nn是你想从哪个结点开始遍历
v是一个数组，用来记录这个结点有没有被访问过
stack是一个栈，被访问过的元素就入栈
至于那个printf就是把原本的数字1以字母A的形式输出

接下来就是循环，循环的条件是栈里面有结点
found是用来记录在node行里面是否有一条通路是连到另一个结点的，且这个结点没有被访问过。那么条件才成立

进入if以后，把这个结点放进去v数组，说明它也被访问过了，然后也入栈，也就是入stack，然后把fount置为1，就不会进入下一个if

然后第二个if就是你node行里面没有一条通路是连到另一个结点的，那么就开始出栈，也就是回溯。

第一个if里面的条件就是当你当你这个结点里面有这样一条路和其他结点
void depthvisit(graph *ch, ElemType nn, ElemType n)
{
    printf("下面进行图的深度优先遍历\n");
    int node = nn, j = 1, top = 0, found;
    ch->v[nn] = 1;
    ch->stack[top++] = nn;
    printf("%c", 'A' + nn - 1);

    while (top > 0)
    {
        found = 0;
        while (j <= n)
        {
            if (ch->p[node][j] == 1 && ch->v[j] == 0)
            {
                ch->v[j] = 1;
                ch->stack[top++] = j;
                printf("->%c", 'A' + j - 1);
                node = j;
                found = 1;
                break;
            }
            j++;
        }
        j = 1;
        if (!found)
        {
            top--;
            if (top > 0)
            {
                node = ch->stack[top - 1];
                j = ch->stack[top];
            }
        }
    }
    putchar('\n');
}
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

人造人
发表于 2023-12-12 21:30:34 | 显示全部楼层
1613551 发表于 2023-12-12 21:07
具体思路就是，n是结点总数，nn是你想从哪个结点开始遍历
v是一个数组，用来记录这个结点有没有被访问 ...

没看懂
stack是一个栈，被访问过的元素就入栈
为什么要入栈？

是不是我下面这个代码的效果？
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

typedef int ElemType;

typedef struct {
    ElemType **p; // 邻接表矩阵
    size_t n;
    bool *flag;
} graph;

void Initialization(graph *ch, size_t n) {
    ch->p = malloc(sizeof(ElemType *) * n);
    for(int i = 0; i < n; i++) {
        ch->p[i] = malloc(sizeof(ElemType) * n);
    }
    ch->flag = malloc(sizeof(bool) * n);
    ch->n = n;
}

void graph_deinit(graph *graph) {
    for(size_t i = 0; i < graph->n; ++i) free(graph->p[i]);
    free(graph->p);
    free(graph->flag);
}

void create(graph *ch) {
    printf("请输入邻接表矩阵\n");
    for(int i = 0; i < ch->n; i++) {
        for(int j = 0; j < ch->n; j++) {
            scanf("%d", &ch->p[i][j]);
        }
    }
}

void visit_sub(graph *ch, ElemType n) {
    if(ch->flag[n]) return;
    ch->flag[n] = true;
    printf("visit: %d\n", n);
    for(size_t i = 0; i < ch->n; ++i) {
        if(ch->p[n][i]) visit_sub(ch, i);
    }
}

void visit(graph *ch, ElemType n) {
    memset(ch->flag, false, sizeof(bool) * ch->n);
    visit_sub(ch, n);
}

int main(void) {
    unsigned int n, nn;
    graph p;
    printf("请输入结点数：");
    scanf("%u", &n);
    Initialization(&p, n);
    create(&p);
    do {
        printf("请选择从哪个结点开始遍历:");
        scanf("%d", &nn);
        if(nn > n) printf("您的输入不正确！\n");
    } while(nn > n);
    visit(&p, nn - 1);
    graph_deinit(&p);
    return 0;
}
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

人造人
发表于 2023-12-12 21:33:18 | 显示全部楼层
1613551 发表于 2023-12-12 21:07
具体思路就是，n是结点总数，nn是你想从哪个结点开始遍历
v是一个数组，用来记录这个结点有没有被访问 ...

我好像明白了，我那个是递归的版本，你是要非递归的版本
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

1613551
 楼主| 发表于 2023-12-12 21:39:49 | 显示全部楼层
人造人 发表于 2023-12-12 21:30
没看懂
stack是一个栈，被访问过的元素就入栈
为什么要入栈？

入栈才能回溯呀，就类似于递归，被访问过的结点入栈，比如你有三个结点
邻接矩阵是：
0 1 0
0 0 1
0 1 0
从第一个结点开始遍历，访问第一行，这时候第一个结点入栈，然后它和第二个结点之间有通路，所以第二个结点入栈，这时候开始访问第二行，然后它和第三个结点之间有通路，所以第三个结点入栈，这时候开始访问第三行。第三行的第二个元素已经访问过了，所以不会入栈，这时候第三行的所有元素都访问了一遍，循环结束，开始弹栈，又从第二行开始遍历，第二行也没有元素没访问过了，然后再弹栈，就回到第一行。
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

1613551
 楼主| 发表于 2023-12-12 21:40:26 | 显示全部楼层
人造人 发表于 2023-12-12 21:30
没看懂
stack是一个栈，被访问过的元素就入栈
为什么要入栈？

你那个代码我运行不了啊
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

人造人
发表于 2023-12-12 21:40:58 | 显示全部楼层
1613551 发表于 2023-12-12 21:40
你那个代码我运行不了啊

？
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

1613551
 楼主| 发表于 2023-12-12 21:43:35 | 显示全部楼层
人造人 发表于 2023-12-12 21:30
没看懂
stack是一个栈，被访问过的元素就入栈
为什么要入栈？

而且我看不懂你那些函数
1702388578668.png
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

人造人
发表于 2023-12-12 21:45:44 | 显示全部楼层
1613551 发表于 2023-12-12 21:43
而且我看不懂你那些函数

你用的什么编译器？
这看起来你用的C++的编译器
这是C语言代码，用C++编译器编译C语言代码，有问题很正常
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

1613551
 楼主| 发表于 2023-12-12 21:46:42 | 显示全部楼层
人造人 发表于 2023-12-12 21:45
你用的什么编译器？
这看起来你用的C++的编译器
这是C语言代码，用C++编译器编译C语言代码，有问题很正 ...

我用的vscode，我一直都写的c程序呀
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

下一页 »
12下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-23 11:09

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表