20220520数据结构绿皮书读书笔记
TMD都520了，我却只能在这里读书

4.1 指针和链式结构

用数组迟早会溢出，所以有一种内存结构是指针，每次只申请一小块，记录下一个内存的地址，串起来
contiguous list 和linked list英文上统称是list，不知道咋翻译
中文第一个可以叫线性表，第二个叫做链表。区别就是一个内存上连续，一个不连续。但统称一般也被翻译为线性表，就混淆了

动态内存申请，C/C++支持使用new和delete进行动态内存申请和释放

基础结构

4.2 链栈

细节略掉
实现时候注意next的修改顺序即可

4.3 安全措施

防止客户端内存泄漏，对于没有垃圾回收的语言，一旦内存动态申请忘了释放，时间长了就会出现内存泄漏

析构函数可以解决这个问题，当类的实例超出定义域时，会自动调用析构函数。这里记得清理动态申请的内存

运算符重载，C++特性，我们可以重载赋值操作的含义，正常的赋值操作是指针地址的拷贝。但自定义类中我们可以定义不同类的对象和我们定义的类做运算时具体的行为，允许覆盖已有的操作符来简化写法。但这个也是个大坑，运算符里可能包含了非预期行为，需要看源码才能知道

当复制一个对象的时候调用拷贝构造函数，完整复制一个对象的实例
这里需要知道深浅拷贝的概念，如果一个对象里包含另一个对象，浅拷贝就是单纯的每个字段都复制过去，但对象不复制。深拷贝就是把对象递归的做浅拷贝，递归到最后都是基本类型。拷贝的深度由各个类实现的拷贝构造函数自行决定

4.4 链式队列

细节略掉
实现时候注意next的修改顺序即可

4.5 链式结构应用 多项式算数

我们小学二年级就学过的省略加号的代数和，分开存x的系数和指数，可以把多项式的项可以认为都是相加，如果需要相减把系数改为负数即可，常数项指数为0即可。

总结
数据结构的分层结构，从抽象到具体

数学概念：序列Sequence
抽象数据类型：General list、Stack、Queue
数据结构：（以队列为例）Physical、Linear、Circular、Linked
实现：Array(Linear)、Array+计数器/flag/空格占位（Circular）、两个指针/首尾指针/数组+两个指针（Linked）
应用：排队的人（Physical）、机场模拟

5 递归

5.1 介绍

自程序调用的栈帧，当计算机执行的程序调用另一个程序或子程序的时候，子程序返回需要知道返回到什么位置，因此操作系统需要记录调用方。每一层调用的记录称作栈帧，做法是调用的时候把当前地址或下一个地址压栈，当程序执行完成后从栈中pop出下一条指令的地址继续执行。

这个调用过程中是个树型的结构，被调用的子程序是父程序的子节点。开始的程序是树根、调用层次是树的高度。相同层级的子程序是兄弟节点。。。树的基础定义不再赘述

阶乘定义同理，也是递归定义

汉诺塔游戏，也可以递归。顺带一提九连环也是

注意，计算机递归调用方法是有限制的，不能无限制的递归下去。因此一些时候需要对递归做优化，消除递归调用

5.2 递归原则

设计递归算法的套路是
找到停止规则，也就是基值条件。
找到关键步骤，那个关键步骤是可递归的
列出您的算法伪码或大纲
检查是否可终止
画出递归树

虽然递归好写，但执行需要消耗大量时间和空间。必要时候需要考虑递归的消除
1.分布式，拆分独立的子问题，分布式异步/并行处理
2.单线程处理，压缩存储需要重复执行的内容
3.程序重用，核心程序只有一份
4.栈和树可相互转化

尾递归可直接优化

不能用递归实现的场景
1.阶乘，递归层级会随着输入暴涨
2.斐波那契数列，同理
比较迭代和递归，计算阶乘的时候如果用迭代算法从1开始，空间消耗永远都是1。而递归是从n开始，消耗是O(n)。而斐波那契数列的计算则更离谱，分裂导致了指数级的增长，如果使用迭代则可以消除所有重复任务的计算时间和空间

