956237586 – 第 11 页 – HYL Studio

20220516数据结构绿皮书读书笔记

大型项目的实验和需求分析最终应当是需求的正规陈述，这种陈述成为用户和软件工程师的主要表达和交流方法，来让软件工程师尝试理解并建立标准。
1.功能性需求
2.系统的假设和限制
3.维护需求
4.文档需求
需求规范陈述软件应该做什么，怎么做。且需求应当让用户和软件工程师同时理解，他们将形成后面阶段设计、编码、测试和维护的基础

编码
在合适的的时间启动编码

编程原则
在需求准确和完成之前不要开始写代码
Act in haste and repent at leisure. Program in haste and debug foreve。不翻译，翻译不出这个意境
从0开始通常比在旧程序打补丁要容易

正如我们自上而下地设计，我们应该自上而下地编码。一旦顶层的规范是完整而精确的，我们应该开始对高抽象层次的Class和方法进行编码，并通过包含适当的Stub来测试它们。如果发现我们的设计有缺陷，我们可以轻易的修改它而不至于让低级别的方法白写

如果一个程序的10%都要做修改，那是时候重写它了。相比在一个大程序上重复的打补丁，很多的bug都是由同一个地方导致。

项目练习1.6

1.幻方判断和生成
1.1.写一个程序读取一个矩阵，判断是否是幻方
1.2.写一个程序，用下面的方法生成幻方
方法仅对奇数大小的幻方有效，开始把1放在第1行中间然后依次填写2，3，4。。。顺序如下：
向上、向右，按对角线方向，当你遇到了第一行则跳回到最后一行，当你遇到最后一列则跳回第一列。当被占用的时候向下移动一格再继续填写

结果如下
17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9

2.一维的Life模拟游戏
把游戏改成仅在横着的单元格中进行，规则和二维类似，在细胞的两侧2格内都是邻居
当死亡的细胞存在2或3个存活的邻居时复活，当存活的细胞存在0，1，3个邻居存活时死亡（因此死亡细胞存在0，1，4个邻居的时候依然是死亡，存活细胞存在2，4个邻居时依然存活）
设计，编写，测试一个程序，模拟一维的Life游戏

3.打印日历
不赘述，麻烦的一B，到现在做日历项目的我还有没搞定的高效算法

总结
1.为了改进你的程序，先review逻辑，不要在一个垃圾的算法上做代码的优化
2.在你的程序正确和工作之前，不要开始优化
3.除非绝对必要，否则不要优化代码
4.保持你的方法足够的短，任意一个方法都应该在一屏内（屏幕大的好处）
5.在开始写代码之前，确认你的算法是正确的（我要是能提前知道对不对，我早去搞算法了，实际需求里大概率我没法100%证明正确性）
6. 验证你算法最复杂的部分
7. 保持你的逻辑简单
8. 在你决定解决问题之前，确认你理解了你的问题
9. 在写代码之前，确认你理解了算法（我要是理解，我还用动手写？）
10.当遇到困难的时候，拆分问题来独立思考。（不幸的是很多时候拆分问题本身就是个困难）
11. 描述一个问题时出现的名词暗含了关联的Class名称，动词往往对应着方法名
（需求分析常用套路，前提是需求文档无歧义表达，否则需要人工去重。这也是个消除歧义的好时机，可能会让产品发现自己表达的错误和歧义）
12. 给你的每个方法细心的添加注释和文档（想啥呢，不存在的hhh）
13. 给每个方法细心的填写前提条件和执行效果
14. 在方法开始的时候进行错误检查，保证前提条件是满足的
15. 每使用一个方法的时候，问你自己为什么你知道它的前提条件是满足的
（实际情况是管它满不满足呢，写了再说，大概率不会出问题的。为啥呢？我就是这么自信，我相信我对数据结构的设计有足够的容错性，做的前提检查足够的严谨，对代码执行路径的静态分析足够正确，才有胆量这么干）
16. 使用stub桩、driver测试用例、黑盒、白盒测试来简化调试
17. 使用大量的脚手架代码来帮助定位错误
18. 在用数组的时候，注意index需要减1，永远使用边界值检查使用了数组的程序
19. 保持你的程序有良好的格式，因为书写和debug的时候会更加容易
20. 永远保持你的文档和代码的一致性，当阅读一个程序的时候以代码为准，而不要轻易相信注释
（典型的自己懒得写，要求别人写。所以最好的办法就是不写，然后让代码自解释）
21. 小黄鸭调试法，尝试向别人解释你的代码，这会让你更好的理解代码逻辑
（当别人问问题时，也可以诱导对方使用这种方法，描述自己程序的逻辑和他自己的想法，然后大概率就没问题了）

