20202306 2020-2021-2《数据结构与面向对象程序设计》课程总结

• 课程内容总结

课程总结

　　第一章：引言——java程序设计入门

1. java是一种面对对象的编程语言。
2. java编程语言中，程序是由一个及以上的类所组成，类中包含一个及以上个方法。
3. 我们习惯上以“骆驼体”命名我们的类，尤其是是由多个单词构成的时候更加明显，如：public class JavaSocket。
4. 类名下我们开始书写可运行的方法体：public static void main（String[ ] args）{}，即方法头psvm，花括号中书写方法体。
5. 一个有良好习惯的程序员在程序中也会用注释注代码的含义：“//”或“/* */”或“/** */”。
6. 类名不应以数字开头，由于java对大小写敏感，所以Abc与abc是不同的两个类。
7. 编写和运行java程序，需要相应的开发工具包JDK，后续也会运用到其他的插件辅助。

　　第二章：数据与表达式

1. 字符串的输出我们采用System.out.print/println("XXX")；来表示。
2. 数据类型分为数值型（byte、int、float等）、字符型（char）、布尔型（Boolean等）。
3. 算数表达式包括：+-*%/（加减乘除模），要注意前后的数据类型是否需要强制转换。
4. 常量、变量的定义：int AB = 10；（定义一个变量AB）final int MAX_AB=10；（定义一个常量MAX_AB）
5. 符号的优先级。
6. 其他运算符：++、--、+=等。
7. 类型转换与强制类型转换。
8. debug调试，设置断点。

　　第三章：类与对象

1. String类：String用于操作字符串，但需要提前声明String name=new String。然后才可以使用，如，String name=“lijincheng”；
2. 在java中文件通常放在包中用于归纳整理与调用，并放在java标准库中。调用时import java.util.*；import java.lang.*等。
3. 随机数的生成：Random类。
4. 数学方法的使用：Math类。
5. 枚举方法： enum XXX{a，b，c}；
6. 包装器类：Integer.parselnt( )  Integer.toHexString( )

　　第四章：OO设计

1. OO是指“Object Oriented”，即面对对象的设计模，包括封装、继承、多态三大类，是java程序设计中的重中之重。
2. 首先，在程序设计前，要明确设计目的，然后进行伪代码的编写，最后编写程序代码，测试代码，测试无误后，才能进行使用。
3. 类间关系：若是一个类需要另一个类中包含有的方法，那么可以根据情况使用静态方法或非静态方法进行实现，如：B.xxx()——直接调用，静态方法；B b = new B（）；b.xxx( );——声明后使用，非静态方法。
4. java中常用到接口的使用。抽象的方法使用abstract，实现接口使用implement，类若是调用接口，便可以使用接口中的方法了。
5. 我们所使用的常用接口有一下两个：Comparable和Iterator。
6. 封装：就是将抽象性的接口的实现细节部分包装、隐藏的过程。修改属性的可见性来限制对属性的访问（一般限制为private）。通常情况下，我们会使用到被称为getter和setter的方法进行传输。
7. this关键字的使用时调用自己类中的方法，避免与其他类中相同名称的方法搞混。
8. 继承：就是使得子类对象具有父类的方法。在 Java 中通过 extends 关键字可以申明一个类是从另外一个类继承而来的。需要注意的是 Java 不支持多继承，但支持多重继承。
9. 多态：就是在同一个接口下，能够使用不同的实例而执行不同操作。

　　第五章：线性表

1. 在数据结构中，其中逻辑结构是程序编写的基石和命脉。
2. 线性表是具有相同特性（数据类型）的元素构成的有限序列。
3. 结点类型队列定义为：LinearNode<T>；链队列类型队列定义为：LinkedQueue<T>。其中front表示队头指针，rear表示队尾指针。
4. 队列是一段连续的空间以存储元素，因此我们设定了两个指针进行指示操作。在非空队列中，front指向队头元素，rear指向队尾元素的下一个空位。
5. 如果队列是循环的，那么移动指针的时候要i=（i+1）%MAX。
6. 线性表的实现可以用数组来完成，因为线性表中的元素可以随意添加，因此数组中的元素需要不断移动。与之匹配的是ArrayList类，这是一个可以动态修改的数组，与普通数组的区别就是它是没有固定大小的限制，我们可以添加或删除元素。其中的方法有add( )——添加元素；get( )——访问元素；set( )——修改元素；remove( )——删除元素；size( )——计算大小；
7. 而在链式的线性表中，我们使用到的是LinkedList类，其用法基本上与ArrayList一致，不过在几种情况下提供了更高效的方法，如，addFirst( )——在列表开头添加元素；removeFirst( )——在列表开头移除元素；getFirst( )——获取头部元素；getLast( )——获取列表结尾元素等。

