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

鱼C论坛

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

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

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


  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4. typedef int ElemType;
  5. typedef struct graph
  6. {
  7.     ElemType *v;  // 通过入栈的方式判断结点是否有被遍历
  8.     ElemType **p; // 邻接表矩阵
  9.     ElemType *stack;
  10. } graph;
  11. void Initialization(graph *ch, ElemType n)
  12. {
  13.     ch->p = (ElemType **)malloc(sizeof(ElemType *) * pow((n + 1), 2));
  14.     for (int i = 1; i <= n; i++)
  15.     {
  16.         ch->p[i] = (ElemType *)malloc(sizeof(ElemType) * (n + 1));
  17.     }
  18.     ch->v = (ElemType *)malloc(sizeof(ElemType) * (n + 1));
  19.     ch->stack = (ElemType *)malloc(sizeof(ElemType) * n);
  20. }
  21. void create(graph *ch, ElemType n)
  22. {
  23.     printf("请输入邻接表矩阵\n");
  24.     for (int i = 1; i <= n; i++)
  25.     {
  26.         for (int j = 1; j <= n; j++)
  27.         {
  28.             scanf("%d", &(ch->p[i][j]));
  29.         }
  30.     }
  31. }
  32. void visit(graph *ch, ElemType nn, ElemType n)
  33. {
  34.     int node = nn, j = 1, top = 0;
  35.     ch->v[nn] = 1;
  36.     ch->stack[top++] = nn;
  37.     printf("%d", nn);
  38.     while (1)
  39.     {
  40.         if (ch->p[node][j] == 1 && ch->v[j] == 0)
  41.         {
  42.             ch->v[j] = 1;
  43.             ch->stack[top++] = j;
  44.             printf("->%d", j);
  45.             node = j;
  46.             j = 1;
  47.         };
  48.         if (j == n + 1)
  49.         {
  50.             if (ch->stack[top] == nn)
  51.             {
  52.                 break;
  53.             }
  54.             ch->stack[top--] = 0;
  55.             node = ch->stack[top];
  56.             j = 1;
  57.         }
  58.         j++;
  59.     }
  60. }
  61. int main(void)
  62. {
  63.     int n, nn;
  64.     graph p;
  65.     do
  66.     {

  68.         printf("请输入结点数：");
  69.         scanf("%d", &n);
  70.         if (n <= 0)
  71.         {
  72.             printf("结点数不得小于等于0！\n");
  73.         }
  74.     } while (n <= 0);
  75.     Initialization(&p, n);
  76.     create(&p, n);
  77.     do
  78.     {

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

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdbool.h>
  4. #include <string.h>

  6. typedef int ElemType;

  8. typedef struct {
  9.     ElemType e;
  10.     size_t status;
  11. } stack_elem_t;

  13. typedef struct {
  14.     stack_elem_t *data;
  15.     size_t size, top;
  16. } stack_t;

  18. stack_t *stack_init(void) {
  19.     stack_t *stack = malloc(sizeof(*stack));
  20.     stack->data = NULL;
  21.     stack->size = stack->top = 0;
  22.     return stack;
  23. }

  25. void stack_deinit(stack_t *stack) {
  26.     free(stack->data);
  27.     free(stack);
  28. }

  30. size_t stack_size(const stack_t *stack) {
  31.     return stack->top;
  32. }

  34. bool stack_empty(const stack_t *stack) {
  35.     return stack_size(stack) == 0;
  36. }

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

  44. void stack_pop(stack_t *stack) {
  45.     if(stack_empty(stack)) return;
  46.     --stack->top;
  47. }

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

  54. typedef ElemType vector_elem_t;

  56. typedef struct {
  57.     vector_elem_t *data;
  58.     size_t size;
  59. } vector_t;

  61. vector_t *vector_init(void) {
  62.     vector_t *vector = malloc(sizeof(*vector));
  63.     vector->data = NULL;
  64.     vector->size = 0;
  65.     return vector;
  66. }

  68. void vector_deinit(vector_t *vector) {
  69.     free(vector->data);
  70.     free(vector);
  71. }

  73. size_t vector_size(const vector_t *vector) {
  74.     return vector->size;
  75. }

  77. size_t vector_empty(const vector_t *vector) {
  78.     return vector_size(vector) == 0;
  79. }

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

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

  92. void vector_append(vector_t *vector, vector_elem_t e) {
  93.     vector_set(vector, vector_size(vector), e);
  94. }

  96. bool vector_find(const vector_t *vector, vector_elem_t e) {
  97.     for(size_t i = 0; i < vector_size(vector); ++i) {
  98.         if(vector_get(vector, i) == e) return true;
  99.     }
  100.     return false;
  101. }

  103. typedef struct {
  104.     ElemType **p;
  105.     size_t n;
  106. } graph;

  108. void Initialization(graph *ch, size_t n) {
  109.     ch->p = malloc(sizeof(ElemType *) * n);
  110.     for(int i = 0; i < n; i++) {
  111.         ch->p[i] = malloc(sizeof(ElemType) * n);
  112.     }
  113.     ch->n = n;
  114. }

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

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

  130. void visit(graph *ch, ElemType n) {
  131.     stack_t *stack = stack_init();
  132.     vector_t *vector = vector_init();
  133.     stack_elem_t se = {n, 0};
  134.     stack_push(stack, se);
  135.     while(!stack_empty(stack)) {
  136.         se = stack_top(stack);
  137.         switch(se.status) {
  138.             case 0:
  139.                 printf("%d\n", se.e);
  140.                 stack_pop(stack);
  141.                 stack_push(stack, (stack_elem_t){se.e, 1});
  142.                 vector_append(vector, se.e);
  143.                 for(size_t i = 0; i < ch->n; ++i) {
  144.                     if(ch->p[se.e][i] && !vector_find(vector, i)) stack_push(stack, (stack_elem_t){i, 0});
  145.                 }
  146.                 break;
  147.             case 1:
  148.                 stack_pop(stack);
  149.         }
  150.     }
  151.     vector_deinit(vector);
  152.     stack_deinit(stack);
  153. }

  155. int main(void) {
  156.     unsigned int n, nn;
  157.     graph p;
  158.     printf("请输入结点数：");
  159.     scanf("%u", &n);
  160.     Initialization(&p, n);
  161.     create(&p);
  162.     do {
  163.         printf("请选择从哪个结点开始遍历:");
  164.         scanf("%d", &nn);
  165.         if(nn > n) printf("您的输入不正确！\n");
  166.     } while(nn > n);
  167.     visit(&p, nn - 1);
  168.     graph_deinit(&p);
  169.     return 0;
  170. }
复制代码

最佳答案

人造人

查看完整内容

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

使用道具 举报

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

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdbool.h>
  4. #include <string.h>

  6. typedef int ElemType;

  8. typedef struct {
  9.     ElemType e;
  10.     size_t status;
  11. } stack_elem_t;

  13. typedef struct {
  14.     stack_elem_t *data;
  15.     size_t size, top;
  16. } stack_t;

  18. stack_t *stack_init(void) {
  19.     stack_t *stack = malloc(sizeof(*stack));
  20.     stack->data = NULL;
  21.     stack->size = stack->top = 0;
  22.     return stack;
  23. }

  25. void stack_deinit(stack_t *stack) {
  26.     free(stack->data);
  27.     free(stack);
  28. }

  30. size_t stack_size(const stack_t *stack) {
  31.     return stack->top;
  32. }

  34. bool stack_empty(const stack_t *stack) {
  35.     return stack_size(stack) == 0;
  36. }

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

  44. void stack_pop(stack_t *stack) {
  45.     if(stack_empty(stack)) return;
  46.     --stack->top;
  47. }

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

  54. typedef ElemType vector_elem_t;

  56. typedef struct {
  57.     vector_elem_t *data;
  58.     size_t size;
  59. } vector_t;

  61. vector_t *vector_init(void) {
  62.     vector_t *vector = malloc(sizeof(*vector));
  63.     vector->data = NULL;
  64.     vector->size = 0;
  65.     return vector;
  66. }

  68. void vector_deinit(vector_t *vector) {
  69.     free(vector->data);
  70.     free(vector);
  71. }

  73. size_t vector_size(const vector_t *vector) {
  74.     return vector->size;
  75. }

  77. size_t vector_empty(const vector_t *vector) {
  78.     return vector_size(vector) == 0;
  79. }

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

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

  92. void vector_append(vector_t *vector, vector_elem_t e) {
  93.     vector_set(vector, vector_size(vector), e);
  94. }

  96. bool vector_find(const vector_t *vector, vector_elem_t e) {
  97.     for(size_t i = 0; i < vector_size(vector); ++i) {
  98.         if(vector_get(vector, i) == e) return true;
  99.     }
  100.     return false;
  101. }

  103. typedef struct {
  104.     ElemType **p;
  105.     size_t n;
  106. } graph;

  108. void Initialization(graph *ch, size_t n) {
  109.     ch->p = malloc(sizeof(ElemType *) * n);
  110.     for(int i = 0; i < n; i++) {
  111.         ch->p[i] = malloc(sizeof(ElemType) * n);
  112.     }
  113.     ch->n = n;
  114. }

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

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

  130. void visit(graph *ch, ElemType n) {
  131.     stack_t *stack = stack_init();
  132.     vector_t *vector = vector_init();
  133.     stack_elem_t se = {n, 0};
  134.     stack_push(stack, se);
  135.     while(!stack_empty(stack)) {
  136.         se = stack_top(stack);
  137.         switch(se.status) {
  138.             case 0:
  139.                 printf("%d\n", se.e);
  140.                 stack_pop(stack);
  141.                 stack_push(stack, (stack_elem_t){se.e, 1});
  142.                 vector_append(vector, se.e);
  143.                 for(size_t i = 0; i < ch->n; ++i) {
  144.                     if(ch->p[se.e][i] && !vector_find(vector, i)) stack_push(stack, (stack_elem_t){i, 0});
  145.                 }
  146.                 break;
  147.             case 1:
  148.                 stack_pop(stack);
  149.         }
  150.     }
  151.     vector_deinit(vector);
  152.     stack_deinit(stack);
  153. }

  155. int main(void) {
  156.     unsigned int n, nn;
  157.     graph p;
  158.     printf("请输入结点数：");
  159.     scanf("%u", &n);
  160.     Initialization(&p, n);
  161.     create(&p);
  162.     do {
  163.         printf("请选择从哪个结点开始遍历:");
  164.         scanf("%d", &nn);
  165.         if(nn > n) printf("您的输入不正确！\n");
  166.     } while(nn > n);
  167.     visit(&p, nn - 1);
  168.     graph_deinit(&p);
  169.     return 0;
  170. }
复制代码
想知道小甲鱼最近在做啥？请访问 -> 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 | 显示全部楼层
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdbool.h>
  4. #include <string.h>

  6. typedef int ElemType;

  8. typedef struct {
  9.     ElemType **p; // 邻接表矩阵
  10.     size_t n;
  11.     bool *flag;
  12.     /*
  13.     ElemType *v;  // 通过入栈的方式判断结点是否有被遍历
  14.     ElemType *stack;
  15.     */
  16. } graph;

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

  28.     /*
  29.     ch->v = (ElemType *)malloc(sizeof(ElemType) * (n + 1));
  30.     ch->stack = (ElemType *)malloc(sizeof(ElemType) * n);
  31.     */
  32. }

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

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

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

  59.     // 没看懂
  60.     /*
  61.     int node = n - 1, j = 1, top = 0;
  62.     ch->v[n] = 1;
  63.     ch->stack[top++] = n;
  64.     printf("%zu", n);
  65.     while(1) {
  66.         if(ch->p[node][j] == 1 && ch->v[j] == 0) {
  67.             ch->v[j] = 1;
  68.             ch->stack[top++] = j;
  69.             printf("->%d", j);
  70.             node = j;
  71.             j = 1;
  72.         };
  73.         if(j == ch->n + 1) {
  74.             if(ch->stack[top] == n) {
  75.                 break;
  76.             }
  77.             ch->stack[top--] = 0;
  78.             node = ch->stack[top];
  79.             j = 1;
  80.         }
  81.         j++;
  82.     }
  83.     */
  84. }

  86. int main(void) {
  87.     unsigned int n, nn;
  88.     graph p;
  89.     printf("请输入结点数：");
  90.     scanf("%u", &n);
  91.     Initialization(&p, n);
  92.     create(&p);
  93.     do {
  94.         printf("请选择从哪个结点开始遍历:");
  95.         scanf("%d", &nn);
  96.         if(nn > n) printf("您的输入不正确！\n");
  97.     } while(nn > n);
  98.     visit(&p, nn - 1);
  99.     graph_deinit(&p);
  100.     return 0;
  101. }