输出大小的比较，对于斐波那契数列而言输出永远是O(n)，而汉诺塔、九连环这类输出是指数级上升的

决定是否使用递归的好方法：
分析递归树，如果简单则可以使用，如果复杂则放弃。处理问题自顶向下设计的时候可以考虑递归，但实现时候要看具体情况决定是否转为迭代算法

5.3 回溯

练习：八皇后/n皇后问题
规则：n*n的棋盘内，皇后棋子两两之间不能在相同的横、竖、对角线上

这里会用到回溯算法，当子问题不可解导致父问题终结时，需要尝试下一个父问题
还会用到一种方法，打印每个单元格的横纵坐标，来观察坐标规律来决定如何实现横竖对角线的判断。当然如果你的平面几何学的足够好，可以直接套用公式或者在公式基础上直接优化实现即可。
直接给结论，如果row-column相等则是f(x)=c-x这条线上的。如果row+column相等则是f(x)=c+x这条线上的，注意数学坐标轴和棋盘是反的。
证明：显然嘛
f(x1) + x1 = c = f(x2) + x2 = y1 + x1 = y2 + x2;
f(x1) – x1 = c = f(x2) – x2 = y1 – x1 = y2 – x2;

优化方案
寻找重复的子问题问题，可以直接记录前一次的运行结果。如果你分析的足够好，可以直接用这个子问题的结果来直接做类似于动态规划的题

回溯算法的效率分析
上限分析
对八皇后来说，总的探索空间有8*8=64个格子，从里面挑选8个皇后的组合C(64,8)有
4426165368个，不会算组合数的回去补下概率论和数理统计，或者复习复习高中数学

如果加上条件限定，每行只能有一个，则这个结果可以减少到8^8=16777216个组合。解释下，每行有8个位置可选选8次，所以是8的8次方个。不是8*8，仔细想想原因！！！

如果继续加限定，每列只能有一个的话，结果减少到8的阶乘，也就是8!=40320个。解释下，每列选完了下一行可选列会少一个，所以是8765432*1=8!

这个数字对计算机来说完全ok，注意实际的程序在发现对角线的时候，会直接停止尝试下一行，直接放弃这个结果，所以总的尝试次数一定小于8!

下限分析
阶乘的增长也是相当快的，因此如果n皇后的n变大，还是很恐怖。
让我们简单思考下，当一个棋子被放置后，就同时排除了同行同列和两个对角线。
对于第1行，回溯算法会尝试n个位置
对于第2行，最少要尝试n-3个位置
对于第3行，最少要尝试n-6个位置
因此，仅仅为了尝试前n/4行，就至少需要n(n − 3)(n − 6). . . (n − 3n/4)这么多次数
估算下，最后一个因子是n/4,前面的因子一定大于n/4，所以结果一定大于(n/4)^(n/4)个位置。这是寻找函数下界的一种方式，虽然不是下确界，但也足够我们分析算法了。不知道下界和下确界有啥区别的同学，建议回去复习高等数学（逃

结果的数量
我们并没有证明计算机可以在n很大的情况下打印出所有答案，只是证明了回溯法是不可能的。获取存在一种算法可以比回溯法更快的计算这个问题，但并不在这个case中。资料显示是可以证明n皇后问题的总数不会低于n的多项式，事实上显然这个数字甚至不能被表达成为k^n，其中k是常数，但这个结论的证明目前还没有（书不是最新的，最新的结论需要查下文献，懒得看了，至少这个书写的时候，还没有证明）

附八皇后代码，
单机版
https://github.com/956237586/DSExperiments/blob/master/DSExperiment2-1/DSExperiment2-1/Queen.c

mpich2分布式版本
https://github.com/956237586/DSExperiments/blob/master/DSExperiment2-1/DSExperiment2-1/Queen-mpich2.c
8皇后共92个答案，8节点机器下测试执行时间为0.017814s
16皇后共14772512个答案，4节点机器下测试执行时间为690.668119s，8节点执行时间358.213900s
有兴趣同学可自行搭建分布式平台测试

