数据结构课程设计报告-约瑟夫环+停车场管理.doc

数据结构课程设计报告题目一：约瑟夫环题目二：停车场管理班级：计算机科学与技术系1班姓名：学号： 指导教师： 完成日期：题目一： 约瑟夫环一、问题描述：约瑟夫问题的一种描述是：编号为1，2，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将它的密码作为新的m值，从它的顺时针方向的下一个人开始重新从1报数，如此下去，直至全部人出列为止。最后按照出列的顺序印出各人的编号。二、数据结构：其主要的数据类型为无头结点的单向循环链表，如下： typedef struct Nodeint data; /存储人数int password; /存储的每人所对应的密码struct Node *next;Node, *LinkList;三、大致的程序流程：1. 函数之间的调用关系图： mainPersonNumber FirstValue CreatLinkList InitLinkList OutputOrder printResult Password2.主要模块的流程图： 开始输出界面输入人数目输入初始上限值输入第1人密码 输入第n人密码退出系统 结束3主程序A）以下两个函数作用是构建并初始化一个单循环链表，初始化时将链表*L赋值给链表*q,（*q）为头指针，并赋值pdata为第一人的编号，赋值ppassword为此人对应的密码。再通过for（）循环，以链表q为过渡，依次给pnext赋值q。最后令pnext等于链表L的头指针(*L)。void CreatLinkList(LinkList *L)/*构建单链表*/(*L) = (LinkList)malloc(sizeof(Node);if (*L) = NULL)printf(memory allocation failed);exit(1);void InitLinkList(LinkList *L, int personNumber)/*初始化单链表*/Node *p, *q;int i ;p = (*L);p-data = 1;p-password = Password();for (i = 2; i password = Password();q-data = i;p-next = q;p = q;p-next = (*L); B）以下三个函数的作用分别是确定输入人数，确定每人密码，确定开始的上限制。他们都是通过库函数scanf（）来接受用户输入的数据，并且数据类行为整型（int）。其中用户输入的人数必须在0MAXPERSONNUMBER之间，密码必须在0MAXPASSWORDVALUE之间 ，开始查找的上限值必须在0MAXFIRSTVALUE之间。如果用户输入数值大于上限值或小于0，则返回重新输入。此过程是通过while（）函数实现的。如果while运行说明输入数据不合要求，重新输入。/*确定需要处理的人数*/int PersonNumber()int personNumber;printf(请输入需要输入人的数目:);scanf(%d,&personNumber);while (personNumber MAXPERSONNUMBER | personNumber MAXPASSWORDVALUE | password MAXFIRSTVALUE | firstValue data即为保数到reportvalue时所对应的人的编号，将其赋值到数组array，并将此人对应的密码赋值给reportValue，令q的下一个指针指向pnext用来保存pnext的位置之后，释放p的存储空间，再令p指向qnext，得到被输出编号下一个编号的存储位置。之后人数减1，继续while (personNumber)循环，直到personNumber0返回array 。/*得到出队顺序*/void OutputOrder(LinkList *L, int personNumber, int reportValue, int arrayMAXPERSONNUMBER)Node *p, *q;int count = 1, i = 0;p = (*L);while (personNumber)while (count != reportValue)q = p;p = p-next;count+;arrayi+ = p -data;reportValue = p-password;q-next = p-next;free(p);p = q-next;count = 1;personNumber-; D）此函数功能就是在主函数调用时通过for（）循环打印出数组array 的值。/*输出结果*/void printResult(int array,int personNumer)int i;printf(n出队的顺序为:);for(i = 0; i data = 1;p-password = GetPassword();for (i = 2; i password = GetPassword();q-data = i;p-next = q;p = q;p-next = (*L);/*确定需要处理的人数*/int GetPersonNumber()int personNumber;printf(请输入需要输入人的数目:);scanf(%d,&personNumber);while (personNumber MAXPERSONNUMBER | personNumber MAXPASSWORDVALUE | password MAXFIRSTVALUE | firstValue next;count+;arrayi+ = p -data;reportValue = p-password;q-next = p-next;free(p);p = q-next;count = 1;personNumber-;/*输出结果*/void printResult(int array,int personNumer)int i;printf(n出队的顺序为:);for(i = 0; i top=0; for(i=0;istacks-top=NULL; /*初始化便道*/int InitQueue(LinkQueueCar *Q) Q-head=(QueueNode *)malloc(sizeof(QueueNode); if(Q-head!=NULL) Q-head-next=NULL; Q-rear=Q-head; return(1); else return(-1); B）此函数主要起到显示出站车信息的作用。包括显示车进入停车场的时间，出车场的时间，车牌号，和应收取的费用。公式(B1-A1)*60+(B2-A2)*price用来计算费用，price为0.1元，单位为每分钟。/*打印出站车的信息*/void PRINT(CarNode *p,int room) int A1,A2,B1,B2; printf(nplease input thedepart time:/*:*/); scanf(%d:%d,&(p-leave.hour),&(p-leave.min); printf(nthe number of the car:); puts(p-num); printf(nthe time the car arrive: %d:%d,p-reach.hour,p-reach.min); printf(the depart time: %d:%d,p-leave.hour,p-leave.min); A1=p-reach.hour; A2=p-reach.min; B1=p-leave.hour; B2=p-leave.min; printf(nthe fee: %2.1f元,(B1-A1)*60+(B2-A2)*price); free(p); C）此函数实现的功能是实现汽车进停车场的操作。第一步操作是确定要进停车场车的车牌号，然后通过函数if(Enter-topreach.hour,p-reach.min存储。若车场已满则进入便道，由队列实现。/*车辆到达*/int Arrival(SeqStackCar *Enter,LinkQueueCar *W) CarNode *p; QueueNode *t; p=(CarNode *)malloc(sizeof(CarNode); flushall(); printf(ninput the number of the car(例:1234):); gets(p-num); if(Enter-toptop+; printf( nthe place of the car: %d ,Enter-top); printf(nthe time thecar arrive:/*:*/); scanf(%d:%d,&(p-reach.hour),&(p-reach.min); Enter-stackEnter-top=p; return(1); else /*车场已满，车进便道*/ printf(n该车须在便道等待.); t=(QueueNode *)malloc(sizeof(QueueNode); t-data=p; t-next=NULL; W-rear-next=t; W-rear=t; return(1); D）此函数实现的功能是实现车出停车场时的操作。包括显示车的位置，车进、出停车场的时间，得出应交纳的费用。然后便道上等候的车进入停车场。通过函数if(Enter-top0)来判断栈是否为空，如不为空，则执行if（）函数。之后第一个while（1）函数的作用是确定出停车场车的位置。第二个while(Enter-toproom)函数作用是令存储在栈内选定位置上方的数据存入临时栈Temp，令选定位置处于栈的顶端。之后取出栈顶元素。取出之后再用第三个while(Temp-top=1)函数将临时栈Temp中数据依次返回停车场栈中。之后当停车场中留出空位，执行函数if(W-head!=W-rear)&Enter-toptop0) /*有车*/ while(1) /*输入离开车辆的信息*/ printf(n请输入车在车场的位置/1-%d/：,Enter-top); scanf(%d,&room); if(room=1&roomtop) break; while(Enter-toproom) /*车辆离开*/ Temp-top+; Temp-stackTemp-top=Enter-stackEnter-top; Enter-stackEnter-top=NULL; Enter-top-; p=Enter-stackEnter-top; Enter-stackEnter-top=NULL; Enter-top-; while(Temp-top=1) Enter-top+; Enter-stackEnter-top=Temp-stackTemp-top; Temp-stackTemp-top=NULL; Temp-top-; PRINT(p,room); /*判断通道上是否有车及车站是否已满*/ if(W-head!=W-rear)&Enter-tophead-next; t=q-data; Enter-top+; printf(n便道的%s号车进入车场第%d位置.,t-num,Enter-top); printf(n请输入现在的时间/*:*/:); scanf(%d:%d,&(t-reach.hour),&(t-reach.min); W-head-next=q-next; if(q=W-rear) W-rear=W-head; Enter-stackEnter-top=t; free(q); else printf(n便道里没有车.n); else printf(n车场里没有车.); /*没车*/ E）主函数实现了用户界面。并通过调用各自定义函数，实现了停车场管理系统的模拟。void main() SeqStackCar Enter,Temp; LinkQueueCar Wait; int ch; InitStack(&Enter); /*初始化停车场*/ InitStack(&Temp); /*初始化让路的临时栈*/ InitQueue(&Wait); /*初始化通道*/ while(1) printf(n*);printf(n 1. the car arrive); printf( 2. the car leave); printf( 3. quitn); printf(*n); while(1) scanf(%d,&ch); if(ch=1&ch=4)break; else printf(nplease choose： 1|2|3); switch(ch) case 1:Arrival(&Enter,&Wait);break; /*车辆到达*/ case 2:Leave(&Enter,&Temp,&Wait);break; /*车辆离开*/ case 3:exit(0); /*退出程序*/ default: break; 四、调试分析此程序输入输出的数据都为整型（int）。线程控制，使程序达到参数即时可控，同时提高程序的健壮性。上机过程中遇到过一些错误，主要是语法错误经过我的再三排查终于改正了错误。程序功能：模拟停车场管理系统，一狭长结构停车场，一次只允许一辆车进出。当停车场未满时，车进停车场，当满时，车进便道。当停车场内某辆车要离开时，在它之后进入的车必须先退出车场为他让路，待该车开出大门外，其他车再按原次序进入车场，每辆停放在车场的车在它离开车场时必须按它停留的时间长短交纳费用。五、用户手册 1 输入进站车信息，界面：2输入出站信息，界面：3便道车入站，界面：六测试结果第一组：输入数据：1 车牌号：1234 到达时间12：12 2 离开车位置：1 离开时间 12：34输出数据：出站车牌号 1234 到达时间 12：12 离开时间：12：34 收费：4.4元第二组：输入数据：1 车牌号：1234 到达时间 12：12 输入数据：1 车牌号：1122 到达时间 13：01 2 离开车位置：1 离开时间 14：00输出数据：出站车牌号 1234 到达时间 12：12 离开时间：14：00 收费：10.08元七、附录停车场管理源代码：#include #include #include #define MAX 2 /*车库容量*/ #define price 0.1 /*每车每分钟费用*/*-定义数据类型-*/ /*时间结点*/ typedef struct time int hour; int min; Time; /*车辆信息结点*/typedef struct node char num10; Time reach; Time leave; CarNode; /*模拟车站*/typedef struct NODE CarNode *stackMAX+1; int top; SeqStackCar; /*车道结点*/typedef struct car CarNode *data; struct car *next; QueueNode; /*模拟通道*/ typedef struct Node QueueNode *head; QueueNode *rear; LinkQueueCar; /*-预定义函数-*/ void InitStack(SeqStackCar *); /*初始化栈*/ int InitQueue(LinkQueueCar *); /*初始化便道*/ int Arrival(SeqStackCar *,LinkQueueCar *); /*车辆到达*/ void Leave(SeqStackCar *,SeqStackCar *,LinkQueueCar *); /*车辆离开*/ /*-自定义函数-*/ /*初始化栈*/void InitStack(SeqStackCar *s) int i; s-top=0; for(i=0;istacks-top=NULL; /*初始化便道*/int InitQueue(LinkQueueCar *Q) Q-head=(QueueNode *)malloc(sizeof(QueueNode); if(Q-head!=NULL) Q-head-next=NULL; Q-rear=Q-head; return(1); else return(-1); /*打印出站车的信息*/void PRINT(CarNode *p,int room) int A1,A2,B1,B2; printf(nplease input thedepart time:/*:*/); scanf(%d:%d,&(p-leave.hour),&(p-leave.min); printf(nthe number of the car:); puts(p-num); printf(nthe time the car arrive: %d:%d,p-reach.hour,p-reach.min); printf(the depart time: %d:%d,p-leave.hour,p-leave.min); A1=p-reach.hour; A2=p-reach.min; B1=p-leave.hour; B2=p-leave.min; printf(nthe fee: %2.1f元,(B1-A1)*60+(B2-A2)*price); free(p); /*车辆到达*/int Arrival(SeqStackCar *Enter,LinkQueueCar *W) CarNode *p; QueueNode *t; p=(CarNode *)malloc(sizeof(CarNode); flushall(); printf(ninput the number of the car(例:1234):); gets(p-num); if(Enter-toptop+; printf( nthe place of the car: %d ,Enter-top); printf(nthe time thecar arrive:/*:*/); scanf(%d:%d,&(p-reach.hour),&(p-reach.min); Enter-stackEnter-top=p; return(1); else /*车场已满，车进便道*/ printf(n该车须在便道等待.); t=(QueueNode *)malloc(sizeof(QueueNode); t-data=p; t-next=NULL; W-rear-next=t; W-rear=t; return(1); /*车辆离开*/void Leave(SeqStackCar *Enter,SeqStackCar *Temp,LinkQueueCar *W) int room; CarNode *p,*t; QueueNode *q; /*判断车场内是否有车*/ if(Enter-top0) /*有车*/ while(1) /*输入离开车辆的信息*/ printf(n请输入车在车场的位置/1-%d/：,Enter-top); scanf(%d,&room); if(room=1&roomtop) break; while(Enter-toproom) /*车辆离开*/ Temp-top+; Temp-stackTemp-top=Enter-stackEnter-top; Enter-stackEnter-top=NULL; Enter-top-; p=Enter-stackEnter-top; Enter-stackEnter-top=NULL; Enter-top-; while(Temp-top=1) E