【说明】<br /> 已知类LinkedList表示列表类，该类具有四个方法addElement()、lastEl..

免费智能真题库 > 历年试卷 > 程序员 > 2009年下半年程序员下午试卷案例

第5题

知识点：继承栈 C++

【说明】
已知类LinkedList表示列表类，该类具有四个方法:addElement()、lastElement()、number-OfElement()以及removeLastElement()。四个方法的含义分别为：
void addElement(Object)：在列表尾部添加一个对象；
Object lastElement()：返回列表尾部对象；
int numberOfElement()：返回列表中对象个数；
void removeLastElement()：删除列表尾部的对象。
现需要借助LinkedList来实现一个Stack栈类，C++代码1和C++代码2分别采用继承和组合的方式实现。

问题：5.1

若类LinkedList新增加了一个公有的方法removeElement(int. index),用于删除列表中第index个元素，则在用继承和组合两种实现栈类Stack的方式中，哪种方式下Stack对象可访问方法removeElement(int index)? (5) (A.继承B.组合）


知识点讲解
· 继承 · 栈 · C++

继承

C++最重要的性能之一是代码重用。但是，为了具有可进化性，我们应当能够做比复制代码更多的工作。在C的方法中，这个问题未能得到很好的解决。而用C++，可以用类的方法解决，通过创建新类重用代码，而不是从头创建它们。这样，就可以使用其他人已经创建并调试过的类。创建一个新类作为一个已存在类的类型，采取这个已存在类的形式，对它增加代码，但不修改它。这个有趣的活动被称为继承，其中大量的工作由编译器完成。继承是面向对象程序设计的基石。

继承的一般形式如下：

访问权限是访问控制说明符，它可以是public、private或protected。派生类与基类是有一定联系的，基类描述一个事物的一般特征，而派生类有比基类更丰富的属性和行为。如果需要，派生类可以从多个基类继承，也就是多重继承。通过继承，派生类自动得到了除基类私有成员以外的其他所有数据成员和成员函数，在派生类中可以直接访问，从而实现了代码的复用。派生类对象生成时，要调用构造函数进行初始化。编译器的调用过程是先调用基类的构造函数，对派生类中的基类数据进行初始化，然后再调用派生类自己的构造函数，对派生类的数据进行初始化工作。当然，在派生类中也可以更改基类的数据，只要它有访问权限。每个派生类只需要编写与基类行为不同或扩展的方面。

例如：A是基类，B是A的派生类，那么B将继承A的数据和函数。代码如下：

这个简单的示例程序也说明了：C++的"继承"特性可以大大提高程序的可复用性。

栈

栈的定义

栈是只能在表的一端进行插入、删除的线性表。栈中允许插入、删除的一端称为栈顶，相反，栈中不允许插入、删除的一端称为栈底。处于栈顶位置的数据元素称为栈顶元素，不含任何数据元素的栈称为空栈。栈的特点为后进先出（Last In First Out, LIFO）。

下图是一个栈的示意图，通常用指针top指示栈顶的位置，用指针bottom指向桟底。栈顶指针top动态反映栈的当前位置。

栈的出入示意图

栈的基本操作

栈的基本操作主要有以下6种。

.InitStack（&S）：初始化操作，构造一个空栈S。

.StackEmpty（S）：若栈S为空栈，返回1，否则返回0。

.Push（&S, e）：插入元素e为新的栈顶元素。

.Pop（&S,&e）：删除S的栈顶元素，并用e返回其值。

.GetTop（S,&e）：用e返回S的栈顶元素。

.ClearStack（&S）：将S清为空栈。

栈的顺序存储结构

栈的顺序存储用向量作为栈的存储结构，向量S表示栈，m表示栈的大小，用指针top指向栈顶位置，S[top]表示栈顶元素，当在栈中进行插入、删除操作时，都要移动栈指针；而当top=m-1时，则栈满，当top=-1时，表示栈空。同时为了避免浪费空间可以采用双栈机制，即向量的两端为栈底。

栈的顺序存储结构的C语言描述如下：

栈的说明如下。

.由于C语言的数组下标的范围从0至StackSize-1，初始化设置sq.top=-1。

.栈空条件为sq.top=-1，栈满条件为sq.top=StackSize-1。

.栈顶元素为sq.data[sq.top]。

.元素压栈的规则为：在栈不满时，先改变栈顶指针（top=top+1），再压栈。出栈时，在桟非空时，先取栈顶元素的值，再修改栈顶指针（top=top-1）。

.栈中元素的个数为当前栈顶指针加1。

在顺序栈上实现基本操作的有关函数如下。

1）初始化InitStack（SqStack *S）

2）判空StackEmpty(SqStack S）

3）压栈Push（SqStack *S, ElemType e）

4）出栈Pop（SqStack *S, ElemType *e）

5）取栈顶GetTop（SqStack *S, ElemType*e）

6）清栈ClearStack（SqStack *S）

栈的链式存储结构

栈的链式存储也叫链栈，我们把插入和删除均在链表表头进行的链表称为链栈。链栈也分有头节点和无头节点两种。带头节点的链栈操作比较方便。

链栈的节点类型定义如下：

链栈的约定与说明如下。

.栈以链表的形式出现，链表（不带头节点）首指针为S，即栈顶为S，链表尾节点为栈底。

.初始化时，S=NULL（不带头节点）；S=（LStack *），malloc（sizeof（LStack）），S→next=NULL（带头节点）。

.栈顶指针的引用为S（不带头节点）或S→next（带头节点），栈顶元素的引用为S→data（不带头节点）或S→next→data（带头节点）。

.栈空条件为S==NULL（不带头节点）或S→next=NULL（带头节点）。

.进栈操作和出栈操作与单链表在开始节点的插入和删除操作一致。

对不带头节点的链栈，其基本操作函数如下。

1）初始化initstack（LStack *S）

2）压栈（入栈）push（LStack *S, ElemType x）

3）退栈（出栈）pop（LStack *S, ElemType *x）

4）读栈顶元素gettop（LStack *S, ElemType *x）

5）判栈空isempty（LStack *S）

栈的应用

栈具有广泛的应用，例如，求表达式的值及递归到非递归等。

1）表达式求值

在源程序编译中，若要把一个含有表达式的赋值语句翻译成正确求值的机器语言，首先应正确地解释表达式。例如，对赋值语句X=4+8×2-3；，其正确的计算结果应该是17，但若在编译程序中简单地按自左向右扫描的原则进行计算，则为：X=12×2-3=24-3=21。这个结果显然是错误的。因此，为了使编译程序能够正确地求值，必须事先规定求值的顺序和规则。通常采用运算符优先法。

2）递归到非递归

将一个递归算法转换为功能等价的非递归算法有很多方法，可以使用栈保存中间结果。其一般形式如下：

例如，求n！的递归函数如下：

使用转换成等价的非递归算法如下：

其中，st[top][0]用于存放n值，st[top][1]用于存放n！值，在初始时，设置st[top][1]为0，表不n！尚未求出。

C++

C++语言是一种面向对象的强类型语言，由AT&T的Bell实验室于1980年推出。

C++语言是C语言的一个向上兼容的扩充，而不是一种新语言。C++是一种支持多范型的程序设计语言，它既支持面向对象的程序设计，也支持面向过程的程序设计。

C++支持基本的面向对象概念，包括对象、类、方法、消息、子类和继承。C++完全支持多继承，并且通过使用try/throw/catch模式提供了一个完整的异常处理机制。它同时支持静态类型和动态类型，也完全支持多继承，不提供自动的无用存储单元收集，这必须通过程序员来实现，或者通过编程环境提供合适的代码库来予以支持。

题号导航 2009年下半年程序员下午试卷案例

本试卷我的完整做题情况



	第5题在手机中做本题