《作业答案》ppt课件

1、if语句不能用作循环语句：语句不能用作循环语句：for或或while用于循环语句。用于循环语句。 if；i+ 1. 简述以下算法的功能：简述以下算法的功能：status algo(Stack S)int i,n,A255;n=0;while(!StackEmpty(S) n+;Pop(S,An);for(i=1;i=n;i+) Push(S,Ai); 功能：将栈中的元素倒置放置。功能：将栈中的元素倒置放置。 2.假设一个算术表达式中可以包含三种括号：圆括号假设一个算术表达式中可以包含三种括号：圆括号“和和“(、方括号、方括号“和和“和花括号和花括号“和和“，而且这三种括号可以按恣意的次序嵌套运

2、用而且这三种括号可以按恣意的次序嵌套运用如：如：()。编写判别给。编写判别给定表达式中所包含能否正确配对出现的算法知表达式定表达式中所包含能否正确配对出现的算法知表达式已存入数据元素为字符的顺序表中。已存入数据元素为字符的顺序表中。Status AllBrackets_Test(char *str)/用用str代表表达式，判别表达式中三种括号能否匹配代表表达式，判别表达式中三种括号能否匹配.Status AllBrackets_Test(char *str) /判别表达式中三种括号能否匹配判别表达式中三种括号能否匹配 InitStack(S); for(p=str;*p;p+) if(*p=(

3、|*p=|*p=) push(S,*p); else if(*p=)|*p=|*p=) if(StackEmpty(S) return ERROR; pop(S,c); if(*p=)&c!=() return ERROR; if(*p=&c!=) return ERROR; if(*p=&c!=) return ERROR; /必需与当前栈顶括号匹配必需与当前栈顶括号匹配 /end else if /end for if(!StackEmpty(s) return ERROR; return OK;/AllBrackets_Test 3.假设希望循环队列中的元素都能得到利用，那么需求设置假设

4、希望循环队列中的元素都能得到利用，那么需求设置一个标志域一个标志域tag，并以，并以tag的值为的值为0或或1来区分尾指针和头来区分尾指针和头指针值一样时的队列形状是指针值一样时的队列形状是“空还是空还是“满。试编写满。试编写与此构造相应的入队列和出队列的算法，并从时间和空与此构造相应的入队列和出队列的算法，并从时间和空间角度讨论和不设标志这两种方法的运用范围如当循间角度讨论和不设标志这两种方法的运用范围如当循环队列容量较小而队列中每个元素占的空间较多时，哪环队列容量较小而队列中每个元素占的空间较多时，哪一种方法较好。一种方法较好。提示：将标志的初值置提示：将标志的初值置“0。一旦元素入队列使

5、得。一旦元素入队列使得rear=front时，需求置时，需求置tag为为“1：反之，一旦元素出：反之，一旦元素出队列使得队列使得rear=front时，需求置时，需求置tag为为“0，以便使得，以便使得下一次进入队列或出队列操作时，此时下一次进入队列或出队列操作时，此时front=rear，根，根据据tag的值来判别队列的形状。的值来判别队列的形状。分析分析:当循环队列容量较小而队列中每个元素占的空当循环队列容量较小而队列中每个元素占的空间较多时间较多时,此种表示方法可以节约较多的存储空此种表示方法可以节约较多的存储空间，较有价值。间，较有价值。 Status EnCyQueue(CyQueu

6、e &Q,int x) /带带tag域的循环队列入队算法域的循环队列入队算法 if(Q.tag=1) /tag域的值为域的值为0表示表示空空,1表示表示满满 return ERROR; Q.baseQ.rear=x; Q.rear=(Q.rear+1)%MAXSIZE; if(Q.front=Q.rear) Q.tag=1; /队列满队列满/EnCyQueue Status DeCyQueue(CyQueue &Q,int &x) /带带tag域的循环队列出队算法域的循环队列出队算法 if(Q.tag=0) /队列空队列空 return ERROR; x=Q.baseQ.front; Q.fr

7、ont=(Q.front+1)%MAXSIZE; if(Q.front=Q.rear) Q.tag=0; /队列空队列空 return OK;/DeCyQueue4.假设称正读和反读都一样的字符序列为假设称正读和反读都一样的字符序列为“回文，例回文，例如，如，abba和和abcba回文，回文，abcde和和ababab不是回文。试写一个算法判别读入的不是回文。试写一个算法判别读入的一个以一个以为终了符的字符序列能否是为终了符的字符序列能否是“回文。回文。int Palindrome_Test()/判别输入的字符串能否回文序列判别输入的字符串能否回文序列,是那么前往是那么前往1,否那么否那么前往

8、前往0. Status Palindrome_Test()/检查能否回文检查能否回文 InitStack(S);InitQueue(Q);while(c=getchar()!=) Push(S,c);EnQueue(Q,c); /同时运用栈和队列两种构造同时运用栈和队列两种构造 while(!StackEmpty(S) Pop(S,a);DeQueue(Q,b); if(a!=b) return ERROR; return OK; 5. 假设如题假设如题1所述火车调度站的入口处有所述火车调度站的入口处有n节硬席或软席车厢分别以节硬席或软席车厢分别以H和和S表示表示等待调度，试编写算法，输出对这

9、等待调度，试编写算法，输出对这n节车节车厢进展调度的操作即入栈或出栈操作厢进展调度的操作即入栈或出栈操作序列，以使一切的软席车厢都被调到硬席序列，以使一切的软席车厢都被调到硬席车厢之前。车厢之前。 提示：提示：void Train_arrange(char *train) /这里用字符串这里用字符串train表示火车表示火车, 字符字符H表表示硬席示硬席,S表示软席，设两个指针表示软席，设两个指针p和和q，其中，其中，p指向字符串指向字符串train，q指向一个新指向一个新的字符串，用于存放排序后的结果。的字符串，用于存放排序后的结果。 void Train_arrange(char *tra

10、in) char *p,*q; p=train;q=newtrain; InitStack(s); while(*p) if(*p=H) push(s,*p); /把把H存入栈中存入栈中 else *(q+)=*p; /把把S调到前部调到前部 p+; while(!StackEmpty(s) pop(s,c); *(q+)=c; /把把H接在后部接在后部 /Train_arrange 6. 假设将循环队列定义为：以域变量假设将循环队列定义为：以域变量rear和和length分别指示循环队列中队尾元素的位分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列置和内含元素的个数。试给出

11、此循环队列满的条件，并写出相应的入队列和出队列满的条件，并写出相应的入队列和出队列的算法在出队列的算法中要前往队头元的算法在出队列的算法中要前往队头元素。提示：素。提示：rear不是指向队尾元素的不是指向队尾元素的下一个位置，而是指向队尾元素；队列的下一个位置，而是指向队尾元素；队列的队头指针队头指针head=(Q.rear-Q.length+1)%MAXSIZE Status EnCyQueue(CyQueue &Q,int x)/入队列入队列 if(length=MAXSIZE) return ERROR; Q.rear=(Q.rear+1)%MAXSIZE; Q.baseQ.rear=x; Length+;Return OK; 队满的条件：队满的条件：length=MAXSIZE