复制代码

评分

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

查看全部评分

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

使用道具 举报

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

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

  6. typedef int ElemType;

  8. typedef struct {
  9.     ElemType **p; // 邻接表矩阵
  10.     size_t n;
  11.     bool *flag;
  12. } graph;

  14. void Initialization(graph *ch, size_t n) {
  15.     ch->p = malloc(sizeof(ElemType *) * n);
  16.     for(int i = 0; i < n; i++) {
  17.         ch->p[i] = malloc(sizeof(ElemType) * n);
  18.     }
  19.     ch->flag = malloc(sizeof(bool) * n);
  20.     ch->n = n;
  21. }

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

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

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

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

  52. int main(void) {
  53.     unsigned int n, nn;
  54.     graph p;
  55.     printf("请输入结点数：");
  56.     scanf("%u", &n);
  57.     Initialization(&p, n);
  58.     create(&p);
  59.     do {
  60.         printf("请选择从哪个结点开始遍历:");
  61.         scanf("%d", &nn);
  62.         if(nn > n) printf("您的输入不正确！\n");
  63.     } while(nn > n);
  64.     visit(&p, nn - 1);
  65.     graph_deinit(&p);
  66.     return 0;
  67. }
复制代码

评分

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

查看全部评分

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

使用道具 举报

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