明天开始看堆栈，难度开始逐渐提高
mark 目前是49页，pdf是67页

20220513数据结构绿皮书读书笔记

20220513数据结构绿皮书读书笔记
效率分析
程序运行哪里耗时最长？显然不是输入，因为只有一次，输出一般来说也很快。大量的计算都是在update方法个neighborCount方法的调用上，在每代update都需要重新计算每个细胞的邻居，在一个常见的布局中，可能仅有5%的细胞是存活的，并且集中在一个区域。因此update会消耗大量的时间在计算死亡的细胞上，他们没有存货的邻居，也不可能复活。如果95%的细胞都死了，那么下一代的计算是相当没有效率的
但是这种性能下降重要吗？一般来说不重要，因为对用户来说计算可以很快的完成，看起来就是一瞬间的事情。反过来说，如果你在一个很垃圾的电脑上运行这个程序，或者是分时的系统上，你才可能需要找出程序的时间耗费在了哪里。但是一般来说，优化这个程序的运行时间是没有必要的，即使它的效率并不高

编程原则
除非必要，否则不要去优化你的代码
当你的程序没有完成且正确运行的情况下不要开始优化
大多数程序90%的时间会花费在10%的指令上。找到这10%，把你的精力花费在这上面

另外一个原因就是优化一个程序通常会产生很复杂的代码，当程序需要修改的时候这会变得更加困难

编程原则
保持你的算法尽可能的简单，当有疑问选择最简单的方式实现

为了修订程序添加的边界限制，需要使用我们还没写的数据结构，等到了9.9章的时候，我们会重新来看这个程序，在那时候我们会找出一个更加高效的算法，因此那个新的程序会更加的通用以及有更好的计算效率

编程原则
有时候推迟问题可以简化解决方案（凡事三思而后行：能不能不做？能不能别人做？能不能明天做？）

思考题
如何让矩阵的宽度也由用户输入？把常量改了呗，改成变量，推迟申请数组内存的时间
一个提高性能的办法是删掉周围一圈边界，这样计算边界的时候就不用算那些永远都是0的格子了。这种做法在这个联系里值得做么？显然不值，边界占比才多少- –

P1. 修改程序的初始化方法，接受连续的空字符和多个x作为存活的表示。代替现有的坐标输入方式
代码自己改吧，懒得写，就是换下读取函数而已

P2. 支持从文件读初始值，同样是改输入函数

P3.当程序结束的时候，输出最后一次的布局到文件里，给上一个问题用

P4. 在任意一代生成的时候，支持用户可以手动编辑插入新的存活细胞

P5. 在任意一代生成时，如果用户想看帮助，支持打印帮助

P6. 增加单步模式，解释每一个细胞的变化和原因
你看我说什么来着，肯定有新需求，你要是第一版没记，实际工作加这种需求就GG了

P7. 使用光标定位功能来让打印局部更新，而不是完整输出所有布局
关于命令行的光标定位功能本质上也是一系列的特殊字符，但是麻烦的是当你想局部更新的时候，需要计算要更新的坐标和当前光标的坐标才能知道输出什么控制字符
这个会很有意思，但是我懒得动hhhh 看看得了，我确认我写的出来的我就不写了

P8. 使用不同的颜色来表示每一代变化了和没变化的细胞
这个同样也是7里的控制字符，有的控制字符能修改后续字符的颜色，准备好打印之前修改对应字符的颜色就好了，难点是需要额外信息记录哪个变了

本章内容均为基础，看了下主要的部分，其中一些在后面会逐渐加深难度，其他的将会在其他课程中学习，还有一些需要在实践中学习

软件工程的实际周期
1.完整的分析需求，确认需求的合理性
2.构建原型和实验直到所有的需求都满足
3.设计算法和数据结构
4.验证算法的正确性，或者让算法足够简单来保证有足够的自信确认
5.分析算法来确定它的依赖并且确认满足需求
6.编码实现
7.用合适的测试数据来评估程序
8.重构程序使其足够的functional，不知道怎么翻译，意思应该是可重用
9.当必要的时候，优化代码来提高性能
10.维护程序，面对后续用户所需要的更改

