全部科目 > 程序员 >
2011年上半年 下午试卷 案例
第 4 题
知识点 数据类型   栈   数组  
 
 
假设一个算术表达式中可以包含以下三种括号：“(”和“)”、“[”和“]”及和 “}”，并且这三种括号可以按照任意的次序嵌套使用。
下面仅考虑表达式中括号的匹配关系，其他问题暂时忽略。例如，表达式 [a-(b-5)]*c[{}]中的括号是完全匹配的，而表达式[a-(b-5]))*c中的括号不是完全匹配的， 因为“(”与“]”不能匹配，而且多了一个“)”，即缺少一个与“)”相匹配的“(”。
函数ifMatched (char expr[])的功能是用栈来判断表达式中的括号是否匹配，表达式 以字符串的形式存储在字符数组expr中。若表达式中的括号完全匹配，则该函数的返回 值为Matched,否则返回值为Mismatched。
该函数的处理思路如下：
(1) 设置一个初始为空的栈，从左至右扫描表达式。
(2) 若遇上左括号，则令其入栈；若遇上右括号，则需要与栈顶的左括号进行匹配。
(3) 若所遇到的右括号能与栈顶的左括号配对，则令栈顶的左括号出栈' 然后继续匹配过程；否则返回Mismatched，结束判断过程。
(4) 若表达式扫描结束，同时栈变为空，则说明表达式中的括号能完全匹配，返回 Matched o
函数ifMatched中用到了两种用户自定义数据类型BOOL和STACK,其中，BOOL 类型的定义如下：
 
问题：4.1   填补C函数中的空缺（1)〜（5)




 
 
 
知识点讲解
· 数据类型
· 栈
· 数组
 
        数据类型
        C++中的数据类型完全包括了C的类型。同时，C++还新增了以下两个类型。
        （1）布尔类型：类型名bool，包括的数据true和false，表达逻辑操作的结果。bool类型还可以作为函数的返回类型，表示条件测试的结果。true可以对应整数1，false对应整数0。不为0的整型数据对应true；等于0的整型数据对应false。
        （2）抽象数据类型：类类型。
        归纳起来，C++语言中的类型有如下几种。
        基本类型：bool，char，int，double等。
        特殊类型：void。
        用户定义类型：enum，数组，结构，联合。
        指针类型：type*。
        抽象数据类型：类类型。
 
        栈
               栈的定义
               栈是只能在表的一端进行插入、删除的线性表。栈中允许插入、删除的一端称为栈顶，相反，栈中不允许插入、删除的一端称为栈底。处于栈顶位置的数据元素称为栈顶元素，不含任何数据元素的栈称为空栈。栈的特点为后进先出（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！尚未求出。
 
        数组
               数组的定义及基本运算
               一维数组是长度固定的线性表，数组中的每个数据元素类型相同。n维数组是定长线性表在维数上的扩张，即线性表中的元素又是一个线性表。
               设有n维数组A［b1，b2，…，bn］，其每一维的下界都为1，bi是第i维的上界。从数据结构的逻辑关系角度来看，A中的每个元素A［j1，j2，…，jn］（1≤ji≤bi）都被n个关系所约束。在每个关系中，除第一个和最后一个元素外，其余元素都只有一个直接后继和一个直接前驱。因此就单个关系而言，这n个关系仍是线性的。
               以下面的二维数组A［m］［n］为例，可以把它看成是一个定长的线性表，它的每个元素也是一个定长线性表。
               
               可将A看作一个行向量形式的线性表：
               Am*n=［［a11a12…a1n］［a21a22…a2n］…［am1am2…amn］］
               也可将A看作列向量形式的线性表：
               Am*n=［［a11a21…am1］［a12a22…am2］…［a1na2n…amn］］
               数组结构的特点如下：
               （1）数据元素数目固定。一旦定义了一个数组结构，就不再有元素的增减变化。
               （2）数据元素具有相同的类型。
               （3）数据元素的下标关系具有上下界的约束且下标有序。
               在数组中通常做下面两种操作：
               （1）取值操作。给定一组下标，读其对应的数据元素。
               （2）赋值操作。给定一组下标，存储或修改与其相对应的数据元素。
               几乎所有的程序设计语言都提供了数组类型。实际上，在语言中把数组看成是具有共同名字的同一类型多个变量的集合。需要注意的是，不能对数组进行整体的运算，只能对单个数组元素进行运算。
               数组的顺序存储
               由于数组一般不作插入和删除运算，也就是说，一旦定义了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动，因此数组适合于采用顺序存储结构。
               对于数组，一旦确定了它的维数和各维的长度，便可为它分配存储空间。反之，只要给出一组下标便可求得相应数组元素的存储位置，也就是说，在数据的顺序存储结构中，数据元素的位置是其下标的线性函数。
               二维数组的存储结构可分为以行为主序（按行存储）和以列为主序（按列存储）两种方法，如下图所示。
               
               二维数组的两种存储方式
               设每个数据元素占用L个单元，m、n为数组的行数和列数，那么以行为主序优先存储的地址计算公式为：
               Loc（aij）=Loc（a11）+（（i-1）×n+（j-1））×L
               同理，以列为主序优先存储的地址计算公式为：
               Loc（aij）=Loc（a11）+（（j-l）×m+（i-1））×L



更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5
京公网安备 11010502032051号 | 营业执照
 Copyright ©2000-2025 All Rights Reserved
软考在线版权所有