　　第六章：栈

1. 栈是一种线性集合，其元素的添加和删除都是在同一侧进行了，特性是先进后出，后进先出（LIFO）的原则，即，只允许在表尾插入和删除的线性表。我们通常将允许插入和删除的一段叫做栈顶（top），而将另一端称为栈底（bottom）。类似于一个没有盖，但有底的圆筒，你的加入和删除只能从上端先进行。
2. 表达式有三种标识法，分别是前、中、后缀表示法。其中，前缀表示法的操作是，连续出现的两个操作数和在它们之前且紧靠着的运算符构成一个最小表达式。后缀表示法是指运算符的顺序就是表达式的运算顺序。中缀表达法是一个通用的算术或逻辑公式表示方法， 操作符是以中缀形式处于操作数的中间。
3. 栈的优势是，存取速度快，且栈之间的数据可以共享；缺点是缺乏灵活性，存取有严格的要求。
4. 栈的初始化命令为：stack，基本操作和命令有empty( )——判断是否为空；peek( )——取栈顶值；push(object)——入栈；pop( )——出栈。

　　第七章：查找与排序

1. 查找是根据所确定的数在表中寻找等同的记录或元素的过程。常用的方法有线性查找法、二分查找法、分块查找法、索引查找法。
   
   • 线性查找法，也就是顺序查找法，在表中按照顺序一个一个地对比是否相同。这个过程需要遍历所有的元素，也因此只适用于元素数较少的或者没有顺序的未排序的表。
   • 折半查找，也叫二分查找。首先要将数据进行排序，形成有序表。将目标元素与正中元素比较，若小于则在左半部查找，否则在右半部查找。这样每次可以缩小1/2的范围，直到查到或查找失败。
   • 分块查找，是折半查找和顺序查找的改进方法。分块查找要求把一个大的线性表分解成若干块，每块中的节点可以任意存放，但块与块之间必须排序。先选取各块中的最大关键字构成一个索引表；step2 查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中。
   • 哈希表算法，它可以提供快速的插入操作和查找操作。不论哈希表中有多少数据，插入和删除，只需要接近常量的时间即0(1）的时间级。它的操作是在记录的存储地址和它的关键字之间确立确定关系，也因此可能会出现冲突的情况。
     • 在哈希表构造时，有五种常见方法：直接定址法、数字分析法、平方取中法、折叠法、除留余数法，其中我们重点掌握的是除留余数法，也就是用关键字除以不大于散列表长度的数所得的余数为哈希地址。
     • 解决出现的冲突的异常的时候，我们需要掌握两种方法：开放定址法，及从发生冲突的单元开始，按一定的次序，找出表中空闲的存储的安远，并将冲突的待插入关键字存储到该空白区域，即Hi=(H(key)+di)MOD m；链地址法，将所有相互发生冲突的同义词存储到同一个单链表中，形成一个横纵交错的链表。
2. 由于需要量化查找的效率，我们引进了ASL（平均查找长度），ASL=PiCi累加运算，若每一个元素被查找的概率相同，则查找每一个元素所需的比较次数之和再平均就是ASL。
3. 排序，也就是将无序的序列按照从小到大或从大到小进行排序，使之形成一个有序的、便于查找等功能的序列。
   • 插入排序：将需排序的元素，一个一个插入到有序序列或空序列的适当位置。
     
     • 直接插入：设定哨兵，从后向前依次比较，然后安插在合适的两个元素之间。
     • 折半插入：与折半查找的思路相类似
     • 2路插入
     • 希尔排序
   • 交换排序：比较两个元素的大小，按照排序要求判断是否需要交换位置。
     • 冒泡排序
     • 快速排序
   • 选择排序：选择需排序的合适元素放在排序序列的最后位置。
     • 简单选择排序
     • 堆排序
   • 基数排序：根据数据的不同位数（权重）的大小，得到排序的结果。
   • 归并排序：将元素从中分开，再分开……如此往复，直到所有部分的元素个数都为1，再从最底层按顺序逐步合并排序好的数列。
4. 与查找算法中的ASL相似的是，排序算法衡量一个方法好坏的标准是时间效率、空间效率和稳定性。

　　第七章：树与二叉树

1. 树是由n个结点组成的有限集合。
2. 结点的层次
3. 树的深度
4. 有序/无序树
5. 基本操作：查找类、插入类、删除类
   • getRoot( )；——返回根结点
   • getParent( )；——返回父结点
   • getChildCount( )；——返回孩子结点数
   • getFirstChild( )；——返回第一个孩子结点
   • getNextChild( )；——返回下一个兄弟结点
   • isEmpty( )；——判定树是否为空
   • depth( )；——求深度
   • traverse( )；——遍历
   • tree( )；——初始化一棵空树
   • delete( )；——删除操作
6. 存储结构：双亲表示法、孩子表示法、双亲孩子表示法、孩子兄弟表示法。
7. 二叉树：子树有左右之分，结点度数至多为2。
8. 满二叉树：每层都“充满”结点的二叉树。
9. 完全二叉树：满二叉树去掉最下层最右边若干结点。
10. 二叉排序树：左子树小于父结点，右子树大于或等于父结点。
    • 二叉排序树的生成、删除
    • 二叉排序树的查找
11. 平衡二叉树、二叉排序树的平衡化（AVL树）
12. 编码：定长编码、变长编码、前缀码
13. 最优二叉树：平均编码长度最短。最优前缀码——哈夫曼编码。

　　第八章：图

1. 无向图：任意两个顶点之间的边都是无向边。
2. 有向图：图中所有边都是有向边。
3. 邻接点：边的两个顶点。
4. 边的权：图的边带有与边相关的数据。
5. 入度、出度、路径、回路、子图、连通图、非连通图、生成树
6. 图的表示法：邻接矩阵（无向图邻接矩阵、有向图邻接矩阵、网的邻接矩阵）、边集数组、邻接表、十字链表、邻接多重表
7. 图的遍历：
   • 广度优先遍历：从一个顶点开始，优先遍历周围区域。
   • 深度优先遍历：从一个顶点开始，优先遍历源节点拓展出的可达结点。
8. 最短路径问题：Kruska算法、Dijkstra算法
9. 拓扑排序

作业总结

• 作业1：封装继承多态重写重载文件字符字节读写（点击标题进入网址，下同）

　　　　编写一组程序，要体现一下知识点：
　　　　　　（1）继承
　　　　　　（2）多态
　　　　　　（3）重写
　　　　　　（4）重载
　　　　　　（5）目录创建
　　　　　　（6）文件创建
　　　　　　（7）字节流读写
　　　　　　（8）字符流读写

• 作业2：实现自己的ArrayList

　　　　　1.编写自己的ArrayList类
　　　　　　要求：实现增加、删除、修改、查找、判断是否为空、返回list长度等操作。
　　　　　2.测试。

• 作业3：ArrayStack测试

　　　　（1）撰写自己的类；
　　　　（2）提供StackADT，ArrayStack（框架），实现ArrayStack里面的剩余方法；
　　　　（3）编写测试类，测试所写的方法是否正确。

• 作业4：栈应用—进制转换

　　　　算法基于原理：     N = (N div d)×d + N mod d  
　　　　例如：（1348)10 = (2504)8 ，其运算过程如下：
      　　　　  N        N div 8        N mod 8
     　　　   1348        168              4
       　　　　168         21              0
        　　 　21          2               5
           　　2           0               2

