《数据结构》实验二.doc

《《数据结构》实验二.doc》由会员分享，可在线阅读，更多相关《《数据结构》实验二.doc（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、华北水利水电大学 数据结构 实验报告20152016学年 第 一 学期 2013级 计算机科学与技术专业班级： 学号： 姓名： 冯浩亮 实验二 栈和队列及其应用一、 实验题目：栈和队列及其应用二、 实验内容：1 病人看病模拟程序编写一个程序，反映病人到医院看病，排队看医生的情况。在病人排队过程中，主要重复两件事：（1） 病人到达诊室，将病历本交给护士，排到等待队列中候诊。（2） 护士从等待队列中取出一位病人的病历，该病人进入诊室就诊。要求采用带头结点的单链表作为队列，模拟病人等待就诊这一过程。程序采用菜单方式，其选项及功能说明如下：（1） 排队输入排队病人的病历号，加入到病人排队队列中。（2）

2、 就诊病人排队队列中最前面的病人就诊，并将其从队列中删除。（3） 查看队列从队首到队尾输出所有病人的病历号。（4） 不再排队，余下依次就诊从队首到队尾列出所有的排队病人的病历号，并退出运行。（5） 下班退出运行。 2停车场管理设停车场是一个可停放n辆车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北段），若停车厂内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车迹可开入；停车场内某辆车要离开时，在它之后进入的车连必须先退出车厂为它让路，待该车辆开出大门外，其

3、他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车时必须按它停留的时间长短缴纳费用。编写按上述要求进行管理的模拟程序。可以将停车场定义成一个顺序栈s0，便道定义成一个链队列q，而停车场中的某辆车要离开，则在它后面进停车场的车必须让道，让其离开，所以必须有一个临时的顺序栈s1，存放让道的车辆。当有车辆进停车场时，若栈s0不满，则直接进入栈s0；若栈s0满，则进入便道（链队列q）。若有s0中车辆x离开时，先让在x后面进栈的车从s0退栈并进入栈s1中，让x离开并收取停车费（在便道上停留的时间不收费），然后再把s1中所有元素退栈并重新进入s0栈，最后，将链队列q中的队头元素出队并进栈到s0中。三

4、、 实验要求：1 使用C语言完成算法设计和程序设计并上机调试通过。2 撰写实验报告，提供实验结果和数据。3 写出算法设计小结和心得。四、 程序源代码：1.#include #include typedef int QElemType;typedef struct node QElemType data;struct node *next; Qnode,*QueuePtr;typedef structQnode *front;Qnode *rear;LinkQueue;void menu() /菜单函数 printf(n); printf( 计科156班 n); printf(n); print

