201723282018-2019《java软件结构与数据结构》第六周学习总结(代码片段)

lxy462283007 lxy462283007     2023-01-11     693

关键词:

20172328 2018-2019《Java软件结构与数据结构》第六周学习总结

概述 Generalization

本周学习了第十章:非线性集合与数据结构--树。主要讨论了树的使用和实现,以及考察实现和使用树的实例。

教材学习内容总结 A summary of textbook

  • 树(tree):树是一种非线性结构,其元素被组织成了一个层次结构。下面是树的术语,了解一下吧!
    • 树有一个包含结点(node)边(edge)的集构成,其中的元素被储存在这些结点中,边则将一个结点和另一个结点连接起来。
    • 根(root):位于该树顶层上的唯一结点。一棵树只有一个根节点。
    • 孩子(children):位于树中较低层的结点是上一层结点的孩子。
    • 兄弟(sibling):同一双亲的多个孩子互称为兄弟。其一定位于同一层级上。
    • 叶子(leaf):没有任何孩子的结点称为孩子。
    • 内部结点(internal node):一个至少有一个孩子的非根节点称为一个内部结点。
    • 根是树中所有结点的最终祖先(ancestor),沿着起始自某一特定结点的路径可以到达的结点是该结点的子孙(descendant)
    • 路径长度(path length):结点的层也就是从根结点到该结点的路径长度。
    • 高度(height):是指从根到叶子之间最远路径的长度。
  • 树的分类: 对树进行分类最重要的一条标准是按度(order)分类,另一种方式是看该树平衡与否
    • 度即为树中任一结点可以具有的最大孩子数目。对结点所含有的孩子无限制的树称为广义树,每一结点限制不超过n个孩子的树称为n元树,而进行二胎政策的也就是结点最多有两个孩子的树称为二叉树
    • 对树进行分类的另一种方式是该树平衡与否。如果树的所有叶子都位于同一层或者至少是彼此相差不超过一个层,就称之为平衡的。
    • 完全树:如果某树是平衡的,且底层所有叶子都位于树的左边,则认为该树是完全的。
      • 完全二叉树是:在每个k层上都具有2的k次方个结点,最后一层除外,在最后一层必须是最左边结点。
    • 满树:如果一颗n元树的所有叶子都位于同一层且每一结点要么是一片叶子要么正好具有n个孩子,则称此树是满的。
  • 实现树的策略:链式结构实现和数组实现。
  • 树的数组实现之计算策略:一种可能的计算策略是将元素n的左孩子置于位置(2n+1),将右孩子置于位置(2(n+1))。
    • 缺点:如果我们存储的树是不完全的或者是相对完全的,则该数组会为不包含数据的树位置分配空间,这就浪费了大量的存储空间。
  • 树的数组实现之模拟链接策略:模拟链接策略允许连续分配数组位置而不用考虑该树的完全性。
    • 缺点:这种方式虽然能够使得元素连续的存储在空间中,不会浪费空间,但该方式增加了删除树中元素的成本,因为他要么需要对剩余元素进行移位来维持连续状态,要么需要保留一个空闲列表。
  • 对于树的分析:对于任何含有m个元素的平衡n元树,树的高度都将是logn(m),有了二叉查找树的排序性质后,就可以保证在最坏的情况下,查找一条从根到叶子的路径,且该路径不会长于logn(m)。
  • 遍历树的4种基础方法
    技术分享图片
    • 前序遍历(preorder traversal):从根结点开始,访问每一节点及其孩子。按照上图遍历结果就是 A、B、D、E、C。
    • 中序遍历(inorder traversal):从根结点开始,访问结点的左孩子,然后是该结点,再然后是任何剩余结点。按照上图遍历结果就是 D、B、E、A、C。
    • 后序遍历(posterorder traversal):从根结点开始,访问结点的孩子,然后是该结点。按照上图遍历结果就是 D、E、B、C、A。
    • 层序遍历(level-order traversal):从根结点开始,访问每一层的所有结点,一次一层。按照上图遍历结果就是 A、B、C、D、E。
  • 本章后面有关于几种遍历的代码实现(以下是前序遍历的实现和层序遍历的实现):
