第五章学习总结

  这章的题目是关于树的,树不同于前面的内容的可能就是它并不是呈线性关系,但是只要找到基于题目下各个节点的关系就可以拟一个大致的框架,在实际去做这周的三道题的过程中,我发现这些题在思想上其实是有一定的相似度的。

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

  这周我拿深入虎穴这道题进行分析,还是因为老师讲过,所以思想更为清晰。

 

7-2 深入虎穴 (30 分)  

著名的王牌间谍 007 需要执行一次任务,获取敌方的机密情报。已知情报藏在一个地下迷宫里,迷宫只有一个入口,里面有很多条通路,每条路通向一扇门。每一扇门背后或者是一个房间,或者又有很多条路,同样是每条路通向一扇门…… 他的手里有一张表格,是其他间谍帮他收集到的情报,他们记下了每扇门的编号,以及这扇门背后的每一条通路所到达的门的编号。007 发现不存在两条路通向同一扇门。

内线告诉他,情报就藏在迷宫的最深处。但是这个迷宫太大了,他需要你的帮助 —— 请编程帮他找出距离入口最远的那扇门。

输入格式:

输入首先在一行中给出正整数 N(<),是门的数量。最后 N 行,第 i 行(1)按以下格式描述编号为 i 的那扇门背后能通向的门:

K D[1] D[2] ... D[K]

其中 K 是通道的数量,其后是每扇门的编号。

输出格式:

在一行中输出距离入口最远的那扇门的编号。题目保证这样的结果是唯一的。

 

 

 在做这道题之前,我们首先想到的是怎么去存储这样的数据,老师首先举例的是一个二维数组,这是一个相对简单且直观的存储方法,但是它有一个问题,就是稀疏矩阵,大多数时候我们的数据都不会这么多能填满,所以会造成很大的存储空间的浪费

 后来决定定义一个结构体数组来存储门的个数和后面的门的编号,因为刚好是从1开始的,所以我们从一开始存储

 

首先是,主函数的代码,在主函数中主要调用的有input和level函数

第五章学习总结 随笔 第1张
 1 int main()
 2 {
 3     node *a;//用于存储整棵树
 4     int i, j, k;
 5     int n;//门的数量
 6     cin >> n;
 7     int root;
 8     a = new node[n+1];
 9     
10     root = input(a, n);
11     cout << level(a, root) << endl;
12     
13     return 0;
14 }
View Code

input函数:

第五章学习总结 随笔 第3张
 1 int input(node *a, int n)
 2 {//读入n扇门的信息给a数组,同时还要返回根所在的门牌号/下标    
 3     int i, j;
 4     bool *vi;//判断根节点 
 5     vi = new bool[n+1];
 6     for(i=1; i<=n; ++i)//初始化vi数组的全部元素为false 
 7         vi[i] = false; 
 8 
 9     for(i=1; i<=n; ++i){//读入n扇门的信息 
10         cin >> a[i].doors;
11         if(a[i].doors!=0){
12             a[i].p = new int[a[i].doors];//为a[i].p申请空间 
13             for(j=1; j<=a[i].doors; ++j){// 输入后面的门 
14                 cin >> a[i].p[j-1];
15                 vi[a[i].p[j-1]] = true;// 如果后面有门就不是根节点 
16             }
17         } 
18         else//doors为0
19             a[i].p = NULL; 
20     } 
21     
22     for(i=1; i<=n; ++i)
23         if(!vi[i]) return i;
24  } 
View Code

level函数:主要是进行层次遍历并返回头节点

第五章学习总结 随笔 第5张
 1 int level(node *a, int r)
 2 {//从a[r]开始对a进行层次遍历,并返回遍历的最后一个节点的编号 
 3     queue<int> q;
 4     int t,i;
 5     q.push(r);
 6     
 7     while(!q.empty()){//遍历 
 8         t = q.front();
 9         q.pop();
10         
11         if(a[t].doors!=0){//t号门后面还有门 
12             for(i=0; i<a[t].doors; ++i)
13                 q.push(a[t].p[i]);
14         }
15     } 
16     
17     return t;
18 }
View Code

最后是完整的代码

第五章学习总结 随笔 第7张
 1 #include <iostream>
 2 #include <queue>
 3 using namespace std;
 4 
 5 typedef struct{//一行输入所包含的内容 
 6     int doors;//门的数量
 7     int *p;//指向后面的门的编号序列
 8 }node;
 9 
10 int input(node *a, int n)
11 {//读入n扇门的信息给a数组,同时还要返回根所在的门牌号/下标    
12     int i, j;
13     bool *vi;//判断根节点 
14     vi = new bool[n+1];
15     for(i=1; i<=n; ++i)//初始化vi数组的全部元素为false 
16         vi[i] = false; 
17 
18     for(i=1; i<=n; ++i){//读入n扇门的信息 
19         cin >> a[i].doors;
20         if(a[i].doors!=0){
21             a[i].p = new int[a[i].doors];//为a[i].p申请空间 
22             for(j=1; j<=a[i].doors; ++j){// 输入后面的门 
23                 cin >> a[i].p[j-1];
24                 vi[a[i].p[j-1]] = true;// 如果后面有门就不是根节点 
25             }
26         } 
27         else//doors为0
28             a[i].p = NULL; 
29     } 
30     
31     for(i=1; i<=n; ++i)
32         if(!vi[i]) return i;
33  } 
34  
35 int level(node *a, int r)
36 {//从a[r]开始对a进行层次遍历,并返回遍历的最后一个节点的编号 
37     queue<int> q;
38     int t,i;
39     q.push(r);
40     
41     while(!q.empty()){//遍历 
42         t = q.front();
43         q.pop();
44         
45         if(a[t].doors!=0){//t号门后面还有门 
46             for(i=0; i<a[t].doors; ++i)
47                 q.push(a[t].p[i]);
48         }
49     } 
50     
51     return t;
52 }
53 
54 int main()
55 {
56     node *a;//用于存储整棵树
57     int i, j, k;
58     int n;//门的数量
59     cin >> n;
60     int root;
61     a = new node[n+1];
62     
63     root = input(a, n);
64     cout << level(a, root) << endl;
65     
66     return 0;
67 }
View Code

 

心得体会:

  每次跟着老师打题都会感觉题目变简单了,大概是因为老师的思路比我们要清晰,这些都是需要长期的积累的,还是需要多做多想

 

 

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