资源描述：
《《栈和队列》word版》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第三章栈和队列1．何为栈和队列？简述两者的区别和联系。栈：是一种只允许在一端进行插入和删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入和删除的一端称为栈顶（top），另一端称为栈底(bottom)。栈顶元素总是最后入栈的，因而是最先出栈；栈底元素总是最先入栈的，因而也是最后出栈。因此，栈也被称为“后进先出”的线性表。队列：队列（queue）是一种只允许在一端进行插入，而在另一端进行删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入的一端称为队尾（rear），只允许进行删除的一端称为队头
2、(front)。队头元素总是最先进队列的，也总是最先出队列；队尾元素总是最后进队列，因而也是最后出队列。因此，队列也被称为“先进先出”表。区别和联系：从数据结构上看，栈和队列也是线性表，不过是两种特殊的线性表。栈只允许在表的一端进行插入或删除操作，队列只允许在表的一端进行插入操作、而在另一端进行删除操作。因而，栈和队列也可以被称作为操作受限的线性表。2．若依次读入数据元素序列{a,b,c,d}进栈，进栈过程中允许出栈,试写出各种可能的出栈元素序列。可能的出栈序列：a,b,c,db,c,d,ab,a,c,da
3、,b,d,ca,d,c,ba,c,b,da,c,d,bb,d,c,ab,a,d,cc,d,b,ac,b,d,ac,b,a,dd,c,b,a等3．试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如‘序列1—序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而’1+3&3-1’则不是。StatusModel(){ //识别依次读入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列 //序列1和序
4、列2中不包含字符‘&’，序列1是序列2的逆序列 InitStack(s); c=getchar(); while(c!='&'){Push(s,c);c=getchar();} c=getchar(); while(c!='@'&&!StackEmpty(s)){ Pop(s,x); if(c==x)c=getchar(); elsereturnFALSE; } if(c=='@'&&StackEmpty(s))returnTRUE; elsereturnFALSE;} 4．试写一个判别表达式中
5、开、闭括号是否配对出现的算法。StatusBracket_Test(char*str)//判别表达式中小括号是否匹配{ count=0; for(p=str;*p;p++) { if(*p=='(')count++; elseif(*p==')')count--; if(count<0)returnERROR; } if(count)returnERROR;//注意括号不匹配的两种情况 returnOK;}//Bracket_Test5．假设表达式由单字母变量和双目四则运算算符
6、构成。试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰式。voidNiBoLan(char*str,char*new)//把中缀表达式str转换成逆波兰式new{ p=str;q=new;//为方便起见,设str的两端都加上了优先级最低的特殊符号 InitStack(s);//s为运算符栈 while(*p) { if(*p是字母))*q++=*p;//直接输出 else { c=gettop(s); if(*p优先级比c高)push(s,*p);
7、 else { while(gettop(s)优先级不比*p低) { pop(s,c);*(q++)=c; }//while push(s,*p);//运算符在栈内遵循越往栈顶优先级越高的原则 }//else }//else p++; }//while}//NiBoLan6．假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和
8、出队列的算法。voidInitCiQueue(CiQueue&Q)//初始化循环链表表示的队列Q{ Q=(CiLNode*)malloc(sizeof(CiLNode)); Q->next=Q;}//InitCiQueuevoidEnCiQueue(CiQueue&Q,intx)//把元素x插入循环链表表示的队列Q,Q指向队尾元素,Q->next指向头结点,Q->next->next指向队头元素{ p=(C
