《数据结构与面向对象程序设计》课程总结

• 课程内容总结

  •  绪论

    • Java程序设计语言
    • 程序开发
    • 问题求解
    • 软件开发行为
    • 面向对象程序设计

            我们首次接触Java是从其程序设计语言和基本的程序开发过程开始的。我们了解程序编译运行的步骤，理解问题求解的一般方法，了解软件开发的一般过程，面向对象技术相关概念，面向对象的程序设计，类是对象的蓝图，虚拟机介绍与安装，IDEA介绍与安装。还提到了面向对象程序设计的三大特征：封装、继承、多态。封装的意义：1、封装的意义在于保护或者防止代码（数据）被我们无意中破坏。2、保护成员属性，不让类以外的程序直接访问和修改；3、隐藏方法细节。继承的意义：主要实现重用代码，节省开发时间。多态的三个条件:1.继承的存在(继承是多态的基础,没有继承就没有多态)；2、子类重写父类的方法(多态下调用子类重写的方法)3、父类引用变量指向子类对象(子类到父类的类型转换)。实现多态方式：1.接口多态性；2.继承多态性；3.通过抽象类实现的多态性。多态的好处：1.可替换性；2.可扩充性；3.接口性；4.灵活性；5.简化性。

  •  数据和表达式

    • 字符串
    • 变量和赋值
    • 基本数据类型
    • 表达式
    • 数据转化
    • 读输入数据

      1.字符串

      • print及println方法
      • 字符串连接
      • 转义字符
      • 变量和赋值

      2.变量和赋值

      • 赋值语句
      • 常量
      • 基本数据类型
      • 整型和浮点型
      • 字符类型
      • boolean类型

      3.基本数据类型

      • 8 种基本类型(byte,short,int,long,float,double,boolean,char)

      • 6种数字类型(byte,short,int,long,float,double)

      • 4种整数类型(byte,short,int,long)，

      4.表达式

      • 算术运算符
      • 运算符优先级
      • 自增及自减运算符
      • 赋值运算符

      5.数据转化

      • 转换技术
      • 基本类型之间的转换：加宽转换与缩窄转换。

      6.输入数据

      • Scanner类的输入

      7.字符串

      • print及println方法
      • 字符串连接
      • 转义字符
      • 变量和赋值

      8.变量和赋值

      • 赋值语句
      • 常量
      • 基本数据类型
      • 整型和浮点型
      • 字符类型
      • boolean类型

      9.基本数据类型

      • 8 种基本类型(byte,short,int,long,float,double,boolean,char)

      • 6种数字类型(byte,short,int,long,float,double)

      • 4种整数类型(byte,short,int,long)，

      10.表达式

      • 算术运算符
      • 运算符优先级
      • 自增及自减运算符
      • 赋值运算符

      11.数据转化

      • 转换技术
      • 基本类型之间的转换：加宽转换与缩窄转换。

      12.输入数据

      • Scanner类的输入

      在本章节中，我们跟着王老师学习了java中简单的操作以及基本原理，如数据类型、类型转换之类的。

  •  使用类和对象

    • 创建对象
    • String类
    • 包
    • Random类
    • Math类
    • 格式化输出
    • 枚举类型
    • 包装类

           在java中，类是一个模板，它描述一类对象的行为和状态，它表示一个共性的产物，类之中定义的是属性和行为（方法）；而对象是类的一个实例，是一种个性的表示，表示一个独立的个体，每个对象拥有自己独立的属性，依靠属性来区分不同对象。

           可以一句话来总结出类和对象的区别：类是对象的模板，对象是类的实例。类只有通过对象才可以使用，而在开发之中应该先产生类，之后再产生对象。类不能直接使用，对象是可以直接使用的。

  •  条件和循环

    • 布尔表达式
    • if语句
    • 数据比较
    • switch语句
    • while语句
    • 迭代器
    • do语句
    • for语句

    这章感觉没啥好说的，毕竟循环语句判断语句在c里就已经很熟悉了，本章也主要侧重如何在Java中实现循环判断功能。

  •  编写类

    • 再谈类和对象
    • 类的剖析
    • 封装
    • 方法的剖析
    • 静态类成员
    • 类方法
    • 方法设计
    • 方法重载
    • 测试
    • 调试

  •  数组

    • 数组元素
    • 数组的声明及使用
    • 对象数组
    • 命令行参数
    • 变长参数表
    • 二维数组

  •  继承

    • 创建子类
    • 方法的重写
    • 类层次
    • 可见性
    • 设计继承

  •  多态

    • 后绑定
    • 通过继承实现多台
    • 接口
    • 通过接口实现多态

  •  异常

    • 异常处理
    • 不捕获异常
    • try-catch语句
    • 异常传播
    • 异常类的层次
    • I/O异常

  •  递归

    • 递归思想
    • 递归程序设计
    • 使用递归
          递归是编程中一种非常重要的思想，常言道“要理解递归，就得先了解什么是递归”这句话其实就是一个递归，本章中介绍了递归思想，我们学习了一些简单的利用递归设计的程序。

  •  算法分析

    • 算法效率
    • 增长函数和打O符号
    • 比较增长函数

  •  查找与排序

    • 查找
    • 排序
    • 分析查找及排序算法

    本章的查找和排序算法一大堆，作业也很多，但学习到了很多关于计算机数据处理、存放方面的知识

    查找

    • 线性查找

    • 二分查找：从中间开始，要求表是有序的，每次比较后可以减少查找池中的一半元素。

    • 分块查找：先二分查找，再线性查找。

    • 哈希查找：直接通过关键字找到存储地址，是的查找时间可以常数级。

    • 散列查找

    排序

    • 选择排序：分别将每个值放在排好序的最终位置，从而完成一组值的排序。

    • 插入排序：将一个具体的值插入到表中已有序的子系列中，从而完成一组值的排序。

    • 冒泡排序：重复地比较表中的相邻元素，如果它们不符合要求则交换他们。

    • 快速排序：根据一个任意选定的划分元素来对表进行划分，然后再递归地对划分元素两边的字段进行排序，从而完成对表的排序。

    • 归并排序：递归地对分表，知道每个子表只含有一个元素时为止，然后再将子表按序合并，从而完成对表的排序。

    分析查找及排序算法

    确实很多，嗯。

  •  栈

    • 集合的介绍
    • 栈集合
    • 继承、多态和泛型
    • 栈的ADT
    • 使用栈：计算后缀表达式
    • 异常
    • 使用数组实现栈
    • ArrayStack类
    • 将引用作为链
    • 管理链表
    • 没有链的元素
    • 使用链实现栈
    • 使用java.util.Stack类实现栈
    • 包

    本章所介绍的数据结构是非常重要的栈（stack），它是一种有序特殊的线性表，只能在栈顶执行插入和删除操作，最后插入的元素将第一个被删除，因此栈也称为FILO的线性表。我们还学习了栈的基本操作如创建栈，判空，入栈，出栈，获取栈顶元素等。

  •  队列

    • 队列是一个线性集合，它在一端添加元素，在另一端删除元素————先进先出。

    • 接口中一般有以下功能：

    1. enqueue：将元素插入到队尾。
    2. dequeue：从队头删除元素。
    3. first：检测队头的元素。
    4. isEmpty：判定队列是否为空。
    5. size：断定队列中的元素个数。

                                  队列也是种线性表（特殊的），因为它只能对表的前端进行删除操作，而在表的后端进行插入操作，和栈一样，队列是一种操作受限制的线性表。

                                  算法简单，理解上和栈一样没什么难度。