问题分析
因用户说的和计算机科学天然有鸿沟，所以以下问题用户必须理解
1. What form will the input and output data take? How much data will there be?
格式可以让产品定义好，但必须满足第一范式。不满足则继续追问
多少数据产品有概率不知道，可能得自己算

2. Are there any special requirements for the processing? What special occurrences will require separate treatment?
特殊逻辑，也是产品给。没给就是没有

3. Will these requirements change? How? How fast will the demands on the
system grow?
需求会变不会变的产品自己都不知道。。。更不用提变得多快了，pass

4. What parts of the system are the most important? Which must run most efficiently?
拿部分都重要，出bug就得修。。。不被测试和用户发现的bug那能是bug么？那是feature
大部分都不需要啥效率，能跑就得了，但设计上还是要最佳的方案，免得有坑。

5. How should erroneous data be treated? What other error processing is needed?
错误的数据拒绝处理，但要保证系统能正常对其他数据运行。最坏情况下影响到个别人可以接受，但影响所有人不可以

6. What kinds of people will use the software? What kind of training will they have? What kind of user interface will be best?
非后台开发需要考虑的，丢给前端和产品

7. How portable must the software be, so that it can move to new kinds of equipment? With what other software and hardware systems must the project be
compatible?
后台来说不需要，linux能跑就行

8. What extensions or other maintenance are anticipated? What is the history of previous changes to software and hardware
设计时有犹豫的，就留出扩展。记录原始数据备用。历史上改的东西只有天知地知git知

mark 目前是41页第1.6.3，pdf是58页
明天和后天看心情更新

20220512数据结构绿皮书读书笔记

维护程序的第一步就是review、分析、评估。思考如下几个问题
1.程序是否按需求正确解决了问题？
2.程序在所有条件下都能正常的工作吗
3.程序是否有一个好的用户界面？用户能否方便简单的输入，输出是否有用简洁？程序是否提供了可选的特性供使用者选择？是否包含足够的指导和其他信息？
4.程序的逻辑是否使用使用方便和简短的函数来清晰的书写，数据结构能否准确的反映程序的需要
5.程序是否有良好的文档？命名是否意义准确？对困难和主要的代码是否有解释？
6.程序对空间和时间的利用是否高效？通过修改算法能否让程序的性能进一步提升？

review整个程序
首先是问题的定义：
如果我们回去看问题定义的规则，会发现我们并没有完全遵守，规则没提到gird矩阵有边界，但我们定义了最大值。在程序中超出边界的细胞被我们忽略了。
虽然任意的计算机模拟都肯定会有边界，但我们定义了20 60这种数字太过随意，其实可以做到不限定矩阵大小，但在此之前我们需要实现几种特殊的数据结构。

编程原则
确认你完全理解了你的问题，如果你必须修改问题描述，清晰的解释你改了什么

然后是程序的正确性：
因为程序测试无法证明错误不存在，我们需要其他的方式来二次证明程序的正确性，构造符号来证明程序的正确性通常是困难的，但有的时候是可以做到的。
Life模拟这个程序只有update会修改数据，只有neighborCount会统计邻居，我们关注这两个
对于neighborCount，只有有限的几个邻居和状态，使用白盒测试构造几个case即可完整测试
对于update，每个单元格的邻居数量只有几种情况，分别测试输出即可

接着是用户交互界面：
对于初始化状态通过坐标输入其实是比较反人类的，部分布局非常复杂，人工计算容易出问题。所以最好是支持用户输入一整行的数据，空行代表都是死亡比较方便。或者是支持从文件读入。另一个选项就是允许用户通过任意方式自己编辑初始值。

输出也有提升空间，如果直接我们不是每次都重新打印，只再原来的输出上修改变化的部分，看起来会更好一些。（命令行里，这其实是可以做到的）

帮助信息，可以用弹框或其他形式，更加直观

一般来说，设计一个程序必须要慎重考虑用户的使用体验，大型程序很重要的一点就是提供用户界面，通常设计界面的精力要比其他所有地方加起来都要多

效率分析，下次更新，不一定是明天，明天放假了hhhh 可能是下周再说了
mark 目前是37页第6点，pdf是54页

20220511数据结构绿书读书笔记

20220511
Life类的定义
每个Life对象都需要包含一个矩形数组，用1表示存活的细胞，0表示死亡的细胞。这样表示的好处是，如果要计算一个特定细胞的邻居，我们只需要把相邻的加起来就行了。因为每代的更新中都需要重复的计算每个细胞的邻居数量，所以Life类应当包含一个成员方法neighborCount来做这个任务。因为client的代码不需要知道这个方法，所以设置成private