public Iterator<T> iteratorPreOrder() 
    
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        preOrder(root, tempList);

        return new TreeIterator(tempList.iterator());
    

    protected void preOrder(BinaryTreeNode<T> node,
                            ArrayUnorderedList<T> tempList) 
    
        if (node != null)
        
            tempList.addToRear(node.getElement());
            preOrder(node.getLeft(), tempList);
            preOrder(node.getRight(), tempList);
        
    
public Iterator<T> iteratorLevelOrder()
                
                    ArrayUnorderedList<BinaryTreeNode<T>> nodes =
                            new ArrayUnorderedList<BinaryTreeNode<T>>();
                    ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
                    BinaryTreeNode<T> current;

                    nodes.addToRear(root);

                    while (!nodes.isEmpty())
                    
                        current = nodes.removeFirst();

                        if (current != null)
                        
                            tempList.addToRear(current.getElement());
                            if (current.getLeft() != null)
                    nodes.addToRear(current.getLeft());
                if (current.getRight() != null)
                    nodes.addToRear(current.getRight());
            
            else
                tempList.addToRear(null);
        
        
        return new TreeIterator(tempList.iterator());
    
  • 二叉树の使用:表达式树:
    技术分享图片
  • 表达式树就是使用二叉树来计算后缀表达式,表达树的根及其内部结点包含着操作,且所有叶子也包含着操作数,对表达式的求值是从下往上的。链式结构实现优于数组结构实现,因为链式结构在将表达树组合成一颗新树时其复杂度为O(1),而要把两个数组归并,在最佳情况下其复杂度为O(n)。
  • 用链表实现二叉树
  • 具体内容看代码实现
  • 二叉树的性质:若二叉树的根结点位于第一层

    • 性质1:在二叉树的第i层最多有2的i-1方个结点(i>=1)
    • 性质二:深度为K的二叉树最多有2的k次方-1个结点(K>=1)
    • 性质三:对任何一棵二叉树,如果其叶结点个数为n0,度为2的结点数为n2,则有:
      n0 = n2 + 1
  • 完全二叉树的性质:
    • 性质1:具有n个结点的完全二叉树的高度为[log2(n)]+1 []代表取整
    • 性质2:如果将一棵有n个结点的完全二叉树自顶向下,同一层自左向右连续给结点编号1,2,3,···n,则对于任一结点i(1<i<=n),有:
      • 若i = 1,则该结点是树根,他没有双亲
      • 若2i > n,则编号为i的结点无左孩子,否则他的左孩子是编号为2i的结点
      • 若2i+1>n,则编号为i的结点无右孩子,否则其右孩子节点编号为2i+1;

教材学习中的问题和解决过程 Problem and countermeasure

  • 问题1:树的数组实现中的模拟链接策略没有看懂。?
  • 问题1的理解以及解决:通过老师上课的讲解,我对这个问题有了自己的理解。当确定好进入数组的顺序后,通过先来先服务的基准连续分配数组位置,而不是通过其在树中的定位将树元素指派到数组位置上。数组的每一个元素都是结点类,每一个结点存储的是该结点孩子的数组索引。
    技术分享图片

  • 问题2:ExpressionTreeOp类中的int型变量termType=1的用处是什么?当在ExpressionTree类中创建ExpressionTreeOp类的对象时没有具体的方法参数,但是已经可以判断出运算符和操作数,所以不明白。
  • 问题2的理解以及解决:其实这个int型变量termType就是在程序中判断操作符和操作数的一个中间值,在PostfixEvaluator中也有体现.
 if ((operator == '+') || (operator == '-') || (operator == '*') || 
                 (operator == '/'))
            
                operand1 = getOperand(treeStack);
                operand2 = getOperand(treeStack);
treeStack.push(new ExpressionTree 
                                  (new ExpressionTreeOp(1,operator,0), operand2, operand1));
                                  
else
            
                treeStack.push(new ExpressionTree(new ExpressionTreeOp
                                    (2,' ',Integer.parseInt(tempToken)), null, null));
                                              

