# javalab **Repository Path**: sduwz/javalab ## Basic Information - **Project Name**: javalab - **Description**: No description available - **Primary Language**: Java - **License**: MIT - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 21 - **Forks**: 0 - **Created**: 2022-10-13 - **Last Updated**: 2025-05-18 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # 高级程序设计（Java）实验手册 山东大学软件学院 ## 简介 本手册介绍《高级程序设计（Java）》课程的实验内容和要求。 - 实验结构：实验共10组实验题目、8次课、16课时。每次课根据个人情况可以练习1至2组实验题。 - 实验要求：每组实验交一份电子版实验报告（Markdown格式，参考附录2），10个实验占实验成绩若干比例。报告总结实验的心得体会、典型问题、解决方法。报告文件命名为 “学号-姓名-实验N.md”。每次实验课后提交实验报告到教师指定的系统。 - 评判标准：实验报告质量、结果正确性、程序健壮性、界面友好；实验课中提问和讨论的表现。时限内提交的先后不影响评分。 建议把实验项目保存在`C:\repos\`目录，手工解压安装的软件放在`C:\opt\`目录。后续说明以此为例。路径越简单越好，最好只用字母和数字。 为更好地掌握Java语言，建议补充课外练习。可以注册[力扣](https://leetcode.cn/)、[牛客](https://www.nowcoder.com/)、[洛谷](https://www.luogu.com.cn/)等在线评测（Online Judge，OJ）网站，练习其中的简单题目。 ## 目录结构 - `assets/`目录是些图标、图片资产，可以无视。 - `cn/edu/sdu/sc/javalab/`是主要的源码目录，包括代码和报告模板。等咱们学到Java的package（包）就能理解这个冗长的目录结构对应`cn.edu.sdu.sc.javalab`包名，意思是“山东大学-软件学院-Java实验”项目。 - `XX-report.md`：实验报告模板。Markdown格式。 - `labXX-notes.md`：实验课演示讲解的提纲和备忘，**教师使用，非实验任务**。大家也可参考，提建议和意见、补充或调整内容。 - `demos/`是各种演示程序。 - `doc/`是一些补充文档，介绍编程常识和规范、工具用法等。不涉及考试内容，但有助于编程和开发。 - [charset-encoding: 字符集与编码](doc/charset-encoding.md) - [coding-skills.md: 编程技巧](doc/coding-skills.md) - [git-guide.md: Git入门](doc/git-guide.md) - [history.md: 计算机简史](doc/computer-history) - [idea-guide.md: IDEA使用技巧](doc/idea-guide.md) - [java-key-points.md: ](doc/java-key-points.md) 要点（我觉得） - [java-puzzles.md: Java谜题](doc/java-puzzles.md) 学完再看。 - [java-style-guide.md: Java代码风格指南](doc/java-style-guide.md) **建议掌握** - [markdown-demo.md: Markdown示例](doc/markdown-demo.md) - [markdown-guide.md: Markdown极简指南](doc/markdown-guide.md) 实验手册、实验报告、doc目录的这些文档都是用Markdown格式写的。 - [oops.md: 面向对象的讨论](doc/oops.md) - [roadmap.md: 语言技能路线图](doc/roadmap.md) TODO: 待补充 - [skill-tree.md: 技能树](doc/skill-tree.md) TODO: 待补充 - [typing-guide.md: 打字入门](doc/typing-guide.md) - [vim-guide.md: Vim编辑器入门](doc/vim-guide.md) - `TODO.md`供教师用记录待办事宜，**教师使用，非实验任务**。 ## 准备工作 需要安装IDEA和JDK两种软件，参考[IDEA安装和使用指南](doc/idea-guide.md)。 ## 实验1：Hello, Java - 实验目的： - 熟悉Java开发环境的使用和配置。 - 熟悉IntelliJ IDEA软件的使用，包括创建项目、编辑程序、运行、调试等功能。 - [ ] 任务1：创建IDEA项目，录入HelloJava程序并运行和分析。 ```java public class HelloJava { public static void main(String[] args){ System.out.println("Hello, Java!"); } } ``` - 类名改成`HelloJava2`后还可以运行吗？ - 注意：IDEA中源码出现红色波浪线可能有语法错误。 - [ ] 任务2：调试示例（DebugDemo） - 功能：启动调试、运行至光标、结束调试。 - 功能：Step into、Step Over、Step out。 - 功能：断点的设置、清除。在暂停时查看变量。 - [ ] 任务3：修正程序（Fixme） - 新建项目和源文件，粘贴以下代码并修正其中的错误（有十几处），使运行结果为`Hello`。 - 练习编译错误的分析和修正方法。 - 讨论：区分词法错误、语法错误、逻辑错误。 ```txt Class Fix-Me { int Mian(string argv[]){ system.in.print('Hell') } }; ``` - [ ] 任务4（选做）：CLI - Command-Line Interface - 尝试在命令行（Win的CMD，Linux/Mac的终端Terminal）运行`javac`编译源码。运行`java`运行`*.class`文件，与IDEA功能对比。 - 了解环境变量用途和设置方法，了解`JAVA_HOME`、`PATH`两个环境变量的作用。 - Win用户：了解“系统级/用户级”环境变量的区别。 补充说明： - JDK既有开源免费版本，也有收费商业版本。Java语言本身的发展由Oracle公司主导，由于授权因素，业界有些顾虑，所以我们用开放社区版的OpenJDK。 - JDK通常每6个月发布短期版，展示新特性。商用则侧重稳定，所以隔几年会发布长期支持版（long-term support, LTS），不追求新语言特性的话用JDK-21长期支持版也可以。 ## 实验2：方程求解 本实验对应课本第二章知识，交互式应用程序： - 实验目的： - 掌握利用`Scanner`读入数据、`System.out.println`输出结果的基本方法。 - 掌握Java**基础类型、变量、表达式、类型转换**等基本概念。 - [ ] 任务1：进制转换（RadixConverter） - 编写程序从键盘读入三位（不要求任意位）十进制数，以八进制的形式输出。 - 样例：输入`888`，输出`1570` - 问题：输入数字超过三位，结果如何？最大可以输入多少而不报错？（`int`的范围） - 问题：关于`printf()`格式化输出，十进制`%d`（Decimal）、八进制（`%o`, Octal）、十六进制（`%x`, heXadecimal），但是二进制输出呢？ - [ ] 任务2：求平方根（SquareRoot） - 录入以下程序，测试并思考问题。 ```java import java.util.Scanner; public class SquareRoot { public static void main(String[] args) { var s = new Scanner(System.in); double x = s.nextInt(); // FIXME: 修正缺陷 System.out.printf("sqrt(%.9f) = %.9f\n", x, Math.sqrt(x)); } } ``` - 问题： - 输入负数结果如何？ - 输入非数字结果如何？（例如"abc"） - 把变量`x`定义为`float`有什么影响？ - 上述程序有缺陷（defect），对某些输入会出错（bug）。你能找到并修正吗？ - `var`自动类型推导非常方便，有什么缺点？ - [ ] 任务3：编程求解一元二次方程$$ax^2 + bx + c = 0$$ - 从键盘读入3个系数a、b、c，判断根的情况并计算输出。结果保留9位小数。 - 提示：一元二次方程求根公式： $$x_{1,2} = \frac{-b \pm \sqrt{b ^ 2 - 4 a c}}{2a}$$ - [ ] 任务4（选做）：奇偶性（Parity） - 读入一个整数，是奇数时输出字母`O`、偶数时输出字母`E`，**不用控制语句或条件算符或位运算**。 - 提示：回忆课堂介绍逻辑操作符`&& ||`时与算术操作符的类比。 - [ ] 任务5：URL Dissector（URL解析器） - 上网时浏览器地址栏会显示网址，正规说法是“Uniform Resource Locator”，统一资源定位器，缩写是**URL**。URL看起来有一定规律，比如`https://g.cn`，正式的说明可以参考[RFC3986 - Uniform Resource Identifier (URI): Generic Syntax](https://www.rfc-editor.org/rfc/rfc3986)。本次任务是解析URL的各个组成部分。 - 经验： - 自顶向下，任务分解。 - 自底向上，增量实现。 - 善用断言，测试先行。 - 相似的功能抽象为方法。 ## 实验3：控制结构 本实验对应课本第五章内容，流程控制。 - 实验目的 - [ ] 尝试阅读理解简单的分支、循环程序。 - [ ] 练习分支、循环的使用。 - [ ] 任务1：程序阅读（Reading1） - 阅读以下程序，推测其功能，执行并验证你的结论。 ```java import java.util.Scanner; public class Reading1 { public static void main(String[] args){ var scn = new Scanner(System.in); final int n = scn.nextInt(); for(int i = 0; i < n; ++i){ for(int j = 0; j < n; ++j){ if(i == 0 || i == (n-1) || j == 0 || j == (n-1)){ System.out.print('#'); }else{ System.out.print('.'); } } System.out.print('\n'); } } } ``` - [ ] 任务2：程序阅读（Reading2） - 阅读以下程序，并与上步比较两种写法的优缺点。 ```java import java.util.Scanner; public class Reading2 { static boolean on_border(int x, int n){ return x == 0 || x == (n-1); } public static void main(String[] args){ var scn = new Scanner(System.in); final int n = scn.nextInt(); for(int i = 0; i < n; ++i){ for(int j = 0; j < n; ++j){ System.out.print((on_border(i, n) || on_border(j, n)) ? '#' : '.'); } System.out.print('\n'); } } } ``` - [ ] 任务3：统计分析 - 随机生成10个`[1, 100]`内的整数，统计**总和、算术平均数，最大值，最小值，第二大数值、第二小数值**并输出。平均数输出时保留3位小数。 - 参考代码： ```java import java.util.Random; public class Stat { public static void main(String[] args){ var rng = new Random(); final int n = 10; int sum = 0, max1 = 0, max2 = 0, min1 = 0, min2 = 0; // FIXME: 最小值统计量应怎样初始化？ for(int i = 0; i < n; ++i){ int x = rng.nextInt() % 100; // FIXME: 鼠标指向nextInt()方法，阅读说明，修正错误。 sum += x; if(min1 > x){ min1 = x; } // TODO: 统计总和、最大值，最小值，第二大数值、第二小数值。 } // TODO: 输出总和、算术平均数（输出时保留3位小数），最大值，最小值，第二大数值、第二小数值。 System.out.printf("sum = %d\n", sum); System.out.printf("avg = %.3f\n", (double)(sum / n)); // FIXME: 修正错误。 System.out.printf("max1 = %d\n", max1); System.out.printf("max2 = %d\n", max2); System.out.printf("min1 = %d\n", min1); System.out.printf("min2 = %d\n", min2); } } ``` - [ ] 任务4：绘制空心菱形（Lozenge） - 编程读入正整数`n`（小于10），用`*`打印边长为`n`的菱形轮廓。 - 样例：`n = 3`的结果 ```txt * * * * * * * * ``` - [ ] 任务5（选做）：命令行参数（Command-Line Arguments） - 将上步的程序改造成可以读入尺寸`n`、字符`c`两个数据，用指定的字符`c`绘制边长为`n`的菱形。 - 用`main(String[] args)`的`args`参数，从命令行获取参数`n, c`。 - 比较**输入数据**和**命令行参数**的优缺点。 - [ ] 任务6：奇妙的图形 - 本题的成果需要大家探索。 - 请参照[代码模板](labs/ex03/MagicImage.java)添加以下功能： 1. 首先检查命令行参数的个数，如不等于3则报错并返回。输出错误信息的方法是`System.err.printf("java %s \n", MagicImage.class.getCanonicalName());`，注意是`System.err`而不是`System.out`。输出流`out`和报错流`err`就像两个电视频道，虽然在控制台貌似混在一起，其实互不干扰。 2. 将`args[0]`按整型值解析，赋给常量W，表示宽度（列数）。解析可用`Integer.parseInt()`方法。 3. 将`args[1]`按整型值解析，赋给常量H，表示高度（行数）。 4. 将`args[2]`按整型值解析，赋给常量N，表示迭代轮次。 5. 定义二维整型数组`img`表示图片，H行、W列，元素值为1表示黑点、0表示背景白色。 6. 创建一个名叫`rng`的`Random`类对象。 7. 循环N轮，每轮完成以下操作： - 随机选择一个顶点：用`rng.nextInt()`生成`[0, 3)`的随机数赋给变量`k`。 - 计算点`(x, y)`与顶点`(vx[k], vy[k])`的**中点**坐标，分别赋给`x`和`y`。 - 将图片对应像素`img[y][x]`设为1。 8. 输出图片内容：用两层嵌套`for`循环，输出H行、每行W个像素值，像素值以空格分隔。 - 外层变量r迭代H行。 - 内层变量c迭代W列，输出img[r][c]，像素值之间以空格分隔。 - 每行末尾换行。 - 本题输出可能多达数MB，并且要重定向到图片文件查看，所以只在IDEA构建（编译）而不运行。操作是点击Build（构建）菜单、Build Project（构建项目），或用快捷键`Ctrl+F9`。 - 编译正常的话，在IDEA点击左下角的“Terminal”图标，打开终端面板，**然后选择Command Prompt**。 ![](assets/idea-terminal-cmd.jpg) - 在终端面板用`dir`和`cd`命令逐级浏览并进入`\out\production\javalab-pub\`目录。 - [`dir`命令用法](https://learn.microsoft.com/zh-cn/windows-server/administration/windows-commands/dir) - [`cd`命令用法](https://learn.microsoft.com/zh-cn/windows-server/administration/windows-commands/cd) - 执行`java <包名>.MagicImage`，包名是`MagicImage.java`文件开头`package`后面那串文字（不含末尾的分号），例如`java labs.ex03.MagicImage`。注意`java`后面有个空格。 - 你可能用其他包名，要根据实际情况修改。包名在执行时会对应到目录。比如`labs.ex03.MagicImage`是告诉`java`在当前目录的`labs`子目录的`ex03`子目录找名叫`MagicImage.class`的文件。只有类文件才可执行，所以`.class`不用/不能写出。 - 不加参数时程序应当提示需要width、height、round三个参数。 - 指定三个参数`20 10 5`并运行应当看到类似下图的输出。具体0/1数值可能不同，因为有一定的随机性。 ![](assets/lab03-run-1.jpg) - 程序输出其实是“Portable BitMap”图片格式，需要**重定向**到扩展名为`.pbm`的图片文件，这次参数换成`100 100 100`，即宽100像素、高100像素、迭代100轮。 - `... 100 100 100 > tmp.pbm`的大于号表示“重定向”，`out`输出不显示在终端，而是保存到`tmp.pbm`文件。 - 之后用`start tmp.pbm`命令查看图片文件。如果电脑无法打开PBM格式图片，可安装[WPS Office](https://www.wps.cn/)。 ![](assets/lab03-run-2.jpg) - 上步参数生成的图片是一些随机点。按照以下参数运行、查看输出的图片，会出现有趣的模式： - `100 100 1000` 模式初现 - `100 100 10000` 模式更加清晰 - `1000 1000 10000` 图片尺寸扩大为1000x1000，需要运行几秒钟 - `1000 1000 100000` - `1000 1000 1000000` 粗略测量程序的运行时间，猜猜与哪个参数相关性更大？ - `2000 2000 4000000` 大约要几十秒，耐心等待。 - 测量程序运行时间：`System.currentTimeMillis()`可以获得当前时间（毫秒数），类型为`long`。程序开始取一次时间，记为`begin_time`。图片输出完成后再取一次时间，记为`end_time`。两者相减得到的时间差就是程序运行时间。但如果直接输出时间，也会重定向到图片文件，破坏了图片文件格式，所以要用`System.err.print...`输出。 - 在图片生成之后、输出"P1"之前也输出时间。看看*图片生成、图片输出*哪一步最耗时间，这就是所谓的程序“热点（hotspot）”。 - 2000x2000的图片大概8MB，我们的程序输出可能要几十秒。考虑到SSD写入速度一般在500~7000MB/s，这个运行时间慢得离谱。把`System.out.print()`换成`System.out.write()`试试。 - [ ] 任务7：单元测试与自动测试 - 学习循环结构之后，上次的“一元二次方程”实验可以扩展功能：循环“读入、求解、输出”，每轮处理一组参数`a b c`。并且预设期望的结果。自动判断程序答案是否正确。 ### 循环结构渐进练习（选做） 循环在程序设计的学习中是个难点，因为写的是静态表述（源程序），但设计时要想象出动态执行的效果。 如感觉完成任务4有困难，可尝试本节的系列任务，循序渐进。 每个任务需要编写一个**函数（静态方法）**，从`main()`调用并测试。输出的末尾要换行。 如果某题很自信可以解决，跳过继续也无妨。但若没有十分把握，一定要动手编程验证下是否真能解决。 我在设计这些例子时也多次出错。 #### 常数序列 - 任务：函数有1个整型参数n，功能是输出n个1，每项后有逗号。 - 样例：`f(5)`输出`1,1,1,1,1,` - 说明：逗号便于确认格式是否正确。 #### 递增序列 - 任务：函数有1个整型参数n，功能是从0输出到`n - 1`。 - 样例：`f(5)`输出`0,1,2,3,4,` - 说明：**输出不包含n**。从0开始计数是程序员的特征:) #### 平方序列 - 任务：函数有1个整型参数n，功能是输出1到n的平方。 - 样例：`f(5)`输出`1,4,9,16,25,` - 提示：根据迭代变量计算。但不要误改迭代变量。 #### 递减序列 - 任务：函数有1个整型参数n，功能是从n输出到1。 - 样例：`f(5)`输出`5,4,3,2,1,` - 提示：递减迭代变量。 #### 常数序列2 - 任务：函数有2个整型参数n和m，输出n个m，逗号分隔但**末尾不要多余逗号**。 - 样例`f(5, 3)`输出`3,3,3,3,3` - 方案1：每轮先输出数字，然后判断循环是否结束，如**未结束**则输出逗号。 - 方案2：每轮先判断迭代变量是否等于初值，否则输出逗号。 - 方案3：定义布尔型控制变量`first`，初值为`true`。每轮根据`first`决定是否输出逗号。首次输出后将`first`改为`false`。 - 方案4：先输出首元素，再进入循环，每轮均输出分隔符、元素。优点是循环内减少了分支。缺点是要处理空区间的情况。 - 说明：“末尾没有多余空格”的要求引用很多变化。 #### 递增序列2：左闭右开区间 - 任务：函数有2个整型参数`begin`和`end`，从`begin`**递增**到`end`（不含）并输出，逗号分隔。 - 样例：`f(3, 5)`输出`3,4` - 样例：`f(5, 3)`输出为空。 - 说明：**左闭右开区间的设计惯例极为重要**。这种做法在多个循环“拼接”处理时可用前段循环的结束点作为后段循环的开始点，没有重复、也没有空隙。 - 例如：[0, 5), [5, 9), [9, 100) #### 等差序列 - 任务：函数有3个整型参数b、e、d，输出从b到e（不含）公差为d的等差序列。 - 样例：`f(1, 10, 3)`输出`1,4,7` #### 等比序列 - 任务：函数有2个参数，浮点参数x、整型参数n，输出公比为x的等比序列前n项，**保留3位有效小数**，每项后带一个空格。 - 样例：`f(0.9, 5)`输出`0.900 0.810 0.729 0.656 0.590`（最后其实还有个空格） #### 序列求和 - 任务：函数有2个整型参数b、e，从b累加到e（不含e）并**返回**，由主调函数输出。 - 样例：`sum(0, 101)`输出`5050` - 样例：`sum(9, 1)`输出`0` #### 幂函数 - 任务：函数有2个参数，浮点x、非负整数n，**返回x的n次方**，由主调函数输出（保留9位小数）。 - 样例：`power(1.01, 365)`输出`37.783434333` - 样例：`power(1.01, 0)`输出`1.000000000` #### 幂函数2 - 任务：类似上题，但n允许负数。 - 样例：`power(1.01, -10)`输出`0.905286955` #### 阶乘函数 - 任务：函数有1个整型参数n，**返回n的阶乘**，由主调函数输出。不需考虑溢出。 - 样例：`power(1.01, 365)`输出`37.783434333` #### 周期序列 - 任务：函数cycle有2个整型参数r和n，输出以r为周期的序列前n项，每项后接空格。 - 样例：`cycle(3, 5)`输出`0 1 2 0 1` - 说明：每轮循环需要对两个变量迭代。 #### 长方形 - 任务：函数有2个整型参数row和col，输出row行col列的星号。 - 样例：`f(2, 3)`输出 ```txt *** *** ``` - 说明：用双重循环和单层循环各实现一次。 #### 下三角 - 任务：函数有1个整型参数n，输出n行下三角星号。 - 样例：`f(3)`输出 ```txt * ** *** ``` - 说明：用双重循环和单层循环都可以实现。 #### 上三角 - 任务：函数有1个整型参数n，输出n行下三角星号，空格填充。 - 样例：`f(3)`输出 ```txt *** ** * ``` #### 实心菱形 - 任务：函数有1个整型参数n，用星号和空格绘制轴长`2 * n - 1`的菱形。 - 样例：`f(3)`输出 ```txt * *** ***** *** * ``` - 现在应该可以解决“绘制空心菱形”的问题了。 ## 实验4：计算器 - 实验目的 - 学习、理解Scanner扩展应用 - 尝试阅读理解简单的分支、循环程序 - 更深入学习的利用Debug工具分析程序控制流程 - 简单的文本处理 - [ ] 任务1：前缀计算器（PrefixCalculator） - 自行创建`data1.txt`文件。 - 用调试（Debug）模式运行并分析该程序，写出该程序的作用， - 补充完整该程序，使得其可以正确计算data.txt中的所有运算，并友好的输出结果 - 修改该程序，使其支持data1.txt数据处理 - 修改data1.txt存放路径或数据内容，使程序发生以下错误，截图并说明你如何实现的。 - 计算结果溢出 - 数据处理异常 - 文件未找到异常 ```java package cn.edu.sdu.sc.javalab.ex04; import java.util.Scanner; public class PrefixCalculator { private static int calculate(char op, int a, int b) { int x = 0; switch (op) { // 问题：算符用String、char类型各有何利弊？ // TODO: 实现加法、减法、乘法。 case '/': return a / b; // FIXME: 检查除零的情况。 // FIXME: 处理无效字符。 } return x; } public static void main(String[] args) { var scn = new Scanner(System.in); // TODO: 改为打开文件。 while (scn.hasNext()) { // 判断是否有数据可读入 String ops = scn.next(); // 问题：String改用var声明可以吗？ char op = ops.charAt(0); // FIXME: 索引可能越界。 // FIXME: 判断后续是否有数据。 int a = scn.nextInt(); int b = scn.nextInt(); System.out.printf("%d %c %d = %d\n", a, op, b, calculate(op, a, b)); } } } ``` - 数据样例（`data1.txt`）： ```txt + 1 2 + 12 34 + 2000000000 2000000000 - 1 1 - 1 2 - 123 23 - -2000000000 -2000000000 * 3 4 + 2000000000 2 / 5 3 * 21 32 / 15 4 / 15 0 + 22 6 ``` - 问题：数据中的空行需要特殊处理吗？ - 八卦：前缀表达式又叫波兰表示法（Polish notation，波兰记法） - 八卦：Lisp编程语言就是用前缀表达式。类似：`(exp (* (sqrt -1) pi))` - [ ] 任务2：中缀表达式计算器（InfixCalculator） - 自行创建`data2.txt`文件。 - 每行有固定的3个操作数（整数）、2个操作符（`+ - * /`之一），都以空格分隔。 - 表达式总是正确的，暂不考虑错误处理。 - 补全程序，使其能够读入`data2.txt`，读入各行表达式并求值。 ```java import java.util.Scanner; public class FixedCalculator { private static int eval(char op, int a, int b) { int x = 0; switch (op) { // TODO：修正并补全程序 case '+': case '-': case '*': case '/': x = a + b; default: throw new RuntimeException("invalid operator: " + op); } return x; } private static int level(char op) { return 0; // 给运算符确定优先级，只需分2级。 } public static void main(String[] args) { var scn = new Scanner(System.in); while (scn.hasNext()) { int a = scn.nextInt(); char op1 = scn.next().charAt(0); int b = scn.nextInt(); char op2 = scn.next().charAt(0); int c = scn.nextInt(); int x = a + op1 + b + op2 + c; // TODO: 修改此处，利用eval()和level()完成计算。 System.out.printf("%d %c %d %c %d = %d\n", a, op1, b, op2, c, x); } } } ``` - 样例输入（`data2.txt`）： ```txt 12 + 15 - 13 17 - 18 + 24 33 * 6 / 6 55 / 10 + 2 ``` - [ ] 任务3：更灵活的计算器 - 在前两个任务的基础上，支持操作符数量不定的算术表达式。 - 表达式格式都是正确的，不需要考虑异常情况。 - 运算符与运算数之间空格数量不定，可能没有。因此需要逐个读入字符，识别数字或算符。 - 提示：只要没有括号，每次检查两个运算符，先乘除后加减，平级则先算左边。 - 样例输入（`data3.txt`）： ```txt 123 123 - 23 123 -23 123- 23 2 + 3 *4 2 + 3 + 2* 3 + 2 3 *4 - 2* 3 1234 - 567 / 7 + 22 ``` - 思考：付出这么大努力才实现基本算术运算，那么计算机（computer）与计算器（calculator）相比有何优势？为什么要学编程？ - 八卦：对称地，还有种后缀记法（postfix），又叫逆波兰式（reverse Polish notation, RPN）。Forth、PostScript语言使用后缀记法。 - 扩展阅读：上网搜索“前缀表达式、中缀表达式、后缀表达式”的含义、优缺点、相互转换的方法。 ## 实验5：交易模拟 - 实验目的 - 掌握`String`、`math`等常用类库的使用方法。 - 熟悉面向对象编程（OOP）的概念。 - 掌握自定义类的一般方法。 - [ ] 任务1：银行账户类 - 自定义一个银行账户类，包括属性（用户名，账号，余额）以及方法（存钱、取钱、加利息、查询余额）。遵从封装原则。 - 创建两个用户对象，模拟两个用户的各3次交易，例如：取钱，存钱，查询余额。 - 创建账户所需的信息由键盘输入；存钱、取钱的数额由随机数模拟。 - 每次账户交易在屏幕打印交易后的账户信息，有一定的排版 - 不允许出现账户金额为负数的操作。 - [ ] 任务2：JavaDoc - 为方便技术交流和知识传递，代码应有完备的文档描述类的设计思路、业务知识、使用方法。 - 学习JavaDoc的编写规则，为类和方法添加JavaDoc注释，练习用IDEA导出文档。 - [ ] 任务3（选做）：测试驱动开发（test-driven development, TDD） - 掌握`assert`的用法。 - 掌握单元测试（unit testing）的概念。 - 练习先编写测试用例、再实现所用功能的开发方法，体验增量实现的开发优势。 ## 实验6：密码破译 - 实验目的 - 综合运用控制流程、预定义类。 - 掌握`String, Random`等类的用法。 - [ ] 任务1：频数统计 - 利用随机采样的方法，分别统计字符`s`和`z`的出现频率（例如，随机选择100，1000，10000个字符，计算其中字符`s`的比例） - 用WPS的电子表格（et）画折线图，可视化不同采样样本数量与GT之间的关系（随着采样数的增加，逐渐逼近Ground Truth） - 编程统计文本中各字符出现的次数。 ```java import java.util.Random; public class Ex06Task1 { public static void main(String[] args){ String str = "test"; int count = 0; for (int i = 0, L = str.length(); i < L; i++){ if (str.charAt(i) == 's'){ count++; } } System.out.println("percentage of 's' is " + count/str.length()); } } ``` - [ ] 任务2：频率统计 - 上一步只统计了两种字母的频率，现在我们统计一段文本里面所有字母的出现频率。不区分大小写，遇到小写字母则转成大写字母并统计。 - 样本使用实验6目录中的`turing.txt`文件。因为内容较多，粘贴不方便，建议用“输入重定向”的方式导入文件内容，具体操作方法请自行上网搜索。 - 提示：`Character`类有判断和转换大小写的静态方法。 - 提示：将字母按频率降序排序并输出便于分析，可以利用`Arrays.sort()`排序。 - 扩展：设想回到60年代，计算机只有字符界面，没有电子表格或图形界面，有什么可视化的方法吗？ - [ ] 任务3：凯撒密码 - 凯撒密码（Caesar Cipher）是种古老的密码方案，加密时把明文中的字母全部偏移固定的位置，超过字母表就折回。比如当偏移量为3时，"AZ"替换为"DC"，知道偏移量就能解密。实用中还有些细节： - 大小写其实不耽误情报理解，还可能暴露结构，干脆全部大写。 - 单词间的空格、标点符号会成为分析、破译的线索，通常删掉。 - 去掉标点空格的密文容易抄错，于是写成固定的分组。比如每5个字符一组。 - 分组后最后一组可能不齐，留着又怕暴露真实长度，于是用随机字符填充。比如长为5的分组可能填充1至4个字符。多几个字母不影响理解。 - 试试破译这段密文：`VITAJ JGXVI RMDOZ XJYZO CVOVX JHKPO ZMXVI PIYZM NOVIY BJJYK MJBMV HHZMN RMDOZ XJYZO CVOCP HVINX VIPIY ZMNOV IYYMK` - 凯撒密码的偏移量只有25种，破译者穷举尝试总能找到符合词法的情况。判断是否明文有几种方法： - 方案A：人工观察…… - 方案B：在逆变换的结果中搜索常见词汇，找到明文时匹配词汇骤增。实验6目录提供了常见英文单词列表。 - 方案C：利用字母频率。当找到正确的偏移量时，复原文本的频率分布比较接近英文的正常分布。判断“接近”可以用方差或余弦距离等指标。 - [ ] 任务4（暂停——不做）：替换密码 - 替换密码的简单方案是把每个字母换成与其不同的字母，对于英文字母表（不区分大小写），就有25*24*……*1即25!种替换方案，穷举破解对此数量级无能为力。但这种一对一的替换保留了字母频率的特征，比如"GREED"无论怎样替换，两个E加密后的字符相同、出现的频率就是明文字符的频率。另外`tion`，`ing`，`ed`也都是特征，统计密文字符的频率，再与相似语料的频率分布对比，往往能容易地解密。 - 生成替换表（密钥）、加密、解密的的示例程序：`demos/GenCipherKey.java` - 估算替换式密码的密钥空间，估算暴力破解所需的计算量和时间。 - 使用频率分析技术破译下列替换式密文： ```txt WRWKHICWHSUUICAKHSRETVTHPCSTWKTKWYYVBSEBYVUICAITSHPDPLSUPZBSUBUWRUWNNVIKHSRTHNKUHSIRTHIAPNQINCUWYUKYWHSIRTIQWUIRTSDPNWMYPINDPNIQUICAYPXSHVPEHITIYLPWRIRYSRPWNAWNHSWYDSQQPNPRHSWYPGKWHSIRSRINSRDPAPRDPRHLWNSWMYPTRKCPNSUWYYVHBPSRTHNKUHSIRTZBSUBEILPNRHBSTIAPNWHSIRCKTHMPESLPRHIHBPDPLSUPSRWMTIYKHPYVPXBWKTHSLPDPHWSYHBPVSRUYKDPWYYRKCPNSUWYSRQINCWHSIRZBSUBSTNPGKSNPDHITIYLPHBPANIMYPCKRDPNUIRTSDPNWHSIRSRSHSWYWRDMIKRDWNVLWYKPTIQHBPDPAPRDPRHLWNSWMYPTLWYKPTIQQSXPDAWNWCPHPNTUIRTHWRHTHWMYPTIQQSXPDQKRUHSIRTZBSUBIUUKNSRHBPTHWHPCPRHIQHBPANIMYPCHBPTPSRTHNKUHSIRTCKTHMPESLPRSRTICPQINCZBSUBHBPDPLSUPUWRTPRTPAKRUBPDSRHIWTVTHPCIQAKRUBUWNDTINIRHPYPHVAPHWAPCWERPHSUWYYVSCANPTTPDIRTHPPYHWAPINZSNPABIHIENWABSUWYYVSCANPTTPDIRCIHSIRASUHKNPQSYCZSNPDSRHIIRPINCINPQSXPDINPXUBWREPWMYPAYKEMIWNDTHBSTYSTHMPSREMVRICPWRTRPUPTTWNSYVUICAYPHPWYYHBPTPANIUPDKNPTNPGKSNPHBPKTPIQTICPUIDPHIPXANPTTHBPYIESUWYWRDHBPWYEPMNWSUWYDPQSRSHSIRIQHBPANIMYPCKRDPNUIRTSDPNWHSIRWTZPYYWTHBPRPUPTTWNVRKCPNSUWYCWHPNSWYUQWMILPIRUPHBPTPSRTHNKUHSIRTWNPESLPRHIHBPDPLSUPSHCKTHMPWMYPHIUWNNVHBPCIKHUICAYPHPYVWRDZSHBIKHWRVRPPDQINQKNHBPNSRHPYYSEPRHBKCWRSRHPNLPRHSIRWHHBPPRDIQHBPNPGKSNPDIAPNWHSIRTHBPDPLSUPCKTHNPUINDHBPNPTKYHTWEWSRSRIRPIQHBPQINCTNPQPNNPDHIWMILPHBPNPTKYHTWNPRKCPNSUWYDWHWHBPVWNPWTAPUSQSPDAWNHIQHBPRKCPNSUWYCWHPNSWYANIDKUPDMVHBPDPLSUPSRHBPANIUPTTIQUWNNVSREIKHHBPSRTHNKUHSIRTNPQPNNPDHIWMILP ``` - 课外阅读：[中华人民共和国密码法](https://www.gov.cn/xinwen/2019-10/27/content_5445395.htm) - “密码，是指采用特定变换的方法对信息等进行加密保护、安全认证的技术、产品和服务。” ## 实验7：万年历 - 实验目的 - 更深入的理解Java控制流程。 - [ ] 任务1：月历 - 输入一个月份（YYYY-MM），输出这个月的日历，要求每行显示7列，对应星期一到星期日。参考系统日历的布局。 - 样例输入：`2022-12` - 样例输出： ```txt Mon Tue Wed Thu Fri Sat Sun 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 ``` - 提示：整数的格式化输出`System.out.printf("%3d", 12);`，右对齐、宽3列字符。 - [ ] 任务2：输入一个月份，同时输出该月起始的两个月的日历，要求两个月的日历水平排列而非上下排列。 - [ ] 任务3（选做）：万年历 - 输入年份（1800~9999），输出该年度12个月份的日历。每排4个月，共3排。 - 日历中每周的第一天是周一还是周日？尝试添加参数和逻辑支持在两种风格之间切换。 - 扩展阅读：`java.time`包的`Instant, LocalDateTime, ZonedDateTime`等类的用法。 时间、日期、历法是个深坑，受历史、政治因素的影响很大，之前Java做了3套日期库都不理想。上网搜索1582年的西历变动、夏令时、F22战斗机跨越国际日期变更线时宕机时间。 ## 实验8：动态数组 - 实验目的 - 本部分对应课本第八章，帮助深入理解数组使用方法 - [ ] 任务1：利用数组实现Java的`ArrayList`容器类的基本功能，包括以下方法： - 初始`ArrayList`长度默认为4（可以指定），长度不足容量翻倍策略。 - `void append(Object obj)`将对象追加到数组尾部。 - `void insert(Object obj, long idx)`在参数指定位置插入数据，参数位置错误则不加入。 - 比较`(obj, idx)`和`(idx, obj)`两种参数排布方式的优缺点。 - `void delete(long idx)`删除参数指定位置元素，考虑参数位置错误情况。 - 设计成返回被删除的对象`Object delete(long idx)`是否更方便？有何缺陷？ - `Object get(long idx)`，根据参数指定位置定位元素，考虑参数位置错误情况。 - 对于参数位置错误，比较用`boolean`返回值、抛出异常两种方式的优缺点。 - 对于`get()`方法，无法用返回值报告位置错误。有同学建议索引错误时返回`null`，你觉得这种方法如何？ - 有三个方法需要检查参数位置，如果添加专门的检查方法`boolean checkIndex(long idx)`有何优劣？不检查索引呢？ - [ ] 任务2：性能测试 - Java怎样统计时间差？计时精度如何？能否设计个`Stopwatch`类？ - 重复测试几次，耗时的波动范围多大？你觉得计时秒数精确到小数后几位比较合理？ - 利用`append()`尾部加入50万个随机生成的对象； - 利用`insert()`头部加入50万对象； - 利用`insert()`随机位置加入50万个对象。 - 每加入1万个对象，统计一次时间，用Excel等软件绘制数据量～时间曲线并分析。 - 用Java的`ArrayList`做同样的实验，对比效率。 - 数据格式 - 方案1：使用TAB分隔输出的结果，可以复制粘贴到Excel单元格中。 - 方案2：使用逗号分隔，重定向到CSV文件，用Excel打开。 - [ ] 任务3（选做）：功能扩展 - 运用Java的模板特性完善动态数组类，加强类型安全（type-safe）。 - 实现`void swap(ArrayList lst)`方法，注意自反的检测。 - 实现`boolean equals(ArrayList lst)`方法，注意自反、对称、传递，`null`的处理。 - 实现`int hashCode()`方法。了解`equals`与`hashCode`的关系。 - `int`有`2^32`个不同的值。如向数组逐个添加对象直到长度大于`2^32`，期间是否会有长度不同但`hashCode`相同的情况？ - [ ] 任务4（选做）：Java数组长度类型是`int`，最大约21亿，对于`byte`类型元素才2GB内存。通过分块能实现支持更大长度吗？ ## 实验9：图形家族 - 实验目的： - 本实验涉及的知识点主要为**继承、多态、排序**，对应课本9、10章知识点 - [ ] 任务1：形状类（Shape） - 以形状（Shape）为最顶层的类，求面积、周长的方法，作为形状类的抽象方法。 - [ ] 任务2：实现矩形（Rectangle）、正方形（Square）、菱形（Diamond）、圆形（Circle）子类，设计出一个层次化的类结构。 - 矩形（Rectangle）需要实现`setWidth()`和`setHeight()`两个方法。 - 思考：按照几何定义正方形都是矩形，那么`Rectangle`与`Square`类需要体现这种关系吗？ - [ ] 任务3：排序 - 写一个程序，随机创建20个形状，用**实验8开发的动态数组保存**；利用多态思想。 - 对象保存到数组后都是`Shape`引用，能否确定对象的实际类型？ - 写一个静态排序方法，实现所有形状按照周长、面积从大到小及从小到大四种规则排序。 - [ ] 任务4：修改排序方法，使其同时支持一种新的排序规则，按照面积，所有圆形从小到大排列，后面是所有其他图形从大到小排列。 - > 实现软件需求和在水上行走都很容易——只要它们都是冻结的。 - 输出结果应当能清晰直观的体现程序的正确性。 - 讨论：为支持新的排序方法，你的程序改动大吗？ - [ ] 任务5（选做）：DRY - Don't Repeat Yourself - 总结排序方法的共性，抽象出通用的**排序方法、比较方法**。 - 扩展阅读：函数式编程（Functional programming, FP）风格。与面向对象编程（OOP）风格的排序实现方式比较，讨论各自的优缺点。 ## 实验10：链表 - 实验目的 - 掌握链表的原理和基本算法。 - 掌握参数化类型（模板）的使用。 - 掌握排序准则的概念、比较器的用法。 - 加深对引用的理解和使用。 - [ ] 任务1：实现`LinkedList`模板类，包括以下方法： - 默认的无参构造器`LinkedList()`。 - 接受变长参数的构造方法`LinkedList(T... a)`。 - 获取链表长度`int length()`。 - 维护长度成员的方案。 - 即时统计的方案。 - 在第k个节点**之前**添加数据`void insert(int k, T value)`。 - 处理k无效的情况（小于0或大于长度），抛出异常。 - 在此基础上，怎样实现在第k个节点**之后**添加数据？ - 由小到大排序的方法`void sort(Comparator cmp)` - 判断链表是否有序`boolean isOrdered(Comparator cmp)` - 合并两个有序链表`void merge(LinkedList another);` - 两个链表需要确保有序，否则结果也会无序。 - 讨论：如果添加参数`Comparator cmp`并用`isOrdered()`检查两个链表有序，这种设计有何利弊？ - 之前为动态数组设计的排序算法是否可用于链表排序？ - 如可用：有何缺陷？哪部分代码应对缺陷负责？ - 不可用：算是代码重复吗？是否有对数组和链表都可用且高效的排序算法？ - 代码量：约400行 - [ ] 任务2：目标 - 通过媒体广告、搜索引擎了解IT培训机构的Java课程内容、零基础学员半年后具备的能力。 - 与我们的课程内容和目前能力进行对比，并给出合理的解释。 ## 实验16：自我复制（选做） - 实验目的： - 加深对转义序列、格式化输出的掌握。 - 激发对可计算性、计算机科学的兴趣。 - [ ] 任务1：**编写一个Java程序，使其输出与源码完全相同**。 - 要求：不用任何输入，包括标准输入、读取文件等。 - 提示：`printf()`，转义字符。 - 挑战：我的答案代码有166字节，你能写出更短的实现吗？ - 扩展： - 如果把Java环境看作从文本（源码）到文本（输出）的映射（函数），这种自复制程序就是Java环境的**不动点（fixed point）**。 - 给变量`x`任意初值，迭代调用`x = Math.cos(x);`，也会收敛到一个不动点。写程序试试。 - 头上的“旋”、台风的“眼”也是不动点的例子，感兴趣的话可以看看“毛球定理”。 --- ## 附录：Git 坏消息：除了IDEA、VSCode、JDK外，还有个必备的源码管理工具需要安装和学习——Git 好消息：Git一次学习，终身受益，并且适用于各种代码和文档的管理（例如：CPU硬件逻辑、你的实验报告、小说、游戏存档等）。 详情参考`git-guide.md`文件。 ## 附录：Markdown Markdown是种轻量的标记语言，能方便地描述格式（加粗、斜体、目录、超链接、配色等），还可以转换为PDF、HTML、PPT等格式，特别适合用于编写科技文档。Markdown用纯文本编写（相对的DOC/PDF等是二进制文件），体积小，便于比较、搜索、版本控制。本手册就是用Markdown格式编写的。 详情参考`markdown-guide.md`文件。 ## 附录：相关术语 - Java版本 - Java SE: 标准版 - Java EE: 企业版 - Java ME: 微型版，用于嵌入式和移动设备环境。 - LTS: Long Term Support，长期支持版。比如Java-8、11、17版本有8年的缺陷修复与更新，适合软件产品使用。 - Ubuntu系统也有类似概念。 - 字符集（charset） - ASCII: 7-bits, 128-chars. 应熟悉数字、大写字母、小写字母的相对位置，转换方式。熟悉关键字符： - NUL，空字符，\0 - BS，Backspace，退格，0x08 - HT，TAB，制表符，0x09 - LF，换行，0x0A - CR，回车，0x0D - ESC，退出或转义，0x1B - SP，空格，0x20 - '0'，0x30，48 - 'A'，0x41，65 - 'a'，0x61，97 - DEL，删除，0x7F - ISO-8859-1: 8-bits, 256-chars. - GB2312、GBK、GB18030：中文编码相关国家标准。既是字符集也是编码。 - GB2317：双字节，六千多字符。 - GBK：双字节，两万多字符。 - GB18030：变长编码（1、2、4字节），七万多字符。 - Unicode: 前128个字符与ASCII相同。 - 编码（encoding） - UTF-8：变长，1~4字节，编码容量1百万。如扩展到6字节其实可对int32编码。 - UTF-7, UTF-16 LE/BE, UTF-32：建议了解。 - 换行序列： - LF（U+000A）: Linux/Mac使用 - CRLF: Win使用。用回车（CR）和换行（LF）两个字符分隔行。 - Win下编辑的文件在Linux打开时行尾可能出现`^M`字符（CR）。 - Linux编辑的文件在Win中打开，可能全在一行，没有换行。 - 缩进（indent）： - 代码每层语法结构一般缩进2个空格或4个空格。 - 缩进可用空格符（SP）或制表符（HT）。本实验要求使用空格缩进。 - 字体（font） - 字号。正体/斜体/粗体。 - 熟悉：等宽字体（fixed-width, monospace）为便于对齐代码，开发环境通常使用等宽字体。 - 了解：衬线字体（serif）、无衬线字体（sans-serif） - 语法加亮（syntax highlight） - 为方便理解程序，提示语法，开发环境通常对代码中的关键字、算符、常量、方法、类名等用不同的颜色和字型进行提示。 - 编码风格（coding style） - 不同的编程语言、组织（公司）可能有特定的编码风格。保持一致的编码风格有利于理解和交流。混用编码风格可能被开发社区认为是外行。**目前我们不用深究，用IDEA时只需`Ctrl+A`全选然后`Ctrl+Alt+L`自动排版即可**。下面是相同代码在不同编码风格下的样子： - 样例1： ```c++ int ack(int m, int n) { if(m <= 0) { return n + 1; } else if(n <= 0) { return ack(m - 1, 1); } else { return ack(m - 1, ack(m, n - 1)); } } ``` - 样例2： ```c++ int ack (int m, int n) { if (m <= 0) { return n + 1; } else if (n <= 0) { return ack (m - 1, 1); } else { return ack (m - 1, ack (m, n - 1)); } } ``` - 命名约定（naming conventions） - pascal case: 又叫`UpperCamelCase`，每个单词的首字母大写。**Java的类名建议用这种方式**。例如：`UserLog` - camel case: 又叫`lowerCamelCase`，除第一个字母外每个单词的首字母大写。**Java的变量和方法名建议用这种方式**，以便和类名区分。例如：`userLog` - snake case: 用下划线（`_`）连接单词。`C/C++/SQL`常用这种方式，便于切分单词。形如：`user_log` - kebab case: 用连字符（`-`）连接单词。`URL/CSS/Lisp`常用这种方式。形如：`user-log` - 匈牙利命名法（Hungarian notation）：由匈牙利籍传奇程序员Charles Simonyi发明，即在变量命名时添加代表用途和类型的前缀。例如：`lpszName`表示“Name是个长指针，指向含0结束符的字符串”。这个记法在开发环境较简陋时有一定价值，现在不常用了。看Windows SDK的帮助文档（MSDN）时可能遇到。 --- > 纸上得来终觉浅，绝知此事要躬行。