《湖南大学数据结构试验1约瑟夫问题》由会员分享，可在线阅读，更多相关《湖南大学数据结构试验1约瑟夫问题（12页珍藏版）》请在金锄头文库上搜索。
1、HUNAN UNIVERSITY课程实习报告题 目： 约瑟夫环问题 学生姓名 刘乐 学生学号 专业班级 通信工程2班 指导老师 朱宁波 完 成 日 期 2010年4月18日 一、需求分析1 本程序要求采用单链表问题，计算并输出用户输入的某个初始人数数字下，确定初始密码的约瑟夫问题。2 初始人数，初始密码由键盘输入，初始人数其取值范围为（0， 100）。不对非法输入做处理，即假设输入都是合法的。3 在Dos界面输出约瑟夫问题出队列列表。4 测试数据输入114输出4， 8 ，1，6,11，7,3,2，5，10,9二、概要设计抽象数据类型为实现上述程序的功能，应以整数存储用户的输入，以及计算出的结果
2、。算法的基本思想5 根据题目要求，采用单链表问题，计算并输出用户输入的某个初始人数数字下，确定初始密码的约瑟夫问题。设两数为n，m。用循环单向链表根据初始密码移动指针m次，然后把此数删除即出队列，然后把指针指向下一个地址，如果下一个地址为线性表的null则转向第一个地址继续计数，直到最后一个节点出队列。定义如下线性表ADT LinkList 数据对象：D=a | a LNode, i=1,2,.,n, n0 数据关系：R=| a ,a D, a a , i=2,.,n, n0 基本操作：Status InitList(SqList &L) 构造一个空的线性表Lint ListLength(Sq
3、List &L) 线性表已经存在，返回L中数据元素的个数Status ListEmpty(SqList &L) 线性表已经存在，若L为空表，则返回TRUE，否则返回FALSEStatus ListInsert(SqList &L, int i, Elemtype e) 线性表L已存在，1=i=ListLength(L)+1在L中第i个位置之前插入新的数据元素e，L的长度加1Status ListDelete(SqList &L, int i, Elemtype &e) 线性表L已存在且非空，1=i=ListLength(L) 删除L的第i个位置的数据元素，并用e返回其值，L的长度减1通过调用函
4、数建立线性表l，每个m个数，取出对应的值，删除L的第i个位置的数据元素，并用e返回其值，L的长度减1.循环，直至最后一个数。本程序包含三个基本模块（1）输入模块：完成两个正整数的输入，存入变量n,m中。（2）调用循环模块：调用函数建立线性表，并用循环取出报数号序列。（3）输出模块：屏幕上显示出结果。三、详细设计算法的具体步骤构造节点：typedef struct NodeType int id; /* 编号 */ int cipher; /* 密码 */ struct NodeType *next; NodeType; 创建循环链表： static void CreaList(NodeType
5、 *ppHead, const int n,const int m) int i, iCipher; NodeType *pNew, *pCur; for (i = 1; i next = *ppHead; else pNew-next = pCur-next; pCur-next = pNew; pCur = pNew; printf(完成单向循环链表的创建!n); 运行约瑟夫问题:static void StatGame(NodeType *ppHead, int iCipher) int iCounter, iFlag = 1; NodeType *pPrv, *pCur, *pDel;
6、 pPrv = pCur = *ppHead; /* 将pPrv初始为指向尾结点，为删除作好准备 */ while (pPrv-next != *ppHead) pPrv = pPrv-next; while (iFlag) /* 开始搞了! */ /* 这里是记数，无非是移动iCipher-1趟指针! */ for (iCounter = 1; iCounter next; if (pPrv = pCur) /* 是否为最后一个结点了 */ iFlag = 0; pDel = pCur; /* 删除pCur指向的结点，即有人出列 */ pPrv-next = pCur-next; pCur
7、= pCur-next; iCipher = pDel-cipher; printf(第%d个人出列n, pDel-id /* 这个编号标识出列的顺序 */ ); free(pDel); *ppHead = NULL; /* 没人了！为了安全就给个空值 */ 得到一个节点：static NodeType *GetNode(const int iId, const int iCipher) NodeType *pNew; pNew = (NodeType *)malloc(sizeof(NodeType); if (!pNew) printf(Error, the memory is not e
8、nough!n); exit(-1); pNew-id = iId; pNew-cipher = iCipher; pNew-next = NULL; return pNew; 另外需测试链表是否为空，如果为空返回TRUE非空返回FALSE。主函数如下：int main(void) int n, m; NodeType *pHead = NULL; while (1) printf(请输入人数n（最多%d个）: , MAX_NODE_NUM); scanf(%d, &n); printf(和初始密码m: ); scanf(%d, &m); if (n MAX_NODE_NUM) printf(人数太多，请重新输入！n); continue;
