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

Question

数据结构森林如何用c语言实现遍历?（最好用递归实现）
如何实现搜索（参数是数据和顶点指针，返回结果是结点指针）

Answer 1

用深度优先搜索（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); //搜索，第二个参数是从哪个节点寻找
}