栈和队列,数据结构实验报告
为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划栈和队列,数据结构实验报告数据结构课程实验报告注：空间不够，可以增加页码。第三章栈和队列的应用【实验目的】1熟练掌握栈和队列的结构，以及这两种数据结构的特点；2能够在两种存储结构上实现栈的基本运算，特别注意栈满和栈空的判断条件及描述方法；3熟练掌握链队列和循环队列的基本运算，并特别注意队列满和队列空的判断条件和描述方法；第一节知识准备一、栈：1.基本概念栈是一种限定仅在表的一端进行插入与删除操作的线性表。允许进行插入与删除操作的这一端称为栈顶，而另一端称为栈底，不含元素的空表称为空栈，插入与删除分别称进栈与出栈。由于插入与删除只能在同一端进行，所以较先进入栈的元素，在进行出栈操作时，要比较后才能出栈。特别是，最先进栈者，最后才能出栈，而最晚进栈者，必最先出栈。因此，栈也称作后进先出的线性表，简称LIFO表。栈示意图见图3-12.栈的抽象数据类型定义：ADTStack数据对象：D=|ElemSet,i=1,2,.,n,n>=0数据关系：R1=|,D,i=2,.,n基本操作：InitStack(&S)构造一个空栈SStackEmpty(S)判断栈S是否为空StackLength(S)返回栈S的元素个数,即栈的长度GetTop(S,&e)取栈S的栈顶元素Push(&S,e)将元素e入栈Pop(&S,&e)删除S的栈顶元素并用e返回其值ADTStack3.栈的表示：栈有两种存储表示方法：顺序存储结构和链式存储结构。(1)顺序存储结构：#defineSTACK_INIT_SIZE100；/存储空间初始分配量#defineSTACKINCREMENT10；/存储空间分配增量typedefstructSElemType*base；/栈底指针SElemType*top；/栈顶指针intStackSize；/栈的当前容量SqStack；(2)链式存储结构：TypedefstructLnodeElemTypedata;structLnode*next;Lnode,*LinkList;二、队列：1.与栈相对应，队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端进行删除元素。允许插入的一端称队尾，允许删除的一端称队头。插入与删除分别称为入队与出队。队列示意图见图3-2：出队a1a2?an-1an进队队头队尾图3-2队列2.队列的抽象数据类型定义：ADTQueue数据对象：D=|ElemSet,i=1,2,.,n,n>=0数据关系：R1=|,D,i=2,.,n基本操作：InitQueue(&Q)构造一个空队列QQueueEmpty(Q)判断队列是否为空QueueLenght(Q)返回队列Q的元素个数，即队列的长度GetHead(Q,&e)取队列Q的队头元素，并用e返回EnQueue(&Q,e)将元素e入队列DeQueue(&Q,&e)删除非空队列Q的队头元素，并用e返回其值ADTQueue3.队列的表示：队列有两种表示方法：链队列、循环队列。链队列的表示：typedefstructQNodeQElemTypedata;structQNode*next;QNode,*QueuePtr;typedefstructQueuePtrfront;QueuePtrrear;LinkQueue;(2)循环队列的表示第二节循环队列的表示和实现【问题描述】设计一个抽象数据类型队列的顺序表示和实现的演示程序。【数据描述】#defineMaxQsize100/最大队列长度typedefstructQElemType*base;/初始化的动态分配存储空间intfront;/头指针，若队列不空，指向队列头元素intrear;/尾指针，若队列不空，指向队列尾元素的下一个位置SqQueue;【算法描述】StatusInitQueue(SqQueue&Q)/构造一个空队列Q=(QelemType*)malloc(MaxQsize*sizeof(QelemType);if(!)exit(OVERFLOW);/存储分配失败=0;returnOK;StatusQueueEmpty(SqQueueQ)/若队列Q为空队列，则返回TRUE，否则返回FALSEif()returnTRUE;elsereturnFALSE;intQueueLength(SqQueueQ)/返回Q的元素个数，即为队列的长度return(+MaxQsize)%MaxQsize;StatusGetHead(SqQueueQ,QelemType&e)/若队列不为空，则用e返回Q的队头元素，并返回OK；否则返回ERRORif(=)returnERROR;e=;returnOK;StatusEnQueue(SqQueue&Q,QelemTypee)/插入元素e为Q的新的队尾元素if(+1)%MaxQsize=)returnERROR;/队列满=e;=(+1)%MaxQsize;returnOK;StatusDeQueue(SqQueue&Q,QelemType&e)/若队列不空，则删除Q的队头元素，用e返回其值，并返回OK,否则返回ERRORif(=)returnERROR;/队列空e=;=(+1)%MaxQsize;returnOK;【C源程序】#include#includetypedefintQElemType;typedefintStatus;#defineOK1#defineTRUE1#defineFALSE0#defineERROR0#defineOVERFLOW-2#defineMaxQsize100/*最大队列长度*/typedefstructQElemType*base;/*初始化的动态分配存储空间*/intfront;/*头指针，若队列不空，指向队列头元素*/intrear;/*尾指针，若队列不空，指向队列尾元素的下一个位置*/SqQueue;StatusInitQueue(SqQueue*Q)/*构造一个空队列Q*/(*Q).base=(QElemType*)malloc(MaxQsize*sizeof(QElemType);if(!(*Q).base)return(OVERFLOW);/*存储分配失败*/(*Q).front=(*Q).rear=0;returnOK;StatusQueueEmpty(SqQueueQ)/*若队列Q为空队列，则返回TRUE，否则返回FALSE*/实验报告课程名称数据结构程序设计实验项目数据结构中栈和队列的应用系别_计算机学院_专业_网络工程_班级/学号_网工1202/XX_学生姓名_王宇涵_实验日期_XX年6月2日成绩_指导教师实验题目:表达式的运算一、程序功能分析程序整体功能流程分析如下。第一步，用户输入表达式。第二步，对用户输入的表达式进行过滤，如果有错，请用户重新输入正确表达式；否则，返回正确的表达式。第三步，对表达式进行处理，将运算数和运算符按照“计算器算法”分别压入栈中，并在此过程中记录顶元素的变化情况。第四步，最后，返回结果，打印输出。二、设计方案数据结构设计任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置，base为栈底指针，在顺序栈中，它始终指向栈底，即top=base可作为栈空的标记，每当插入新的栈顶元素时，指针top增1，删除栈顶元素时，指针top减1。为了实现算符优先算法。可以使用两个工作栈。一个称为OPTR，用以寄存运算符，另一个称做OPND，用以寄存操作数或运算结果。1.首先置操作数栈为空栈，表达式起始符”#”为运算符栈的栈底元素；2.依次读入表达式，若是操作符即进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完毕。数据存储结构因为表达式是由操作符，运算符和界限符组成的。如果只用一个char类型栈，不能满足2位以上的整数，所以还需要定义一个int类型的栈用来寄存操作数。定义两个栈的类型如下：/*定义字符类型栈*/typedefstructintstacksize;char*base;char*top;Stack;/*定义整型栈*/typedefstructintstacksize;int*base;int*top;Stack2;1.Precede(charc1,charc2)判断运算符优先权，返回优先权高的。算符间的优先关系如下：算法步骤：第一步，如果输入符号位“+”或“减”。如果栈顶元素为“”“*”“/”，此时栈顶元素符号优先级高，返回“>”，否则，栈顶符号优先级低，返回“”。第五步，输入符号为其他。栈顶元素为“#”,此时优先级同，返回“=”；否则，栈顶元素符号优先级高，返回“>”。算法代码charPrecede(charc1,charc2)staticchararray49='>','>','','>','>','>','','>','>','>','>','>','','>','>','>','>','>','','>','','>','>','>','!','>','>','<','<','<','<','<','!','='/用一维数组存储49种情况switch(c1)/*i为下面array的横标*/case'+':i=0;break;case'-':i=1;break;case'*':i=2;break;case'/':i=3;break;case'(':i=4;break;case')':i=5;break;case'#':i=6;break;switch(c2)/*j为下面array的纵标*/case'+':j=0;brea
