约瑟夫斯问题求解与停车场停车问题

1、计算机软件技术基础2013实验报告I数据结构_031120206_李希文实验一：约瑟夫斯问题求解一、问题描述1、实验题目 约瑟夫斯（Josephus）问题的一种描述是：编号为1，2，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，按出列顺序印出各人编号。2、基本要求利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。3、测试数据n=7，7个人的

2、密码依次为：3，1，7，2，4，8，4。m初值为6（正确的出列顺序应为6，1，4，7，2，3，5）。二、需求分析1、本程序利用循环链表结构模拟出约瑟夫斯问题中在任意人数每人任意编号情况下，各编号的出列顺序2、程序运行后显示提示信息，建立输入处理，输入n输入以及每个人的密码；m的初值。控制输入的n、m及个人密码必为正整数。3、建立一个输出函数，程序自动输出正确的序列。三、概要设计为实现上述功能，用单向循环链表存储结构模拟此过程，因此需要有单向循环链表这一数据结构。1、 定义一个结点类型来储存每个人编号及密码： typedef int ElemType; typedef struct node E

3、lemType mima; int bianhao; struct node *next; SLNODE; 2、单向循环链表抽象数据类型定义： ADT 数据对象：SLNODE类型 数据关系：线性关系 基本操作： SLNODE *initlist();/创建空链表 void createfromRear( SLNODE *head,int n);/尾插法输入循环链表；利用n来控制输入次数 void DelLinkList(SLNODE *p); /* 删除p指针指向结点的后一个结点 */ void xunhuan(SLNODE *head);/循环链表 3、主程序流程及其模块调用关系 1）主函数

4、流程输入起始m调用输出函数，输出出列顺序编号输入n个编号密码输入编号总数n 2）模块调用关系 主程序模块 单向循环链表单元模块：实现单向循环链表的抽象数据类型 单向循环链表单元模块主函数模块 四、详细设计1、单向循环链表结点类型typedef int ElemType;typedef struct nodeElemType mima;int bianhao;struct node *next; SLNODE; 2、实现每个基本操作的伪码 /创建空链表SLNODE *initlist()SLNODE *head;head =(SLNODE *) malloc( sizeof(SLNODE) );

5、head->next = NULL; return head;/尾插法输入循环链表；void createfromRear( SLNODE *head,int n)/注意控制n>0; SLNODE *r, *s; ElemType x;int i=1;/利用i来控制输入次数r = head;cout<<"输入第"<<i<< "个密码"cin>>x; while (x>0&&i<=n) s =(SLNODE*) malloc( sizeof(SLNODE) ); s-&

6、gt;mima =x;s->bianhao=i; r->next =s;r=s; /*r永远指向链表的最后一个结点*/ r->next =NULL; i+;if(i<=n)/控制输入提示语句出现个数cout<<"输入第"<<i<< "个密码" cin>>x; /循环链表void xunhuan(SLNODE *head)SLNODE *r;r=head;while(r->next!=NULL)r=r->next;r->next=head;/删除函数；void Del

7、LinkList(SLNODE *p) /* 删除p指针指向结点的后一个结点 */ SLNODE *q; if(p->next !=NULL) q=p->next ; /* q指向p的后继结点 */ p->next=q->next; /* 修改p结点的指针域 */ free(q); /* 删除并释放结点 */ 3、主函数伪码int main()cout<<"实验名称：实验一.约瑟夫斯求解问题"<<endl;cout<<"学号：031120206"<<endl;cout<<

