南航-计算机实践报告--数据结构

《计算机实践》实验报告I—数据结构班号：0315206学号：031520629姓名：陈叶杭Email：[e-mail]签名：南京航空航天大学2017年11月1日目录实验一：约瑟夫斯问题求解………………………….3实验二：停车场管理问题…………………………….10实验三：管道铺设施工的最佳方案问题...................23实验四：内部排序算法的实现与比较………………32实验一：约瑟夫斯问题求解对象：编号为1,2，···，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为上报上线值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出个人的编号。测试数据：n=7，7个人的密码依次为：3，1，7，2，4，8，4。m初值为6（正确的出列顺序应为6,1,4,7,2,3,5）1.单向循环链表抽象数据类型定义：structnode{inttop;intnum;structnode*next;};typedefstructnodeNODE;基本操作：structnode*create_sl(intn);//创建单向循环链表2.主程序流程及其模块调用关系1)创建循环列表流程图：a=1a=nscanf(%d,&x)s-data=x;s-num=a;head-next==headhead=sp-next=s;p=s;p-next=head;YNNY结束开始2）约瑟夫斯问题求解流程图p=head;i=1p-next!=pimm=p-data;q=p;i++p=p-next;q-next=p-next;p=q-next;输出p-numYNNY结束开始3）主函数流程图初始界面显示输入n,m以及密码值结束开始调用create_sl调用Josephus主程序：#includestdio.h#includemalloc.h#includestdlib.h#includetime.htypedefintElemType;typedefstructnode{ElemTypedata;ElemTypenum;structnode*next;}SLNODE;//单链表的定义structnode*create_sl(intn);voidJosephus(SLNODE*head,intn,intm);intmain()//主函数{SLNODE*head;intn,m;time_trawtime;structtm*timeinfo;time(&rawtime);timeinfo=localtime(&rawtime);head=(SLNODE*)malloc(sizeof(SLNODE));printf(实验名称：试验一：约瑟夫斯问题求解\n);//初始界面printf(学号：031520629\n);printf(姓名：陈叶杭\n);printf(/-------------------/\n);printf(程序运行开始，Currentlocaltimeanddate:%s,asctime(timeinfo));printf(请输入总人数n=\n);scanf(%d,&n);printf(请输入报数上限值（为正整数）m=\n);scanf(%d,&m);head=create_sl(n);//创建单链表Josephus(head,n,m);time(&rawtime);timeinfo=localtime(&rawtime);printf(程序运行结束，Currentlocaltimeanddate:%s,asctime(timeinfo));return0;}structnode*create_sl(intn){SLNODE*p,*s,*head;ElemTypex;inta;head=(SLNODE*)malloc(sizeof(SLNODE));p=head;head-next=head;for(a=1;a=n;a++)//循环直到输入n个密码值跳出循环{s=(SLNODE*)malloc(sizeof(SLNODE));printf(请输入第%d个人的密码值\n,a);scanf(%d,&x);s-data=x;s-num=a;if(head-next==head)head=s;elsep-next=s;p=s;}p-next=head;returnhead;}voidJosephus(SLNODE*head,intn,intm)//约瑟夫斯问题求解{SLNODE*p,*q;inti;p=head;printf(出列序列:);while(p-next!=p){for(i=1;im;i++)//程序运行到第m个人跳出循环{q=p;p=p-next;}m=p-data;//读取新的密码值printf(%4d,p-num);q-next=p-next;//删除p节点free(p);p=q-next;}printf(%4d\n,p-num);}运行结果：实验调试和感想开始先去搜索程序开始和结束时间代码，发现有错误，一直以为是格式错了，后来反复查验后发现是开始没有调用时间函数。主程序调试时，开始有一个错误，也是再找原因，后来仔细检查后，发现是链表定义错误，定义成循环链表，应该是用单链表做。后来改过来后就没错了。由于是第一次做数据结构的实验，而上学期的C++也因长时间没有碰过而稍显手生，在码程序的过程中遇到了很多问题，但通过翻看教材已基本解决。约瑟夫虽然构思起来比较简单，但实际执行时经常出现各种意想不到的问题，如输出次数不对等等，通过将近两天的调试才终于完成，很有成就感。接下来如果有时间可以在原程序中加入其实位置编号，使得起始位置也可由用户自定。实验二：停车场管理问题对象：设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列。若停车场内已经停满n辆车，那么后来的车只能在门外的便车道上等候。一旦有车开走，则排在便道上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后进入的车辆必须退出车场为它开路，待该辆车开出大门外，其他车辆再按原次序进入车场。每辆停放在车场的车在它离开停车场时必须按照它停留的时间长短缴纳费用。试为停车场编制按上述要求进行管理的模拟程序。基本要求：以栈模拟停车场，以队列模拟车场外的便道，按照终端读入数据的序列进行模拟管理。每一组输入数据包括三个数据项：汽车的“到达”（‘A’表示）或“离去”（‘D’表示）信息、汽车标识（车牌号）以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或者便道上的停车位置；若是要离去，则输出汽车在停车场停留的时间和应缴纳的费用（便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。测试数据：设n=2,输入数据为：（‘A’，1,5）,（‘A’，2,10），（‘D’，1,5），（‘A’，3,20），（‘A’，4,25），（‘A’，5,30），（‘D’，2,35），（‘D’，4,40），（‘E’，0,0）。主程序模块：开始初始界面显示输入停车场最大容量n输入车辆信息car.AL=='A'car.AL=='D'car.AL='P'，car.NO=0，car.time=0car.AL='W'，car.NO=0，car.time=0car.AL!='E'栈满进入队列输出车辆在便道的位置入栈，输出车辆在停车场的位置出栈，输出车辆停留时间队列为空进栈，车辆从便道进入停车场显示停车场的车数显示候车场的车数输入结束结束输入车辆信息NYYYYYNNNN出栈：开始找到车牌号为P.NO的车，驶出停车场计算停留时间输出候车场为空候车场驶入停车场结束NY判断栈是否为空：开始s-top==-1栈空返回1栈不为空返回0结束YN判断栈是否已满：开始s-top=n-1栈满返回1栈不满返回0结束NY判断队列是否为空：开始q-front==q-rear队列空返回1队列不为空返回0结束NY出队：开始q-front-next==NULLq-rear=q-front;结束NYp=q-front-next;q-front-next=p-next;q-num--;运行结果：实验调试和感想关于算法，题中解析说的已经很清楚了，主要是编程时用到了一些数据结构需要用单独的类定义出来，使得程序清晰完整。这一问题一个重要的思路是对于汽车出停车场时，由于不一定每次都是最外面的车出去，所以需要用到另一个栈存储车辆。如图，将要出停车场的车i上面的车都倒入另一个栈中，然后将i删除，再将栈Park2中的都倒回停车场park1中即可。对于数据的输出：输入A：输出在停车场或者候车场的位置，编号由北向南1~2；输入D：输出车辆停靠时间（出栈时间减去入栈时间）（这里涉及到一个计算：并不是出去时间减去到达时间，因为有可能到达后在候车区等待一段时间，这段时间不能算收费时间），和收费。输入P时按照从栈顶到栈底输出车辆车牌号；输入W时，输出候车区车辆总数；输入E，退出程序这个程序设计需要栈和队列的相关操作，所以在程序设计过程中逐渐熟悉了栈和队列的相关操作，由于像栈，队列这样，有判断栈空，栈满，入栈，出栈这样的操作，使自己更加熟悉了栈和队列的相关知识。主程序#includestdio.h#includestdlib.h#includetime.h#defineOK1#defineERROR0#defineMAX_STACK_SIZE2/*停车场大小*/typedefintStackData;typedefintQueueData;typedefintElemType;typedefstructNode{intNo;intTimeinit;}Node;typedefstructQueueNode/*队列*/{structNodedata;structQueueNode*next;}QueueNode;typedefstructLinkQueue/*链式队列*/{structQueueNode*rear,*front;}LinkQueue;typedefstructSqStackNode/*栈*/{inttop;intbottom;structNodestack_array[MAX_STACK_SIZE+1];}SqStackNode;SqStackNode*InitStack()/*初始化栈*/{SqStackNode*S=(SqStackNode*)malloc(sizeof(SqStackNode));S-bottom=S-top=0;return(S);}intFullStack(SqStackNode*S){returnS-top==MAX_STACK_SIZE;}intpushStack(SqStackNode*S,Nodedata)/*入栈*/{if(FullStack(S)){returnERROR;}S-top++;(S-stack_array[S-top]).No=data.No;(S-stack_array[S-top]).Timeinit=data.Timeinit;returnOK;}intpopStack(SqStackNode*S,Node*data)/*弹出栈顶元素*/{if(S-top==0){returnERROR;}(*data).No=(S-stack_array[S-top]).No;(*data).Timeinit=(S-stack_array[S-top]).Timeinit;S-top--;returnOK;}intFindStack(SqSta