数据结构课程设计报告—敢死队的问题

《数据结构课程设计报告—敢死队的问题》由会员分享，可在线阅读，更多相关《数据结构课程设计报告—敢死队的问题（15页珍藏版）》请在毕设资料网上搜索。

1、 数据结构课程设计 系 别 专 业 计算机科学与技术 班级学号 姓 名 指导教师 成 绩 年 月 日 敢死队问题 问题描述问题描述 有 M 个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决 定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战 士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到 5 时，对应的战士就去 执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数 数，被数到第 5 时，此战士接着去执行任务。以此类推，直到任务完成为止。 排长是不愿意去的，假设排长为 1 号，请你设计一程序，求出从第几

2、号战士开始计数才 能让排长最后一个留下来而不去执行任务。 要求：至少采用两种不同的数据结构的方法实现。 一、一、单循环链表数据结构单循环链表数据结构 (一一) 需求分析需求分析 1.本程序任务是通过输入任意队伍人数 n 和报数上限 m，输出使排长最后一个执行任 务而开始记数的初始位置。 首先输入队伍人数 n， 然后输入报数上限 m(mnext-data=i;/*给第i 个结点赋值 i*/ q=q-next; q-next=t; /* 生成后续结点，并使其 data 值即为它所在链表（队伍）中的位置 */ return t; （3）删除结点模块： DELETE (LNode* t,int m)/

3、* 链表的删除 */ LNode *a;int i; while (t-next!=t) for (i=1;inext; a=t-next; t-next=a-next; free(a);/*释放结点*/ t=t-next; /* while 循环依次删除被点到的士兵 */ printf(“n“); return (t-data); (三三) 调试分析：调试分析： 1.本程序运行后的结果应是如下提示： Exit please input 0 Or Go on Please input the tatal of the team: 输入队伍总人数 Please input the excursi

4、on: 输入间隔人数 结果显示：The wanted position is 选择的位置 2.在程序调试运行的过程中产生了各种各样的问题，有的是多了空格，有的是拼写错误，还 有的是少了括号，类似的问题有很多。解决的办法是一遍遍尝试，不断逐行逐句进行修改。 例如程序调试过程中遇到警告：发现错误为 if(m=1) 后改正为 if(m=1)程序运行正确了，运行如下： 显示输出如图： 3.由程序分析可得：本程序时间复杂度为 O（nm）! 4.在设计生成循环单链表时，考虑到程序结果需要士兵的位序，故将每个结点的 data 值 设置为他们在队列中的位置，方便返回。 在删除单链表时，如果在报数时直接数到出列士兵则不方便链表的删除，可设置 inext; t-next=a-next; free(a);/*释放结点*/ t=t-next; 在程序设计前，如果按原题所设，则需设队长为第一位，再分别测试从第几个开始才能 符合条件。现在改变思想，通过数学思想：单循环链表本身是一个循环体，可先求出当从第 一个出发的话，求出每隔 m 个出去一个最