栈和队列的应用.docx

《栈和队列的应用.docx》由会员分享，可在线阅读，更多相关《栈和队列的应用.docx（20页珍藏版）》请在三一办公上搜索。

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

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

3、栈输出的字符就与原来的顺序相反了，而队列输出的字符与原来的顺序仍然是一样的，这样比较它们输出的字符是否相等就可以判断是否是回文了。是则输出1，不是则输出。 (2)编写函数nzhi来实现一段字符串的逆置。逆置是通过栈的反序输出来实现的。通过它将队列的一组字符串进行逆置。将队列的字符串顺序入栈然后出栈。这样得到的字符串与原来的字符串就逆置过来了。 3、定义车节点的类型及栈和队列的相关操作。 用栈的操作编写一个停车场，队列的操作编写一个便车道。 wilyes11收集 博客(与学习无关)： 编写函数Carrival实现车辆入库管理，若车库满则进入便车道，这个函数是利用栈的入栈等操作来实现的，并利用“t

4、=localtime(&car.t);”语句记录入库时间。 编写函数Carleave实现车辆出库管理并利用“t=localtime(&car.t);”语句记录出库时间，计算车辆的管理费用。若便车道内有车等候，则进入停车场，并记录此时时间。主要用到了栈的入栈出栈及队列中的入队列等操作。用“(car.t-car2.t)*charge”语句来计算车辆的管理费用。 五、模块划分。 1、定义栈和队列及其基本操作。 void InitStack(SqStack *S) 初始化栈 int StackLength(SqStack S) 求栈的长度 void Push(SqStack *S,ElemType e

5、)及void Pop(SqStack *S,ElemType *e) 入栈及出栈 void InitQueue(LinkQueue *Q) 初始化队列 int QueueLength 求队列的长度 (6) int EnQueue(SqQueue *Q，ElemType e)及void DeQueue(LinkQueue *Q, ElemType *e) 入队列及出队列 2、 int Palindrome_Test(SqStack *S,LinkQueue Q) 判断是否为回文，是则输入1，否则输出0。 3、 void nzhi(LinkQueue Q) 实现字符串的逆置。 4、 typedef

6、 struct ParkCar 定义车节点类型。 5、 void Carrival(LinkQueue *q,ParkCar car) 实现车辆入库管理及记录时间的功能。 6、 void Carleave(LinkQueue* q,ParkCar car) 实现车辆出库管理及时间记录，管理费用的计算的功能。 7、 int main 主函数。调用定义的函数进行操作及结果的输出。 六、数据结构/(ADT) 1、链栈 typedef int ElemType; typedef struct SNode wilyes11收集 博客(与学习无关)： ElemType Data; struct SNode

7、 *next; SNode *LinkStack; 循环队列typedef struct ElemType *base; int front; int rear;SqQueue; 2、顺序栈typedef char ElemType; typedef struct ElemType *base; ElemType *top; SqStack; 链式队列typedef struct QNode ElemType data; struct QNode *next; QNode, *QueuePtr; typedef struct QueuePtr front; QueuePtr rear; Lin

8、kQueue; 3、车节点 typedef struct ParkCar char ADmark; int Plate; time_t t; ElemType,ParkCar; 七、源程序 1.用顺序栈和链式队列实现逆置和回文 #include #include #define N 20 typedef char ElemType; typedef struct wilyes11收集 博客(与学习无关)： ElemType *base; ElemType *top; SqStack; typedef struct QNode ElemType data; struct QNode *next;

