敢死队问题.doc

福建工程学院

课程设计

课程:数据结构课程设计
题目:敢死队问题
专业:计算机科学与技术
班级:计算机1001
学号:3100301118
姓名:林国辉
指导老师:蒋建辉刘建华林芳
设计时间:-
实验题目:敢死队问题
要解决的问题
有M 个敢死队员要炸掉敌人的一碉堡,谁都不想去,排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务,则要再派一个战士上去。现给每个战士编一个号,大家围坐成一圈,随便从某一个战士开始计数,当数到5 时,对应的战士就去执行任务,且此战士不再参加下一轮计数。如果此战士没完成任务,再从下一个战士开始数数,被数到第 5 时,此战士接着去执行任务。以此类推,直到任务完成为止。排长是不愿意去的,假设排长为 1 号,请你设计一程序,求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。
算法基本思想描述

首先从第一号开始报数,循环到指定的偏移位置,删除该结点,直至剩下一个结点。然后返回该结点元素,通过公式计算出从哪里开始计数。


首先从第一号开始报数,循环到指定的偏移位置删除结点,直至剩下一个结点。然后再比较一下它的号码是不是等于1,如果等于则输出开始计数位置,如果不等,继续循环查找,直到找出符合条件的计数起始位置,输出结果。
设计
数据结构的设计和说明
链表实现
typedef struct node /*定义结构体链表*/
{
int data;
struct node *next;
}LinkNode; /* 定义结点类型*/
队列实现
#define MAXSIZE 100 /*假定预分配的队列空间最多为100个元素*/
typedef struct{
int data[MAXSIZE];
int front;
int rear;
int count; /*计数器,记录队中元素总数*/
}SeqQueue;
关键算法的设计
链表实现
int Delete(LinkNode* t) /* 链表的删除*/
{
LinkNode *a;int i;
while (t->next!=t) /*while循环依次删除被点到的士兵*/
{
for (i=1;i<4;i++) /*查找要删除结点的前一结点*/
t=t->next;
a=t->next;
t->next=a->next; /*执行删除操作,删除数据*/
free(a); /*释放结点*/
t=t->next;
}
printf("\n");
return (t->data); /*返回t的值*/
}
void main()
{
LinkNode *p;
int m,n,z,y;
printf("请输入士兵总数:");
scanf ("%d",&n); /*输入队员总数*/
/*当队员总数等于0时退出*/
p=Creat(n); /*创建链表p*/
y=Delete(p); /*选出去炸碉堡的人调用删除函数*/
z=n-y+2;
if(z%n==0) /* 排除特殊情况*/
printf ("从第%d号开始计数排长最后一个留下来而不去执行任务:\n",z);
else
printf("从第%d号开始计数排长最后一个留下来而不去执行任务:\n",(n-y+2)%n);
} /* 通过数学思想求得实验要求情况下的数值*/
队列实现
int begin,count,i,j,num;
SeqQueue *s;
printf("请输入敢死队的人数:");
scanf("%d",&num);
for(begin=1;begin<=num;begin++)/*begin为测试起点*/
{
s=Initial();
for(i=1;i<=num;i++)
{
EnQueue(s,i);
}
for(i=1;i<begin;i++)
{
j=DeQueue(s);
EnQueue(s,j);/*把对头的元素取出来然后放到对尾去,
经过这个循环以后,要从那个开始的士兵的编号就会在队的对头位置了*/
}
count=1;/*删除结点数*/
while(count<num)
{
for(i=1;i<5;i++)
{
j=DeQueue(s);
EnQueue(s,j);/*是把对头的元素取出来然后放到对尾*/
}/*经过这个循环以后,对头的那个节点的