下周继续看树型结构
mark 目前是198页5.4 ，pdf是2159页

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

2.5.3 优化数据结构的定义

4个层次，1.概念，2.算法，3.编程，4.应用
分别对应抽象层 数据结构层 实现层 应用层
前两层聚焦于概念性的解决问题，中间两层更倾向于精确的方法来表达和操作数据，最后两层更关注如何写代码

编程原则
让你的数据结构化你的程序
一旦你的数据完全结构化了，你的算法就会几乎自然完成

总结

1. 用数据结构来使你的程序逻辑变得清晰
2. 实现数据结构的时候练习信息隐藏和封装，用方法来访问你的数据结构并保持他们在class内部，从应用程序程序中分离
3. 尽可能推迟你数据结构实现的细节
4. 栈是所有类型的数据结构中最简单的一个，当合适的时候使用栈
5. 在任意问题中需要反转数据的时候考虑使用栈
6. 避免使用奇技淫巧来存储你的数据，通常奇技淫巧不适用于其他场景
7. 确认你的数据结构被初始化了
8. 在算法设计的时候，永远细心小心的处理边界情况和极端情况，特别是数据结构是空或者是null的时候
9. 在选择实现方案之前确认所有数据结构和操作在抽象层都完整定义了

3 队列

3.1 定义

队列是一种列表，所有添加都在一侧进行，所有的删除都在另一侧进行
添加的那侧叫做front或head，删除的那侧叫做rear或者tail，通常翻译为队首和队尾

3.1.1 操作

1.初始化
2.append元素，参数x，类型T，返回错误码
如果有空间，x将被添加到队尾，否则返回overflow
3.serve元素，无参，返回错误码
如果队列非空，队首第一个元素将被移除，否则返回underflow
4.取出元素，参数x，类型T，返回错误码
如果队列非空，队首的元素将会被记为x，否则返回underflow
6.判断是否为空，无参，返回布尔值
判断当前队列是否是空，如果是空返回true，否则返回false

3.1.2 扩展操作

可以通过继承扩展操作，比如增加full方法判断是否满了，增加serveAndRetrieve来同时获取和移除队首元素

is-a关系，扩展的队列和原来的队列政治为is-a关系，因为每一个被扩展队列的对象，都是一个队列。如果我们看到Every A is a B这种短语，我们应当考虑实现派生类A作为B的子类。注意，C++一般叫做派生类和基类，java叫做父类和子类，有的时候可能混用

考虑这么几个类，大学，学生，大学生，人。每个学生都是人，每个大学生都是学生，也是人。大学和大学生之间的关系就并不是is-a了，但每个大学都有大学生（现在可不一定，疫情可能封校了hhhh），他们之间的关系是has-a关系

3.2 队列的实现

1.物理模型
如果使用数组实现，其中一种策略是保证队首永远在数组的开始位置，然后每添加一个元素则增加计数器并放到数组最后一个元素的后面。移除操作则相反，然而为了移除第一个元素需要昂贵的代价，移除后需要移动后面每一个元素到前一个位置。当队列变长后这种操作会变得十分缓慢，虽然我们的存储模型非常接近实际的排队模型，但给计算机使用太不合适了，垃圾

2.线性实现
为了更有效率我们需要同时追踪队首和队尾的位置，而不移动实际的数据，当数据增加的时候和1一样，但当数据减少的时候，我们直接把队首记录往后挪一个即可。虽然这种方式避免了移动数据，但这种方式有一个坏处，队首和队尾永远会无限增长下去，前面的内存都被浪费了。虽然可以通过动态内存的方式释放前面浪费的内存，但这样下去很快队首和队尾的指针就会增长到极限，然后boom。垃圾

3.循环数组
逻辑上把数组连接成一个环形，数据当到达数组最后一个元素的时候，返回数组的第0个位置继续使用