计算邻居
可以预见（这说法特别像数学证明里的显然可得，然而初学者设计程序并不会有这种经验，只能是踩过坑才知道），如果需要边界细胞的邻居需要更多的判断条件，我们可以做一些优化，让数组的实际大小比定义的大一些，周围留出一圈，这样既避免了从0开始数的麻烦，也避免掉了多余的判断，让所有单元格计算邻居的时候可以用相同的代码

更新矩阵
更新的动作是相当明确的，我们首先计算一个新的矩阵用于记录更新后的数据，然后完整的把新的数据复制回原地即可（直接用新的不好吗？）
更新过程的算法比较容易，我们遍历非边界的地方，然后判断存活邻居的个数，实际上只需要判断2个和3个就行，其他的无论如何都是死亡。
这里需要注意下，如果需求让你打印死亡或存活的原因，就不能这么更新了。这也是很多搞算法的同学容易忽略的，算法题往往只需要一个正确的结果，记录这个结果一个bit位或者一个int就能搞定，而真实的需求往往会要求记录更多的信息。在这个例子里，可能的需求就是记录下每个细胞存活和死亡的代数和原因，后面可能还有可能查出相同复活和死亡原因的细胞分布，或者统计每个细胞存活的代数。什么？你没记？你怎么能不记呢？不记到时候加需求你怎么做啊？hhhhhh
程序的运行应当尽可能的留痕以供人工查阅或后期处理，记录尽可能原始的数据，而不是像AI神经网络一样输出一个莫名其妙大概率正确的结果而不知道为什么
如果考虑实际需求，那么数组的类型就不能是int了，还得再套个对象，记录当前细胞每代更新对自己的影响结果这种原始数据备用，可以用于计算它的出生代数、死亡代数、存活实际等其他数据，以防产品后面加需求。这是一个来自刚工作几年没少踩坑的开发的经验之谈，信不信由你

输入和输出
程序一般设计上是给很多人使用的，输入和输出的方法通常是最长的，输入的程序需要完整检查用户出入的正确性和一致性，输出要合理的格式化，要好好考虑什么应该输出什么不应该

编程原则：
保持你的输出和输出再不同的方法里，来让他们可以被轻易的修改，让你的系统有一定的custom tailored

提示语打印程序是一个非常简单的程序，只负责打印提示

测试用例drivers
可以写一小段程序给一个方法提供一些特定的输入，单独测试一个方法的运行是否正常

程序跟踪和debug
一个很常用的工具就是打印语句，详细的打印程序执行时所处的位置和相关变量的状态，生产环境一般用日志框架来处理，有的公司会有完整的日志收集、搜索、监控平台来做这件事情，自己写着玩直接print就好
脚手架代码也可以在debug的时候提供额外的帮助，用过之后记得删掉就好。当你的程序出现奇怪的错误时，脚手架代码可以放在1个或2个主程序的关键位置，用于快速确认问题出现的具体行数。

程序测试原则
测试数据的质量远比测试数据的数量要重要
程序测试可以证明bug的存在型，但无法证明bug不存在

程序测试方法
黑盒测试
使用普通数据、特殊的正常数据、边界附近的数据、非法的数据（参考测试工程师进酒吧）

白盒测试
分析程序的的每个分支，对每个执行路径都进行测试，大型程序种这种测试并不现实，一般选择性测试主要的执行路径

Ticking-Box测试
不知道怎么翻译，翻译成随缘测试吧hhh
写完了让用户自己去用吧，出了问题一定是你不会用，才不是bug呢


import java.util.Scanner;

import javax.print.attribute.standard.PrinterLocation;

public class Main0510_1 {
    /**
     * 前置条件：用户指定了初始布局
     * 预期结果：根据规则打印所有存活的细胞
     * 依赖：Life类和成员方法initialize、print、update
     */
    public static void main(String[] args) {
        Life conf = new Life();
        instructions();
        conf.initialize();
        conf.print();
        System.out.println(&quot;是否继续下一代？&quot;);
        while (userSaysYes()) {
            conf.update();
            conf.print();
            System.out.println(&quot;是否继续下一代？&quot;);
        }
    }

