资源预览内容
第1页 / 共12页
第2页 / 共12页
第3页 / 共12页
第4页 / 共12页
第5页 / 共12页
第6页 / 共12页
第7页 / 共12页
第8页 / 共12页
第9页 / 共12页
第10页 / 共12页
亲,该文档总共12页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
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二、概要设计抽象数据类型为实现上述程序的功能,应以整数存储用户的输入,以及计算出的结果。算法的基本思想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(SqList &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通过调用函数建立线性表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 *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; 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 = 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 enough!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;
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号