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结束

0 Comments
Leave a Reply