5、f( *病人看病模拟程序*n); printf( 1.排队n); printf( 2.就诊n); printf( 3.查看队列n); printf( 4.不在排队n); printf( 5.下班n); printf( *n); printf(n);void InitQueue(LinkQueue &Q)/构造一个空队列QQ.front=Q.rear=(Qnode*)malloc(sizeof(Qnode);Q.front-next=NULL;void DestroyQueue(LinkQueue &Q)/销毁队列Qwhile(Q.front)Q.rear=Q.front-next;free(Q

6、.front); Q.front=Q.rear;void EnQueue(LinkQueue &Q,QElemType e)/插入队尾元素e为Q的新的队尾元素 int i=1;Qnode *a = (Qnode *)malloc(sizeof(Qnode);a-data=e;a-next=NULL;Q.rear-next=a;Q.rear=a;printf(您排在第：%d号n,i+);void DeQueue(LinkQueue &Q)/就诊，并且删除头结点if(Q.front=Q.rear) return ;/判断 Qnode *p = (Qnode *)malloc(sizeof(Qnod

7、e);p=Q.front-next;printf(就诊患者病历号：%d,p-data);Q.front-next=p-next;if(Q.rear=p) Q.rear=Q.front;free(p);printf(n);void prin(LinkQueue Q) /查看就诊队列，即输出现有队列QueuePtr p;p=Q.front-next;printf(现有排队患者:);while(p!=NULL)printf(%d ,p-data);p=p-next;printf(n);main()int Cz,e;LinkQueue Q;InitQueue(Q);menu();while(Cz)pr

8、intf(t【输入操作】：);scanf(%d,&Cz);switch(Cz)case(1):printf(输入病历号:);scanf(%d,&e);EnQueue(Q,e);break;case(2):DeQueue(Q);break;case(3):prin(Q);break;case(4):prin(Q);DestroyQueue(Q);Cz=0;break;case(5):Cz=0;break;if(Cz=0) printf(ntt谢谢使用!n);return 0;2.#include #include #include #include #define max 3#define pr

9、ice 1int b=1;typedef struct int day; int hour; int min;TIME; /时间结点typedef structchar num10; /车牌号TIME time; /进入停车场的时间 int n; /进入停车场的位置information;/栈结构体定义typedef struct nodeinformation data;struct node *next;stacknode;stacknode *top1,*top2;/队列结构体定义typedef struct information data;stacknode *front,*rear

10、;LQueue;LQueue *Q;stacknode *Init(); /栈的初始化stacknode *into(stacknode *top1,LQueue *Q); /初始化车辆进入 int expenses(stacknode *p,int x,int y); /停车费用计算函数stacknode *leave(stacknode *top1,char str,LQueue *Q); /车辆驶出出场函数LQueue *InitLQue(); /初始化队列函数 LQueue *wait(LQueue *q,stacknode *s); /车辆进入候车便道函数 int EmptyLQue

11、(LQueue *q); /判断候车便道有无等待车辆函数stacknode *out(LQueue *q); /候车区车辆出队 stacknode *LQinto(stacknode *p,stacknode *top1); /从候车便道进入停车场函数 void show(stacknode *top1); /显示停车场所有信息函数void T_shou(LQueue *Q); /显示候车区信息/*函数部分*/主函数void main()char str10;Q=InitLQue();top1=Init();top2=Init();Q=InitLQue();int i;printf(ttt*n

12、);printf(tttt 停车场管理系统n);printf(ttt| 1. 车辆进入停车场 |n);printf(ttt| 2. 车辆离开停车场 |n);printf(ttt| 3. 显示停车场内所有车辆信息 |n);printf(ttt| 4. 显示候车区内所有车辆信息 |n);printf(ttt| 5. 退出 |n);printf(ttt*n);while(i!=5)printf(t请输入选项1-5:);scanf(%d,&i);switch(i)case 1:top1=into(top1,Q);break;case 2:printf(请输入离开车辆的车牌号：);scanf(%s,st

13、r);top1=leave(top1,str,Q);break;case 3:show(top1);break;case 4:T_shou(Q);break;case 5:exit(1);default:printf(输入错误，请重新输入15:);break; /*子函数*/初始化stacknode *Init()stacknode *top;top=(stacknode *)malloc(sizeof(stacknode);top=NULL;return top;/初始化车辆进入stacknode *into(stacknode *top1,LQueue *Q)stacknode *p,*q

14、;time_t rawtime; /调用系统时间函数struct tm *timeinfo; /时间结点time(&rawtime);timeinfo=localtime(&rawtime);p=(stacknode *)malloc(sizeof(stacknode);if(p=NULL)printf(内存分配失败);return top1;printf(请输入进入停车场车辆的车牌号:);scanf(%s,p-data.num);q=top1;while(q!=NULL)if(strcmp(p-data.num,q-data.num)=0)printf(车牌号输入有误，该车已进入!);ret

15、urn top1;q=q-next;p-data.time.day=timeinfo-tm_mday;p-data.time.hour=timeinfo-tm_hour;p-data.time.min=timeinfo-tm_min;p-data.n=b;if(bmax)printf(停车场已满,请在便道等候!n);wait(Q,p);return top1;if(top1=NULL)p-next=NULL;top1=p;elsep-next=top1;top1=p;b+;printf(车辆进入停车场成功，时间已经自动载入!n);printf(车牌为%s的汽车驶入时间为:%d号%d点%d分n,

16、top1-data.num,top1-data.time.day,top1-data.time.hour,top1-data.time.min);return top1;/停车费用计算函数int expenses(stacknode *p,int x1,int x2,int x3)int w;if(x3!=0)w=(x1*24+x2+1-(p-data.time.day*24+p-data.time.hour)*price;elsew=(x1*24+x2-(p-data.time.day*24+p-data.time.hour)*price;return w;/车辆驶出出场函数stacknod

17、e *leave(stacknode *top1,char str,LQueue *Q)int i,day,hour,min;time_t rawtime;struct tm *timeinfo;time(&rawtime);timeinfo=localtime(&rawtime);day=timeinfo-tm_mday;hour=timeinfo-tm_hour;min=timeinfo-tm_min;stacknode *p,*q;if(top1=NULL)printf(停车场没有车辆!n);return top1;q=(stacknode *)malloc(sizeof(stackno

18、de);if(p=NULL)printf(内存分配失败);return top1;q=top1;while(q!=NULL)if(strcmp(q-data.num,str)=0)break;q=q-next;if(q=NULL)printf(输入有误，该车辆不在停车场!n);return top1;for(i=top1-data.n;iq-data.n;i-)p=(stacknode *)malloc(sizeof(stacknode);if(p=NULL)printf(内存分配失败);return top1;strcpy(p-data.num,top1-data.num);p-data.t

19、ime=top1-data.time;p-data.n=top1-data.n-1;top1=top1-next;if(top2=NULL)p-next=NULL;top2=p;elsep-next=top2;top2=p;top1=top1-next;while(top2!=NULL)p=(stacknode *)malloc(sizeof(stacknode);if(p=NULL)printf(内存分配失败);return top1;p-data.n=top2-data.n;strcpy(p-data.num,top2-data.num);p-data.time=top2-data.tim

20、e;p-next=top1;top1=p;top2=top2-next;if(EmptyLQue(Q)p=out(Q);p-data.n-;top1=LQinto(p,top1);else b-;printf(车牌为%s的汽车驶出时间为:%d号%d点%d分n,q-data.num,day,hour,min);printf(车辆驶出停车场需要缴纳的费用为:%d元n,expenses(q,day,hour,min);return top1;/队列函数初始化LQueue *InitLQue()LQueue *Q;stacknode *p;Q=(LQueue *)malloc(sizeof(LQueu

21、e);p=(stacknode *)malloc(sizeof(stacknode);p-next=NULL;Q-front=Q-rear=p;return Q;/候车区队列入队LQueue *wait(LQueue *q,stacknode *s)s-next=NULL;q-rear-next=s;q-rear=s;return q;/判断候车便道有无车辆等待int EmptyLQue(LQueue *q)if(q-front=q-rear)return 0;elsereturn 1; /候车区车辆出队stacknode *out(LQueue *q)stacknode *p;p=q-fro

22、nt-next;if(q-front-next=q-rear)q-rear=q-front;return p;elseq-front-next=p-next;p-next=NULL;return p;/候车队列进入停车场stacknode *LQinto(stacknode *p,stacknode *top1)p-next=top1;top1=p;return top1;/显示停车场内所有车辆信息void show(stacknode *top1)printf( 停车场内全部车辆信息表n);if(top1=NULL)printf( 停车场内无车!n);elseprintf(车牌号 进入时间

23、位置n);while(top1!=NULL)printf( %s %d号%d点%d分 第%d位n,top1-data.num,top1-data.time.day,top1-data.time.hour,top1-data.time.min,top1-data.n);top1=top1-next;/显示候车区的汽车信息void T_shou(LQueue *Q)LQueue *q;q=(LQueue *)malloc(sizeof(LQueue);q-rear=Q-rear-next;printf( 候车区信息n);if(q-front=q-rear)printf(候车区没有车辆!n);els

24、eprintf(车牌号 进入时间n);while(q!=NULL)printf(%s %d号%d点%d分,q-data.num,q-data.time.day,q-data.time.hour,q-data.time.min);q-rear=q-rear-next;五、 程序运行结果（采用截图方式给出运行结果）1.2.六、 小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等） 通过本次实验课练习我掌握栈的特点(先进后出FILO)及基本操作，如入栈、出栈等，栈的顺序存储结构和链式存储结构和掌握了队列的特点(先进先出FIFO)及基本操作，如入队、出队等，队列顺序存储结构、链式存储结构和循环队列的实现;在编写程序过程中，可以分开建立函数并对各个函数进行调试来完善程序，将错误尽可能早的查找出来更利于主函数中 对这些函数的调用。