第五章学习小结

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