Video在线视频

同学们

大家好

我们这节课开始讲

怎么样利用已有的资源已有的代码

通过各种各样的组合

形成我们所需要的程序

前几节我们实际上通过各种方式

相当于把我们的需求

或者说我们所希望的程序

我们脑子里存在的这个程序

给它进行各种维度上的分解

通过这种分解使得一个复杂的程序

变成了一个又一个的相对比较简单

比较明了

比较容易表达的一个一个的模块

但是我们

经常会遇到这么样一种情况

当我们真正说去

完成一个程序的时候

完成一个软件系统设计的时候

我们并不是说是从

一张白纸上

或者从一个什么也没有的状态开始

一般情况下

我们会有一系列的已有资源

已有的代码

至少会有一些基础的东西

这就有点像我们前面说的

分久必合合久必分

我们前面把一个

系统分离成了很多小的部件

小的模块之后

我们现在就要考虑

怎么样去利用已有的各种小模块

去用组装的方式把它组装成

我们需要的一个比较大规模的

比较实用的

具有一定实际功能的程序

总的来讲

利用已有的资源

已有的代码组合成需要的程序

当然了你直接把原代码拷贝过来

然后修改修改

这也是一种方法

但是这个说实话

我们并不推荐这种方法

真正比较常用的几种方法

无非就是继承

组合和模板的实例化

继承就是我们已有的各种资源

实际上从我们面向对象

程序设计角度来看

就是已有的各种类

这些类已经完成了

放在那儿了

他具有它的接口

有它的功能

我们在这些类的基础之上

通过继承的方式产生出新的类

使这个新的类满足

利用原有的类的各种功能

然后满足我们的一些需求

这是一种方式

还有一种方式是组合

组合实际上就是把原有的类

已经实际上已经存在的这些类

他们产生的对象组合起来

形成一些新的类

通过这种方式

去将原有的功能进行组合

从而实现一些新的功能

至于实例化

就是像上节课我们讲的了

模板的实例化

当我们使用模板的时候

它是一种泛型编程的思想

在那里面它是把类型这个东西

先给抽离出去了

而实际上把实现的是

抽象的算法或者抽象的数据结构

类似这些问题

我们就可以针对这些抽象的算法

针对抽象的数据结构

根据我们的需求

把这个模板利用一些

实际上我们所需要的数据结构

数据定义数据类型

还有相关的一些算法细节

把它添到原来的抽象算法

或者是抽象数据结构里面去

从而使得这个抽象数据算法

或者抽象数据结构

成为一个适合于我们所需要的

这么一个对象或者说一个实际算法

这实际上都是我们常见的

利用已有的资源

组合出相应程序的一些最常见的手段

当然了

从我们实际使用来讲

实例化是属于受限比较多的了

如果你没有相应的抽象算法

没有相应的数据结构

抽象结构

那你也没法通过实例化的方式去使用

但是如果说我们已经有了

相应的抽象法的话

使用模板实例化来进行这种

对于已有资源的使用

实际上是最快捷

最有效的一种手段

从继承和组合这两者来看

一般的情况下

从我们推荐来讲

是优先使用组合而不是继承

原因很简单

因为组合相对继承来讲更加灵活

实现起来更加快捷

而继承相对来讲没有那么灵活

但是有一些情况下

我们是必然要使用继承的

就是说如果我的新代码里面

所涉及到的对象

和我原有的资源代码里的对象

他们之间确实天然上存在着

这种包含关系

存在着逻辑关系

就有点像比如说一个

06：43

这类的

一个抽象的东西

和一个实例之间的关系

或者说是这种包含关系

那么我们就应该使用继承的方式

把这个原有代码使用起来

那么具体来讲

我们怎么样在我们实际的程序里面

使用已有的代码

这实际上也有一些常见的手法

一些常见的例子

我们现在来看一个

我们要搞一个叫栈的

这么一个新的类型

栈实际上在计算机里面

是一种非常常用的数据结构

它和宿主很相象

是一段连续的存储空间

存储空间是分了很多的格子

每个格子是同类的数据

比如说都是整数或者都是浮点数

栈和宿主相比起来

不一样是在哪儿呢

宿主是属于随即访问的

你可以访问这个宿主里面

任何一个变量

而且宿主是定长的

比如说10个

那好OK

就10个输入

栈不一样在哪儿呢

它是一个可变长的

非随即访问的类型

栈有一个栈底

有一个栈顶

栈底是不变的

栈顶是可变的

我们每次

把栈的原数放入栈中的时候

总是把它放在栈顶上

每次从栈里面取出元素

也都是从栈顶取元素

而我们栈对外

只能看到栈顶这一个元素

这就有点像什么呢

我们以前有过那种

用来装硬币的那种直筒

它是一端封闭的

另一端开放

然后一个直筒

每次硬币都塞进去一个

每次塞进去一个

你总是只能看到那上面一个硬币