4.实现循环数组
用小学二年级就学习过的余数就能解决，当超过数组大小后，继续对队首和队尾的位置取余数即可返回第一个位置
5.c++里的循环数组

6.边界条件
注意如何判断队列的空或满，当使用循环数组的时候，当队首和队尾位置一样的时候，极有可能是空，也有可能是满
不详细解释了，自己画图试试就懂了

7.解决方案
7.1.保留一个空的位置，不用了，浪费一个空间
7.2.记录一个flag来表示空或者满，或者记录size
7.3.记录一个特殊值，这个值永远不可能出现的值

8.总结
物理模型，模拟实际物理空间队列的情况
线性数组，对物理模型进行优化得到
循环数组，对线性数组进行优化得到

3.3 C/C++基于循环数组实现的队列

https://github.com/956237586/DataStructure-C/blob/master/DataStructure-C/3.1.queue.h
https://github.com/956237586/DataStructure-C/blob/master/DataStructure-C/3.1.queue.c

https://github.com/956237586/DataStructure-C/blob/master/DataStructure-C/3.2.queue.h
https://github.com/956237586/DataStructure-C/blob/master/DataStructure-C/3.2.queue.c

3.4 证明和测试

一个最简单的方式就是编写一个菜单驱动的测试程序，让我们选择所有可能的操作来观察执行结果

3.5.队列的应用：模拟

模拟飞机跑道，模拟飞机起飞等。。。通常计算机模拟可以用来代替昂贵的物理模型模拟，而提前观察或预测实际的情况

顺带一提B站之前有个16级的学弟xyx用计算机模拟疫情传播的视频，就是一个很好的计算机模拟的例子

总结

1. 在选择实现方案之前确认所有数据结构和操作在抽象层都完整定义了
2. 在选择实现方案时，需要考虑数据结构上必要的操作
3. 如果每一个A类的实例都拥有所有B类实例的属性，考虑把A实现为B的派生类（这个不绝对，因为这个关系很可能被后期的需求变更打破）
4. 当声明基类的时候，考虑派生类的需求
5. 用public的继承可以实现is-a的关系
6. 用成员变量的方式实现has-a的关系
7. 可以用随机的变量来为随机事件建模

明天继续链表实现的栈和队列
mark 目前是113页 ，pdf是129页

为了良好的阅读体验，建议到个人博客或CSDN，QQ空间就是备份用的，tx看起来彻底放弃日志了。。。。

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

2.2.2 类的定义

2.2.3方法实现

具体实现C语言版参考我大学写过的代码

https://github.com/956237586/DataStructure-C/blob/master/DataStructure-C/2.1.stack.h

https://github.com/956237586/DataStructure-C/blob/master/DataStructure-C/2.1.stack.c

https://github.com/956237586/DataStructure-C/blob/master/DataStructure-C/2.2.stack.h

https://github.com/956237586/DataStructure-C/blob/master/DataStructure-C/2.2.stack.c

2.2.4 封装

注意我们的实现强制客户端来使信息隐藏，声明的private可见性的数据不可能被正式暴露的几个方法以外的方式来修改。这种数据可见性的好处是，无论客户端如何操作，正常来说不可能出现非法数据。

编程原则
数据结构的公开方法应当被实现成没有任何前提条件。成员数据应当保持私有化

2.3 应用：计算器

逆波兰式计算器
比较简单，都应该会写，略过

假设这个代码工作正常，解释下为什么这种风格是不好的？
显然同一行最好只做同一个动作，多个动作同时在一行代码里，一旦出错将难以定位是哪个方法的错误
有没有可能两个不同的C++编译器，都是严格遵循C++标准，但执行这个语句执行出不一样的结果？
理论上可能，numbers.pop() − numbers.pop()这个表达式的执行可能不是严格的先后顺序，导致两个数位置完全相反？

2.4 应用：括号匹配

相对简单，代码判断条件略复杂一点
在线处理算法需要stack记录所有的左括号，当碰到右括号需要和栈顶对比
非在线处理算法可以偷懒，读取过程可以先算下总数是否匹配，如果不匹配直接结束
匹配的话，再确定嵌套层次是否正确