9、 QNode, *QueuePtr; typedef struct QueuePtr front; QueuePtr rear; LinkQueue; void InitStack(SqStack *S) S-base=(ElemType *)malloc(N*sizeof(ElemType); if (!S-base) exit(0); S-top=S-base; void DestroyStack(SqStack *S) free(S-base); void ClearStack(SqStack *S) S-top=S-base; int StackEmpty(SqStack S) if

10、(S.top=S.base) return 1; else return 0; int StackLength(SqStack S) return S.top-S.base; void GetTop(SqStack S, ElemType *e) if (S.topS.base) *e=*(S.top-1); void Push(SqStack *S,ElemType e) if (S-top-S-basetop)=e; S-top+; else printf(n栈满); void Pop(SqStack *S,ElemType *e) if (S-topS-base) wilyes11收集

11、博客(与学习无关)： S-top-; *e=*(S-top); void InitQueue(LinkQueue *Q) Q-front=Q-rear=(QueuePtr)malloc(sizeof(QNode); if (!(Q-front) exit(0); Q-front-next=NULL; void DestroyQueue(LinkQueue *Q) while (Q-front) Q-rear=Q-front-next; free(Q-front); Q-front=Q-rear; int QueueEmpty(LinkQueue Q) if (Q.front=Q.rear) r

12、eturn 1; else return 0; int QueueLength(LinkQueue Q) QueuePtr p; int n=0; p=Q.front; while (p!=Q.rear) n+; p=p-next; return n; void EnQueue(LinkQueue *Q, ElemType e) QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode); if (!p) exit(0); p-data=e; p-next=NULL; Q-rear-next=p; Q-rear=p; void DeQueue(LinkQueue

13、*Q, ElemType *e) QueuePtr p; if (Q-front!=Q-rear) p=Q-front-next; *e=p-data; Q-front-next=p-next; wilyes11收集 博客(与学习无关)： if (Q-rear=p) Q-rear=Q-front; free(p); int Palindrome_Test(SqStack *S,LinkQueue Q) char c,a,b; int flag=0; while(c=getchar!=) Push(S,c);EnQueue(&Q,c); /同时使用栈和队列两种结构 while(!StackEmp

14、ty(*S) Pop(S,&a);DeQueue(&Q,&b); if(a!=b) flag=1; if(flag=0) return 1; else return 0; /*/ void nzhi(LinkQueue Q) char ch;SqStack S; InitStack(&S); while(!QueueEmpty(Q) DeQueue(&Q,&ch); Push(&S,ch); while(!StackEmpty(S) Pop(&S,&ch); EnQueue(&Q,ch); while(!QueueEmpty(Q) DeQueue(&Q,&ch); printf(%c,ch);

15、 wilyes11收集 博客(与学习无关)： int main SqStack s;LinkQueue q;char chN;int i; InitStack(&s);InitQueue(&q); if(Palindrome_Test(&s,q) printf(这是回文n); else printf(这不是回文n); fflush(stdin); for(i=0;inext; free(p); /* 清空链栈 */ void ClearStack(LinkStack *top) wilyes11收集 博客(与学习无关)： LinkStack p; while(*top!=NULL) p=*to

16、p; *top=(*top)-next; free(p); /* 判断顺栈是否为空 */ int StackEmpty(LinkStack top) if (top=NULL) return 1; else return 0; /* 求链栈长度 */ int StackLength(LinkStack top) LinkStack p; int n=0; p=top; while (p!=NULL) n+; p=p-next; return n; /* 取链栈栈顶元素 */ void GetTop(LinkStack top, ElemType *e) if (top!=NULL) *e=to

17、p-data; /* 入链栈 */ void Push(LinkStack *top, ElemType e) LinkStack new1; new1=(LinkStack)malloc(sizeof(SNode); new1-data=e; new1-next=*top; *top=new1; /* 出链栈 */ void Pop(LinkStack *top, ElemType *e) LinkStack p; if (*top!=NULL) *e=(*top)-data; p=*top; (*top)=p-next; free(p); wilyes11收集 博客(与学习无关)： /*

18、遍历链栈并输出: 栈顶向栈底方向输出 */ void StackTraverse(LinkStack top) LinkStack p; printf(nStack:); p=top; while (p) printf(t%d,p-data); p=p-next; typedef struct ElemType *base; char front; char rear;SqQueue; void InitQueue(SqQueue *Q) Q-base=(ElemType*)malloc(N*sizeof(ElemType); Q-front=Q-rear=0; void DestroyQue

19、ue(SqQueue *Q) free(Q-base); void ClearQueue(SqQueue *Q) Q-front=Q-rear=0; int QueueEmpty(SqQueue Q) if(Q.front=Q.rear) return 1; else return 0; int QueueLength(SqQueue Q) return (Q.rear+N-Q.front)%N; void GetHead(SqQueue Q,ElemType *e) if(Q.front!=Q.rear) *e=Q.baseQ.front; int EnQueue(SqQueue *Q,El

20、emType e) if(Q-rear+1)%N=Q-front) return 0; Q-baseQ-rear=e; Q-rear=(Q-rear+1)%N; return 1; wilyes11收集 博客(与学习无关)： int DeQueue(SqQueue *Q,ElemType *e) if(Q-front=Q-rear) return 0; *e=Q-baseQ-front; Q-front=(Q-front+1)%N; return 1; void QueueTraverse(SqQueue Q) int i; printf(nQueue:); if(Q.rearQ.front)

21、 Q.rear=Q.rear+N; for(i=Q.front;iQ.rear;i+) printf(%dt,Q.basei%N); int Palindrome_Test(LinkStack *S,SqQueue Q) char c,a,b; int flag=0; c=getchar; while(c!=) Push(S,c);EnQueue(&Q,c); c=getchar;/同时使用栈和队列两种结构 while(!StackEmpty(*S) Pop(S,&a);DeQueue(&Q,&b); if(a!=b) flag=1; if(flag=0) return 1; else ret

22、urn 0; /*/ void nzhi(SqQueue Q) char ch;LinkStack S; InitStack(&S); while(!QueueEmpty(Q) DeQueue(&Q,&ch); Push(&S,ch); wilyes11收集 博客(与学习无关)： while(!StackEmpty(S) Pop(&S,&ch); EnQueue(&Q,ch); while(!QueueEmpty(Q) DeQueue(&Q,&ch); printf(%c,ch); int main LinkStack s;SqQueue q;char chN;int i; InitStack

23、(&s);InitQueue(&q); printf(请输入一段字符串，并以结尾n); if(Palindrome_Test(&s,q) printf(这是回文n); else printf(这不是回文n); fflush(stdin); printf(n对一段字符串进行逆置n); for(i=0;i6;i+) scanf(%c,&chi); EnQueue(&q,chi); nzhi(q); system(pause); 3.停车场管理系统 #include #include #include #define N 2 #define charge 50 /*车节点类型*/ typedef s

24、truct ParkCar char ADmark; int Plate; time_t t; ElemType,ParkCar; wilyes11收集 博客(与学习无关)： typedef struct ElemType *base; ElemType *top; SqStack; typedef struct QNode ElemType data; struct QNode *next; QNode, *QueuePtr; typedef struct QueuePtr front; QueuePtr rear; LinkQueue; SqStack s; void InitStack(

25、SqStack *S) S-base=(ElemType *)malloc(N*sizeof(ElemType); if (!S-base) exit(0); S-top=S-base; void DestroyStack(SqStack *S) free(S-base); void ClearStack(SqStack *S) S-top=S-base; int StackEmpty(SqStack S) if (S.top=S.base) return 1; else return 0; int StackLength(SqStack S) return S.top-S.base; voi

26、d GetTop(SqStack S, ElemType *e) if (S.topS.base) *e=*(S.top-1); void Push(SqStack *S,ElemType e) if (S-top-S-basetop)=e; S-top+; else printf(n栈满); wilyes11收集 博客(与学习无关)： void Pop(SqStack *S,ElemType *e) if (S-topS-base) S-top-; *e=*(S-top); void InitQueue(LinkQueue *Q) Q-front=Q-rear=(QueuePtr)mallo

27、c(sizeof(QNode); if (!(Q-front) exit(0); Q-front-next=NULL; void DestroyQueue(LinkQueue *Q) while (Q-front) Q-rear=Q-front-next; free(Q-front); Q-front=Q-rear; int QueueEmpty(LinkQueue Q) if (Q.front=Q.rear) return 1; else return 0; int QueueLength(LinkQueue Q) QueuePtr p; int n=0; p=Q.front; while

28、(p!=Q.rear) n+; p=p-next; return n; void EnQueue(LinkQueue *Q, ElemType e) QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode); if (!p) exit(0); p-data=e; p-next=NULL; Q-rear-next=p; Q-rear=p; void DeQueue(LinkQueue *Q, ElemType *e) QueuePtr p; if (Q-front!=Q-rear) p=Q-front-next; *e=p-data; Q-front-next=p

29、-next; wilyes11收集 博客(与学习无关)： if (Q-rear=p) Q-rear=Q-front; free(p); /栈和队列的基本操作 void Carrival(LinkQueue *q,ParkCar car) struct tm *t; t=localtime(&car.t); if(StackLength(s)=N) printf(对不起宝马停车场已满，请进入便车道等候); EnQueue(q,car); else printf(宝马%d在%02d:%02d:%02d进入车n,car.Plate,t-tm_hour,t-tm_min,t-tm_sec); Push

30、(&s,car); /车的入库管理 void Carleave(LinkQueue* q,ParkCar car) struct tm *t; t=localtime(&car.t); SqStack st; ParkCar car2,car1;InitStack(&st); while(!StackEmpty(s) Pop(&s,&car2); if(s.top-Plate=car.Plate) break; else Push(&st,*s.top); printf(宝马%d在%02d:%02d:%02d离开车nn,car.Plate,t-tm_hour,t-tm_min,t-tm_sec

31、); printf(宝马%d号所花停车消费%d元n,car.Plate,(car.t-car2.t)*charge) while(!StackEmpty(st) Pop(&st,&car2); Push(&s,car2); if(!QueueEmpty(*q) DeQueue(q,&car1); car1.t=car2.t; printf(n宝马%d在%02d:%02d:%02d进入车n,car1.Plate,t-tm_hour,t-tm_min,t-tm_sec); Push(&s,car1); else printf(n宝马车库还有空位，等待车辆进入n); /车出库管理及费用计算 int

32、main LinkQueue q; ParkCar Bmw; InitStack(&s); InitQueue(&q); wilyes11收集 博客(与学习无关)： 库库库 printf(n请按要求输入，：如A 5表示5号车到达 D 6表示6号车离开车库n); while(1) scanf(%c%d,&Bmw.ADmark,&Bmw.Plate); if(Bmw.ADmark=A) time(&Bmw.t); Carrival(&q,Bmw); else if(Bmw.ADmark=D) time(&Bmw.t); Carleave(&q,Bmw); else break; fflush(st

33、din); printf(n); system(pause); return 1; 八、测试情况 程序的测试结果如下： 验证正确. wilyes11收集 博客(与学习无关)： 验证正确。 九、参考文献 1、严蔚敏，数据结构 C语言，清华大学出版社。 2、谭浩强，c语言程序设计，清华大学出版社。 wilyes11收集 博客(与学习无关)： 小结 通过这次课程设计让我们明白了许多,让我们明白了许多自身的不足与缺点,如我们实践经验上的缺乏,对设计的原理理解缺乏等等.与此同时,我们也学到了许多宝贵的经验与教训,这是我们平时学不到的.这些可以让我们受益一生. 首先是团队合作，通过这次课程设计我充分认识到

34、了团队协作的重要性。这次多亏了几个组员的帮助，群策群力，才能顺利而又完满的完成这次课程设计。团队的力量是无穷的。其次是搜集、选择相关的资料。在理解题目要求的基础上，了解了所需要实现的功能后，确定好大概的设计思路，再去查看书籍，去网上搜索相关资料，再来进行操作。这样无形中效率就提高了很多。最后是对于程序的修改和完善。我们几个组员在一起思考，补充。综合大家的意见完成了这份课程设计。我觉得和大家一起完成这份报告真的很高兴，很充实。这次我们的课题是字符串的回文与逆置操作以及编写一个简易的停车场管理系统。因为原来学过一点的原因，逆置和回文对我们来说还是比较容易的，主要的难题出在停车场管理系统上，通过上网

35、搜集相关的资料后，我们用栈和队列写出了这个程序，主要问题是在时间的输入问题上，我们的程序必须手动输入。经过老师的指导，我们修改了这部分程序，让系统能够自动记录时间。 这次的设计项目有很大的灵活度,但是基于我们经验与知识的不足,我们选择了停车场管理系统里面最简单的一种设计，只能实现其基本的一些功能，比如入库出库、便车道、还有停车费用的计算。通过这次设计我们有些体会,其一是要多交流.交流能让大家的想法统一,能让大家把分歧解决,能较好的交流可以促进项目的开发进度,也可以让组员之间更加默契,效率更高. 其二是多主动,其实也可以说是多思考.可能很多人都会想自己主动了,可是仔细想想,许多提出来的问题是动动

36、脑筋能解决的事,只是习惯的和别人讨论. 其三是要温故而知新。课程设计发端之始，思绪全无，举步维艰，对于理论知识学习不够扎实的我深感“书到用时方恨少”，于是想起圣人之言“温故而知新”，便重拾教材与实验手册，对知识系统而全面进行了梳理，遇到难处先是苦思冥想再向同学请教，终于熟练掌握了基本理论知识，而且领悟诸多平时学习难以理解掌握的较难知识，学会了如何思考的思维方式，找到了设计的灵感。 其四是思路即出路。当初没有思路，诚如举步维艰，茫茫大地，不见道路。在对理论知识梳理掌握之后，茅塞顿开，柳暗花明，思路如泉涌，高歌“条条大路通罗马”顿悟，没有思路便无出路，原来思路即出路。 其五实践出真知。时至今日，课

37、程设计基本告成，才切身领悟“实践是检验真理的唯一标准”，才明晓实践出真知。不为则不知，无为则无知，实践出真知。不认认真真的做是不会出成果的。 其六创新求发展。“创新”目前在我国已经提升到国家发展战略地位，足见“创新”的举足轻重。而在DVD产品上市之初及以后相当长时间内，由于核心技术受制于国外，原本前景看好的国内市场却使国内DVD生产商无利可图或图的仅仅蝇头小利，只因核心技术受制于wilyes11收集 博客(与学习无关)： 人，使用国外专利技术，每台售出总要交付高额专利技术使用费。因此，我们要从小处着手，顺应时代发展潮流，在课程设计中不忘在小处创新，未必是创新技术，但凡创新思维亦可，未必成功，只要实现创新思维培育和锻炼即可。 通过这次课程设计，锻炼了我们的协作能力，提高了我们用数据结构以及C语言知识解决实际问题的能力。当然体会不是只有这些,这些体会是我们得到的财富,是日后不管在什么时间,什么工作岗位上都能用的到的. wilyes11收集 博客(与学习无关)：