实验四栈与队列

《实验四栈与队列》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验四栈与队列姓名王艳青学号520713130135日期2009.12.9实验题目栈与队列实验内容1.采用链式存储实现栈的初始化、入栈、出栈操作。2.采用顺序存储实现栈的初始化、入栈、出栈操作。3.采用链式存储实现队列的初始化、入队、岀队操作。4.采用顺序存储实现循环队列的初始化、入队、出队操作。5.在主函数屮设计一个简单的菜单，分别测试上述算法。*6.综合训练:1）利用栈实现表达式求值算法。2）利用栈实现迷宫求解。实验说明1.基本要求：实现算法1、3或算法2、4即可。2.类型定义顺序栈示例ttdefineMAX100

2、〃栈的最大值typedefstruet{ElemType*base；inttop；}SqStack；顺序队列示例ttdefineMAX100//队列的最大长度typedefstruet{ElemType*base；intfront,rear；}SqQueue；3.算法6的每个子功能尽可能写成函数形式。注意问题1.重点理解栈、队列的算法思想，能够根据实际情况选择合适的存储结构。2.注意算法6的各个函数之间值的传递情况。3.栈、队列的算法是后续实验的基础（广义表、树、图、查找、排序等）。实验源代码头文件#prtigmaon

3、ce^defineWIN32_LEAN_AND_MEAN//从Windows头中排除极少使川的资料^include^include栈文件include^includeusingnamespacestd;typedefintDataType;structScqStack//顺序栈类型定义{intMAXNUM;//栈屮最大元素个数intt;//t

4、ck*PSeqStack;//顺序栈类型的指针类型//算法题：创建一个空栈PSeqStackcreateEmptyStackseq(intm);//算法题：判断栈是否为空intisEmptyStack_seq(PSeqStackpastack);//进栈(在栈中压入一个元索x)voidpushseq(PSeqStackpastack,DataTypex);〃出栈(删除栈顶元素)voidpopseq(PSeqStackpastack);//取栈顶元索(当pastack所指的栈不为空时，求栈顶元索的值)DataTypeto

5、pseq(PSeqStackpastack);structNode;//单链表结点typedefstructNode*PWde;//指向结点的指针类型structNode//单链表结点定义{DataTypeinfo;PNodelink;}；structLinkStack//链接栈类型定义{PNodetop;//指向栈顶结点)；typedefstructLinkStack*PLinkStack;//链接栈类型的指针类型//创建一个空链栈PLinkStackcreateEmptyStacklink(void);//判断单链

6、形式栈是否为空栈intisEmptyStack1ink(PLinkStackplstack);//进栈(在栈中压入一个元素)voidpush_link(PLinkStackplstack,DataTypex);〃出栈voidpop1ink(PLinkStackplstack)://取栈顶元素DataTypetop_link(PLinkStackplstack);structSeqQueue//顺序队列类型定义{intMAXNUM;//队列屮最大元索个数intf,r;DataType*q;}；typedefSeqQueu

7、e*PSeqQueue;//顺序队列类型的指针类型//创建一个空队列PSeqQueuecreateEmptyQueueseq(intm);//判断队列是否为空intisEmptyQueue_scq(PSeqQueuepaqu);//入队(在队尾插入元素x)voidenQueueseq(PSeqQueuepaqu,DataTypex);//出队(删除队列头部元素)voiddeQueueseq(PSeqQueuepaqu)://取队列的头元索DataTypefrontQueuc_seq(PSeqQueuepaqu);str

8、uctLinkQueue//链接队列类型定义{PNodef;//头指针PNoder;//尾指针}；typedefstructLinkQueue*PLinkQueue;//链接队列类型的指针类型//创建一个空队列PLinkQueuecreateEmptyQueue1ink();//判断链接表示队列是否为空队intisEmptyQue