第三章作业答案

第三章作业答案1.简述下列算法的功能：statusalgo(StackS){ inti,n,A[255]; n=0; while(!StackEmpty(S)){n++;Pop(S,A[n]);} for(i=1;i<=n;i++)Push(S,A[i]);}功能：将栈中的元素倒置放置。2.假设一个算术表达式中可以包含三种括号：圆括号“）”和“(”、方括号“[”和“]”和花括号“{”和“}”，而且这三种括号可以按任意的次序嵌套使用（如：…[…{…}…[…]…]…[…]…(…)…。编写判别给定表达式中所包含是否正确配对出现的算法（已知表达式已存入数据元素为字符的顺序表中）。StatusAllBrackets_Test(char*str)//用str代表表达式，判别表达式中三种括号是否匹配{……..}StatusAllBrackets_Test(char*str){//判别表达式中三种括号是否匹配

InitStack(S);

for(p=str;*p;p++)

{

if(*p=='('||*p=='['||*p=='{')push(S,*p);

elseif(*p==')'||*p==']'||*p=='}')

{

if(StackEmpty(S))returnERROR;

pop(S,c);

if(*p==')'&&c!='(')returnERROR;

if(*p==']'&&c!='[')returnERROR;

if(*p=='}'&&c!='{')returnERROR;//必须与当前栈顶括号匹配

}//end

elseif

}//endfor

if(!StackEmpty(s))returnERROR;

returnOK;

}//AllBrackets_Test3.如果希望循环队列中的元素都能得到利用，则需要设置一个标志域tag，并以tag的值为0或1来区分尾指针和头指针值相同时的队列状态是“空”还是“满”。试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论和不设标志这两种方法的使用范围（如当循环队列容量较小而队列中每个元素占的空间较多时，哪一种方法较好）。（提示：将标志的初值置“0”。一旦元素入队列使得rear=front时，需要置tag为“1”：反之，一旦元素出队列使得rear=front时，需要置tag为“0”，以便使得下一次进入队列或出队列操作时，此时front=rear，根据tag的值来判断队列的状态。）分析:当循环队列容量较小而队列中每个元素占的空间较多时,此种表示方法可以节约较多的存储空间，较有价值。StatusEnCyQueue(CyQueue&Q,intx){//带tag域的循环队列入队算法

==1)//tag域的值为0表示"空",1表示"满"

returnERROR;

]=x;

=(Q.rear+1)%MAXSIZE;

==)=1;//队列满

}//EnCyQueueStatusDeCyQueue(CyQueue&Q,int&x){//带tag域的循环队列出队算法

==0)//队列空returnERROR;

x=];=(Q.front+1)%MAXSIZE;

==)=0;//队列空

returnOK;

}//DeCyQueue

4.假设称正读和反读都相同的字符序列为“回文”，例如，’abba’和’abcba’回文，’abcde’和’ababab’不是回文。试写一个算法判别读入的一个以’@’为结束符的字符序列是否是“回文”。intPalindrome_Test()//判别输入的字符串是否回文序列,是则返回1,否则返回0

{…………..}

StatusPalindrome_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)returnERROR;

}

returnOK;}5.假设如题1所述火车调度站的入口处有n节硬席或软席车厢（分别以H和S表示）等待调度，试编写算法，输出对这n节车厢进行调度的操作（即入栈或出栈操作）序列，以使所有的软席车厢都被调到硬席车厢之前。提示：voidTrain_arrange(char*train){}//这里用字符串train表示火车,字符'H'表示硬席,'S'表示软席，设两个指针p和q，其中，p指向字符串train，q指向一个新的字符串，用于存放排序后的结果。voidTrain_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_arrange6.假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列满的条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。（提示：rear不是指向队尾元素的下一个位置，而是指向队尾元素；队列的队头指针head=(Q.rear-Q.length+1)%MAXSIZE）StatusEnCyQueue(CyQueu