不好意思，还没时间仔细看，但是我昨天其实自己弄出来一个了

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. typedef int ElemType;
  4. typedef struct graph
  5. {
  6.     ElemType *v;
  7.     ElemType **p;
  8.     ElemType *stack;
  9. } graph;
  10. void Initialization(graph *ch, ElemType n)
  11. {
  12.     ch->p = (ElemType **)malloc(sizeof(ElemType *) * (n + 1));
  13.     for (int i = 0; i <= n; i++)
  14.     {
  15.         ch->p[i] = (ElemType *)malloc(sizeof(ElemType) * (n + 1));
  16.     }
  17.     ch->v = (ElemType *)malloc(sizeof(ElemType) * (n + 1));
  18.     ch->stack = (ElemType *)malloc(sizeof(ElemType) * (n + 1));
  19.     for (int i = 0; i <= n; i++)
  20.     {
  21.         ch->v[i] = 0;
  22.         ch->stack[i] = 0;
  23.     }
  24. }
  25. void create(graph *ch, ElemType n)
  26. {
  27.     printf("请输入邻接表矩阵\n");
  28.     for (int i = 1; i <= n; i++)
  29.     {
  30.         for (int j = 1; j <= n; j++)
  31.         {
  32.             scanf("%d", &(ch->p[i][j]));
  33.         }
  34.     }
  35. }
  36. void visit(graph *ch, ElemType nn, ElemType n)
  37. {
  38.     int node = nn, j = 1, top = 0;
  39.     ch->v[nn] = 1;
  40.     ch->stack[top++] = nn;
  41.     printf("%d", nn);
  42.     while (1)
  43.     {
  44.         if (ch->p[node][j] == 1 && ch->v[j] == 0)
  45.         {
  46.             ch->v[j] = 1;
  47.             ch->stack[top++] = j;
  48.             printf("->%d", j);
  49.             node = j;
  50.             j = 1;
  51.         }
  52.         if (j > n)
  53.         {
  54.             if (nn == ch->stack[top])
  55.             {
  56.                 break;
  57.             }
  58.             ch->stack[top--] = 0;
  59.             node = ch->stack[top];
  60.             j = 1;
  61.         }
  62.         j++;
  63.     }
  64. }
  65. int main(void)
  66. {
  67.     int n, nn;
  68.     graph p;
  69.     do
  70.     {
  71.         printf("请输入结点数：");
  72.         scanf("%d", &n);

  74.         if (n <= 0)
  75.         {
  76.             printf("结点数不得小于等于0！\n");
  77.         }
  78.     } while (n <= 0);
  79.     Initialization(&p, n);
  80.     create(&p, n);
  81.     do
  82.     {
  83.         printf("请选择从哪个结点开始遍历:");
  84.         scanf("%d", &nn);

  86.         if (nn < 1 || nn > n)
  87.         {
  88.             printf("您的输入不正确！\n");
  89.         }
  90.     } while (nn < 1 || nn > n);
  91.     visit(&p, nn, n);
  92.     system("pause");
  93.     for (int i = 0; i <= n; i++)
  94.     {
  95.         free(p.p[i]);
  96.     }
  97.     free(p.p);
  98.     free(p.v);
  99.     free(p.stack);
  100.     return 0;
  101. }