    private static void instructions() {
        System.out.println(&quot;欢迎来到xxx游戏&quot;);
        System.out.println(&quot;这个游戏使用的布局大小是&quot; + Life.MAX_ROW + &quot;x&quot; + Life.MAX_COL);
        System.out.println(&quot;每个细胞都可以是活的也可以是死的&quot;);
        System.out.println(&quot;它们将一代代的根据邻居的存活数量不断迭代&quot;);
    }

    public static boolean userSaysYes() {
        try {
            Scanner in = new Scanner(System.in);
            boolean userInput = in.nextBoolean();
            return userInput;
        } catch (Exception e) {
            return userSaysYes();
        }
    }
}

class Life {
    public static final int MAX_ROW = 20;
    public static final int MAX_COL = 60;
    private int gird[][] = new int[MAX_ROW + 2][MAX_COL + 2];
    // 多两行两列用于方便计数，省的判断边界

    private int neighborCount(int row, int col) {
        int count = 0;
        for (int i = row - 1; i &lt; row + 1; i++) {
            for (int j = col - 1; j &lt; col + 1; j++) {
                count += gird[i][j];// 把存活的邻居记录上
            }
        }
        count -= gird[row][col];// 减去掉自己，因为自己不是自己的邻居
        return count;
    }

    public void initialize() {
        System.out.println(&quot;请输入存活细胞的坐标，以(-1,-1)结束，&quot;);
        System.out.println(&quot;格式为行&lt;空格&gt;列，从1开始数：&quot;);
        Scanner in = new Scanner(System.in);
        while (true) {
            int row = in.nextInt();
            int col = in.nextInt();
            // 正常程序建议in.nextLine()读入整行后trim
            // 然后先正则判断下格式对不对，避免脑残乱输入
            if (row == -1 || col == -1) {
                break;
            }
            boolean rowCorrect = row &gt;= 1 &amp;&amp; row &lt;= MAX_ROW;
            boolean colCorrect = col &gt;= 1 &amp;&amp; col &lt;= MAX_COL;
            if (!rowCorrect || !colCorrect) {
                System.out.println(&quot;行或列输入错误，MDZZ，再试一次吧&quot;);
                continue;
            }
            gird[row][col] = 1;
        }
    }

    public void print() {
        for (int row = 1; row &lt;= MAX_ROW; row++) {
            for (int col = 1; col &lt;= MAX_COL; col++) {
                int cell = gird[row][col];
                System.out.print(cell);
            }
            System.out.println();
        }
    }

    public void update() {
        int newGird[][] = new int[MAX_ROW + 2][MAX_COL + 2];
        for (int row = 1; row &lt;= MAX_ROW; row++) {
            for (int col = 1; col &lt;= MAX_COL; col++) {
                int neighborCount = neighborCount(row, col);
                if (neighborCount == 2) {
                    newGird[row][col] = gird[row][col];
                } else if (neighborCount == 3) {
                    newGird[row][col] = 1;
                } else {
                    newGird[row][col] = 0;
                }
            }
            gird = newGird;
        }
    }

}

100

101

102

103

104

105

106

107

108

109

110

import java.util.Scanner;

import javax.print.attribute.standard.PrinterLocation;

