数据结构实验二：栈和队列的应用

PAGE第1页共5页数据结构实验报告实验二栈和队列的应用实验目的：1．深入了解栈和队列的特性；2．熟练掌握栈和队列的存储结构及实现方式实验要求：1．C完成算法设计和程序设计并上机调试通过。2．撰写实验报告，提供实验结果和数据。3．写出算法设计小结和心得。实验内容：1．用栈实现：识别依次读入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘1+3&3-12．假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列等操作。程序源代码：1、#include"stdio.h"#include"stdlib.h"#include"string.h"#defineEMPTY0#defineFULL10000#defineMAX10000typedefchardata;typedefstructelem{datad;structelem*next;}elem;typedefstructstack{intcnt;elem*top;}stack;voidinitialize(stack*stk);voidpush(datad,stack*stk);datapop(stack*stk);boolempty(conststack*stk);boolfull(conststack*stk);//栈操作函数voidinitialize(stack*stk){stk->cnt=0;stk->top=NULL;}boolempty(conststack*stk){returnstk->cnt==EMPTY;}boolfull(conststack*stk){returnstk->cnt==FULL;}voidpush(datad,stack*stk){elem*p;if(!full(stk)){p=(elem*)malloc(sizeof(elem));p->d=d;p->next=stk->top;stk->top=p;stk->cnt++;}}datapop(stack*stk){datad;elem*p;if(!empty(stk)){d=stk->top->d;p=stk->top;stk->top=stk->top->next;stk->cnt--;free(p);}returnd;}intmain(void){datainput[MAX];stacktemp;inti=0;intflag=0;initialize(&temp);//初始化临时栈printf("输入字符串:\n");scanf("%s",&input);//输入字符串while(input[i]!='@')//字符串入栈{push(input[i],&temp);i++;}while(!empty(&temp))//字符依次出栈和字符数组比较，判断是否符合“序列1&序列2@”形式{if(temp.top->d==input[flag]){pop(&temp);flag++;}else{printf("此字符序列不符合“序列1@序列2@”形式\n");break;}}if(empty(&temp))printf("此字符序列符合“序列1@序列2@”形式\n");return1;}2、#include"iostream.h"typedefintElmeType;structNode{ ElmeTypedate; Node*next;};typedefNodeQueue;voidInitQueue(Queue*&rear)//InitQueue对队列进行初始化{ rear->date=-1; rear->next=rear;}voidInQueue(Queue*&rear,ElmeTypee)//入列{ Queue*p=newQueue; p->date=e; if(rear->next==rear) { p->next=rear; rear->next=p; rear=p; } else { p->next=rear->next->next; rear->next->next=p; } cout<<"插入"<<e<<endl;}ElmeTypeOutqueue(Queue*&rear)//出列{ if(rear->next==rear) { cout<<"队列空"<<endl; returnNULL; } Queue*p=rear; while(p->next!=rear) p=p->next; ElmeTypee=rear->date; p->next=rear->next; deleterear; rear=p; returne;}voidshow(Queue*rear)//队列的输出{ Queue*p=rear->next; p=p->next; while(p->date!=-1) { cout<<p->date<<""; p=p->next; } cout<<endl;}voidmain(){ Queues; Queue*rear=&s; InitQueue(rear); show(rear); InQueue(rear,12); InQueue(rear,96); InQueue(rear,23); InQueue(rear,56); InQueue(rear,6); InQueue(rear,8); show(rear); ElmeTypee; e=Outqueue(rear); cout<<"出队队尾元素："<<endl<<e<<endl; e=Outqueue(rear); cout<<e<<endl; e=Outqueue(rear); cout<<e<<endl; e=Outqueue(rear); cout<<e<<endl; show(rear);}测试结果1、2、六、小结（包括收获、心得体会、