数据结构设计报告—挑战解决的难题.docx

《数据结构设计报告—挑战解决的难题.docx》由会员分享，可在线阅读，更多相关《数据结构设计报告—挑战解决的难题.docx（25页珍藏版）》请在第一文库网上搜索。

1、数据构造课程设计系别专业4班级学号姓名指导教师成绩敢死队问题问题描述有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的措施来决定哪个战士去执行任务。假如前一种战士没完毕任务，则要再派一种战士上去。现给每个战士编一种号，大家围坐成一圈，随便从某一种战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参与下一轮计数。假如此战士没完毕任务，再从下一种战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完毕为止。排长是不乐意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最终一种留下来而不去执行任务。规定：至少采用两种不一样的数据构造的

2、措施实现。一、单循环链表数据构造（一）需求分析1 .本程序任务是通过输入任意队伍人数n和报数上限m,输出使排长最终一种执行任务而开始记数的初始位置。首先输入队伍人数n,然后输入报数上限m（m=n）,从1号开始报数，当到达报数上限时，那名士兵出列执行任务，从下个人开始记数，再次循环，直到只剩一人，得到其在队伍中的位置，记下该位置视为排长位置，则1号即可视为最先报数的人，通过数学计算即可获得所求。2 .功能模块和流程：1）功能模块该程序功能比较单一，重要是为处理敢死队问题而设计。通过输入队伍人数和报数上限即可获得开始报数的位置。2）程序流程（1）构造链表（2）数据输入（3）执行删除（4）输出规定数

3、值（5）结束3 .数据测试：当n=10,f5,输出成果为：规定的位置是：9o（二）详细设计1算法设计：本程序其实质是约瑟夫环问题。从排长位置即1号开始报数，共有n个人，到达报数上限m=5的战士出列，继续进行报数，直到剩余最终一人，记下该位置为匕若将该位置视为排长位置，则原先的1号位置即位所有的开始报数的位置z。则z=n-k+202 .以单循环链表为存储构造，包括三个模块：（1）主程序模块（2）构造链表并初始化（3）删除结点3 .结点类型和指针类型typedefstructnode（intdata;structnode*next;1Node;/*定义结点类型*/1Node*p;4 .每个模块的分

