栈和队列的应用实验报告

数据结构实验报告栈和队列的应用(10003809389j)一实验目的使学生掌握栈的特点及其逻辑结构和物理结构的实现；使学生掌握队列的特点及其逻辑结构和物理结构的实现；使学生掌握链栈和顺序栈结构的插入、删除等基本运算的实现；使学生掌握链队列和顺序队列结构的插入、删除等基本运算的实现；使学生熟练运用栈结构解决常见实际应用问题；使学生熟练运用队列结构解决常见实际应用问题；二实验环境所需硬件环境为微机；所需软件环境为MicrosoftVisualC++6.0；三实验内容链栈:#include"LinkList0.c"/*详见实验1*/LinkListInitStack_Sl(){LinkListS;S=InitList_Sl();returnS;}StatusDestroyStack_Sl(LinkListS){if(!S)returnERROR;/*链栈不存在*/DestroyList_Sl(S);returnOK;}StatusStackEmpty_Sl(LinkListS){if(!S)returnERROR;/*链栈不存在*/if(S->next==NULL)returnTRUE;elsereturnFALSE;}/*若链栈S存在，则当S非空时返回栈顶元素e*/StatusStackGetTop_Sl(LinkListS){if(!S)returnERROR;/*链栈不存在*/if(S->next==NULL)returnFALSE;/*栈空*/elsereturn(S->next->elem);}/*若链栈S存在，则当S非空时，删除栈顶元素并用e保存删除的栈顶元素*/StatusStackPop_Sl(LinkListS,ElemType*e){if(!S)returnERROR;/*链栈不存在*/ListDelete_Sl(S,e);returnOK;}/*若链栈S存在时，插入元素e为新的栈顶元素*/StatusStackPush_Sl(LinkListS,ElemTypee){if(!S)returnERROR;/*链栈不存在*/ListInsert_Sl(S,e);returnOK;}/*若链栈S存在，返回链栈中元素个数*/intStackLength_Sl(LinkListS){if(!S)returnERROR;/*链栈不存在*/returnListLength_Sl(S);}/*若链栈S存在，遍历链栈S，对每个元素执行操作void(*operate)(ElemType*)*/StatusStackTraverse_Sl(LinkListS,void(*operate)(ElemType*)){if(!S)returnERROR;/*链栈不存在*/return(ListTraverse_Sl(S,operate));}链队列#include"LinkList0.c"/*详见实验1*/typedefstructQode{ElemTypeelem;structQode*next;}Qode,*Queue;typedefstruct{Queuefront;Queuerear;}Linkqueue,*LinkQueue;/*InitQueue_Sq()构造一个空的队列*/LinkQueueInitQueue_Sl(){LinkQueueQ;Q->front=Q->rear=(Queue)malloc(sizeof(Qode));if(!Q->front)returnNULL;/*存储分配失败*/Q->front->next=NULL;returnQ;}/*若队列Q存在，销毁链队列Q*/StatusDestroyQueue_Sl(LinkQueueQ){Queuep;if(!Q)returnERROR;/*链队列不存在*/do{/*释放单向线性链表空间*/p=Q->front;Q->front=Q->front->next;free(p);}while(Q->front);returnOK;}/*若链队列Q存在，则当Q为空时返回TRUE，否则返回FALSE*/StatusQueueEmpty_Sl(LinkQueueQ){if(!Q)returnERROR;/*链队列不存在*/if(Q->front==Q->rear)returnTRUE;elsereturnFALSE;}/*若链队列Q存在，则当Q非空时，返回队头元素e*/StatusQueueGetTop_Sl(LinkQueueQ,ElemTypee){if(!Q)returnERROR;/*链队列不存在*/if(QueueEmpty_Sl(Q)==TRUE)returnFALSE;/*队列空*/elsereturn(Q->front->next->elem);}/*若链队列Q存在，则当Q非空时，删除队头元素并用e保存删除的队头元素*/StatusDeQueue_Sl(LinkQueueQ,ElemType*e){Queuep;if(!Q)returnERROR;/*顺序队列不存在*/if(QueueEmpty_Sl(Q)==TRUE)returnFALSE;/*队列空*/else{p=Q->front->next;*e=p->elem;Q->front->next=p->next;if(Q->front->next==NULL)Q->rear=Q->front;free(p);returnOK;}}/*若链队列Q存在时，插入元素e为新的队头元素*/StatusEnQueue_Sl(LinkQueueQ,ElemTypee){Queuep;if(!Q)returnERROR;/*单向线性链表结点L不存在*/p=(Queue)malloc(sizeof(Qode));if(!p)exit(OVERFLOW);/*存储空间增加失败*/p->next=NULL;p->elem=e;Q->rear->next=p;Q->rear=p;returnOK;}/*若链队列Q存在，返回链队列元素个数*/intQueueLength_Sl(LinkQueueQ){inti=0;Queuep;if(!Q)returnERROR;/*链队列不存在*/p=Q->front;while(p!=Q->rear){i++;p=p->next;}return(i);}/*若链队列Q存在，遍历链队列Q，对每个元素执行操作void(*operate)(ElemType*)*/StatusQueueTraverse_Sl(LinkQueueQ,void(*operate)(ElemType*)){Queuep;if(!Q)returnERROR;/*链队列不存在*/p=Q->front->next;while(p!=NULL){operate(&p->elem);p=p->next;}return(OK);}表达式求解#include"LinkStack.c"//用链栈实现中缀表达式求解。intprecede(intc,chard)//判断运算符的优先级，{intt;switch(c){case45:case43:switch(d){case')':case'#':case'+':case'-':t=1;break;case'*':case'(':case'/':t=-1;break;default:t=-2;}break;case42:case47:switch(d){case'+':case'-':case')':case'*':case'/':case'#':t=1;break;case'(':t=-1;break;default:t=-2;}break;case40:if(d=='*'||d=='/'||d=='('||d=='+'||d=='-')t=-1;elseif(d==')')t=0;elset=-2;break;case41:if(d=='+'||d=='-'||d==')'||d=='#'||d=='*'||d=='/')t=1;elset=-2;break;case35:if(d=='*'||d=='/'||d=='('||d=='+'||d=='-')t=-1;elseif(d=='#')t=0;elset=-2;break;default:t=-2;}returnt;}intOperate(inta,inttheta,intb){//实现加减乘除运算。intt;switch(theta){case43:t=a+b;break;case45:t=a-b;break;case42:t=a*b;break;case47:t=a/b;break;default:printf("Error");}returnt;}intmain(){charc;inta,b,d=1,p,q,theta,x;LinkListOPND,OPTR;printf("请输入中缀表达式，以#结尾：\n");OPTR=InitStack_Sl();StackPush_Sl(OPTR,35);OPND=InitStack_Sl();c=getchar();while(c!='#'||StackGetTop_Sl(OPTR)!=35){//当输入字符和栈底元素都为#时退出循环。if(c>=48&&c<=57){p=c-48;c=getchar();//是数字就入栈while(c>=48&&c<=57){q=c-48;p=10*p+q;c=getchar();}//循环实现多位数求解StackPush_Sl(OPND,p);}else{switch(precede(StackGetTop_Sl(OPTR),c)){case-1:StackPush_Sl(OPTR,c);c=getchar();break;case0:StackPop_Sl(OPTR,&x);c=getchar();break;case1:StackPop_Sl(OPTR,&theta);StackPop_Sl(OPND,&b);StackPop_Sl(OPND,&a);StackPush_Sl(OPND,Operate(a,theta,b));break;default:printf("Error!");d=0;}}if(d==0)break;}//输入错误退出循环printf("结果为：%d\n",StackGetTop_Sl(OPND));}四实验分析及问题思考1、分析链栈和顺序栈结构之间的差异；答:顺序栈结构由一个顺序表和一个top组成，而链栈由链表组成。顺序栈有top记录栈顶的位置，而链栈没有，但链栈的下一结点就是栈顶。插入和删除顺序栈顶元素时需要改变top的值，链栈不需要。2、分析顺序表及线性链表的优缺点；1顺序表：优点：1、逻辑相邻，物理相邻2可随机存取任一元素3存储空间使用紧凑缺点：1插入、删除操作需要移动大量的元素2预先分配空间需按最大空间分配，利用不充分3表容量难以扩充 2线性链表：优点：1空间合理利用，插入和删除不需要移动。2它是一种动态结构，整个存储空间为多个链表共用3不需预先分配空间缺点：1实现某些操作不如顺序存储结构。