有点像那个东西

在计算机里边

这种每次都从一个方向

放入新数据和弹出原有数据

这种做法被称为后进先出

所以栈实际上

也是一种叫做后进先出的队列

因为什么你可以想象

每次你最后推进去那个数据

当取的时候它在栈顶

你是最先把它取出来的

所以它是后进

last in fast out

刚才我们说栈这个东西

它要往里推数据

往外拿数据

还要访问栈顶数据

除了这三个还要提供第四个

就是判断这个栈是不是空

所以栈的四个基本操作就是push

pop还有一个top

最后一个empty

这么四个操作

push pop是分别往里推数据

弹数据

top是看栈顶的那个数据

而empty就是看栈是不是空

为了方面起见

我们这里只用来实现整数的栈

其它的栈暂时不考虑

如果你要想去考虑一个

泛有类型的

就是我们前面说的那种泛型的栈

对于任何数据类型都可用的栈

那么实际上我可以参照

上一节课里面讲的有关

泛型变成那些内容

你就可以通过模板的

这种技术来得到这种泛型的栈

我们来看这儿有一段

栈基数组的实现

这个实现大家看一下

其实相对来讲比较简单

因为我们这里边

栈需要有一段存储空间

然后还要有一个

指出栈顶在哪儿的指针

相当于指针这么一个变量

我们这里就定义了一个m-data

这是存储空间

一个m-top

这个top就是栈顶的指针

我们看在初始化的时候

我们的m-top初始化是-1

这就说明我们这m-top

实际上指向是

我们上一个地址的意思

m-data来判断的时候

就是用m-top是不是小于0来判断

push的时候

当我们加入一个新的数据的时候

我们看这个例子里面

我们就是把m-top先++

然后再把新的数据

放在这个位置上

就像我们图中表示的这样

我们首先把m-top变到

它的下一个位置上去

然后再把那个data

放到对应的那个位置

从这儿大家也可以看到

我们为什么刚开始的时候

m- top要初始化为-1

top也是一样

我们就把m-top--就可以了

这样来讲

最顶端这个数据就没用了

顶上这个数据

就相当于被废弃掉了

top则是一个看栈顶的例子

我们这里边先判断一下是不empty

如果不是empty的话

那么我们把栈顶指针

指向的这个数据返回去

如果是empty了

那怎么办

我们用最小整数

作为一个标志给上一层

栈的定义就是这样

使用起来也非常的简单

我们看这个例子

这个teststack里面

我们先把四个数

push到Stack里面

要注意我这是从1到4

这四个数push进去

然后我们从里面连续的四次

输出栈顶的原数

并且再把栈顶原数

13：46出来

我们看这个结果是

我们push的时候

是以1 2 3 4的次序

push进去的

而输出的时候

次序变成了4321

表现了栈后入先出的特点

刚才是用宿主

我们自己去实现了栈这个东西

上节课呢

我们最后的时候给大家提到了

C语言里边有个SLT

标准模板库

我们仔细看STL里边

它有一个叫做vector的东西

vector这个容器呢

大家注意看呢

它里面实现了这几个方法

有push-mack

从尾巴上push进去一个元素

有size

获得这个vector的大小

有back

看尾巴上那元素是什么

还有个pop- back

这四个仔细来看这四个

方法或者这四个接口

功能上和我们前面所需要的

Stack的功能看起来很接近

我们现在就想

我们有没有可能

直接用vector来实现Stack呢

那么vector我们看

它实际上功能有push

有pop

有看back内容

又有总共有多大size

实际上功能它完全能够满足

Stack的需求

其实它完全能够供Stack用

但是问题在哪儿

接口和Stack不一致

就像我们这个屏幕上展示的似的

我们这个插座提供的也220伏电

我需要的也是220伏电

插头这边需要也是220伏电

但是现在的问题是什么呢

我这个插头插不进插座里去

那怎么办

其实从我们日常生活里

经常遇到这种事情

插座插不到插头里去

那怎么办呢

我们接一插线板

或者接一转接头

什么都OK了

从这个程序里面来看

我们是不是也可以用类似这种思路

通过转接的方式

来弥补接口的不同呢

相当于在两个类之间

能不能想办法接一个转接头呢

看这段

我们其实也可以这样去做

我可以用Uector实现Stack

我们看这个例子里面

首先在Vector Stack里面

我们定义了一个整数的Vector

然后呢你看empty

我们使用了Vector的某一个功能

去完成了它

push

我们调用了Vector的某一个功能

top也都一样

我们都调用了Vector相应的功能

去实现它

在这里面我们实质是

用Vector的功能

实现了Stack所需要的功能

实现了Stack的接口

我们现在去使用它

去运行它

我们看到相同的程序

我们push pop

最后得到的结果

也是跟刚才这些实现是一样的

说明我们这个Stack也能够满足

我们前边的定义

满足我们的需求