敢死队问题探讨.doc

洛 阳 理 工 学 院 课 程 设 计 报 告 课程名称 数据结构课程设计 设计题目 敢死队问题  课 程 设 计 任 务 书 设计题目： 敢死队问题 设计内容与要求：有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。 ?? 排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。 要求至少采用两种不同的数据结构的方法实现。 typedef struct node { int data; struct node *next; }LNode;/* 定义结点类型 */ b.线性表存储结构 #define LIST_INIT_SIZE 100 #define LISTINCCREMENT 10 #define OK 1 #define ERROR 0 typedef int ElemType; typedef struct KList /*定义数据结构体类型*/ { ElemType *elem; /*存储空间基址*/ int length; /*当前长度*/ int listsize; /*当前分配的存储容量(以sizeof(ElemType)为单位)*/ }SqList; c.循环队列存储结构 #define QueueSize 1000 //假定预分配的队列空间最多为1000个元素 typedef struct{ int data[QueueSize]; int front; int rear; int count; //计数器，记录队中元素总数 }CirQueue; 2.总体设计 1.系统结构图 本程序有四个功能模块，包括三个解决敢死队问题方案的模块和一个退出系统模块。三个解决方案分别采用了循环聊表储存结构、线性表储存结构、循环队列储存结构。功能模块如下图所示。 功能模块具体简介如下： 1.循环单链表 以单循环链表为存储结构，包含三个模块： a.主程序模块: 包含敢死队人数的输入，死亡数字的输入，函数的调用，结果的输出。 b.构造链表并初始化: 构造链表，给每个结点赋值，给队员编号。 c．删除: 当报数到死亡数字时队员出列去执行任务，删除该节点。 算法流程图 2.线性表储存结构 功能设计本程序其实质是约瑟夫环问题,本次实验用了线性表数据结构,并运用模块化的程序设计思想,算法的实现是这样的: 定义类类型 a.定义变量并初始化 b.线性表初始化 c.当队员数小于等于1时,输出结果 算法流程图 3.循环队列储存结构解决 功能设计 本程序其实质是约瑟夫环问题,本次实验用了循环队列数据结构,并运用模块化的程序设计思想,算法的实现是这样的: 这个方法是用队列循环来做的，实现的方法是这样的：首先从第一号开始报数，循环到指定的偏移位置删除结点，直至剩下一个结点。然后再比较一下它的号码是不等于1，如果等于则输出开始计数位置，如果不等，继续循环查找，直到找出符合条件的计数起始位置，输出结果。 算法流程图 3.测试与调试 1.调试中遇到的问题及对问题的解决方法 (1).函数调用:函数调用是语言中一块十分重要部分，它可以把一个程序分成若干部分，然后进行配置，所以这块内容对我们很重要。 (2).循环的问题:大量的循环语句的应用，分析使我很头疼，循环是计算机语言中很重要的部分，什么程序也离不开循环，这个问题的解决使我有了坚实的基础。对多层循环的应用也有了深刻的理解。 2.算法的时间复杂度和空间复杂度 算法的时间复杂度是指算法在编程后在机器中所耗费的时间。在创建单链表的算法中时间复杂度为O（n），在单链表删除算法中时间复杂度为O（m），其他算法的时间复杂度为O（1）。算法的空间复杂度是指算法在编程后在机器中所占的存储量。程序的空间复杂度为S(n)。 4.测试结果 进入用户主界面，选择实现结果的方法 运用循环链表存储结构,以10个队员，死亡数字为5来运行，结果如下 选择第2项功能，运用线性表储存结构,输