要求输入一个十进制数，转换成任意进制数并输出。

• 作业5：最小生成树测试

　　　　1.画出Prim算法的最小生成树的生成过程
　　　　2.画出Kruscal算法的最小生成树的生成过程
　　　　3.计算最小权值

• 作业6：快速排序测试　

　　　　3,44,38,5,47,15,36,26,27,2,46,4,19,50,48
　　　　快速排序
　　　　给出第一趟快速排序的结果！

• 作业7：最后一次测试

实验报告链接汇总

　实验一：linux基础与java开发环境（点击进入网址）

　　　　　　1、基于命令行进行简单的Java程序编辑、编译、运行和调试。

　　　　　　2、练习Linux基本命令；

　　　　　　3、学习Java程序的JDB调试技能：https://www.cnblogs.com/rocedu/p/6371262.html

　　　　　　4、编写简单的Java程序。

　实验二：Java基础（数据/表达式、判定/循环语句）

　　　　　　1、 编写简单的计算器，完成加减乘除模运算。

　　　　　　2、要求从键盘输入两个数，使用判定语句选择一种操作，计算结果后输出，然后使用判定和循环语句选择继续计算还是退出。
　　　　　　3、编写测试代码，测试验证。（https://www.cnblogs.com/rocedu/p/4472842.html）

　实验三：数据结构与面对对象程序设计

　　　　　　1、 初步掌握单元测试和TDD
　　　　　　2、 理解并掌握面向对象三要素：封装、继承、多态
　　　　　　3、初步掌握UML建模
　　　　　　4.、完成蓝墨云上 （1）-（5）实验。

　实验四：JavaSocket 编程