public class Main0510_1 {

/**

* 前置条件：用户指定了初始布局

* 预期结果：根据规则打印所有存活的细胞

* 依赖：Life类和成员方法initialize、print、update

public static void main(String[] args) {

Life conf = new Life();

instructions();

conf.initialize();

conf.print();

System.out.println("是否继续下一代？");

while (userSaysYes()) {

conf.update();

conf.print();

System.out.println("是否继续下一代？");

}

private static void instructions() {

System.out.println("欢迎来到xxx游戏");

System.out.println("这个游戏使用的布局大小是" + Life.MAX_ROW + "x" + Life.MAX_COL);

System.out.println("每个细胞都可以是活的也可以是死的");

System.out.println("它们将一代代的根据邻居的存活数量不断迭代");

}

public static boolean userSaysYes() {

try {

Scanner in = new Scanner(System.in);

boolean userInput = in.nextBoolean();

return userInput;

} catch (Exception e) {

return userSaysYes();

}

class Life {

public static final int MAX_ROW = 20;

public static final int MAX_COL = 60;

private int gird[][] = new int[MAX_ROW + 2][MAX_COL + 2];

// 多两行两列用于方便计数，省的判断边界

private int neighborCount(int row, int col) {

int count = 0;

for (int i = row - 1; i < row + 1; i++) {

for (int j = col - 1; j < col + 1; j++) {

count += gird[i][j];// 把存活的邻居记录上

}

count -= gird[row][col];// 减去掉自己，因为自己不是自己的邻居

return count;

}

public void initialize() {

System.out.println("请输入存活细胞的坐标，以(-1,-1)结束，");

System.out.println("格式为行<空格>列，从1开始数：");

Scanner in = new Scanner(System.in);

while (true) {

int row = in.nextInt();

int col = in.nextInt();

// 正常程序建议in.nextLine()读入整行后trim

// 然后先正则判断下格式对不对，避免脑残乱输入

if (row == -1 || col == -1) {

break;

}

boolean rowCorrect = row >= 1 && row <= MAX_ROW;

boolean colCorrect = col >= 1 && col <= MAX_COL;

if (!rowCorrect || !colCorrect) {

System.out.println("行或列输入错误，MDZZ，再试一次吧");

continue;

}

gird[row][col] = 1;

}

public void print() {

for (int row = 1; row <= MAX_ROW; row++) {

for (int col = 1; col <= MAX_COL; col++) {

int cell = gird[row][col];

System.out.print(cell);

}

System.out.println();

}

public void update() {

int newGird[][] = new int[MAX_ROW + 2][MAX_COL + 2];

for (int row = 1; row <= MAX_ROW; row++) {

for (int col = 1; col <= MAX_COL; col++) {

int neighborCount = neighborCount(row, col);

if (neighborCount == 2) {

newGird[row][col] = gird[row][col];

} else if (neighborCount == 3) {

newGird[row][col] = 1;

} else {

newGird[row][col] = 0;

}

gird = newGird;

}

20220511结束，耗时一个半小时，明天继续看程序的评估

20220510数据结构绿书读书笔记

20220510
解决方案：类、对象、方法
大概来说，一个程序运行上述游戏需要以下几个部分组成
1.算法
设置一个初始布局状态，打印这个布局状态，当用户想看下一代的时候根据规则更新布局状态并打印当前状态

2.类和对象
一个configuration布局实体/实例/对象，类型是Life，我们让这个对象使用Life的3个方法：initialize将会初始化一个最开始的状态，print打印当前布局，update让布局更新为下一代

一个Clients类，用于访问前面的对象，可以声明前面这些类的实例。一般可以叫做Main活着xxxTest之类的都ok

3.规范
当编写一个客户端程序的时候，一个很重要的点是我们不需要知道数据是如何存储的，也不需要知道这些方法是如何被编程的。这是自顶向下设计非常重要的一个转变，写代码多了就会熟悉这种思路。这通常被称为information hiding
当我们实现Life类的时候，我们才需要决定如何存储这些数据，以及如何实现这些方法，这些数据和方法对Life来说都是私有的，client程序不需要知道这些，只需要访问公开的方法即可


import java.util.Scanner;

public class Main0510_1 {
    /**
     * 前置条件：用户指定了初始布局
     * 预期结果：根据规则打印所有存活的细胞
     * 依赖：Life类和成员方法initialize、print、update
     */
    public static void main(String[] args) {
        Life conf = new Life();
        instructions();
        conf.initialize();
        conf.print();
        System.out.println(&quot;是否继续下一代？&quot;);
        while (userSaysYes()) {
            conf.update();
            conf.print();
            System.out.println(&quot;是否继续下一代？&quot;);
        }
    }

    private static void instructions() {
        System.out.println(&quot;打印使用指南&quot;);
    }

    public static boolean userSaysYes() {
        Scanner in = new Scanner(System.in);
        boolean userInput = in.nextBoolean();
        return userInput;
    }
}

import java.util.Scanner;

