数据结构课程设计栈和队列

《数据结构课程设计栈和队列》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、邃其种耗孕猿ZUIMYlSHIFAIMXUEVUAIM实验课程名称数据结构与课程设计专业班级10级计科（2）班学生姓名赵腾松学10410902044指导教师冯韵2012至2013学年第1学期第3至4周目录1観32雜撕33順脯34糊i殳i十34.1屮缀表达式转换为后缀表达式算法设计34.2后缀表达式算法设计95程序代码106运行与测试147总结与心得148参考文献141概述本次实验需要对栈和队列进行充分的了解虽然栈和队列实质上是不同的但在编写程序时大致相似。通常找可以用顺序的方式存储分配一块连续的存储区域存放栈中元素并用一个变量指向当前的栈顶。

2、而队列的顺序存储结构需要使用一个数组和两个整数型变量来实现。2系统分析栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表。对丁•顺序栈入栈时首先判断栈是否为满栈满的条件为p-〉top==MAXNUM-1栈满时不能入栈；否则出现空间溢出引起错误这种现象称为上溢。出栈和读栈顶元素操作先判栈是否为空为空时不能操作否则产生错误。通常栈空作为-•种控制转移的条件。队列的顺序存储结构称为顺序队列顺序队列实际上是运算受限的顺序表。入队时将新元素插入rear所指的位置然后将rear加1。岀队时删去front所指的元素然后将front加1并返回被删元素。3概要

3、分析编写一个程序实现顺序栈的各种基本运算并在此基础上设计一个主程序完成如下功能：1初始化顺序栈；2插入元素；3删除栈顶元素；4収栈顶元素；5遍历顺序栈；6置空顺序桟。编写一个程序实现顺序队列的各种基本运算并在此基础上设计一个主程序完成如下功能：1初始化队列；2建立顺序队列；3入队；4出队；5判断队列是否为空；6取队头元素；7遍历队列。4详细设计4.1中缀表达式转换为后缀表达式算法设计顺序扫描屮缀表达式，当读到数字时直接将其送至输出队列屮；当读到运算符时，将栈屮所有优先级高于或等于该运算符的运算符弹出，送至输出队列中，再将当前运算符入栈；当读到

4、左括号时，即入栈；当读到右括号时，将靠近栈顶的第一个左括号上面的运算符全部依次弹出，送至输出队列，再删除栈中的左括号。具体算法如下：voidCTPostExp(SeqQueue*Q)SeqStackOS;//运算符栈charc，t;SeqStack*S;S=&OS;InitStack(S);//初始化栈Push(S；#*);//压入栈底元素’#’do//扫描中缀表达式{c=getchar();switch(c){case’break;//去除空格符case’O’：caseT:case'2':case’3’：case.4’:case’5’：ca

5、se’6’：case7’：case'8’：case’9’：EnQueue(Q，c);break;case’(’：Push(S，c);break;casey：case’#’：do{t=Pop(S);if(t!=C&&a)EnQueue(Q,t)；}while(t!='C&&S-〉top!=-l);break;case'+*:casecasecase7':while(Priority(c)<=Priority(GetTop(S))){t=Pop(S);EnQueue(Q，t);}Push(S,c);break;}//EndSwitch}while

6、(c!=’#

7、);//以•#’号结朿表达式扫描}要执行上述算法，还必须给出相关的栈和队列的定义、操作以及调用该算法的主函数。具体算法如下：#include#defineStackSize100#defineQueueSize100/*队列的相关操作*/typedefcharDataType;typedefstruct{chardata[100];intfront,rear;JSeqQueue;//定义队列类型voidInitQueue(SeqQueue*Q)//初始化队列Q->front=0;Q->reai-0;)intQu

8、eueEmpty(SeqQueue*Q)//判空队列{returnQ->rear==Q->front;)voidEnQueue(SeqQueue*Q,DataTypex)//入队列{if((Q-〉rear+1)%QueueSize==Q->front)printf("Queueoverflow");else{Q->data[Q->rear]=x;Q->rear=(Q->rear+1)%QueueSize;}}intDeQueue(SeqQueue*Q){returnQ->data[Q->front++];}/*栈的相关操作*/typedefs

9、truct{DataTypedata[100];inttop;}SeqStack;//栈类型的定义voidInitStack(SeqStack*S)//初始化枝S-