2.5 抽象数据类型以及实现

2.5.1 介绍

在数据的逻辑结构和物理结构之间划分好边界可以更好的帮助我们设计程序。
举个例子：树形结构的逻辑结构是严格区分父子节点的，而树形结构的物理结构并不是。
我们可以使用三元组、链表、二维数组等多种方式表达相同的一个树形结构，但这些结构并不影响我们解决最终的问题
有时根据需求不同还需要对同一个逻辑结构同时使用多个物理结构来加速计算。举个常见的例子，部门的树形结构往往同时需要知道根节点到当前节点的路径，也需要按层次快速查找，还经常需要知道当前部门是第几层。如果按教科书教的树形结构存储，会发现大量数据都得重新计算，而在实践中，如果树形结构不经常变动，往往会将这些额外的信息提前计算后存到内存或者数据库，来方便后续开发

首先第一步是认识数据之间逻辑上的连接 和 在逻辑结构上表达这些连接

2.5.2 通用概念

1.数学定义

关键定义：”类型”是一个集合，集合的元素叫做这个类型的”值”
我们常说的integer类型意味着所有的整数集合，real类型意味着所有的实数集合，character类型意味着所有的字符的集合
注意，这里已经可以明确的区分抽象数据类型和实现了:例如C++里的int类型，其实并不是所有的整数集合，集合的大小取决于计算机的CPU字长。同理float和double也通常意味着浮点数类型(分别存储了尾数也就是指数、指数也就是幂次，详见计算机组成原理)，他们是所有实数中很小的一部分

2.原子性和结构化/结构体类型

如int,float,char通常成为原子类型，因为我们认为他们的值仅有一个元素，没有任何可分割的意图。计算机语言C++提供了如数组、类、指针等工具可以让我们构建一个新的类型，称之为结构体类型。单独一个值被封装进结构化类型是一个结构化的对象。一个结构化类型的价值有两个方面：1.它可以包含多个组件。2.它是有结构的，是按一组规则把组件放到了一起的
一般来说就像我们在数学中用应用的工具：集合、序列、函数一样。我们学习list的时候，list是有穷序列，但是当我们用数学定义的时候，可能是无穷的。

关键定义，有穷序列(finite sequence)定义如下：
A sequence of length 0 is empty. A sequence of length n ≥ 1 of elements from a set T is an ordered pair (Sn−1, t) where Sn−1 is a sequence of length n − 1 of elements from T , and t is an element of T .
自己细品定义，不翻译了
国内的翻译五花八门，其实看英文原文的话，有的细节就是形容词和名词的区别

从这个定义中我们可以清楚的划分sequential和contiguous的定义区别，sequential表示这些元素能形成sequence。contiguous意味着这些元素在内存地址上是相邻的。
sequential描述的是逻辑结构，而contiguous描述的是物理结构
因此我们可以这么说a sequential list in a contiguous implementation，也就是顺序表的连续实现(之所以这么翻译是因为还有顺序表的离散实现，也就是链表)

3. 抽象数据类型

有限序列(finite sequence)的定义让我们可以尝试开始定义list了：a list of items of a type T is simply a finite sequence of elements of the set T.
关键定义：T类型的集合中元素的有穷序列称之为T类型的list

细心的你一定发现了，stack的定义和list的定义没什么区别，唯一的区别限定是在对元素的操作上

一个T类型元素的有穷序列结合下列操作，称之为T类型元素的栈

1. “创建”栈
2. 测试栈是否为”空”
3. 给定一个”不满”的栈, “Push”一个新的元素到栈顶
4. 给定一个非空的栈，从栈顶”Pop”一个元素
5. 给定一个非空的栈，获取栈”顶”一个元素的值

注意这个定义没说怎么实现，称之为ADT，也就是抽象数据类型：
ADT有两个部分：1.定义数据和数据之间的关系。2.定义可以在这些数据上进行什么动作

