《作业答案》PPT课件.ppt

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.假设一个算术表达式中可以包含三种括号：圆括号“）”和“(”、方括号“”和“”和花括号“”和“”，而且这三种括号可以按任意的次序嵌套使用（如：()。编写判别给定表达式中所包含是否正确配对出现的算法（已知表达式已存入数据元素为字符的顺序表中）。,Status AllBrackets_Test(char *str) /用str代表表达式，判别表达式中三种括号是否匹配 .,Status AllBrackets_Test(char *str) /判别表达式中三种括号是否匹配InitStack(S);for(p=str;*p;p+)if(*p=(|*p=|*p=) push(S,*p);else if(*p=)|*p=|*p=)if(StackEmpty(S) return ERROR;pop(S,c);if(*p=)/AllBrackets_Test,3.如果希望循环队列中的元素都能得到利用，则需要设置一个标志域tag，并以tag的值为0或1来区分尾指针和头指针值相同时的队列状态是“空”还是“满”。试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论和不设标志这两种方法的使用范围（如当循环队列容量较小而队列中每个元素占的空间较多时，哪一种方法较好）。 （提示：将标志的初值置“0”。一旦元素入队列使得rear=front时，需要置tag为“1”：反之，一旦元素出队列使得rear=front时，需要置tag为“0”，以便使得下一次进入队列或出队列操作时，此时front=rear，根据tag的值来判断队列的状态。）,分析:当循环队列容量较小而队列中每个元素占的空间较多时,此种表示方法可以节约较多的存储空间，较有价值。,Status EnCyQueue(CyQueue /队列满/EnCyQueue,Status DeCyQueue(CyQueue /DeCyQueue,4.假设称正读和反读都相同的字符序列为“回文”，例如，abba和abcba回文，abcde和ababab不是回文。试写一个算法判别读入的一个以为结束符的字符序列是否是“回文”。 int Palindrome_Test() /判别输入的字符串是否回文序列,是则返回1,否则返回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表示）等待调度，试编写算法，输出对这n节车厢进行调度的操作（即入栈或出栈操作）序列，以使所有的软席车厢都被调到硬席车厢之前。 提示：void Train_arrange(char *train) /这里用字符串train表示火车, 字符H表示硬席,S表示软席，设两个指针p和q，其中，p指向字符串train，q指向一个新的字符串，用于存放排序后的结果。,void Train_arrange(char *train) 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分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列满的条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。（提示：rear不是指向队尾元素的下一个位置，而是指向队尾元素；队列的队头指针head=(Q.rear-Q.length+1)%MAXSIZE）,Status EnCyQueue(CyQueue ,队满的条件：length=MAXSIZE,Status DeCyQueue(CyQueue ,