• •  树

    • 树
    • 树的遍历
    • 数的实现策略
    • 二叉树的实现
    • 决策树 树是一种数据结构，它是由n(n≥1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树。
      虽然树的数据结构简单明了，但这算法可是一点也不简单，

  •  二叉排序树

    • 二叉查找树
    • 二叉查找树的实现
    • 平衡二叉查找树

    二叉查找树

    • 左子树小于结点，右子树大于结点；
    • 最有效的二叉查找树是平衡的；
    • 可以对二叉树进行旋转使其达到平衡；

  •  堆和优先队列

    • 堆
    • 堆的实现
    • 堆排序
    • 优先队列

    堆

    • 可以使用数组形式，用顺序结构存储最为合适。

    • 最小堆（小顶堆）

    • 最大堆（大顶堆）

    本章主要介绍了查找树的概念，以及典型的二叉查找树的链式实现。

  •  图

    • 无向图
    • 有向图
    • 带权图
    • 常用的图算法
    • 图的实现策略
    图的学习挺痛苦的，因为难度一下子拉高了好几个层次，本章的作业和实验也很难，唉。
    图也是一种非线性数据结构，并且每个数据元素之间可以任意关联。正是任意关联性，导致了图结构中数据关系的复杂性。顶点和边是它的两个组成部分。有向图无向图，带权的不带权的，加上各种算法敲代码堪称坐牢。

    二、总结所做过的作业

    • 作业1：安装虚拟机
    • 作业2：《数据结构与面向对象程序设计》第一周作业
    • 作业3：编写简单的类
    • 作业4：类继承作业
    • 作业5：复数计算器
    • 作业6：栈实践
    • 作业7：二分查找（折半查找）实践
    • 作业8：二叉树的建立和层序遍历法实践
    • 作业9：哈夫曼编码实践
    • 实践1：使用VIM编辑器编写Java程序
    • 实践2：查找及ASL作业
    • 实践3：排序
    • 实践4：树-计算题
    • 实践5：哈夫曼编码测试
    • 实践6：地图染色问题
    • 实践7：最小生成树测试
    • 实践8：Dijkstra(迪杰斯特拉)算法测试   好多。。。

       

       

    三、实验报告总结

    实验一：linux命令行和编写简单java程序

     

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

    2、练习Linux基本命令；

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

    4、编写简单的Java程序。

           
    

     

     

    实验二：编写简单的计算器
    

     1.实验内
    （1） 编写简单的计算器，完成加减乘除模运算。
    （2） 要求从键盘输入两个数，使用判定语句选择一种操作，计算结果后输出，然后使用判定和循环语句选择继续计算还是退出。
    （3） 编写测试代码，测试验证。（https://www.cnblogs.com/rocedu/p/4472842.html）      

     

    实验三：面向对象程序设计
    

    • 初步掌握单元测试和TDD
    • 理解并掌握面向对象三要素：封装、继承、多态
    • 初步掌握UML建      

     

     

     

    实验四：Java Socket编程
    

     1.实验内容

    （一）Java Socket编程

    1.学习蓝墨云上教材《Java和Android编程》“第16章 输入/输出 ”和“第22章 网络”，学习JavaSocket编程
    2.结对编程。结对伙伴A编写客户端SocketClient.java，结对伙伴B编写服务器端。
    3.截图加学号水印上传蓝墨云，代码push到码云，并撰写实验报告。

    （二）Java和密码学

    参考 http://www.cnblogs.com/rocedu/p/6683948.html

    以结对的方式完成Java密码学相关内容的学习（帖子中所有代码和相关知识点需要学习）。提交学习成果码云链接和代表性成果截图，要有学号水印。

    （三）编写有理数/复数计算器

    结对编程，结对伙伴A编写有理数计算器。结对伙伴B编写复数计算器。截图加水印上传蓝墨云，代码push码云。
    

    （四）远程有理数计算器

    结对编程，结对伙伴A编程实现客户端，结果伙伴B实现服务器端。
    客户端通过键盘输入一个有理数计算的公式（例如：1/4 + 1/6 = ）,并把该公式以字符串的形式发送给伙伴B（服务器端），服务器端根据字符串计算出结果为5/12,并把结果返回给客户端A，A收到结果后输出结果。截图加水印上传蓝墨云，代码push码云。
    

    （五）远程复数计算器

    结对编程，结对伙伴B编程实现客户端，结果伙伴A实现服务器端。
    客户端通过键盘输入一个有理数计算的公式（例如：1/4 + 1/6 = ）,并把该公式以字符串的形式发送给伙伴A（服务器端），服务器端根据字符串计算出结果为5/12,并把结果返回给客户端B，B收到结果后输出结果。截图加水印上传蓝墨云，代码push码云。
    注意实验四（4）和实验四（5），一个人不能仅实现客户端，必须实现一个客户端和服务器，否则两个实验均不得分！！！

    （六）实验报告

    在规定时间前发表博客，标题“学号 实验四 《数据结构与面向对象程序设计》实验报告”

        

     

     

     

     

    实验五和六：线性结构及链表
    

    1.链表练习，要求实现下列功能：

    • 通过键盘输入一些整数，建立一个链表；
      这些数是你学号中依次取出的两位数。 再加上今天的时间。
      例如你的学号是 20172301
      今天时间是 2018/10/1， 16：23：49秒
      数字就是
      20， 17，23，1， 20， 18，10，1，16，23，49
      打印所有链表元素， 并输出元素的总数。
      在你的程序中，请用一个特殊变量名来纪录元素的总数，变量名就是你的名字。 例如你叫 张三， 那么这个变量名就是
      int nZhangSan = 0; //初始化为 0.
      做完这一步，把你的程序签入源代码控制（git push）。

    2.链表练习，要求实现下列功能：

    • 实现节点插入、删除、输出操作；
      继续你上一个程序， 扩展它的功能，每做完一个新功能，或者写了超过10行新代码，就签入代码，提交到源代码服务器；
      从磁盘读取一个文件， 这个文件有两个数字。
      从文件中读入数字1， 插入到链表第 5 位，并打印所有数字，和元素的总数。 保留这个链表，继续下面的操作。
      从文件中读入数字2， 插入到链表第 0 位，并打印所有数字，和元素的总数。 保留这个链表，并继续下面的操作。
      从链表中删除刚才的数字1. 并打印所有数字和元素的总数。

    3.链表练习，要求实现下列功能：

    • 使用冒泡排序法或者选择排序法根据数值大小对链表进行排序；
      如果你学号是单数， 选择冒泡排序， 否则选择选择排序。
      在排序的每一个轮次中， 打印元素的总数，和目前链表的所有元素。
      在（2）得到的程序中继续扩展， 用同一个程序文件，写不同的函数来实现这个功能。 仍然用 nZhangSan （你的名字）来表示元素的总数。
    
    

           

     

     

     

    实验七：查找与排序
    

    1.定义一个Searching和Sorting类，并在类中实现linearSearch,SelectionSort方法，最后完成测试。要求不少于10个测试用例，提交测试用例设计情况（正常，异常，边界，正序，逆序），用例数据中要包含自己学号的后四位提交运行结果图。

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

    3.参考http://www.cnblogs.com/maybe2030/p/4715035.html ，学习各种查找算法并在Searching中补充查找算法并测试提交运行结果截图

    4.实现排序方法等(至少3个)测试实现的算法（正常，异常，边界）提交运行结果截图（如果编写多个排序算法，即使其中三个排序程序有瑕疵，也可以酌情得满分）

    5.编写Android程序对实现各种查找与排序算法进行测试提交运行结果截图推送代码到码云（选做，额外加分）

        

     

     

     

    实验八：树

    1.参考教材PP16.1,完成链树LinkedBinaryTree的实现（getRight,contains,toString,preorder,postorder）
    用JUnit或自己编写驱动类对自己实现的LinkedBinaryTree进行测试，提交测试代码运行截图，要全屏，包含自己的学号信息
    课下把代码推送到代码托管平台

    2.基于LinkedBinaryTree，实现基于（中序，先序）序列构造唯一一棵二㕚树的功能，比如给出中序HDIBEMJNAFCKGL和后序ABDHIEJMNCFGKL,构造出附图中的树
    用JUnit或自己编写驱动类对自己实现的功能进行测试，提交测试代码运行截图，要全屏，包含自己的学号信息
    课下把代码推送到代码托管平台

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

    4.输入中缀表达式，使用树将中缀表达式转换为后缀表达式，并输出后缀表达式和计算结果（如果没有用树，正常评分。如果用到了树，即使有小的问题，也酌情给满分）
    提交测试代码运行截图，要全屏，包含自己的学号信息

       

     

     

     

    实验九：图

    一、实验内容

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