数据结构Ⅰ课程设计约瑟夫环范文

年4月19日数据结构Ⅰ课程设计约瑟夫环文档仅供参考数据结构Ⅰ课程设计约瑟夫环问题01月04日目录TOC\o"1-3"\h\u8534目录 212599第1章问题描述 37780第2章基本要求 424538第3章概要设计 587543.1数据结构的设计 586853.2算法的设计 6321673.3抽象数据类型的设计 83115第4章详细设计 1092714.1设计抽象数据类型对应的C++类的定义 10223294.2设计每个成员函数 11150914.3设计主函数 123833第5章运行与测试 13299465.1程序运行环境 13157885.2测试数据及测试结果 13206465.3程序运行结果截图 1630970第6章总结与心得 178934参考文献 1810324附录程序源代码 19第1章问题描述编号是1,2,3……n的n个人按照顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将她的密码作为新的m值，从她在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。

第2章基本要求1)建立数据模型，确定存储结构；2)对任意n个人，密码为m，实现约瑟夫环问题；3)出圈的顺序能够依次输出。

第3章概要设计3.1数据结构的设计解决此问题需要用到单链表的数据结构。约瑟夫环问题，从确定的初报数开始进行，顺着这一方向向前如此循环，若能找到新的密码m所对应的数值则直接输出，若不能找到，继续向下依次寻找，直到找到密码m所对应的数值，再输出，如此循环。约瑟夫环问题中的数据是人所在的位置，而这种数据存在“第一元素、最后元素”，而且存在唯一的前驱和后继，完全符合单链表的特点。很显然，这需要应用单循环链表的知识。单链表的基本思想就是用指针表示结点之间的逻辑关系，要确定指针变量p，结点p，指针p和L。3.2算法的设计按照模块进行划分：（1）链表节点设计structLnode{intpwd;//密码intbianhao;//编号structLnode*next;};（2）采用头插法构造链表，由此必须倒着输入个人的密码和编号，由此可计一个线性表作为缓存暂时保存个人密码和编号。。n为编号，pwd为n的人的密码。（3）将上述2中缓存的数据从a[n]到一次赋给链表L：Lnode*L,*p;L=newLnode;L->next=NULL;for(i=num;i>0;i--){p=newLnode;p->pwd=a[i-1];p->bianhao=i;p->next=L->next;L->next=p;}（4）用循环模拟报数的过程p=L；while(num>0){for(i=1;i<m;i++){p=p->next;if(p->next==NULL){p->next=L->next;}}Lnode*temp;temp=p->next;cout<<temp->bianhao<<"\n";p->next=temp->next;m=temp->pwd;num--;}num是用来控制循环次数的变量，值为总人数n，每完成一次删除操。即每有一个人出列，num减1。循环中设置了中间变量temp用来存储要删除的结点的指针，以保证删除操作不会导致链表指针无法找到下一结点。结束后掉temp。（5）删除结点，即找到出列对象的同时输出这个结点的数据域：编号和密码！3.3抽象数据类型的设计采用类C语言定义相关的数据类型structLnode{intpwd;//每个人持有的密码intbianhao;//人员编号structLnode*next;//指向下一个结点};第4章详细设计4.1设计抽象数据类型对应的C++类的定义（1）链表节点设计structLnode{intpwd;//密码intbianhao;//编号structLnode*next;};（2）将数据从a[n]到一次赋给链表L：Lnode*L,*p;L=newLnode;L->next=NULL;for(i=num;i>0;i--){p=newLnode;p->pwd=a[i-1];p->bianhao=i;p->next=L->next;L->next=p;}（3）运用循环模拟报数过程p=L；while(num>0){for(i=1;i<m;i++){p=p->next;if(p->next==NULL){p->next=L->next;}}Lnode*temp;temp=p->next;cout<<temp->bianhao<<"\n";p->next=temp->next;m=temp->pwd;num--;}4.2设计每个成员函数intpwd;intbianhao;structLnode*next;将密码和编号存入程序中，经过结点指针对所需的数据进行调用。Lnode*temp找到出列对象的同时，输出这个结点的数据域，存储要删除结点，直到程序运行完毕。4.3设计主函数主函数{定义输入人数和密码输入相应的初始报数输入操作完成后，输出相应数据}

第5章运行与测试5.1程序运行环境Windows7系统下在VC++6.0开发平台进行程序的运行与测试。5.2测试数据及测试结果数据1：输入人数5，初次报数3，密码依次为：26847，测试结果：32154数据2：输入人数8，初次报数6，密码依次为：34871645，测试结果：64573128数据3：输入人数13，初次报数9，密码依次为：4637982315758，测试结果：910281312611374515.3程序运行结果截图数据1：程序清单运行结果：32154数据2：程序清单运行结果：64573128数据3：程序清单运行结果：91028131261137451第6章总结与心得我的这次数据结构课程设计的题目是《约瑟夫环问题》，经过对该题目的设计，使我加深了对数据结构的理解。做什么事情，都要对认真，既然是该你做的事，肯定是你应该有这个能力，即使能力不够，也是应该借这个机会来培养。因此放心大胆地做，对自己有信心，就有动力。有人说，世上的事就怕认真二字。确实，做什么，只是认真地去做，踏踏实实，戒躁戒躁，静静地思考，慢慢地进步，真的是天下无难事。这就是我这次课程设计中得到的最大的体会，受益匪浅。经过课程设计我的收获如下：巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。经过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。经过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。根据我在课程设计中遇到得问题，我将在以后的学习过程中注意以下几点：1、认真上好专业实验课，多在实践中锻炼自己。2、写程序的过程中要考虑周到，严密。3、认真的学习课本知识，并在此基础上学会灵活运用。参考文献[1]胡明，王涛等著.数据结构（C++版）[M].北京：清华大学出版社，.[2]谭浩强著.C程序设计（第四版）[M].北京：清华大学出版社，.[3]谭浩强著.C++程序设计[M].北京：清华大学出版社，.

附录程序源代码#include<iostream>usingnamespacestd;structLnode{ intpwd; intbianhao; structLnode*next;};intmain(){ inti=0; intnum,m; cout<<"输入人数："<<"\n"; cin>>num; cout<<"输入初始报数:"<<"\n"; cin>>m; cout<<"输入密码:"<<"\n"; inta[100]; for(i=0;i<num;i++) cin>>a[i]; Lnode*L,*p; L=newLnode; L->next=NULL; for(i=num;i>0;i--){ p=newLnode; p->pwd=a[i-1]; p->bianhao=i; p->next=L->next; L->next=p; } p=L