代码实现时的问题作答 Exercise

  • 问题1:不知道如何实现linkedBinaryTree中的toString方法,不知道如何输出这棵树.
  • 问题1的理解以及解决:首先想用迭代器接解决,但是层序遍历调用的不是很正确,并且如何适当的把每一层分割开来,做出树的样子,这让我很苦恼。其实暂时还没解决。
  • 问题2:当时在写hight时,理解错误了,当时写的是while循环,一直在循环去找左子树,然后只计算了层数(以前的代码忘记截图了)
  • 问题2的解决:但是hight是最远路径,经过我和仇夏同学的讨论,郭恺同学、王文彬的提醒,我们应该去递归找最远的路径,这样来讲我们应该递归去找每一条线路,然后通过比较找到最长的路径返回。
  • 问题3:当时运行BackPainAnalyzer类时显示文件找不到。

技术分享图片

  • 问题3的解决:通过结对小组的讨论,加上路径就解决了这个问题。

技术分享图片

上周测试活动错题改正 Correction

  • 1.The Java Collections API contains _________ implementations of an indexed list.
    A .Two
    B .Three
    C .Four
    D .Five
  • 问题1的解答:本题答案选C。但是原因我找不到,因为列表可以分为有序列表、无序列表和索引列表但是JavaAPI中的索引列表有几种实现方式我还没有找到相关资料。有一篇关于API文档中List的解释(https://www.cnblogs.com/cuglkb/p/7027907.html)但是还是没有讲到这个问题,书本第120页也只是笼统的说了这个概念,并没有进行解释
  • 问题2:An interface name can be used to declare an object reference variable. An interface reference can refer to any object of any class that implements the interface.
    A .True
    B .False
  • 问题2的解答:答案是A,接口名可以用来声明一个对象引用变量,一个接口引用可以用来引用实现了该接口的任意类的任意对象。

    码云链接

代码量(截图)

技术分享图片

结对及互评Group Estimate

点评模板:

  • 博客中值得学习的或问题:
    • 20172301:
    • 20172304:
  • 本周结对学习内容:本周讨论了树的相关概念以及书上代码的理解,对如何输出一个树进行了探讨学习。

    其他(感悟、思考等,可选)Else

    非线性结构的学习开始是不是就意味着线性结构的学习先告一段落了呢,其实不然,在树的处处透露着链表和数组的身影。想要融会贯通,还得继续努力。

    学习进度条Learning List

    代码行数(新增/累积) 博客量(新增/累积) 学习时间(新增/累积)
    目标 5000行 30篇 400小时
    第一周 0/0 1/1 8/8
    第二周 621/621 1/2 12/20
    第三周 678/1299 1/3 10/30
    第四周 2734/4033 1/4 20/50
    第五周 1100/5133 1/5 20/70
    第六周 1574/6707 2/7 15/85

参考资料Reference

201723282018-2019《java软件结构与数据结构》第九周学习总结(代码片段)

201723282018-2019《Java软件结构与数据结构》第九周学习总结概述Generalization本周学习了无向图、有向图、带权图、常用的图算法、图的实现策略。教材学习内容总结Asummaryoftextbook图(graph)与树类似,图由结点和这些结点之间的连... 查看详情

201723282018-2019《java软件结构与数据结构》第八周学习总结(代码片段)

201723282018-2019《Java软件结构与数据结构》第八周学习总结概述Generalization本周学习了二叉树的另一种有序扩展?是什么呢?你猜对了!ヾ(?°?°?)??就是堆。本章将讲解堆的链表实现and数组实现,以及往堆中添加元素或从堆中删除... 查看详情

201723282018-2019《java软件结构与数据结构》第六周学习总结(代码片段)

201723282018-2019《Java软件结构与数据结构》第六周学习总结概述Generalization本周学习了第十章:非线性集合与数据结构--树。主要讨论了树的使用和实现,以及考察实现和使用树的实例。教材学习内容总结Asummaryoftextbook树(tree):... 查看详情

201723282018-2019《java软件结构与数据结构》第七周学习总结(代码片段)

201723282018-2019《Java软件结构与数据结构》第七周学习总结概述Generalization本周学习了第11章:二叉查找树。在本章中,主要探讨了二叉查找树的概念和各种二叉查找树实现,考察为二叉查找树添加和删除元素的算法以及维护平衡... 查看详情

java示例代码_爬上TypeMirror对象的层次结构树

java示例代码_爬上TypeMirror对象的层次结构树 查看详情

Java 套接字提前结束流

】Java套接字提前结束流【英文标题】:Javasocketgivingprematureendofstream【发布时间】:2011-02-0216:21:44【问题描述】:我正在设置一个连接到XMPP服务器的彗星服务器。以下是它的下降方式:客户端与Comet服务器连接,并且打开了一个... 查看详情

java -version,关于三个不同结果行的问题

】java-version,关于三个不同结果行的问题【英文标题】:java-version,questionaboutthreedifferentresultlines【发布时间】:2021-11-1908:56:03【问题描述】:我用Java编程已经有一段时间了,但实际上从来没有太在意版本控制。但是现在我检查... 查看详情

jmeter-察看结果树-响应数据,中文显示乱码问题处理

...t.encoding=utf-8修改配置后,重启生效 by:虾米 北京软件测试QQ1群:507088 北京软件测试跳槽群:450569 北京软件测试QQ2群:132142000 查看详情

logging模块全总结(代码片段)

...信息参考文档一、日志相关概念日志是一种可以追踪某些软件运行时所发生事件的方法。软件开发人员可以向他们的代码中调用日志记录相关的方法来表明发生了某些事情。一个事件可以用一个可包含可选变量数据的消息来 查看详情

java实现飞机大战小游戏|java入门结课作业(代码片段)

...据目录寻找自己需要的段落导语:本博客为个人整理Java学习记录帖,如有错误,感谢指正。系统学习,欢迎持续关注,后续陆陆续续更新Java后端项目,Java部分我不打算更新基础部分知识,会从JavaWeb开... 查看详情

jmeter——查看结果树——html使用

            ========================================================================================================     查看详情

java中&&和?表达式结合时会出现的坑

  首先是背景,刚放假回家比较闲,就把以前写了一些算法题的一个项目拿出来继续写,想把其中的插入排序修改成支持升序和降序的,然后就出现了这个坑,具体是这样的:  先把插入排序的代码摆出来吧。/***插入排序*@... 查看详情

如何正确迭代所有 BigQuery 结果行?

...给了我245217个结果,我可以在浏览器控制台。根据示例在Java 查看详情

java学习多线程:线程创建线程状态线程同步线程通信全总结(代码片段)

目录1、基本概念2、线程创建2.1、继承Thread类(重点)ThreadAPI2.2、实现Runnable接口(重点)Runnable接口API以上两种方式的比较:初识并发问题——买火车票龟兔赛跑问题:img2.3、实现Callable接口(了解ÿ... 查看详情

北航大讲堂结课报告

...过程中,突破外国技术垄断已经是势在必行。然而在航空软件方面还有许多问题等待我们去解决。2.   我国航空航天产业现状随着我国国民经济的持续发展和人民生活水平的不断提高,航空运输行业在国家经济、社会... 查看详情

java学习网络编程全总结——tcpudp多线程io流socket简易在线咨询聊天室java爬虫(代码片段)

...误区trimstartsWith在线咨询:两个人都可以发送1.8、URLJava爬虫----爬取网易 查看详情

对软件工程课程的期望

博文中将包含课程结课后学习到的能力的预期,对课程的期望,对课程项目的愿景规划:一、课程结课后学习到的能力的预期:  1.加强自身的领导力、影响力  2.可以增强与他人的协作能力和团队的领导能力  3.提高自己的... 查看详情

数据结结构(代码片段)

...结构=程序+算法</font>数据结构有什么用当我们使用着java官方给你提供的容器的时候,我们用起来是非常方便的,ArrayList其实是一个无线扩充的数据LinkedList其实是一个链表。现实世界中存储数据,我们要通过一些工具或者建... 查看详情