public class Main0510_1 {

/**

* 前置条件：用户指定了初始布局

* 预期结果：根据规则打印所有存活的细胞

* 依赖：Life类和成员方法initialize、print、update

public static void main(String[] args) {

Life conf = new Life();

instructions();

conf.initialize();

conf.print();

System.out.println("是否继续下一代？");

while (userSaysYes()) {

conf.update();

conf.print();

System.out.println("是否继续下一代？");

}

private static void instructions() {

System.out.println("打印使用指南");

}

public static boolean userSaysYes() {

Scanner in = new Scanner(System.in);

boolean userInput = in.nextBoolean();

return userInput;

}

编程中一个相当重要的道德行为就是命名规范，尽管数据和算法之前就存在了，但只有当给他们有意义的名字的时候，他们才能被正常的阅读。为了精确的理解每个变量和方法的作用，有时需要给类、变量、方法编写文档来说明。它们的名字应当简洁且清晰的精确表示他们的含义，寻找一个好的变量名并不总是一个简单的工作

使用小写字母l、大写字母O、数字0的时候需要额外的注意，底下是一个蛋疼的例子(吐槽下苹果上对于括号的渲染，也是个大坑)


l = 1; x = 1; x = l; x = O; O = 0;

l = 1; x = 1; x = l; x = O; O = 0;

注释要避免解释代码本身的动作，解释Why，而不是解释How


 count ++ //count自增1
 count ++ //增加xxx的计数，这里的xxx是上下文相关的，count的实际含义，虽然我一般会直接用xxxCount来避免这种注释

count ++ //count自增1

count ++ //增加xxx的计数，这里的xxx是上下文相关的，count的实际含义，虽然我一般会直接用xxxCount来避免这种注释

编程原则:

让程序的阅读起来更容易，因为一个程序的阅读时间要远多于编写时间
不要丢掉全局视野
用类来对基础概念进行建模
每个方法都应该只做一件事，但做到极致
每个类都应该隐藏一些东西
保持上下文简洁、如非必要，不要用全局变量
尽可能的避免边际效应，如果一定要用全局变量，写文档

编码&测试&重构
stub打桩技术，快速让主程序通过编译或为了方便测试，可以先搭架子


import java.util.Scanner;

public class Main0510_1 {
    /**
     * 前置条件：用户指定了初始布局
     * 预期结果：根据规则打印所有存活的细胞
     * 依赖：Life类和成员方法initialize、print、update
     */
    public static void main(String[] args) {
        Life conf = new Life();
        instructions();
        conf.initialize();
        conf.print();
        System.out.println(&quot;是否继续下一代？&quot;);
        while (userSaysYes()) {
            conf.update();
            conf.print();
            System.out.println(&quot;是否继续下一代？&quot;);
        }
    }

    private static void instructions() {
        System.out.println(&quot;打印使用指南&quot;);
    }

    public static boolean userSaysYes() {
        Scanner in = new Scanner(System.in);
        boolean userInput = in.nextBoolean();
        return userInput;
    }
}

class Life {

    public void initialize() {
    }

    public void print() {
    }

    public void update() {
    }


}

import java.util.Scanner;

