赞
踩
1.有五个元素,其入栈次序为:A,B,C,D,E,在各种可能的出栈序列中,以元素C、D最先出栈(即C第一个且D第二个出栈)的次序有哪些?
2.铁路进行列车调度时,常把站台设计成栈式结构,试问:
(1) 设有编号为1,2,3,4,5,6的6辆列车,顺序开入栈式结构的站台,则可能的出栈序列有多少种?
(2)若进站的6辆列车顺序如上所述,那么是否能够得到435612、326541、154623和135426的出站序列?如果不能,说明为什么不能;如果能,说明如何得到(写出进栈或出栈的序列)。
3.假设以I和O分别表示入栈和出栈操作。若栈的初态和终态均为空,入栈和出栈的操作序列可表示为仅由I和O组成的序列,则称可以操作的序列为合法序列,否则称为非法序列。(提示:出入栈要合法,不能出现上溢、下溢情况)
(1)试指出判别给定序列是否合法的一般规则
(2)两个不同的合法序列(对两个具有同样元素的输入序列,如ABC和BAC)能否得到相同的输出元素序列?如能得到,请举例说明。
(3)写出一个算法,判定所给的操作序列是否合法。若合法,返回1,否则返回0(被判定的操作序列已存入一维char型数组ch[]中,操作序列以“\0”为结束符)(提示,使用循环遍历数组,依次得到I或O操作)
作业要求:算法题使用如下的栈定义:
//具体数据类型根据题目要求,如第三题中的算法题,需要把int改为char
int a[100];
int top = -1;
//入栈操作,e为待入栈的值
a[++top] = e;
//出栈操作
e = a[top--];
1.回文字符串是指正读反读均相同的字符序列,如“abba”和“abdba”均是回文字符串,但“good”不是回文字符串。试编写算法判断给定的字符串序列是否是回文字符串。(使用栈)
#include <stdio.h> #include <stdlib.h> #include<string.h> #define arraySize 100 //可以使用静态字符数组,或者动态字符数组 //1.静态数组,使用如下方式定义、遍历(#为结束标志) char c[arraySize]; char ch; int i; printf("请输入一个字符串,以#为结束标志:"); scanf("%c", &ch); for(i=0; ch != '#'; i++){ c[i] = ch; scanf("%c", &ch); } c[i] = ch; for(i = 0; i<sizeof(c)/sizeof(char)&&c[i] != '#'; i++){ printf("%c", c[i]); } printf("\n"); //2.动态数组,使用base作为数组基址 char *base; base = (char *)malloc(sizeof(char) * arraySize); printf("请输入一个字符串,以空格或回车为结束标志:"); scanf("%s", base); for(i = 0; i < strlen(base); i++){ printf("%c", base[i]); } printf("\n"); //以上是两种创建数组的方式,可以自行选择 //两种皆可,如果想进行编程测试,可以通过上面的两种创建字符数组的方式, //输入字符串,然后调用judgePalindromStr函数 //作业本上只需写judgePalindromStr函数的代码 int judgePalindromStr(char *base){ //... } int judgePalindromStr(char a[]){ //... }
2.为充分利用存储空间,顺序栈s0、s1共享一个存储区elem[0, …, maxSize-1]。试设计共享栈s0,s1以及有关的入栈、出栈操作的算法,假设栈中元素为int型。
(1)给出基本的设计思想。
(2)根据设计思想,采用C语言描述算法。
//共享栈的结构体定义
typedef struct{
int elem[maxSize];
int top[2]; //top[0], top[1]分别为s0、s1的栈顶指针;0,maxSize-1分别为两个栈顶指针的初始值
}SqStack;
int push(SqStack *st, int stNo, int x){ //stNo是栈的编号,取值范围是0或1,指示x插入到哪个栈中,
//判断栈是否满
}
int pop(SqStack *st, int stNo, int *x){//stNo是栈的编号,取值范围是0或1,指示哪个栈弹出元素
//判断栈是否空
}
要求:使用栈。
测试用例:10(1010)、21(10101)、34(100010)
注意:括号可以嵌套,即: ‘’[()]()’ 这种形式,但 ‘([)’ 或者 ‘([]’ 都不符合要求。
(1)试写出循环队列的类型定义,并解释变量的含义;
(2)写出"从队尾删除"和"从队头插入"的算法。
提示:此为双端队列的概念,队列两端均可进行插入删除,将之想象成底部贴合在一起的两个栈。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。