明天继续
mark 目前是74页2.5.3 ，pdf是91页

20220517数据结构绿皮书读书笔记
2.1.栈的定义
2.1.1.列表list和数组array
思考一个问题：读取一个最大不超过25的整数n，然后读入n个数字，并逆序打印这些数字

有些人会觉得难，大多数人会意识到需要使用数组，但部分人尝试使用变量n声明和初始化数组的时候会看到报错（你看你非得用c++干嘛，java就不会报错，逃）
有的人会说：“如果我知道一共有25个数字那我就能解决了，但我看不到如何处理更少的数字”。或者说：“在我写程序之前告诉我n有多大我才能写”
这些人的困难并不是因为愚蠢（仅仅是因为用了C++，哈哈哈哈哈哈）,而是因为他们有逻辑的思考。
开始的课程并没有足够强调列表和数组的概念差异
第一个概念是n个数字，列表的大小是动态的，数字的列表可以被插入或删除。如果n = 3大小就是3，n等于几大小就是几
第二个概念是编程特性的概念，叫做数组array或者vectory，它包含固定数量的位置，它的大小在程序编译过后就固定了。

列表是抽象数据结构概念，是动态的。数组是具体数据结构实现的概念，是静态的结构
虽然一个变长的列表可以由静态数组保留一部分空间来实现，但我们不能因此混淆实现和基础概念定义之间关系
2.1.2.stack
栈是一个特殊版本的列表list，在做反转应用的时候特别的有用。在栈的结构里所有元素的插入push和删除pop都在同一端进行，叫做栈顶。注意这里的顶是个抽象概念，实际物理上可能不存在这个位置，只要结果对，实际上内存中的位置是中间也没关系。特性是先进后出
2.1.3.反转列表
书里的例子用的是STL实现的，这里略掉
2.1.4.信息隐藏
高级编程语言本身就是信息隐藏，隐藏掉了底层和CPU直接打交道的汇编和内存单元等大量的硬件细节。如果你做过CPU设计，那你就会知道微码层次的”编程”都是和寄存器和硬件打交道，最后被翻译成底层动作去控制集成电路引脚的电平。软件开发大多数情况下并不需要考虑这些细节，所以高级编程语言本身就是信息隐藏
当你面向抽象接口编程的时候，也是一种信息隐藏，具体的实现可以等后面再补或方便的更换

2.1.5 STL
STL本身是系统独立的，正确使用STL可以高效的编程，学习原则和标准库中这些数据结构的实现是有必要的。但后续主要目标是学习数据结构本身，所以不在赘述STL，也就是自己造轮子来学习
我们也可以选择基于vector或基于list实现的stack，为了选取合适的实现，开发者必须
理解他们的优缺点，这些理解只能来自于你长年累月的实践和扎实的理论学习
抛开选取实现来说，STL还保证了方法执行的效率，在stack不同的大小下操作都是固定的时间。在第七章我们将开始系统化的学习算法的时间性能。

2.2.stack栈的实现
2.2.1.栈的方法定义
empty(), top(), push(), pop() 还有init()这个基础操作来提供一个空的stack，否则将会可能存在无效数据
1.构造器/构造方法
前置条件：无
后置条件：存在一个初始化好了的空Stack
2.元素类型/泛化/泛型
C/C++元素类型可以用template来声明，或typedef来替换。java里可以用泛型
3.错误处理
C/C++可以遵循linux风格使用int作为返回值来做错误处理，也可以使用C++的异常处理
成功，上界溢出，下界溢出
succ, overflow, underflow
java可以使用异常来作为错误处理
编程原则：
client使用class方法的时候，应当有决定是否检查结果错误状态的权力，类应当被设计成允许调用方决定如何处理错误
4.方法定义

明天继续Stack类的定义
mark 目前是60页，pdf是77页

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数据结构绿皮书读书笔记
效率分析
程序运行哪里耗时最长？显然不是输入，因为只有一次，输出一般来说也很快。大量的计算都是在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页
明天和后天看心情更新