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

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

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); //搜索,第二个参数是从哪个节点寻找
}
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
数据结构-树和森林的表示和遍历
树的表示方法 森林和二叉树的对应关系 树和森林的遍历 ...
森林的遍历
森林是树的集合,由此可以对森林中的每一棵树依次从左到右(如右图所示)进行先根遍历或者后根遍历。又森林中的(第一棵树的根)、(第一棵树的子树森林)及(其余树构成的森林),分别对应为(二叉树的根)、(二叉树的左子树)和(二叉树的右子树)。由此可如下定义森林的这两种遍历。一、先序遍历森林 若森林不空,则可依下列次序进行遍历 (1) 访问森林中第一棵树的根结点; (2) 先序遍历第一棵树中的子树森林
森林的后根次序遍历问题
请教:rn下面是一个以左孩子、右兄弟法表示的森林:rnrnrn Arn / \rn B \rn \ \rn C \rn \ \rn D \rn / Frn E / \rn G Hrn /rn Irn / \rn K J rnrn请问它的后根次序遍历的结果? rn
数据结构_森林
树转换为二叉树 孩子兄弟表示法: 将同一节点的各个孩子用线串联起来 将每个结点的子树分支,从左往右,除了第一个以外全部删除 如何将一棵二叉树转化成树 将二叉树从上到下分层,并调节成水平方向。(分层方法:每遇到左孩子则为一层) 找到每一层的双亲结点,方法为它的上一层相连的那个结点就是双亲结点 将每一层结点和其双亲结点相连,同时删除该双亲结点各个孩...
树和森林的遍历
树和森林的遍历 一、树的遍历 树的结构是一个根加上森林,而森林又是树的集合,由此我们可以引出树的两种遍历方式(这两种遍历方式本身也是一种递归定义)。 1、先根(先序)遍历:即先访问树的根结点,然后依次先根遍历根的每棵子树 2、后根(后序)遍历:即先依次后根遍历根的每棵子树,然后访问根结点 3、另外还有一种层序遍历,这种遍历就是自上向下,自左向右按层次进行遍历即可 根据上面的两种遍历定义可得上图树...
树 —— 树和森林的遍历
树的遍历 先根遍历 若树非空,则遍历方法为 (1)访问根结点。 (2)从左到右,依次先根遍历根结点的每一棵子树。 先根遍历序列为:ABECFHGD。 后根遍历 若树非空,则遍历方法为 (1)从左到右,依次后根遍历根结点的每一棵子树。 (2)访问根结点。 后根遍历序列为:EBHFGCDA。 森林的遍历 先序遍历 若森林非空,则遍历方法为: (1)访问森林中第一棵树的根结点。 (2)先序遍历第一棵...
C#遍历森林
  [C#开发实战]遍历森林查找一个节点 /**////遍历森林查找一个节点public static Region GetRegion(Region[] regions, string regionCode)...{    if (regions != null &amp;amp;&amp;amp; regions.Length&amp;gt;0)    //深度不为0    ...{    foreach (Regi...
6.4.3树和森林的遍历
6.4.3树和森林的遍历
【数据结构】-树和森林
一、树的存储结构1)双亲表示法 以一组地址连续的空间存储树的结点,同时在结点中附设一个指针域指示其双亲结点的位置。 这种存储结构利用每个孩子只有一个双亲的性质,求结点的双亲可以在常量时间内实现,但求结点的孩子时需要遍历整个结构。2)孩子表示法 树中每个结点可能有多个孩子,所以结点除了一个数据域外,还需要有多个指针域指向孩子结点。 有如下两种结点格式: 同构结点:假设d为树的度,则每一个结点
浅析数据结构之树与森林
树是一种重要的非线性数据结构
数据结构-树与森林-双亲表示法
 以一组连续空间存储结点,各结点附设指示器指示其双亲结点的位置(数据域加双亲下标域)。 首先是辅助宏: #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define OVERFLOW -1 #define UNDERFLOW -2 #define NULL 0 #define MAX_PTREE_SIZE 50010 ...