复制代码
想知道小甲鱼最近在做啥？请访问 -> 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函数
说一下思路

我没改出来他那种效果，于是我自己又重新写了一个
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. typedef int ElemType;
  4. typedef struct Queue
  5. {
  6.     ElemType data;
  7.     Queue *Qnode;
  8. } Queue;
  9. typedef struct graph
  10. {
  11.     ElemType *v;
  12.     ElemType **p;
  13.     ElemType *stack;
  14.     Queue *Qhead;
  15.     Queue *Qtail;
  16. } graph;
  17. void Initialization(graph *ch, ElemType n);
  18. void create(graph *ch, ElemType n);
  19. void enqueue(graph *ch, int nn);
  20. int outqueue(graph *ch);
  21. void widevisit(graph *ch, ElemType nn, ElemType n);
  22. void depthvisit(graph *ch, ElemType nn, ElemType n);
  23. void input(int *n, int *nn, int *option);
  24. void freeG(graph *ch, int n);
  25. int main(void)
  26. {
  27.     int n, nn, option;
  28.     graph p;
  29.     input(&n, &nn, &option);
  30.     Initialization(&p, n);
  31.     create(&p, n);
  32.     option ? widevisit(&p, nn, n) : depthvisit(&p, nn, n);
  33.     freeG(&p, n);
  34.     system("pause");
  35.     return 0;
  36. }
  37. void Initialization(graph *ch, ElemType n)
  38. {
  39.     ch->p = (ElemType **)malloc(sizeof(ElemType *) * (n + 1));
  40.     for (int i = 0; i <= n; i++)
  41.     {
  42.         ch->p[i] = (ElemType *)malloc(sizeof(ElemType) * (n + 1));
  43.     }
  44.     ch->v = (ElemType *)malloc(sizeof(ElemType) * (n + 1));
  45.     ch->stack = (ElemType *)malloc(sizeof(ElemType) * (n + 1));
  46.     for (int i = 0; i <= n; i++)
  47.     {
  48.         ch->v[i] = 0;
  49.         ch->stack[i] = 0;
  50.     }
  51.     ch->Qhead = ch->Qtail = NULL;
  52. }
  53. void create(graph *ch, ElemType n)
  54. {
  55.     printf("请输入邻接矩阵\n");
  56.     for (int i = 1; i <= n; i++)
  57.     {
  58.         for (int j = 1; j <= n; j++)
  59.         {
  60.             scanf("%d", &(ch->p[i][j]));
  61.         }
  62.     }
  63. }
  64. void enqueue(graph *ch, int nn)
  65. {
  66.     Queue *p = (Queue *)malloc(sizeof(Queue));
  67.     p->Qnode = NULL;
  68.     p->data = nn;
  69.     if (ch->Qhead == NULL)
  70.     {
  71.         ch->Qhead = ch->Qtail = p;
  72.     }
  73.     else
  74.     {
  75.         ch->Qtail->Qnode = p;
  76.         ch->Qtail = p;
  77.     }
  78. }
  79. int outqueue(graph *ch)
  80. {
  81.     if (ch->Qhead == NULL)
  82.     {
  83.         return -1;
  84.     }
  85.     Queue *Q = ch->Qhead;
  86.     int temp = Q->data;
  87.     ch->Qhead = ch->Qhead->Qnode;
  88.     if (ch->Qhead == NULL)
  89.     {
  90.         ch->Qtail = NULL;
  91.     }
  92.     free(Q);
  93.     return temp;
  94. }
  95. void widevisit(graph *ch, ElemType nn, ElemType n)
  96. {
  97.     printf("下面进行图的广度优先遍历\n");
  98.     int node = nn;
  99.     ch->v[nn] = 1;
  100.     enqueue(ch, nn);
  101.     while (ch->Qhead != NULL)
  102.     {
  103.         node = outqueue(ch);
  104.         if (node != nn)
  105.         {
  106.             printf("->");
  107.         }
  108.         printf("%c", 'A' + node - 1);
  109.         for (int i = 1; i <= n; i++)
  110.         {
  111.             if (ch->p[node][i] == 1 && ch->v[i] == 0)
  112.             {
  113.                 ch->v[i] = 1;
  114.                 enqueue(ch, i);
  115.             }
  116.         }
  117.     }
  118.     putchar('\n');
  119. }
  120. void depthvisit(graph *ch, ElemType nn, ElemType n)
  121. {
  122.     printf("下面进行图的深度优先遍历\n");
  123.     int node = nn, j = 1, top = 0, found;
  124.     ch->v[nn] = 1;
  125.     ch->stack[top++] = nn;
  126.     printf("%c", 'A' + nn - 1);

  128.     while (top > 0)
  129.     {
  130.         found = 0;
  131.         while (j <= n)
  132.         {
  133.             if (ch->p[node][j] == 1 && ch->v[j] == 0)
  134.             {
  135.                 ch->v[j] = 1;
  136.                 ch->stack[top++] = j;
  137.                 printf("->%c", 'A' + j - 1);
  138.                 node = j;
  139.                 found = 1;
  140.                 break;
  141.             }
  142.             j++;
  143.         }
  144.         j = 1;
  145.         if (!found)
  146.         {
  147.             top--;
  148.             if (top > 0)
  149.             {
  150.                 node = ch->stack[top - 1];
  151.                 j = ch->stack[top];
  152.             }
  153.         }
  154.     }
  155.     putchar('\n');
  156. }

  158. void input(int *n, int *nn, int *option)
  159. {
  160.     while (1)
  161.     {
  162.         printf("下面将进行图的遍历，请选择深度优先遍历（输入0）或广度优先遍历（输入1）：");
  163.         scanf("%d", &(*option));
  164.         if (*option == 0 || *option == 1)
  165.         {
  166.             break;
  167.         }
  168.         else
  169.         {
  170.             printf("您的输入有误！\n\n");
  171.         }
  172.     }
  173.     do
  174.     {
  175.         printf("请输入结点数：");
  176.         scanf("%d", &(*n));

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

  188.         if (*nn < 1 || *nn > *n)
  189.         {
  190.             printf("您的输入不正确！\n");
  191.         }
  192.     } while (*nn < 1 || *nn > *n);
  193. }
  194. void freeG(graph *ch, int n)
  195. {
  196.     Queue *current = ch->Qhead;
  197.     Queue *next;
  198.     while (current != NULL)
  199.     {
  200.         next = current->Qnode;
  201.         free(current);
  202.         current = next;
  203.     }
  204.     for (int i = 0; i <= n; i++)
  205.     {
  206.         free(ch->p[i]);
  207.     }
  208.     free(ch->p);
  209.     free(ch->v);
  210.     free(ch->stack);
  211. }
