# 数据结构森林的遍历和搜索问题

• 写回答

#### 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); //搜索，第二个参数是从哪个节点寻找
}
``````
本回答被题主选为最佳回答 , 对您是否有帮助呢?
评论

#### 悬赏问题

• ¥15 maya的mel里，怎样先选择模型A，然后利用mel脚本自动选择有相同名字的模型B呢。
• ¥15 Python题，根本不会啊
• ¥15 Python题，不会啦
• ¥15 LD衰减结果文件dist的单位?
• ¥15 Python题，回答一下下啦
• ¥15 会会信号与系统和python的来
• ¥15 关于#python#的问题
• ¥20 oracle RAC 怎么配置啊，配置
• ¥15 excel 日常使用中出现问题
• ¥20 pdusession建立失败