8、"姓名：李希文"<<endl;cout<<"程序运行开始，"time_t rawtime; struct tm * timeinfo; time (&rawtime); timeinfo = localtime (&rawtime); printf ("Current local time and date: %s", asctime(timeinfo); SLNODE *head=NULL;head=initlist(); int n,m; do/控制n>0;cout<<&q

9、uot;输入编号总数n"cin>>n;while(n<=0);cout<<"输入编号密码"<<endl;createfromRear(head,n);xunhuan(head);do/控制m>0; cout<<"输入起始m"cin>>m;while(m<=0);cout<<"输出出列顺序编号"shuchu(head,m);cout<<endl;cout<<"程序运行结束，" printf (&

10、quot;Current local time and date: %s", asctime(timeinfo); system("PAUSE"); return 0;4、输出模块的伪码/输出出列顺序编号函数；void shuchu(SLNODE *head,int m) SLNODE *r=head;int j=m,i;while(j>0 && head->next!=head)/控制不再空链表时操作 i=1;/重新计数while(i<j)if(r->next=head)/循环时略过头结点 r=r->next;r=r

11、->next;i+;if(r->next=head)/循环时略过头结点r=r->next;j=r->next->mima;cout<<r->next->bianhao<<" "DelLinkList(r);/删除第m个结点4、函数调用关系图SLNODE *initlist();/创建空链表函数 void createfromRear( SLNODE *head,int n);/尾插法输入循环链表；利用n来控制输入次数 createfromRear( SLNODE *head,int n);/尾插法输入循环链表

12、；利用n来控制输入次数主函数void DelLinkList(SLNODE *p); /* 删除p指针指向结点的后一个结点 */void xunhuan(SLNODE *head);/循环链表 void shuchu(SLNODE *head,int m)/输出出列顺序编号函数；五、调试分析实验遇到的问题以及解决的办法 1）调试无问题，运行时出现了如图的问题经检查：在链表插入函数中插入了新结点后少了r->next=NULL;这一步，致使存储空间无法使用。故无法运行。再添加了该步骤后，以解决。 2）结果显示正确，但其后出现了一大串奇怪字符 经检查：在输出函数中忘记控制空链表结束循环，致使该

13、程序无止境循环。加入控制空链表后问题解决。六、使用说明程序运行后用户根据提示输入编号总数n、n个编号密码以及起始m，如输入数字不合要求，程序会要求用户重复输出。程序将自动调用输出函数，输出出列顺序编号。七、调试结果n=7，7个人的密码依次为：3，1，7，2，4，8，4。m初值为6（正确的出列顺序应为6，1，4，7，2，3，5）。八、实验的收获 在该试验中不仅强化了链表知识，还进一步学习并尝试要运用了循环链表。书本知识的学习与实际操作是截然不同的，有可能较熟的知识在编写程序时只因为一个符号而不能运行。编写代码十分考验耐心与细心。九、附录源程序清单#include <iostream>

14、#include <stdio.h> /* puts, printf */#include <time.h> /* time_t, struct tm, time, localtime */using namespace std;/链表的存储结构；typedef int ElemType;typedef struct nodeElemType mima;int bianhao;struct node *next; SLNODE; SLNODE *initlist();/创建空链表void createfromRear( SLNODE *head,int n);/尾插法输

15、入循环链表；利用n来控制输入次数void DelLinkList(SLNODE *p); /* 删除p指针指向结点的后一个结点 */void shuchu(SLNODE *head,int m);/输出出列顺序编号；void xunhuan(SLNODE *head);/循环链表/头函数；int main()cout<<"实验名称：实验一.约瑟夫斯求解问题"<<endl;cout<<"学号：031120206"<<endl;cout<<"姓名：李希文"<<endl

16、;cout<<"程序运行开始，"time_t rawtime; struct tm * timeinfo; time (&rawtime); timeinfo = localtime (&rawtime); printf ("Current local time and date: %s", asctime(timeinfo); SLNODE *head=NULL;head=initlist(); int n,m; do/控制n>0;cout<<"输入编号总数n"cin>>n;

17、while(n<=0);cout<<"输入编号密码"<<endl;createfromRear(head,n);xunhuan(head);do/控制m>0; cout<<"输入起始m"cin>>m;while(m<=0);cout<<"输出出列顺序编号"shuchu(head,m);cout<<endl;cout<<"程序运行结束，" printf ("Current local time and da

18、te: %s", asctime(timeinfo); system("PAUSE"); return 0;/输出出列顺序编号函数；void shuchu(SLNODE *head,int m) SLNODE *r=head;int j=m,i;while(j>0 && head->next!=head)/控制不再空链表时操作 i=1;/重新计数while(i<j)if(r->next=head)/循环时略过头结点 r=r->next;r=r->next;i+;if(r->next=head)/循环时略过头

19、结点r=r->next;j=r->next->mima;cout<<r->next->bianhao<<" "DelLinkList(r);/删除第m个结点/创建空链表SLNODE *initlist()SLNODE *head;head =(SLNODE *) malloc( sizeof(SLNODE) );head->next = NULL; return head;/尾插法输入循环链表；void createfromRear( SLNODE *head,int n)/注意控制n>0; SLNODE *

20、r, *s; ElemType x;int i=1;/利用i来控制输入次数r = head;cout<<"输入第"<<i<< "个密码"cin>>x; while (x>0&&i<=n) s =(SLNODE*) malloc( sizeof(SLNODE) ); s->mima =x;s->bianhao=i; r->next =s;r=s; /*r永远指向链表的最后一个结点*/ r->next =NULL; i+;if(i<=n)/控制输入提示语

21、句出现个数cout<<"输入第"<<i<< "个密码" cin>>x; /循环链表void xunhuan(SLNODE *head)SLNODE *r;r=head;while(r->next!=NULL)r=r->next;r->next=head;/删除函数；void DelLinkList(SLNODE *p) /* 删除p指针指向结点的后一个结点 */ SLNODE *q; if(p->next !=NULL) q=p->next ; /* q指向p的后继结点 */

22、p->next=q->next; /* 修改p结点的指针域 */ free(q); /* 删除并释放结点 */ 实验二、一、问题描述 1、实验题目 设停车场是一个可停放 n 辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端）。若停车场内已经停满 n辆车，那么后来的车只能在门外的便道上等候。一旦有车开走，则排在便道上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场。每辆停放在车场的车在它离开停车

23、场时必须按它停留的时间长短缴纳费用。试为停车场编制按上述要求进行管理的模拟程序。 2、基本要求 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入数据的序列进行模拟管理。每一组输入数据包括三个数据项：汽车的“到达”（A表示）或“离去”（D表示）信息、汽车标识（牌照号）以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或者便道上的停车位置；若是车辆离去，则输出汽车在停车场停留的时间和应缴纳的费用（便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。 3、测试数据设n=2,输入数据为：（A，1，5），（A，2，10），（D，1，15），

24、（A，3， 20），（A，4，25），（A，5，30），（D，2，35），（D，4，40），（E，0，0）。每一组输入数据包括三个数据项：汽车 “到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，A表示到达；D表示离去，E表示输入结束。其中：（A，1，5）表示1号牌照车在5这个时刻到达，而（D，1，15）表示1号牌照车在15这个时刻离去。二、需求分析 1、本程序模拟出车辆在停车场根据到达时间决定停车位置，对空车位动态补充，车辆离去时计算出在停车场停留的时间和应缴纳的费用。 2、输入数据：程序接受5个命令，分别是：到达（A,车牌号,时间)；离去(D,车牌号,时间)；停车场（P, 0,

25、0）显示停车场的车数；候车场（W, 0, 0）显示候车场的车数；退出（E, 0, 0）退出程序。 3、输出数据：对于车辆到达，要输出汽车在停车场内或者便道上的停车位置；对于车辆离去，则输出汽车在停车场停留的时间和应缴纳的费用（便道上不收费）。3、 概要设计为了实现上述功能，应以两个顺序栈来分别表示停车场（A）与临时停放点（B)，以链式队列(C)来表示便道。故此需要顺序栈与链式队列两个抽象数据类型。1、定义ElemType类型 typedef struct Data /每辆车的信息结构体 int license;/车牌号码int arrivetime;/到达时间ElemType;2、顺序栈抽象数

26、据类型 ADT SeqStack 数据对象：ElemType类型 数据关系：线性关系 基本操作： SeqStack *Init_SeqStack ( );/置空栈 bool push(SeqStack *s,ElemType x,int n );/入栈1 bool Pop(SeqStack *s,ElemType &x);/出栈 3、链式队列两个抽象数据类型 ADT LinkQueue 数据对象：ElemType类型 数据关系：线性关系 基本操作： LinkQueue *Init_LQueen();/创建空对； void In_LQueen(LinkQueue *q,ElemType

27、&x);/入队 bool Out_LQueen(LinkQueue *q,ElemType &x);/出对 int length(LinkQueue *q);/队的长度 程序循环 4、主函数流程输入命令：到达（A,车牌号,时间)；离去(D,车牌号,时间)；（P, 0, 0）显示停车场的车数；候车场（W, 0, 0）；退出（E, 0, 0） 结束程序调用函数显示输出根据提示输入 n 5、模块调用关系 主程序模块 顺序栈单元模块：实现顺序存储方式实现的栈的抽象数据类型 链式队列单元模块：实现链式存储的队列的抽象数据类型顺序栈单元模块主程序模块链式队列单元模块四、详细设计1、定义El

