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

 

 

 

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页

 

0 Comments
Leave a Reply