public class Main0510_1 {

/**

* 前置条件：用户指定了初始布局

* 预期结果：根据规则打印所有存活的细胞

* 依赖：Life类和成员方法initialize、print、update

public static void main(String[] args) {

Life conf = new Life();

instructions();

conf.initialize();

conf.print();

System.out.println("是否继续下一代？");

while (userSaysYes()) {

conf.update();

conf.print();

System.out.println("是否继续下一代？");

}

private static void instructions() {

System.out.println("打印使用指南");

}

public static boolean userSaysYes() {

Scanner in = new Scanner(System.in);

boolean userInput = in.nextBoolean();

return userInput;

}

class Life {

public void initialize() {

}

public void print() {

}

public void update() {

}

20220510结束，耗时1小时10分钟
顺带一提，vscode Code-runner跑代码乱码可以这样解决


    &quot;code-runner.executorMap&quot;: {
        &quot;java&quot;: &quot;cd $dir &amp;&amp; javac -encoding utf-8 $fileName &amp;&amp; java -Dfile.encoding=UTF-8 $fileNameWithoutExt&quot;
    }

"code-runner.executorMap": {

"java": "cd $dir && javac -encoding utf-8 $fileName && java -Dfile.encoding=UTF-8 $fileNameWithoutExt"

}

20220509数据结构绿书读书笔记

20220509
数据结构读书笔记
全书目录如下
1.编程原则
2.栈
3.队列
4.链栈&队列
5.回溯
6.列表和串
7.搜索
8.排序
9.表格与信息检索
10.二叉树
11.多叉树
12.图
13.波兰式

开坑！

第一章其实上学时候就看过，我很多的习惯都是因为这本书才养成的，但当时并没有记录- -，这次一并补上，看英文书的好处就是写的足够详细，什么时候读都能get到作者的意思，不好的地方就是太啰嗦了。但好在我是为了消磨时间才立的这个flag
编写一个large的程序往往有很多问题，这里的large可以理解为实现复杂或者规模庞大
问题1.精确的定义问题
拆分并逐渐分割成小问题，直到可以方便处理
问题2.程序设计
“先跑起来再慢慢优化”对小程序也许有用，但并不适合large的程序，大型程序的每个部分都需要良好的组织、清晰的实现、良好的可读性，否则它将难以复用或被他人阅读
问题3.选择合适的数据结构
同一个问题多种算法和数据结构都能解决，很难选择出一个最好的。在算法设计上一般来说选择的最好方法是看数据是如何存储的：
1.数据之间的关系是怎样的
2.那些数据保持在内存中
3.当需要的时候哪些数据已经被计算好了
4.哪些数据是存在文件里的？文件是如何被组织的
后面会先学列表、栈、队列，然后再学几个厉害的算法来对数据做处理，比如排序和搜索
问题4.算法分析
当有多种方法管理数据和设计算法的时候，就必须有一个标准来帮忙评判算法。
问题5.测试和验证程序的正确性
debug程序的难度会随着程序的规模而增加，可能是指数级
正确性：减少错误，让程序更加方便维护、方便我们验证算法是正确的、有方法可以测试我们的程序，让我们自信的说程序没有非预期行为

问题6.维护
当程序开始提供服务后，可能还会有新的需求

吹一波C++NB：
C++允许抽象数据、允许面向对象设计、允许自顶向下的设计方法、允许代码重用。。。。。

casestudy GameOfLife
cell不知道是翻译作细胞更好，还是叫单元格更好，反正前面都说grid的了，我就先当成细胞了
生存模拟，在一个无边界的矩阵中每个细胞都可以被有机物占用或不占用，被有机物占用的被称作“活着”，未被占用的称作“死的”
规则如下
1.给定1个细胞，它相邻的8个细胞都可以被接触，横竖斜都可以，称之为邻居
2.如果一个细胞活着，但同时邻居都没有存活，或仅剩1个存活，则在下一代将因孤独而死
3.如果一个细胞活着，但同时有4个或4个以上的邻居存活，则在下一代将因拥挤而死
4.如果一个存活的细胞有2个或3个邻居存活，则在下一代可以继续保持存活
5.如果一个细胞死了，但如果正好有3个活着的邻居，那么在下一代将被复活。所有死亡的其他细胞在下一代将保持死亡状态（这不是废话么hhh）
6.所有的生死均在一瞬间同时完成，所以正在死亡的细胞可以帮助其他细胞复活，但无法阻止其他细胞因拥挤导致的死亡。刚出生的细胞也无法复获或杀死上一代存活的细胞

一组特定排列的细胞叫做初始布局，上面的规则描述了一个布局如何在每代更替中变为下一个布局

多样性；有的布局会很快死干净、有的会从很小一点涨到巨大。。。难以人工预测
小目标：写一个程序模拟一个初始布局是如何一代代变化的
这个游戏被发明后不久，MARTIN GARDNER就在Scientific American的专栏里讨论过，被很多人所吸引

跳过面向对象基础部分，直接进入正题

本书的后续将严格区分method和function，中文翻译为方法和函数，方法是公开的，函数是私有的。（我写笔记会尽量遵守，但不保证hhhh

虽然书用的是C++，但并不影响我使用Java来表达相同的内容，代码将于我觉得可以的时机，公开在github和gitee上
耗时一个半小时，才读了8页hhhh，能读得完么= = 后面少记点笔记也许能读的快点
20220509结束

20220424树的布局算法

某群友需要绘制树形结构数据到excel中，拍脑袋想了下感觉不是很难，遂给出算法分析。

偷懒用了excel的column和row函数获取所在行列，直接能看到结果，目测也是算得出来结果的

因为要求是横着的，所以例子是横着的。但算法定义时候是竖着思考的，所以用的是宽度w和距离左侧的宽度l，算完了再横过来画就完了

首先这样定义子节点宽度：
当不存在子节点(即叶子节点)时，宽度为1
当存在子节点时，如果子节点为奇数n则宽度为n，如果为偶数n则宽度为n+1。说明：因为偶数的情况下父节点需要居中占一个，(n+1)/2的位置要空着给父节点
然后计算节点距离左侧长度l：取已知的层序i
如果是非叶子节点：取上一步宽度w, l=(w-1)/2，如果i>1再加上前面所有节点计算的宽度，如果当前层是偶数个子树则再+1
如果是叶子节点，取所在子树上一步计算的宽度，直接铺开排列。非首个子树加下前面的所有宽度，注意偶数子树情况下中间空1个。

偷懒没实现，谁有兴趣可以写下代码试试，允许使用任意数据结构存储相关信息

有个好的文章参考

https://llimllib.github.io/pymag-trees/