DS第5章学习小结

拼搏现实的明天。 2021-11-22 08:14 316阅读 0赞

**一、谈谈你对本章的学习心得，或者任选本章一道题目，谈谈你解决该题的心得体会**

谈谈我做　　第5章作业7-1 List Leaves　　的心得体会吧

![1627872-20190504193003120-680323887.png][]

![1627872-20190504193012705-175162099.png][]

简单讲，就是　　输入一棵树，然后从上到下、从左到右输出叶子结点。

这题其实跟老师在实验课上带我们写的那个　　第5章实践1第2题7-2 深入虎穴　　很像，都需要用到**层次遍历**，然后再稍作修改就差不多了。

附上我的代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<iostream>
      2 #include<queue>
      3 using namespace std;
      4 
      5 
      6 typedef struct
      7 {
      8     int data[2];
      9 }node;
     10 
     11 
     12 int input(node *&a);//按顺序依次输入每个结点的左右孩子，无孩子则用‘-’代替 
     13 void find(const node *a, const int root);//从上到下、从左到右输出叶子结点 
     14 
     15 
     16 
     17 
     18 int main()//List Leaves
     19 {
     20     node *a;
     21     
     22     
     23     int root=0;
     24     root=input(a);
     25     
     26     
     27     find(a,root);
     28     
     29     
     30 return 0;
     31 }
     32 
     33 
     34 
     35 
     36 int input(node *&a)//按顺序依次输入每个结点的左右孩子，无孩子则用‘-’代替 
     37 {
     38     int n=0;
     39     cin>>n;
     40     a=new node[n];
     41     
     42     
     43     bool *vi;
     44     vi=new bool[n];
     45     for(int i=0; i<n; i++)
     46     {
     47         vi[i]=false;
     48     }
     49     
     50     
     51     for(int i=0; i<n; i++)
     52     {
     53         char x;
     54         for(int j=0; j<2; j++)
     55         {
     56             cin>>x;//输入，若为正常的0~9数字则录入 
     57             if('0'<=x && x<='9')
     58             {
     59                 a[i].data[j]=x-'0';
     60                 vi[x-'0']=true;
     61             }
     62             else
     63             {
     64                 a[i].data[j]=-1;
     65             }
     66         }
     67     }
     68     
     69     
     70     for(int i=0; i<n; i++)
     71     {
     72         if(!vi[i])
     73         {
     74             return i;//返回根的下标 
     75         }
     76     }
     77 }
     78 
     79 
     80 void find(const node *a, const int root)//从上到下、从左到右输出叶子结点 
     81 {
     82     queue<int> q;
     83     q.push(root); 
     84     int x=0;//以下用于表示队头元素（当前结点） 
     85     bool flag=true;//以下用于判断是否为第一次输出
     86     bool empty=true;// 以下用于判断当前结点是否为叶子节点 
     87     
     88     
     89     while(!q.empty())
     90     {
     91         x=q.front();
     92         q.pop();
     93         
     94         
     95         empty=true;
     96         for(int i=0; i<2; i++)
     97         {
     98             if(a[x].data[i]!=-1)
     99             {
    100                 empty=false;//若不是-1则该结点还有孩子结点，该结点为非叶子节点 
    101                 break;
    102             }
    103         }
    104         
    105         
    106         if(!flag && empty)
    107         {
    108             cout<<' '<<x;
    109         }
    110         else if(flag && empty)
    111         {
    112             cout<<x;
    113             flag=0;
    114         }
    115         
    116         
    117         if(!empty)
    118         {
    119             for(int i=0; i<2; i++)
    120             {
    121                 if(a[x].data[i]!=-1)
    122                 {
    123                     q.push(a[x].data[i]);//将刚刚出队的结点(若该结点不为叶子节点)的孩子依次从左到右入队 
    124                 }
    125             }
    126         }
    127     }
    128 }

可以看到，只要在进行层次遍历的时候，顺便加个判断条件，　　判断该结点是否为叶子节点，若为叶子结点，则输出，若不是，则继续遍历　　就可以了。

这题之后，我对用队列实现层次遍历有了更深刻的印象。

**二、同时谈谈你对上次制定目标的完成情况**

完成了一半......只看了30页，50多页之后就开始说类了，还是有点懵，我自己对之前知识掌握不够牢固的问题。

**三、以及接下来的目标**

学好第6章的图，将书上有关第6章的图的应用都看看看好多好多好多遍，要做到深刻理解！

转载于:https://www.cnblogs.com/ymj19/p/10809462.html

[1627872-20190504193003120-680323887.png]: /images/20211122/b3d607a57ec1407abfd8d72a5335f857.png
[1627872-20190504193012705-175162099.png]: /images/20211122/e6251e929d0d4266bc9ef47447f9682c.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211122/5ffbe0f834c14723b5693194d409c641.png