数据结构森林如何用c语言实现遍历?(最好用递归实现)
如何实现搜索(参数是数据和顶点指针,返回结果是结点指针)
1条回答 默认 最新
- threenewbee 2018-04-24 14:28关注
用深度优先搜索(deep first search,DFS)写一个:
#include <iostream> #include <string> using namespace std; #define MAXLEN 10 struct Node { int data; Node *next; }; struct Link { int count; string name; Node *head; }; struct Graph { Link link[MAXLEN]; int vexnum; int arcnum; }; int findIndex(Graph &G, string name) { int index = -1; for (int i = 0; i < G.vexnum; i++) { if (G.link[i].name == name) { index = i; break; } } if (index == -1) cout << "error" << endl; return index; } void constructGraph(Graph &G) { cout << "construct graph yooo" << endl; cout << "enter vexnum" << endl; cin >> G.vexnum; string array[] = {"v1", "v2", "v3", "v4", "v5", "v6", "v7", "v8"}; const int size = sizeof array / sizeof *array; for (int i = 0; i < G.vexnum; i++) { G.link[i].name = array[i]; G.link[i].head = NULL; } string leftName; string rightName; cout << "enter a pair" << endl; cin >> leftName >> rightName; while (leftName != "end" && rightName != "end") { int leftIndex = findIndex(G, leftName); int rightIndex = findIndex(G, rightName); Node *node = new Node; node->data = rightIndex; node->next = NULL; node->next = G.link[leftIndex].head; G.link[leftIndex].head = node; cout << "enter a pair" << endl; cin >> leftName >> rightName; } } bool flag[MAXLEN]; void DFSTranverse(Graph &G, int num) { cout << G.link[num].name << " "; flag[num] = true; Node *head = G.link[num].head; while (head != NULL) { int index = head->data; //如果你需要把遍历修改为搜索,可以在这里判断 if (!flag[index]) //判断下是否已经遍历过 DFSTranverse(G, index); //注意,这里是递归 head = head->next; } } void main() { Graph G; constructGraph(G); //生成一个图 for (int i = 0; i < MAXLEN; i++) flag[i] = false; //初始化,默认所有节点都没有遍历过 DFSTranverse(G, 0); //搜索,第二个参数是从哪个节点寻找 }
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报
悬赏问题
- ¥40 复杂的限制性的商函数处理
- ¥15 程序不包含适用于入口点的静态Main方法
- ¥15 素材场景中光线烘焙后灯光失效
- ¥15 请教一下各位,为什么我这个没有实现模拟点击
- ¥15 执行 virtuoso 命令后,界面没有,cadence 启动不起来
- ¥50 comfyui下连接animatediff节点生成视频质量非常差的原因
- ¥20 有关区间dp的问题求解
- ¥15 多电路系统共用电源的串扰问题
- ¥15 slam rangenet++配置
- ¥15 有没有研究水声通信方面的帮我改俩matlab代码