　　　　　　1、Java Socket编程

　　　　　　2、Java和密码学：参考 http://www.cnblogs.com/rocedu/p/6683948.html

　　　　　　3、编写有理数/复数计算器

　　　　　　4、远程有理数计算器

　　　　　　5、远程复数计算器

　　　　　　6、实验报告

　实验五&六：线性结构与链表

　　　　　　1、链表练习，要求实现下列功能：通过键盘输入一些整数，建立一个链表；这些数是你学号中依次取出的两位数。 再加上今天的时间。打印所有链表元素， 并输出元素的总数。

　　　　　　2、链表练习，要求实现下列功能：实现节点插入、删除、输出操作；继续你上一个程序， 扩展它的功能；从磁盘读取一个文件，完成相关操作。

　　　　　　3、链表练习，要求实现下列功能：用冒泡排序法或者选择排序法根据数值大小对链表进行排序；

　　　　　　4、在android上实现实验（1）和（2）

　　　　　　5、在android平台上实现实验（3)

　实验七：查找与排序

　　　　　　1、定义一个Searching和Sorting类，并在类中实现linearSearch,SelectionSort方法，最后完成测试。

　　　　　　2、重构你的代码

　　　　　　3、把Sorting.java Searching.java放入 cn.edu.besti.cs2023.（姓名首字母+四位学号） 包中（例如：cn.edu.besti.cs1823.G2301）重新编译，运行代码，提交编译，运行的截图（IDEA，命令行两种）

　　　　　　4、参考http://www.cnblogs.com/maybe2030/p/4715035.html ，学习各种查找算法并在Searching中补充查找算法并测试

　　　　　　5、实现排序方法等(至少3个)测试实现的算法（正常，异常，边界）

　　　　　　6、编写Android程序对实现各种查找与排序算法进行测试

　实验八：树

　　　　　　1、参考教材PP16.1,完成链树LinkedBinaryTree的实现，自己编写驱动类对自己实现的LinkedBinaryTree进行测试。
　　　　　　2、基于LinkedBinaryTree，实现基于（中序，先序）序列构造唯一一棵二㕚树的功能

　　　　　　3、对自己实现的功能进行测试。

　　　　　　4、自己设计并实现一颗决策树提交测试代码运行截图，要全屏，包含自己的学号信息课下把代码推送到代码托管平台

　　　　　　5、输入中缀表达式，使用树将中缀表达式转换为后缀表达式，并输出后缀表达式和计算结果

　实验九：图

　　　　　　1、初始化：根据屏幕提示（例如：输入1为无向图，输入2为有向图）初始化无向图和有向图（可用邻接矩阵，也可用邻接表），图需要自己定义（顶点个数、边个数，建议先在草稿纸上画出图，然后再输入顶点和边数）
　　　　　　2、图的遍历：完成有向图和无向图的遍历（深度和广度优先遍历）
　　　　　　3、 完成有向图的拓扑排序，并输出拓扑排序序列或者输出该图存在环
　　　　　　4、完成无向图的最小生成树（Prim算法或Kruscal算法均可），并输出
　　　　　　5、完成有向图的单源最短路径求解（迪杰斯特拉算法）

代码托管链接

• 给出statistic.sh的运行结果，统计本学期的代码量。

  总计：5275行，165kb（截图如下）

课程收获或不足

　　课程收获：

　　　　作为一门编程语言课的学习，毫无疑问地拓展了我的知识面和思维能力，不能说是完全掌握了java的奥秘，但也算是涉猎得详尽，动手操作也能有所理解和参透了。相比上学期的程序设计基础，这门面对对象程序设计难度高了不止一个层次，需要理解记忆的东西变多了，需要调试和使用的插件也在累积。我知道在今后的学习过程中，java作为如此重要的语言，一定会占据一席之地，甚至可能会是将来的饭碗。所以很庆幸在大学的黄金阶段遇到王志强老师，在课业的辅导细致透彻，答疑解惑耐心负责，也因此才能在课下练习和课上听讲上有所收获。大体上，我基本上了解了java程序运行的流程可编写的框架，可以基本解决编程问题，如文件读写、基本输入输出、数组、栈、链表、查找排序、树、图等基本操作。并且在很大程度上，强化了我的理科思维和思维能力，这比单纯的数学思考要更加实际，且更加增进了我看待事物和世界的深度和广度。再者，自学能力获得了极大的提高，其实任何一门学科都是这样的，更多的内容还需要课下琢磨、多加练习，也因此学习期间参考了不少书目以及B站教学视频、云班课资源等等，在此基础上受益匪浅，提高了学习能力，培养了学习热情。