4、析(1)主程序模块：main()(1Node*p;intm,n,z,y;do(Printf(P1easeinputthepeop1enumber:n*);scanf(%d,&n);whi1e(n=0);do(printf(,P1easeinputtheexcursion:nzz);scanf(*%d*,&m);whi1e(mdata=1;/*生成第一种结点并使其data值为1*/for(i=2;inext=s;q-next-data=i;/*给第i个结点赋值i*/q=q-next;)q-next=t;/*生成后续结点，并使其data值即为它所在链表(队伍)中的位置*/returnt;)(3)删

5、除结点模块：DE1ETE(1Node*t,intm)/*链表的删除*/(1Node*a;inti;whi1e(t-next!=t)(for(i=1;inext;a=t-next;t-next=a-next;free(a);/*释放结点*/t=t-next;*WhiIe循环依次删除被点到日勺士兵*/printf(n);return(t-data);)()调试分析：1本程序运行后H勺成果应是如下提醒：Exitp1easeinputOOrGoonP1easeinputthetata1oftheteam:输入队伍总人数P1easeinputtheexcursion:输入间隔人数成果显示：Thewant

6、edpositionis选择的位置2 .在程序调试运行的!过程中产生了多种各样的问题，有的是多了空格，有的是拼写错误，尚有的是少了括号，类似的问题有诸多。处理H勺措施是一遍遍尝试，不停逐行逐句进行修改。例如程序调试过程中碰到警告：发现错误为if(m=1)后改正为ifGn=D程序运行对的了，运行如下：显示输出如图:Exip1easeinputSO*Goon.P1eaiseInputtHe七atza1Oftheean：9P1casopuetheecu*sion5hewantedposxeionis3h：Exitp1easeinput0O*Goon.P1easeInput;theof七heeam：1

7、0PIeascinputtbeecu*sion5hewantedpositionis9th：ECp1ea&e1npu0O*Goon.PIcasc:inputthe七at;CIoFhetzcn1P1eaiseInpuCtHeecu*sion1ThCwantzedposxonis1th.Etp1easeinput0,O*Goon.P1casoInput;Izhcofthe七Ca1I1：88P1eaSeInputtbeecusIon：5ThewantedposItionis12th：Exip1easeinput;90*O*Goon.P1eAseinputtbetzctz1oftheteam,rJ3

8、.由程序分析可得：本程序时间免杂度为O(nm)!4 .在设计生成循环单链表时，考虑到程序成果需要士兵的位序，故将每个结点於Jdata值设置为他们在队列中的位置，以便返回。在删除单链表时，假如在报数时直接数到出列士兵则不以便链表的删除，可设置inext;a=t-next;t-next=a-next;free(a);/*释放结点*/t=t-next;.在程序设计前，假如按原题所设，则需设队长为第一位，再分别测试从第几种开始才能符合条件。目前变化思想，通过数学思想：单循环链表自身是一种循环体，可先求出当从第一种出发的话，求出每隔m个出去一种最终是谁未出列，然后再设置它为链头，求出当他为队首时从第几种

9、开始方能使其不出列。(n-y+2)%n即可实现这功能!5 .经验与体会通过这次课程设计我又学到了诸多东西,如程序的模块化设计思想，同步也加深了对数据构造这门课程的理解和学会了怎样在实际中应用数据构造.这个措施是用单循环链表来做的，实现的措施是这样的：首先从第一号开始报数，循环到指定的偏移位置删除结点，直至剩余种结点。然后设计输出，令这个位置为队长位置，队首为开始报数的位置，并按此输出即为所求。这种措施大大H勺减少了时间复杂度，复杂度（五）测试成果Exitp1easeinput0OrGoonP1easeinputthetata1ofthetean：9P1easoinputtheexcursion

10、Thewantedpositionis3th：Exitp1easeinput,0,OrGoon.P1easeinputthetata1oftheteam：10P1easeinputtheexcursion：5hewantedpositionis9th：Exitp1easeinput0OrGoon.P1easeinputthetata1oftheteam：1P1easeinputtheecu*sion：1Thewantedpositionis1th.Exitp1easeinput0OrGoon.P1eaSeinputthetata1oftheteam：88P1easeinputtheexcurs

11、ionhewantedpositionis12tb:Exitp1easeinput*0,0*Goon.P1easoinputthetata1ofthetean：H（六）附件typedefstructnodeintdata;structnode*next;1Node;/*定义结点类型*/1Node*CREAT(intn)/*创立循环链表*/1Node*s,*q,*t;inti;if(n!=0)(t=q=(1Node*)ma11oc(sizeof(1Node);q-data=1;/*生成第一种结点并使其data值为1*/for(i=2;inext=s;q-next-data=i;/*给第i个结点赋

12、值i*/q=q-next;1q-next=t;/*生成后续结点，并使其data值即为它所在链表(队伍)中的位置*/returnt;DE1ETE(1Node*t,intm)/*链表的删除*/1Node*a;inti;whi1e(t-next!=t)(for(i=1;im-1;i+)/*查找要删除结点时前一结点*/t=t-next;a=t-next;t-next=a-next;free(a);/*释放结点*/t=t-next;*whi1e循环依次删除被点到的士兵*/printf(n);return(t-data);)main()(1Node*p;intm,n,z,y;printf(,Exitp1e

13、aseinput,0OrGoon.XnP1easeinputthetata1oftheteam:);scanf(,%d,n);*输入队员总数*/whi1e(n!=O)*当队员总数等于O时退出*/do(printf(P1easeinputtheexcursion:);*输入偏移数*/scanf(,%d,m);Iwhi1e(m=0);if(m=1)printf(Thewantedpositionis1th.n);e1se(p=CREAT(n);y=DE1ETE(p,m);z=n-y+2;if(z%n=0)*排除特殊状况*/printf(Thewantedpositionis%dth:n,z);e1seprintf(Th