1、I 数 据 结 构 课 程 设 计数 据 结 构 课 程 设 计 实 验 报 告实 验 报 告 题 目: 敢死队问题_ 院 系： _ 专业班级： _ 学 号： _ 学生姓名： _ 指导教师： _ 实验地点：_ 2011 年 12 月 27 日 1 一、程序题目：一、程序题目： 问题描述: 敢死队问题 有 M 个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决 定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战 士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到 5 时，对应的战士就去 执行任务，且此战士不再参加下一轮计数。如果此战士没
2、完成任务，再从下一个战士开始数 数，被数到第 5 时，此战士接着去执行任务。以此类推，直到任务完成为止。 排长是不愿意去的，假设排长为 1 号，请你设计一程序，求出从第几号战士开始计数 才能让排长最后一个留下来而不去执行任务。 要求要求：至少采用两种不同的数据结构的方法实现。 二、算法的主要思想：二、算法的主要思想： 分别采用单循环链表单循环链表和循环队列循环队列两种数据结构解决此问题。 1. 单循环链表单循环链表结构结构 需求分析需求分析 1.本程序输入队伍人数 M 为任意的，最终输出记数的初始位置，首先报数上限为 5， 当达到报数上限时， 那名士兵出列执行任务， 从下个人开始记数， 再次循
3、环， 直到只剩一人， 得到其在队伍中的位置，通过数学思想求得题目要求即队长为首的情况下 需要记数初始位 置。 2.程序执行的命令包括： （1）构造链表； （2）数据输入； （3）执行删除； （4）输出要求数值 （5）结束。 概要设计概要设计 以单循环链表为存储结构，包含三个模块： 1.主程序模块 2.构造链表并初始化 3删除 详细设计详细设计 #include using namespace std; typedef struct node 2 int num; node *next; lnode;/定义一个结构体，num 表示士兵的编号 void main() int M;/士兵个数 int
4、 i; int start,count; lnode*l; coutnext=q;/创建其他节点，并将它接到链表尾部 p=q;/把指针 p 移一位，使他指向刚链上的节点 lnode*t=new lnode;/从这里开始创建最后一个节点 t-num=M;/节点编号为 M p-next=t; p=t; t-next=l;/并将最后一个节点与第一个节点相连，变成循环链表 p=l;/p 指向第一个节点 for(i=1;inext; /一个一个往下找，一直找到编号为 start 的那个节点，从这里开始计数 count=0;/删除节点个数 while(countnext=p-next;/删除该节点 count+; p=t-next;/从下个节点开始继续数 /当删除节点为 M-1 个时，结束 3 if(
