过往的不只云烟
2018-04-24 09:12
采纳率: 100%
浏览 1.1k
已采纳

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

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

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

  • blownewbee 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); //搜索,第二个参数是从哪个节点寻找
    }
    
    点赞 评论

相关推荐 更多相似问题