树、森林和二叉树的遍历---数据结构
首先,我们来了解下基本概念: 遍历是指按照某种次序访问所有结点,使每个结点被访问一次且仅被访问一次。 先序、中序、后序遍历都是针对根节点而言的,先访问根节点即为先序遍历,第二访问根节点为中序遍历,最后访问根节点为后序遍历。 层次遍历是指从根节点开始,逐层向下遍历,每一层上按照从左到右的顺序对结点逐个访问。   下面,我们分别介绍一下 树的遍历 1.先序遍历 (1)访问根节点 (2...
二叉树,树和森林(数据结构)
树和森林的创建,几种遍历方式。求高度,树和二叉树的转换等
树、森林与二叉树的转换和遍历
树转换为二叉树 1.加线。所有兄弟结点之间加一条线 2.去线。对每个结点,只保留与第一个孩子的连接,其他孩子的连接断开 3.层次调整。以树的根结点为轴,顺时针旋转某个角度,成为二叉树即可。 森林转换为二叉树 1.把每个树转换为二叉树 2.第一棵树不动,依次把后面二叉树的根结点接到前一棵树根结点的右孩子上 二叉树转换为树 1.加线。将该结点左孩子的n个右孩子,作为该结点的孩子,也就是将该结点和这...
森林树二叉树相互转换和遍历
你有没有面试的时候,被问到数据结构的问题,你有没有在面对需求的时候一头雾水?rn五斗米老师又出新课程了,数据结构一直是程序员的软实力,是算法课题的基础,游戏行业对其更为看重。学习C#语言之后的能力进阶,写出高效的代码,培养专业的程序设计思维,训练使用程序语言描述解决方案的能力,你如果刚好也是一枚Unity程序员,千万不要错过,绝对能帮得到你。
数据结构第六章数和森林
1.树林:是m棵互不相交的树所在组成的集合 2.树的存储结构: 双亲表示法 typedef struct Ptnode{ TElemType data;//结点中的元素 int parent;//父结点位置 }Ptnode; typedef struct{ Ptnode nodes[Maxsize];//存放树中的结点 int n;//树中结点个数 ...
数据结构之树、二叉树和森林
树,二叉树,森林
小白的数据结构与算法学习笔记(二十三)----树,森林的遍历
一、树的遍历 1、先根遍历 先访问树的根结点,然后再依次先根遍历根的每棵子树 2、后根遍历 先依次遍历每棵子树,然后再访问根结点 二、森林的遍历 1、前序遍历 按照树的先根遍历依次访问森林的每一棵树 2、后序遍历 按照树的后根遍历依次访问森林的每一棵树   三、树,森林,二叉树遍历的关系 这里的二叉树是由树或森林转换而得的二叉树。 树、森林的先根(前序)遍历与二叉树的...
挑战数据结构--->遍历问题
有这样一个图:rn grandfather----grandmotherrn |rn _______________rn | | rn father --mother aunt rn |rn __________rn | |rn Me brother---brother's wifern |rn ________rn | |rn nephew niecernrn 有了这样的结构,如何从任一结点遍历其它结点,请给出Person的类结构和如何实现。谢谢!
数据结构链表的遍历问题
typedef struct Nodernrn char name[10];rn char sex[6];rn char No[11];rn int age;rn struct Node *next;rnListNode;rn定义一个学生结构;rn我现在要修改学生信息用p=p->next遍历,到最后p就只有一个信息了rn求方法
树,森林,二叉树之间的转换以及 树,森林的遍历
普通树 树转换为二叉树 1.树中的所有的兄弟节点之间加上一条线 2.对每个节点,除了保留与其长子的连线外,去掉该节点与其他孩子的连线。 将下图普通的树,转换为二叉树 1.树中的所有的兄弟节点之间加上一条线 2.对每个节点,除了保留与其长子的连线外,去掉该节点与其他孩子的连线。 经过简单转变: 森林转换为二叉树 1.现将森林中的每颗树转换为二叉树 2.再将各个二叉树的根节点视为兄弟从左...
【数据结构周周练】017 利用递归算法及孩子兄弟表示法创建森林、遍历森林并求森林的叶子结点个数
 一、前言 从昨天起,就给大家分享一些树和森林的代码啦,昨天分享的是求树的深度,今天要给大家分享的是森林的遍历以及求叶子的个数。 对于森林,大家可以做这样的理解,一个深度大于1,根节点子树个数大于1的树去掉根节点,就是森林。森林中每棵树的根节点再创建一个共同的双亲结点,就成为了一棵树。所以森林转化为二叉树和树转化为二叉树原理是一样的,采用的方法依然是孩子兄弟表示法,转化规律如下: 森林中第一...
数据结构,森林编程作业代码
大学课程、数据结构、森林、建立树的存储结构、求树的深度。
树、森林和二叉树的相互转换---数据结构
树转换成二叉树 任何一棵树可唯一地与一棵二叉树对应,相应地,一棵二叉树也唯一地对应一棵树,即树与二叉树可以相互转化。 将树转换成二叉树的方法: 1.将所有兄弟结点连接起来; 2.保留第一个兄弟结点与父结点的连接,断开其他兄弟结点与父结点的连接,然后以根结点为轴心按顺时针的方向旋转45度角。 举例: 转换过程:   森林转换成二叉树 转换步骤: 1.将每棵树转换成相应的二...
数据结构 数和森林 课件讲解
数据结构的经典内容,详细讲解书和森林,易于理解和掌握
数据结构 搜索 最小路径 问题
数据结构 搜索 最小路径 问题
【数据结构森林】拨开简单的顺序表
我在大学的课堂,觉得数据结构很难理解。不过课后很幸运地借助资料自学了下来。感觉又有什么复杂的呢?无非老师没给我讲清楚罢了。那么我们开始入门:顺序表。 顺序表可以理解为一个长度为SIZE的数组a[SIZE],数组中的每一个元素都有下标,而我们则是通过一个个下标去1插入数组,2删除数组,3遍历数组,4寻找数组中的值。这四步就是顺序线性表的主要操作了。 1.首先定义全局变量:最大长度SIZE,和实时
数据结构ppt教程(树和森林)
数据结构ppt教程(树和森林) 适用于 适用于适用于严蔚敏.数据结构(C语言版).清华大学出版社
数据结构——树、森林、赫夫曼树
树与森林1.树的存储结构(1)双亲表示法:利用每个结点只有一个双亲的性质,在每个结点中附设一个指示器指示其双亲结点在链表中的位置(2)孩子表示法:把每个孩子结点排列起来,看成是一个线性表,且以单链表作存储结构(3)孩子兄弟表示法(称为二叉树表示法或者二叉链表表示法)typedef struct CSNode{  ElemType          data;  struct CSNode   ...
数据结构之从链表而来的森林
公司项目有个需求,用户通过网页对目录结果进行编辑后,产生了如下的数组结构,后台需要对这个数组转换成一个森林,然后方便的进行渲染。这个数组原型大概如下图,|—— 根目录 level:-1 |—— 目录A level:0 |—— 目录A_1 level:1 |—— 目录A_1_1 level:2 |—— 目录A_2 level:1
森林的问题~~
这是ACM上的题目,大体是有P个人和N个数,第一行首先输入P和N ,接下来每行输入i,j代表第i个人听到第j个树的声音,两个人只有听到的树的集合完全相同的时候才算是意见相同,那么问一共有几种不同的意见。例如输入rn3 4rn1 2 rn3 3 rn1 3 rn2 2 rn3 2 rn2 4rn则输出2rn请大虾们能否给个思路,该用什么算法呢?
二叉树以及树和森林的遍历及应用
详细介绍了二叉树的构造,遍历以及应用。还有树和森林与二叉树的转换。
excel搜索和遍历
MFC界面提示 可以选择打开excel文件 能够读取所有工作表的内容 进行遍历搜索 返回相关信息
域名遍历搜索python实现
前记—— 其实我的第一篇博客就是写如何获取给定网址的信息,也有那家公司的面试题。 最近一个星期想把那个面试题中的程序研究透彻.. 毕竟既然有可以参考的大公司的大神的代码,肯底要学习一番嘛,(师夷长技以制夷..不对,额反正就大概是这个意思啦) 正文—— 程序的功能很简单,就遍历可能的域名组合,每个地址都访问一次,获取它的标题。 功能是很简单,但是网址数一旦多就变得很麻烦。 实现的方式是
遍历搜索图形演示
遍历搜索图形演示 if (currentpoint.row == m_rowcount - 2 && currentpoint.col == m_mulcount - 2) { bret = true; break; } currentpoint.InitSereach(m_maps, irow, icol, m_rowcount - 1, m_mulcount - 1); // up if (currentpoint.up == emSereachResult.dsr_None || currentpoint.up == emSereachResult.dsr_NotSereach) { if (!IsListExists(list, irow - 1, icol)) { tempoint = new CSereachPoint(currentpoint, irow - 1, icol); list.Add(tempoint); currentpoint.nextdirect = emDirect.edt_Up; currentpoint = tempoint; DrawSereachLine(g, emDrawType.edt_Forward, emDirect.edt_Up, irow, icol); irow--; continue; } else { currentpoint.up = emSereachResult.dsr_Done; } }
BeautifulSoup 遍历、搜索
# -*- coding: utf-8 -*- import re from bs4 import BeautifulSoup html_doc = &quot;&quot;&quot; &amp;lt;html&amp;gt;&amp;lt;head&amp;gt;&amp;lt;title&amp;gt;The Dormouse's story&amp;lt;/title&amp;gt;&amp;lt;/head&amp;gt; &amp;lt;body&amp;gt; &amp;lt;p cla
两大搜索--tu的遍历
搜索在我们遇到的一些问题当中,有些问题我们不能够确切的找出数学模型,即找不出一种直接求解的方法,解决这一类问题,我们一般采用搜索的方法解决。搜索就是用问题的所有可能去试探,按照一定的顺序、规则,不断去试探,直到找到问题的解,试完了也没有找到解,那就是无解,试探时一定要试探完所有的情况(实际上就是穷举)。
数据结构_马的遍历问题.doc
数据结构的基础,也是比较重要的实例教学。
grep 遍历 搜索
grep &quot;padding-bottom&quot; -r ./ | grep &quot;10&quot;
剑指offer 遍历搜索
1. 广度优先思想 适合题目:给定初始状态跟目标状态,要求从初始状态到目标状态的最短路径。辅助数据结构是队列。 1.1 Prime最小生成树; 1.2 Dijkstra单源最短路径算法; 1.3 树的分层遍历,二叉树的最小深度 1.4 走迷宫,从起点到终点的最短路径; 定义一个二维数组: int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1,
相关热词 c#检测非法字符 c#双屏截图 c#中怎么关闭线程 c# 显示服务器上的图片 api嵌入窗口 c# c# 控制网页 c# encrypt c#微信网页版登录 c# login 居中 c# 考试软件