28、emType类型typedef struct Data /每辆车的信息结构体 int license;/车牌号码int arrivetime;/到达时间ElemType;2、实现顺序栈的每步基本操作定义顺序栈；#define MaxSize 1024typedef struct stack ElemType dataMaxSize;/*用一维数组存放自栈底到栈顶的Data类型*/ int top; /*附设一个位置指针top*/SeqStack;/置空栈SeqStack *Init_SeqStack ( )SeqStack *s;s=(SeqStack *)malloc(sizeof(SeqS

29、tack);s->top=-1;return s;/入栈bool push(SeqStack *s,ElemType x,int n ) if(s->top=n-1)return false; else s->top+;s->datas->top=x;return true; /出栈 bool Pop(SeqStack *s,ElemType &x)if(s->top=-1)return false;elsex=s->datas->top;s->top-;return true;3、 实现链式队列的每步基本操作 /链式队列结点 Ty

30、pedef struct Node ElemType data; struct Node *next; QNODE; /创建空对； LinkQueue *Init_LQueen() LinkQueue *q; QNODE *p; q=(LinkQueue *)malloc(sizeof(LinkQueue);/申请头尾结点 p=(QNODE *)malloc(sizeof(QNODE);/申请链队头结点 p->next=NULL; q->front=q->rear=p; return q; /入队 void In_LQueen(LinkQueue *q,ElemType &a

31、mp;x) QNODE * p; p=(QNODE *)malloc(sizeof(QNODE);/申请新结点 p->data=x; p->next=NULL; q->rear->next=p; q->rear=p; /出队 bool Out_LQueen(LinkQueue *q,ElemType &x) QNODE * p; if(q->front=q->rear) cout<<"队空" return false; else p=q->front->next; q->front->ne

32、xt=p->next; x=p->data; free(p); if(q->front->next=NULL)/只有一个元素时，出栈后队为空 q->front=q->rear;/此时还要修改队尾指针，因为其指向空 return true; /队长 int length(LinkQueue *q) QNODE * p=q->front; int m; for(m=0;p!=q->rear;m+) p=p->next; return m; 4、 主函数 int main()cout<<"实验名称：实验二：停车场管理问题&q

33、uot;<<endl;cout<<"学号：031120206"<<endl;cout<<"姓名：李希文"<<endl;cout<<"程序运行开始，"time_t rawtime; struct tm * timeinfo; time (&rawtime); timeinfo = localtime (&rawtime); printf ("Current local time and date: %s", asctime(tim

34、einfo); SeqStack *A=Init_SeqStack ( ),*B=Init_SeqStack ( ); LinkQueue *C=Init_LQueen(); char order; int License;/车牌号码int Arrivetime,Leavetime; int n; cout<<"输入停车场最大停车数n" cin>>n; while(1) cout<<" A: 到底 D：离去 P：停车场停车数 W: 候车场车数 E:退出程序"<<endl; cout<<"

35、;请输入指令:" cin>>order; switch(order) case 'A': ElemType z; cout<<"输入车牌号：" cin>>License;/车牌号码 z.license=License; cout<<"输入到达时间" cin>>Arrivetime; z.arrivetime=Arrivetime; if(push(A,z,n) cout<<"成功放入停车场！" else In_LQueen(C,z); c

36、out<<"放入便道！" break; case 'D': ElemType y; cout<<"输入车牌号：" cin>>License;/车牌号码 cout<<"输入离去时间" cin>>Leavetime; while(A->dataA->top).license!=License && A->top!=-1)/将停车场A中的车放入B中 if(Pop(A,y) push(B,y,n); if(A->top!=-1)

37、/车停在停车场上 cout<<"停留时间"<<Leavetime-(A->dataA->top).arrivetime<<endl; cout<<"停车费用：￥ "<<2*(Leavetime-(A->dataA->top).arrivetime)<<endl; A->top-; else cout<<"车停在便道上，不收费用！" while(B->top!=-1 && B->top<=1

38、)/栈B的大小虽然不限，但最多有两辆车 if(Pop(B,y) push(A,y,n);/把B中车返回A中； if(A->top<1&&length(C)!=0) while(A->top!=1&&length(C)!=0)/停车场A中未满，便道C中未空时 ，将便道中车放入停车场； Out_LQueen(C,y); y.arrivetime=Leavetime;/便道上车费计算从停入停车场开始，而非到达时间！ push(A,y,n); break; case 'P': cout<<"停车场有"&l

39、t;<(A->top)+1<<"辆车" break; case 'W': cout<<"便道上有"<<length(C)<<"辆车" break; case 'E': printf ("Current local time and date: %s", asctime(timeinfo); return 0; system("PAUSE"); exit(0); 5、函数调用关系停车场仍有空余，入栈成功pu

40、sh(A,z,n) 车辆进入A停车场已满，入栈失败，入队列In_LQueen(C,z)后来车辆从停车场进入临时栈Pop(A,y)；push(B,y,n) 该车离开主函数推出程序E求便道上停车数：length(C)求停车场停车数P：(A->top)+1若停车场有空位，便道车入栈Out_LQueen(C,y) ；push(A,y,n);车辆离开D让道车从临时栈回停车场Pop(B,y)；push(A,y,n)五、调试分析实验遇到的问题以及解决的办法：实验中发现初始停在便道上后进入停车场的车输出的停车费用总是比（在停车场停留时间*单价）要大。经检查，当停车场中有车开出，临时栈中车回到停车场后，若

41、停车场有空位，便道上的车进入停车场后，费用起始时间应从这时算起。Out_LQueen(C,y);y.arrivetime=Leavetime;/便道上车费计算从停入停车场开始，而非到达时间！push(A,y,n);故要加中间一行程序修正起始时间，问题解决。六、使用说明程序运行后用户根据提示输入停车场车位总数n，然后根据提示输入命令输入命令：到达（A,车牌号,时间)；离去(D,车牌号,时间)；（P, 0, 0）显示停车场的车数；候车场（W, 0, 0）；退出（E, 0, 0）。如输入字符不合要求，程序会要求用户重复输出。程序将自动调用输出函数，输出停车地点或应付费用。输入退出（E, 0, 0）命

42、令，则程序结束。七、调试结果 八、实验的收获 程序中时常影藏着细小的错误，在修正时要将代码运行过程及结果在头脑里过一遍，这比较费脑力，但也锻炼了发现问题以及解决问题的能力，增长了经验。例如出现结果后一大串奇怪字符，根据以往经验，可以较快判断是因为没控制运行何时结束，可以在以后发生类似错误时更快找到问题所在。九、附录源程序清单#include <iostream>#include <stdio.h> /* puts, printf */#include <time.h> /* time_t, struct tm, time, localtime */using

43、 namespace std;typedef struct Data /每辆车的信息结构体 int license;/车牌号码int arrivetime;/到达时间ElemType;/定义顺序栈；#define MaxSize 1024typedef struct stack ElemType dataMaxSize;/*用一维数组存放自栈底到栈顶的Data类型*/ int top; /*附设一个位置指针top*/SeqStack;/链式队列结点typedef struct Node ElemType data; struct Node *next;QNODE;/将头尾指针封装在一起 typ

44、edef struct linkQQNODE *front; QNODE *rear;LinkQueue;SeqStack *Init_SeqStack ( );/置空栈bool push(SeqStack *s,ElemType x,int n );/入栈1bool Pop(SeqStack *s,ElemType &x);/出栈LinkQueue *Init_LQueen();/创建空对； void In_LQueen(LinkQueue *q,ElemType &x);/入队 bool Out_LQueen(LinkQueue *q,ElemType &x);/出

45、对 int length(LinkQueue *q);/队的长度 int main()cout<<"实验名称：实验二：停车场管理问题"<<endl;cout<<"学号：031120206"<<endl;cout<<"姓名：李希文"<<endl;cout<<"程序运行开始，"time_t rawtime; struct tm * timeinfo; time (&rawtime); timeinfo = localtime (

46、&rawtime); printf ("Current local time and date: %s", asctime(timeinfo); SeqStack *A=Init_SeqStack ( ),*B=Init_SeqStack ( ); LinkQueue *C=Init_LQueen(); char order; int License;/车牌号码int Arrivetime,Leavetime; int n; cout<<"输入停车场最大停车数n" cin>>n; while(1) cout<<" A: 到底 D：离去 P：停车场停车数 W: 候车场车数 E:退出程序"<<endl; cout<<"请输入指令:" cin>>order; switch(order)