《数据结构课程设计报告(约瑟夫环）》由会员分享，可在线阅读，更多相关《数据结构课程设计报告(约瑟夫环）（19页珍藏版）》请在金锄头文库上搜索。
1、目录目录1任务书.2正 文4一、数据结构定义41.抽象数据类型42.存储结构定义43.基本操作5二、解题过程71.问题分解72.模块结构73.解题思路8三、实现9四、实验结果131.实验数据132.实验结果13五、实验小结161.数据结构使用小结162.需完善之处17课程设计体会19参考文献20课程设计(论文)任务书 软件 学院软件工程专业2012 - 3班 一、课程设计(论文)题目数据结构课程设计二、课程设计(论文)工作自 2013 年 12月 24日起至 2013 年 12月 26 日止。三、课程设计(论文) 地点: 软件工程实训中心 308 四、课程设计(论文)内容要求：1本课程设计的目
2、的（1）使学生熟练掌握抽象数据类型的组织和定义； （2）使学生熟练掌握数据类型的定义和实现； （3）培养学生组织和分析数据的能力；（4）培养学生分析和应用基于不同数据结构的算法的能力；（5）提高学生的科技论文写作能力。2基本要求：每位同学在以下题目中任选一题（在方框中打勾），独立完成课程设计：R 约瑟夫环：参见数据结构题集P179。 赫夫曼编/译码器：参见数据结构题集P149。 教学计划编制问题：参见数据结构题集P150。3课程设计论文编写要求（1）要按照书稿的规格打印誊写课设报告；（2）报告分为封面、任务书（本文档）、正文、课程设计体会和参考文献四部分；学生签名： 年 月 日课程设计(论文)
3、评审意见（1）题目分析（20分）：优（）、良（）、中（）、一般（）、差（）； （2）流程分析（30分）：优（）、良（）、中（）、一般（）、差（）； （3）数据定义（30分）：优（）、良（）、中（）、一般（）、差（）；（4）代码编写（10分）：优（）、良（）、中（）、一般（）、差（）；（5）创新能力（10分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性、设计态度及考勤是否降等级：是（）、否（）评阅人： 职称： 讲 师 2014年1月6日正 文一、 数据结构定义1. 抽象数据类型本设计中用到的数据结构ADT定义如下：ADT Node数据对象：D=id,key|idNode,keyN
4、ode,id=0;key=0数据关系：R=|id,keyD, id=0;key=0基本操作：CreatList(&pHead,k)操作结果：构造单循环链表PrintList(pHead)初始条件：链表已存在操作结果：打印输出链表数据元素Joesph(&pHead,m)初始条件：链表已存在，m为出列者所在编号操作结果：删除出队编号所在结点，并将该结点的key作为新的key，从该结点的下一结点移动 ADT Node2. 存储结构定义数据存储结构的C语言定义如下：typedef struct Node/带头结点的单循环链表 int id;/编号 int key;/密码 struct Node *ne
5、xt;Node,*CircularList;3. 基本操作数据结构的基本操作实现如下：1、 构造单循环链表函数：void CreatList(CircularList *ppHead,const int k)int i,ikey;Node *pNew,*pCur;for(i=1;iid=i;pNew-key=ikey;pNew-next=NULL;if(*ppHead=NULL)*ppHead=pCur=pNew;pCur-next=*ppHead;elsepNew-next=pCur-next;pCur-next=pNew;pCur=pNew;printf(约瑟夫环已建成，可以开始进入报数游
6、戏！n);2、 输出单循环链表函数：void PrintList(const Node *pHead)const Node *pCur=pHead;if(!pHead) printf(单循环链表是空的！n);doprintf(第%d个人所持有的密码是：%dn,pCur-id,pCur-key);pCur=pCur-next;while(pCur!=pHead);3、约瑟夫环规则删除结点并输出结点信息函数： void Joesph(CircularList *ppHead,int ikey)int iCount,iFlag=1;Node *pPrv,*pCur,*pDel;pPrv=pCur=*
7、ppHead;/将pPrv初始为指向尾结点，为删除做好准备while(iFlag)for(iCount=1;iCountnext;if(pPrv=pCur) iFlag=0;/最后一结点pDel=pCur;/删除pCur指向的结点 pPrv-next=pCur-next;pCur=pCur-next;printf(第%d个人出列，所持密码为:%dn,pDel-id,pDel-key);ikey=pDel-key-1;free(pDel); ppHead=NULL;二、 解题过程1. 问题分解该问题主要应实现以下功能：建立约瑟夫环并解约瑟夫环，直到所有玩家出列，并顺序输出出列编号。它主要解决约瑟
8、夫环问题。2. 模块结构系统主要由 5个模块组成，分别是：（1）、构造链表模块 void CreatList(CircularList *ppHead,const int k)（2）、输出链表模块 void PrintList(const Node *pHead)（3）、约瑟夫环函数模块 void Joesph(CircularList *ppHead,int ikey)（4）、菜单模块 void menu()（5）、主函数模块int main(int argc,char *argv)主函数模块int main(int argc,char *argv)模块之间的结构如下：菜单函数void me
9、nu()数字0、退出数字1、建立约瑟夫环Void CreatList(CircularList *ppHead,const int k)输出已建立的约瑟夫环中每个人的信息void PrintList(const Node *pHead)按出列顺序输出约瑟夫环中参与者的编号void Joesph(CircularList *ppHead,int ikey)3. 解题思路各模块的实现步骤为（1）、创建单循环链表函数模块：用一个for循环来给链表的每一个结点分配空间，输入每个人所持有的密码key，并创建结点。然后用头插法建立一个带结点的单循环链表。（2）、输出单循环链表模块：先判断表是否为空，若不空
10、则输出结点信息，同时指针向后移，指向下一结点，继续输出直到指针再次指向头结点为止，输出完毕。（3）、约瑟夫环函数模块：建立一个iFlag标签，值为1执行循环语句，值为0跳出循环。While循环语句里的for循环实现报数功能，设指针pPrv和指针pCur，移动结点到ikey,再删除第ikey个结点并把该结点的key值赋给ikey，再从该结点的下一个结点开始移动，重复上述过程，直到结点全部出列。结束while循环。（4）、菜单模块：用简单的printf设计出具有一定美观的菜单界面，使得程序所要实现的功能一目了然，又可以供操作者自主选择。（5）主函数模块：设置标签iflag，供用户选择输入数字操作。
11、若为1则开始或继续约瑟夫环游戏；若为0，退出游戏。游戏开始后，首先得设置参与者人数n以及初始报数上限m，调用CreatList()创建约瑟夫环，然后调用PrintList()输出当前已输入的信息以确认信息无误，再调用Joesph()函数解决约瑟夫环问题。结束后再用iflag标志位判断是否继续。三、 实现代码及注释：/#includeconsts.h#include#includetypedef struct Node/带头结点的单循环链表 int id;/编号 int key;/密码 struct Node *next;Node,*CircularList;void CreatList(Cir
12、cularList *ppHead,const int k)/构建单循环链表 int i,ikey;Node *pNew,*pCur;for(i=1;iid=i;pNew-key=ikey;pNew-next=NULL;if(*ppHead=NULL)*ppHead=pCur=pNew;pCur-next=*ppHead;elsepNew-next=pCur-next;pCur-next=pNew;pCur=pNew;printf(约瑟夫环已建成，可以开始进入报数游戏！n);void PrintList(const Node *pHead)/输出单循环链表 const Node *pCur=pHead;if(!pHead) printf(单循环链表是空的！n);doprintf(第%d个人所持有的密码是：%dn,pCur-id,pCur-key);pCur=pCur-next;while(pCur!=pHead);void Joesph(CircularList *ppHead,int ikey)/约瑟夫环规则删除结点
