算法与数据结构课程设计--栈和队列的应用

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

1、栈和队列的应用一、问题描述栈和队列是一种常见的数据结构，是两种非常重要的线性结构，也都是线性表，它们是操作受限的的线性表，有顺序栈、链式栈、链式队列和循环队列等形式。它们广泛应用在各种软件系统中。本题就是要用这些线性结构先完成基本的应用，如回文，逆置。再编写一个简易的停车场管理系统，完成对车辆出入库的管理、停车时间的记录和管理费用的结算。二、基本要求1、选择顺序栈和链队列，完成回文判断、字符串的逆置；2、选择链栈和循环队列，完成回文判断、字符串的逆置；3、运用栈和队列，完成简易停车场管理系统，要求：（1）车辆入库管理及时间记录；（2）车辆出库管理、时间的记录及管理费用的结

2、算；（3）若停车场已满则车辆进入便车道等候。三、测试数据1、回文判断的测试数据：abcbc@；2、字符串逆置的测试数据：abcdef；3、停车场管理系统测试数据：（1）输入A1、A2、A3实现车辆的入库及对便车道进行测试；（2）输入D1对车辆出库及管理费用结算进行测试。四、算法思想1、（1）定义顺序栈和链队列及关于它们的基本操作，如定义栈和队列、求栈和队列的长度、入栈出栈、入队列出队列等。方便后面函数的调用，是实现程序的基石。（链栈和循环队列也是如此）2、（1）编写函数Palindrome_Test来实现字符串的回文判断，回文是利用了栈的反序输出原则而队列则是顺序输出这个

3、思想来实现的。往栈和队列输入同一组字符，再将它们一起输出，这样栈输出的字符就与原来的顺序相反了，而队列输出的字符与原来的顺序仍然是一样的，这样比较它们输出的字符是否相等就可以判断是否是回文了。是则输出1，不是则输出。(2)编写函数nzhi来实现一段字符串的逆置。逆置是通过栈的反序输出来实现的。通过它将队列的一组字符串进行逆置。将队列的字符串顺序入栈然后出栈。这样得到的字符串与原来的字符串就逆置过来了。3、（1）定义车节点的类型及栈和队列的相关操作。（2）用栈的操作编写一个停车场，队列的操作编写一个便车道。wilyes11收集博客(与学习无关)：http://blog.si

4、na.com.cn/u/1810231802（3）编写函数Carrival实现车辆入库管理，若车库满则进入便车道，这个函数是利用栈的入栈等操作来实现的，并利用“t=localtime(&car.t);”语句记录入库时间。（4）编写函数Carleave实现车辆出库管理并利用“t=localtime(&car.t);”语句记录出库时间，计算车辆的管理费用。若便车道内有车等候，则进入停车场，并记录此时时间。主要用到了栈的入栈出栈及队列中的入队列等操作。用“(car.t-car2.t)*charge”语句来计算车辆的管理费用。五、模块划分。1、定义栈和队列及其基本操作。（1）vo

5、idInitStack(SqStack*S)初始化栈（2）intStackLength(SqStackS)求栈的长度（3）voidPush(SqStack*S,ElemTypee)及voidPop(SqStack*S,ElemType*e)入栈及出栈（4）voidInitQueue(LinkQueue*Q)初始化队列（5）intQueueLength（SqQueueQ）求队列的长度(6)intEnQueue(SqQueue*Q，ElemTypee)及voidDeQueue(LinkQueue*Q,ElemType*e)入队列及出队列2、intPalindrome_Test

6、(SqStack*S,LinkQueueQ)判断是否为回文，是则输入1，否则输出0。3、voidnzhi(LinkQueueQ)实现字符串的逆置。4、typedefstructParkCar定义车节点类型。5、voidCarrival(LinkQueue*q,ParkCarcar)实现车辆入库管理及记录时间的功能。6、voidCarleave(LinkQueue*q,ParkCarcar)实现车辆出库管理及时间记录，管理费用的计算的功能。7、intmain()主函数。调用定义的函数进行操作及结果的输出。六、数据结构//(ADT)1、链栈typedefintElemType

7、;typedefstructSNodewilyes11收集博客(与学习无关)：http://blog.sina.com.cn/u/1810231802{ElemTypeData;structSNode*next;}SNode*LinkStack;循环队列typedefstruct{ElemType*base;intfront;intrear;}SqQueue;2、顺序栈typedefcharElemType;typedefstruct{ElemType*base;ElemType*top;}SqStack;链式队列typede