发布时间 : 星期四 文章数据结构练习 - 第三章 - 栈和队列更新完毕开始阅读
指向队头元素的前一位置，rear指向队尾元素。当front等于-1时队空，rear等于m-1时为队满。由于队列的性质（“删除”在队头而“插入”在队尾），所以当队尾指针rear等于m-1时，若front不等于-1，则队列中仍有空闲单元，所以队列并不是真满。这时若再有入队操作，会造成假“溢出”。其解决办法有二，一是将队列元素向前“平移”（占用0至rear-front-1）；二是将队列看成首尾相连，即循环队列（0..m-1）。在循环队列下，仍定义front=rear时为队空，而判断队满则常用两种办法，一是用“牺牲一个单元”，即rear+1=front（准确记是（rear+1）%m=front，m是队列容量）时为队满。另一种解法是“设标记”方法，如设标记tag，tag等于0情况下，若删除时导致front=rear为队空；tag=1情况下，若因插入导致front=rear则为队满。
17．如果用一个循环数组q[0..m-1]表示队列时，该队列只有一个队列头指针front，不设队列尾指针rear，而改置计数器count用以记录队列中结点的个数。 编写实现队列的三个基本运算：判空、入队、出队（3分） 队列中能容纳元素的最多个数是多少？（1分） typedef struct {ElemType q[m];
int front,count; ∥front是队首指针，count是队列中元素个数 }cqnode; ∥定义类型标识符。
(1)判空：int Empty(cqnode cq) ∥cq是cqnode类型的变量
{if(cq.count==0) return(1)；else return(0); ∥空队列} 入队: int EnQueue(cqnode cq，ElemType x) {if(count==m){printf(“队满\\n”)；exit(0); }
cq.q[(cq.front+count)%m]=x; ∥x入队
count++; return(1); ∥队列中元素个数增加1,入队成功 }
出队: int DelQueue(cqnode cq)
{if(count==0){printf(“队空\\n”)；return(0);} printf(“出队元素”，cq.q[cq.front]); x=cq.q[cq.front];
cq.front=(cq.front+1)%m; ∥计算新的队头指针 return(x) }
(2) 队列中能容纳的元素的个数为m。队头指针front指向队头元素。
18．给出循环队列中元素个数的计算式(设队最大长度为N,队首指针FRONT，队尾指针REAR)
循环队列中元素个数为（REAR-FRONT+N）%N。其中FRONT是队首指针，指向队首元素的前一位置；REAR是队尾指针，指向队尾元素；N是队列最大长度。
19．若以1、2、3、4作为双端队列的输入序列，试分别求出以下条件的输出序列：
能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列； 能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列； 既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序
13
列。
（1）4132 （2）4213 （3）4231 五、应用题
1．已知一个中缀算术表达式为： 3+4*(25-(6/15))-8@ ，写出对应的后缀算术表达式。
后缀算术表达式：3 4 25 6 15 / － * ＋ 8 － @
2．设有一顺序队列sq，容量为5，初始状态时sq.front=sq.rear=0，画出做完下列操作后队列及其头尾指针的状态变化情况，若不能入队，请简述其理由后停止。（6分） （1） d,e,b入队 （2） d,e出队 （3） i,j入队 （4） b出队 （5）n,o,p入队
六、程序填空题（或算法阅读题） 1．void exam1(SeqStack S, int m) { SeqStack T; int i； IniStack(T);
while(!Stackempty (S))
if ((i=pop(S))!=m) push(T,i); while (!Stackempty(T))
{ i=pop（T）; push(S,i); } } //exam1
程序段1 的功能是将一个非空栈中值等于m的元素全部删除；（根据答题情况酌情给分）
七、算法设计题 1． 设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区[O..maxsize-1],为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。【哈尔滨工业大学 2001 七 （12分）】 [题目分析]两栈共享向量空间，将两栈栈底设在向量两端，初始时，s1栈顶指针为-1，s2栈顶为maxsize。两栈顶指针相邻时为栈满。两栈顶相向，迎面增长，栈顶指针指向栈顶元素。
#define maxsize 两栈共享顺序存储空间所能达到的最多元素数
14
#define ElemType int ∥假设元素类型为整型 typedef struct
{ElemType stack[maxsize];∥栈空间
int top[2]; ∥top为两个栈顶指针 }stk;
stk s; ∥s是如上定义的结构类型变量，为全局变量 （1）入栈操作：
int push(int I,int x)
∥入栈。I为栈号，i=0表示左栈s1，i=1表示右栈s2，x是入栈元素。入栈成功返回1，否则返回0
{if(i<0||i>1){printf(“栈号输入不对\\n”);exit(0);}
if(s.top[1]-s.top[0]==1) {printf(“栈已满\\n”);return(0);} switch(i)
{case 0: s.stack[++s.top[0]]=x; return(1); break; case 1: s.stack[--s.top[1]]=x; return(1); }
}∥push
（2）退栈操作
ElemType pop(int i)
∥退栈算法。I代表栈号，i=0时为s1栈，i=1时为s2栈。退栈成功返回退栈元素，否则返回-1
{if(i<0 || i>1){printf(“栈号输入错误\\n”)；exit(0);} switch(i) {case 0: if(s.top[0]==-1) {printf(“栈空\\n”)；return（-1）；} else return(s.stack[s.top[0]--]); case 1: if(s.top[1]==maxsize {printf(“栈空\\n”); return(-1);} else return(s.stack[s.top[1]++]); }∥switch }∥算法结束
[算法讨论] 请注意算法中两栈入栈和退栈时的栈顶指针的计算。两栈共享空间示意图略，s1栈是通常意义下的栈，而s2栈入栈操作时，其栈顶指针左移（减1），退栈时，栈顶指针右移（加1）。
2．设表达式以字符形式已存入数组E[n]中，‘#’为表达式的结束符，试写出判断表达式中括号（‘（’和‘）’）是否配对的C语言描述算法：EXYX(E); (注：算法中可调用栈操作的基本算法。) 【北京科技大学 2001 九.1 （10分）】 [题目分析]判断表达式中括号是否匹配，可通过栈，简单说是左括号时进栈，右括号时退栈。退栈时，若栈顶元素是左括号，则新读入的右括号与栈顶左括号就可消去。如此下去，输入表达式结束时，栈为空则正确，否则括号不匹配。 Int EXYX(char E[],int n)
∥E[]是有n字符的字符数组，存放字符串表达式，以‘#’结束。本算法判断表达式中圆括号是否匹配
{char s[30]; ∥s是一维数组，容量足够大，用作存放括号的栈 int top=0; ∥top用作栈顶指针。
S[top]= ‘#’; ∥‘#’先入栈，用于和表达式结束符号‘#’匹配 int i=0; ∥字符数组E的工作指针
15
while(E[i]!= ‘#’) ∥逐字符处理字符表达式的数组。 Switch(E[i])
{case‘(’: s[++top]=‘(’; i++ ; break ; case‘)’: if(s[top]==‘(’){top--; i++; break;} else{printf(“括号不配对\\n”);exit(0);}
case‘#’: if(s[top]==‘#’){printf(“括号配对\\n”);return (1);} else {printf(“ 括号不配对\\n”);return (0);} ∥括号不配对 default : i++; ∥读入其它字符，不作处理 }∥switch }∥算法结束。
[算法讨论]本题是用栈判断括号匹配的特例：只检查圆括号的配对。一般情况是检查花括号（‘{’，‘}’）、方括号（‘[’，‘]’）和圆括号（‘（’，‘）’）的配对问题。编写算法中如遇左括号（‘{’，‘[’，或‘（’）就压入栈中，如遇右括号（‘）’，‘）’，或‘）’），则与栈顶元素比较，如是与其配对的括号（左花括号，左方括号或左圆括号），则弹出栈顶元素；否则，就结论括号不配对。在读入表达式结束符‘#’时，栈中若只剩‘#’，表示括号全部配对成功；否则表示括号不匹配。 另外，由于本题只是检查括号是否匹配，故对从表达式中读入的不是括号的那些字符，一律未作处理。再有，假设栈容量足够大，因此入栈时未判断溢出。 3．假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。
（1） 下面所示的序列中哪些是合法的？
1. A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO
（2） 通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。
【武汉大学 2000 五.2(12分)】
（1）A和D是合法序列，B和C 是非法序列。
（2）设被判定的操作序列已存入一维数组A中。 Int Judge(char A[])
∥判断字符数组A中的输入输出序列是否是合法序列。如是，返回true，否则返回false
{i=0; ∥i为下标。
J=k=0; ∥j和k分别为I和字母O的的个数 while(A[i]!=‘\\0’) ∥当未到字符数组尾就作 {switch(A[i])
{case‘I’: j++; break; ∥入栈次数增1 case‘O’: k++; if(k>j){printf(“序列非法\\n“)；exit(0);} }
i++; ∥不论A[i]是‘I’或‘O’，指针i均后移 }
if(j!=k) {printf(“序列非法\\n“)；return(false);} else {printf(“序列合法\\n“)；return(true);}
16