复制代码
想知道小甲鱼最近在做啥？请访问 -> 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里面的条件就是当你当你这个结点里面有这样一条路和其他结点

  1. void depthvisit(graph *ch, ElemType nn, ElemType n)
  2. {
  3.     printf("下面进行图的深度优先遍历\n");
  4.     int node = nn, j = 1, top = 0, found;
  5.     ch->v[nn] = 1;
  6.     ch->stack[top++] = nn;
  7.     printf("%c", 'A' + nn - 1);

  9.     while (top > 0)
  10.     {
  11.         found = 0;
  12.         while (j <= n)
  13.         {
  14.             if (ch->p[node][j] == 1 && ch->v[j] == 0)
  15.             {
  16.                 ch->v[j] = 1;
  17.                 ch->stack[top++] = j;
  18.                 printf("->%c", 'A' + j - 1);
  19.                 node = j;
  20.                 found = 1;
  21.                 break;
  22.             }
  23.             j++;
  24.         }
  25.         j = 1;
  26.         if (!found)
  27.         {
  28.             top--;
  29.             if (top > 0)
  30.             {
  31.                 node = ch->stack[top - 1];
  32.                 j = ch->stack[top];
  33.             }
  34.         }
  35.     }
  36.     putchar('\n');
  37. }
复制代码
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

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

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

