作者:欧新宇(Xinyu OU)
当前版本:Release v1.0
开发平台:gcc 13.1.0, g++ 13.1.0, gdb 13.2
运行环境:Intel Core i7-13700KF CPU 3.4GHz, 32GB RAM
本教案所涉及的数据及代码仅用于教学和交流使用,请勿用作商用。
最后更新:2023年9月30日
作业要求:将【课后作业】的题目及程序代码整理成实验报告,并以PDF格式,或直接拍照上传到【雨课堂】(不要使用word文档进行上传)。
1. 对中缀算法表达式,可以借助运算符栈OPTR和运算数栈OPND进行求值,按照四则运算加、减、乘、除优先关系的惯例,以表格形式完成表达式3×(6-5)的求值过程,要求给出OPTR和OPND栈的具体变化过程。
算法提示:
- 在OPTR运算符栈中,运算符×、(、)将依次入栈;
- 在OPND运算数栈中,运算数3、6、5将依次入栈;
- 每当运算符和运算数满足计算规则,将执行计算(Push(OPND, Operate(OPND, OPTR, OPND))),并将运算结果写入运算数栈中。
步骤 | OPTR栈 | OPND栈 | 读入数据 | 主要操作 |
---|---|---|---|---|
1 | # | # | 3×(6-5)# | Push(OPND, 3) |
2 | # | 3 | ×(6-5)# | Push(OPTR, '×') |
补齐后续内容 | ||||
10 | # | 3 | # | return(GetTop(OPND)) |
【参考答案】
步骤 | OPTR栈 | OPND栈 | 读入数据 | 主要操作 |
---|---|---|---|---|
1 | # | # | 3×(6-5)# | Push(OPND, 3) |
2 | # | 3 | ×(6-5)# | Push(OPTR, '×') |
3 | #× | 3 | 6-5)# | Push(OPTR, '(') |
4 | #×( | 3 | 6-5)# | Push(OPND, '6') |
5 | #×( | 3 6 | -5)# | Push(OPTR, '-') |
6 | #×(- | 3 6 | 5)# | Push(OPND, '5') |
7 | #×(- | 3 6 5 | # | Push(OPND, Operate('6', '-', '5')) |
8 | #×( | 3 1 | # | Pop(OPTR){消去一对括号} |
9 | #× | 3 1 | # | Push(OPND, Operate('3', '×', '1')) |
10 | # | 3 | # | return(GetTop(OPND)) |
2. 回文是指正读反读均相同的字符序列,例如“level”和“eye”都是回文,但“Good”不是回文。试写一个算法判定给定的字符序列是否是回文。
算法提示:
- 回文可以通过比较中心元素两边等距离的元素是否相等来判定。需要注意的是,当字符串为奇数时,需要跳过中心元素;而当字符串为偶数时,直接对比字符串中间的两个元素。
- 在进行元素比较时,可以先用一个堆栈来对字符串前一半的元素进行入栈。在进行对比的时候,再逐个将堆栈中的元素进行出栈操作,此时从堆栈中获得的元素刚好是逆序的。
- 最后,通过从中间字符开始扫描后一半元素,并将其和堆栈栈顶弹出的元素进行对比。
- 若扫描完整个字符串后,所有对比元素均相等,则说明该字符串为回文。
bool isPalindrom(char *t){
// 在此处填入代码
}
【参考代码】
bool isPalindrom(char *t){
InitStack(S); // 1. 初始化一个栈
int len = strlen(t); // 2. 计算字符串的长度
for(int i = 0; i < len/2; i++){ // 3. 遍历字符串,将一半的元素进行入栈
Push(S, t[i]); // 当字符串为奇数时,len/2为浮点数,指针到达中间字符时停止入栈
if(len%2 == 1) // 4. 判断字符串是否为奇数,若是则需要跳过中间的字符
i++
while(!EmptyStack(S)){ // 5. 逐元素判定未入栈元素与栈顶元素是否相等
tmp = PoP(S);
if(tmp == t[i]) // 5.1 若相等,则说明该元素满足回文,继续判定下一个元素
i++;
else // 5.2 若不相等,则说明该元素不满足回文,直接返回false
return false;
}
return true;
} //isPalindrom
3. Q是一个队列,S是一个空栈,试实现将该队列中的元素进行逆置。
算法提示:
- 队列具有先进先出的特点,无法实现将元素逆置;而栈具有先进后出的特点,可以实现将元素逆置。因此,可以将队列Q和栈S进行结合,通过栈S实现将队列Q中的元素逆置。
- 具体操作上,可以先逐元素将队列中的元素全部输出到栈中;然后再将栈中的元素逐个输出到队列中。
Status Inverser(Stack &S, Queue &Q, ElementType &e){
// 在此处填入代码
}
【参考代码】
Status Inverser(Stack &S, Queue &Q, ElementType &e){
while(!QueueEmpty(Q)){ // 1. 逐元素将队列中的元素全部输出到栈中
e = DeQueue(Q);
Push(S, e);
}
while(!StackEmpty(S){ // 2. 逐元素将栈中的元素逐个输出到队列中
Pop(S, e);
EnQueue(Q, e);
}
}
4. 假设存在一个如下图所示的车厢调度系统,其左右两侧铁道均为单向行驶道,调度站有一个用于调度的栈道。火车调度站的入口处有n节硬座(H)和软座(S)车厢的火车。试编写一个算法,输出对这n节车厢进行调度的操作序列,以使所有的软座车厢都被调整到硬座车厢之前。
算法提示:
- 两侧的铁道均为单向行驶,因此,调度站只能从左侧铁道进入,然后从右侧铁道离开。此时,我们可以将两侧铁道看作是一个中间可进出的队列。
- 在队列的中间,存在一个堆栈,用于将软座车厢调整到硬座车厢之前。
- 算法的基本思想是让所有车厢依次在队列中前进,并逐一进行检查,若发现有硬座车厢则将其入栈,等待最后调度;其余车厢顺着队列前移动。
- 等所有车厢都完成检查后,将栈中的硬座车厢全部出栈,并跟随在前面的车厢之后,形成一个完整的队列。
void Train_Conductor(char *train){
// 在此处填入代码
}
【参考代码】
void Train_Conductor(char *train){
char *p = train, *q = train, c; // 1. 定义三个指针,分别指向车厢检查指针、检查后的队列指针及栈顶指针
stack S; // 2. 创建并初始化一个栈,用于保存硬件车厢
InitStack(S);
while(*p){ // 3. 逐个检查车厢,若发现有硬座则将其入栈,其余车厢顺着队列前移动
if(*p == 'H'){ // 3.1 入栈硬座车厢
Push(S, *p);
else // 3.2 其余车厢顺队列前移
*(q++) = *p;
p++;
}
while(!StackEmpty(S)){ // 4. 车厢检查完毕后,将栈中所有硬座车厢出栈,并送入队列,依次前移
Pop(S, c);
*(q++) = c;
}
}
某汽车轮渡口,过江渡船每次能载10辆车过江。过江车辆分为客车类和货车类,上渡船有如下规定:同类车先到先上船;客车先于货车上传,且每上4辆客车,才允许放上1辆货车;若等待客车不足4辆,则以货车代替;若无货车等待,允许客车都上传。试设计一个算法模拟渡口管理。
算法提示:
- 假定数组q的最大小标10为每次载渡的最大量。定义三个队列,分别用于存放渡船(Q)、客车(Q1)、货车(Q2)上车辆的数量;
- 根据题意,车辆调度可分为两种情况:
2.1 若Q1充足,则每取4个Q1的元素后,取一个Q2的元素,直到Q中的元素个数达到上限10;当取Q2元素时,每次完成后都对客车计数器清零。
2.2 若Q1不充足,则直接用Q2进行补齐。退出时,需要对客车计数器进行清零。
void vehicle_scheduling(Queue Q, Queue Q1, Queue Q2){
// 在此处填入代码
}
【参考代码】
void vehicle_scheduling(Queue Q, Queue Q1, Queue Q2){
int i = 0, j = 0; // 1. 定义两个计数器,分别记录队列Q和Q1中的元素个数
while(j < 10){ // 2. 车辆不超过10辆时,可继续上渡船
if(!QueueEmpty(Q1) && i < 4){ // 3. 客车队列不空,且已上渡船数量小于4时,可继续上渡船
DeQueue(Q1, x); // 3.1 从客车队列出队
EnQueue(Q, x); // 3.2 客车进入渡船队列
i++; // 3.3 客车计数器加1
j++; // 3.4 渡船队列计数器加1
}
else if(!QueueEmpty(Q2) && i == 4){ // 4. 客车已上足4辆,且货车队列为空,可继续上渡船
DeQueue(Q2, x); // 4.1 从货车队列出队
EnQueue(Q, x); // 4.2 货车进入渡船队列
j++; // 4.3 渡船队列计数器加1
i = 0; // 4.4 每上一辆货车,客车计数器清零
}
else{ // 5. 其他情况(客车或货车队列为空)
while(!QueueEmpty(Q2) && i < 4 && j < 10){ // 5.1 客车队列为空,使用货车代替
DeQueue(Q2, x); // 5.2 从货车队列出队
EnQueue(Q, x); // 5.3 货车进入渡船队列
j++; // 5.4 渡船队列计数器加1
i++; // 5.5 客车计数器加1(货车代替)
}
i = 0; // 5.5 货车队列为空后,客车计数器清零
}
if(QueueEmpty(Q1) && QueueEmpty(Q2)) // 6. 两个队列为空后,退出循环
return 0;
}
}
1.用栈实现将中缀表达式 8-(3+5)*(5-6/2) 转换成后缀表达式,试给出栈变化过程的表格形式。
算法提示:
- 在OPTR运算符栈中,运算符 -、(、+、)、*、(、-、/、) 将依次入栈;
- 在Postfix后缀表达式栈中,运算数 8、3、5、5、6、2 将依次入栈;
- 每当运算符和运算数满足计算规则,将运算符从OPTR栈移入PostFix栈;
- 需要注意的是,括号"()"不需要写入后缀表达式中。
步骤 | OPTR栈 | Postfix栈 | 读入数据 | 主要操作 |
---|---|---|---|---|
1 | # | Null | 8-(3+5)*(5-6/2)# | Push(Postfix, '8') |
2 | # | 8 | -(3+5)*(5-6/2)# | Push(OPTR, '-') |
补齐后续内容 | ||||
8 | #-( | 835+ | *(5-6/2)# | PoP(OPTR){消除一对括号} |
补齐后续内容 | ||||
16 | #-*(-/ | 835+562 | # | Pop(OPTR, '/'); Push(Postfix, '/') |
补齐后续内容 | ||||
20 | #- | 835+562/-* | # | Pop(OPTR, '-'); Push(Postfix, '-') |
21 | # | 835+562/-*- | # | return Postfix |
【参考答案】
步骤 | OPTR栈 | Postfix栈 | 读入数据 | 主要操作 |
---|---|---|---|---|
1 | # | Null | 8-(3+5)*(5-6/2)# | Push(Postfix, '8') |
2 | # | 8 | -(3+5)*(5-6/2)# | Push(OPTR, '-') |
3 | #- | 8 | 3+5)*(5-6/2)# | Push(OPTR, '(') |
4 | #-( | 8 | 3+5)*(5-6/2)# | Push(Postfix, '3') |
5 | #-( | 83 | +5)*(5-6/2)# | Push(OPTR, '+') |
6 | #-(+ | 83 | 5*(5-6/2)# | Push(Postfix, '5') |
7 | #-(+ | 835 | *(5-6/2)# | Pop(OPTR, '+'); Push(Postfix, '+') |
8 | #-( | 835+ | *(5-6/2)# | PoP(OPTR){消除一对括号} |
9 | #- | 835+ | *(5-6/2)# | Push(OPTR, '*') |
10 | #-* | 835+ | 5-6/2)# | Push(OPTR, '(') |
11 | #-*( | 835+ | 5-6/2)# | Push(OPTR, '5') |
12 | #-*( | 835+5 | -6/2)# | Push(OPTR, '-') |
13 | #-*(- | 835+5 | 6/2)# | Push(OPTR, '6') |
14 | #-*(- | 835+56 | /2)# | Push(OPTR, '/') |
15 | #-*(-/ | 835+56 | 2)# | Push(OPTR, '2') |
16 | #-*(-/ | 835+562 | # | Pop(OPTR, '/'); Push(Postfix, '/') |
17 | #-*(- | 835+562/ | # | Pop(OPTR, '-'); Push(Postfix, '-') |
18 | #-*( | 835+562/- | # | Pop(OPTR){消除一对括号} |
19 | #-* | 835+562/- | # | Pop(OPTR, ''); Push(Postfix, '') |
20 | #- | 835+562/-* | # | Pop(OPTR, '-'); Push(Postfix, '-') |
21 | # | 835+562/-*- | # | return Postfix |
2. 设单链表的表头指针为L,节点结构由data和next两个域构成,其中data域为字符型。试设计算法判断该链表的全部n个字符是否中心对称。例如xyx、xyyx都是中心对称字符。
算法提示:
- 本题考察的问题实际上是在做回文判断,回文可以通过比较中心元素两边等距离的元素是否相等来判定。需要注意的是,当字符串为奇数时,需要跳过中心元素;而当字符串为偶数时,直接对比字符串中间的两个元素。
- 注意本题使用单链表来进行操作,其中p->data为栈链中的指,p->next为栈链中的指针。
- 在进行元素比较时,可以先用一个数组做为栈链来对保存字符串前一半的元素。在进行对比的时候,再逐个将栈链中的元素进行出栈操作,此时从堆栈中获得的元素刚好是逆序的。注意以数组保存的栈链出栈操作应从数组的末尾开始反向进行遍历。
- 最后,通过从中间字符开始扫描后一半元素,并将其和栈链栈顶弹出的元素进行对比。
- 若扫描完整个字符串后,所有对比元素均相等,则说明该字符串为回文。
bool CentralSymmetry(LinkList L, int n){
// 在此处填入代码
}
【参考代码】
bool CentralSymmetry(LinkList L, int n){
char s[n/2] // 1. 创建一个数组用于存储字符串中前半部分元素
LNode *p = L -> next; // 2. 创建一个指针指向字符串链的第一个节点
for(i = 0; i<n/2; i++){ // 3. 遍历字符串,将一半的元素存入数组(链栈)中
s[i] = p -> data; // 3.1 依次将字符串中的元素存入数组
p = p -> next; // 3.2 工作指针向后移动1位
}
if(n%2 == 1) // 4. 判断字符串是否为奇数,若是则需要跳过中间的字符
p = p->next;
while(p != Null){ // 5. 遍历字符串,将后半部分元素与数组中的元素进行对比
i--; // 5.1 将i值回退1位,指向数组的最后一个元素
if(s[i] == p -> data){ // 5.2 若相等,则说明该元素满足回文,继续判定下一个元素
i--; // 5.3 回退i值,指向数组的下一个元素(i相当于栈顶指针)
p = p -> next; // 5.4 栈顶指针指向下一个元素,相当于栈顶元素出栈
}
else // 5.5 若不相等,则说明元素不满足回文,直接返回false
return false;
}
return true;
}
3. 将编号为0和1的两个栈存放于一个数组空间V[m]中,栈底分别处于数组的两端。当第0号栈的栈顶指针top[0]等于-1时,该站为空;当第1号栈的栈顶指针top[1]等于m时,该栈为空。两个栈均从两端向中间增长。试编写双栈初始化,判断栈空、栈满、进栈和出栈的算法函数。双栈的数据结构定义如下:
typedef struct DblStack{
int top[2], bottom[2]; // 定义栈顶和栈底指针
SElementType *V; // 定义栈数组
int m; // 定义栈的最大容量
} //DblStack
算法提示:
- 对于初始化函数,需要对两个栈的栈顶和栈底指针都进行初始化。初始时,左栈栈顶指针为-1,右栈栈顶指针为m;同时,栈底指针与栈顶指针处于相同位置。
- 栈空的条件是左栈栈顶和栈底指针都为-1,右栈栈顶和栈底指针都为m。
- 栈满条件为左栈栈顶指针top[0]的下一个位置top[0]+1等于右栈栈顶指针top[1]。
- 进栈操作时,先判断栈是否满,若满则返回错误信息。否则,执行入栈操作。对于左栈的插入操作将向右扩展,对于右栈的插入将向左扩展。
- 出栈操作时,先判断栈是否空,若空则返回错误信息。否则,执行出栈操作。对于左栈的删除操作指针将向左移动,对于右栈的删除操作指针将向右进行移动。
// 初始化一个大小为m的双向栈 Status InitDblStack(DblStack &S, int m){ // 在此处填入代码 } // 判断第i号栈是否为空,空则返回truen,非空则返回 bool IsDblStackEmpty(DblStack &S, int i){ // 在此处填入代码 } // 判断是否栈满,未满返回false,满返回true bool IsDblStackFull(DblStack &S){ // 在此处填入代码 } // 向第i号栈中插入元素e Status DblPush(DblStack &S, int i, SElementType e){ // 在此处填入代码 } // 将第i号栈的栈顶元素弹出,存入e中 Status DblPop(DblStack &S, int i, SElementType &e){ // 在此处填入代码 }
【参考代码】
// 初始化一个大小为m的双向栈 Status InitDblStack(DblStack &S, int m){ S.V = new SElementType[m]; // 1. 动态分配一个最大容量为m的数组空间 S.top[0] = -1; // 2. 定义左边的0号栈。初始时,栈顶和栈底都指向-1 S.bottom[0] = -1; S.top[1] = m; // 3. 定义右边的1号栈。初始时,栈顶和栈底都指向m S.bottom[1] = m; } // 判断第i号栈是否为空,空则返回truen,非空则返回 bool IsDblStackEmpty(DblStack &S, int i){ if(S.top[i] == S.bottom[i]) return true; else return false; } // 判断是否栈满,未满返回false,满返回true bool IsDblStackFull(DblStack &S){ if (S.top[0] + 1 == S.top[1]) return true; else return false; } // 向第i号栈中插入元素e Status DblPush(DblStack &S, int i, SElementType e){ if(S.top[1] - S.top[] == 1) // 1. 判断栈是否满 return ERROR; if(i == 0) // 2. 对于左边的0号栈,先将栈顶指针加1,在按地址进栈 S.V[++S.top[0] = e; else // 3. 对于右边的1号栈,先将栈顶指针减1,再按地址进栈 S.V[--S.top[1] = e; return OK; } // 将第i号栈的栈顶元素弹出,存入e中 Status DblPop(DblStack &S, int i, SElementType &e){ if(S.top[i] == S.bottom[i]) // 1. 判断栈是否为空 return ERROR; if(i == 0) // 2. 对于左边的0号栈,先将栈顶指针减1,再按地址出栈 e = S.V[S.top[0]--]; else // 3. 对于右边的1号栈,先将栈顶指针加1,再按地址出栈 e = S.V[S.top[1]++]; return OK; }