是不是我下面这个代码的效果？

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdbool.h>
  4. #include <string.h>

  6. typedef int ElemType;

  8. typedef struct {
  9.     ElemType **p; // 邻接表矩阵
  10.     size_t n;
  11.     bool *flag;
  12. } graph;

  14. void Initialization(graph *ch, size_t n) {
  15.     ch->p = malloc(sizeof(ElemType *) * n);
  16.     for(int i = 0; i < n; i++) {
  17.         ch->p[i] = malloc(sizeof(ElemType) * n);
  18.     }
  19.     ch->flag = malloc(sizeof(bool) * n);
  20.     ch->n = n;
  21. }

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

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

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

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

  52. int main(void) {
  53.     unsigned int n, nn;
  54.     graph p;
  55.     printf("请输入结点数：");
  56.     scanf("%u", &n);
  57.     Initialization(&p, n);
  58.     create(&p);
  59.     do {
  60.         printf("请选择从哪个结点开始遍历:");
  61.         scanf("%d", &nn);
  62.         if(nn > n) printf("您的输入不正确！\n");
  63.     } while(nn > n);
  64.     visit(&p, nn - 1);
  65.     graph_deinit(&p);
  66.     return 0;
  67. }
复制代码
想知道小甲鱼最近在做啥？请访问 -> 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-4-29 00:03

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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