《约瑟夫环C实现》由会员分享，可在线阅读，更多相关《约瑟夫环C实现（6页珍藏版）》请在金锄头文库上搜索。
1、约瑟夫环C 实现author,Andy Suee Chan一、需求分析1、本程序演示约瑟夫问题 : 编号为 1，2，.,n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码 ( 正整数 ) 开始任选一个正整数作为报数值 , 自第一个人开始按顺时针方向自1 开始顺序报数，报到m时停止报数，报 m的人出列，将他持有的密码作为新的m值，从他的顺时针方向上的下一个人开始重新从1 报数，如此下去，直至所有的人全部出列为止。编写完整的程序求出出列顺序。2、利用单向循环链表存储结构模拟此过程，按照出列的顺序印出个人的编号3、测试数据 :初始密码 :20 ，人数 :7.7 个人的密码以次是 3、1、7、2、
2、4、8、4二、概要设计1、循环链表抽象数据类型定义ADT OrderedList 数据对象:D=ai | ai属于Elemtype，i=1 ，2，3. .， n =0数据关系:R1 = | ai-1 ,ai属于D，ai-1ai， i= 2， 3.n基本操作 :createNode(n,m)操作结果 : 生成一个结点， n: 编号、 m:密码createList(&L，n)操作结果 : 根据 n 的值，构造一个空的循环链表，n 为链表中结点的个数jose(&L,n)操作结果 : 实现出队操作ADT OrderedList2、本程序包含三个模块(1) 构造结点模块(2) 生成链表模块(3) 出队处
3、理(4) 主函数模块各模块调用关系 :(4)-(2)- (1) ，(4)- (3)三、详细设计1、结点类型typedef struct LNodeint num; /编号int pwd; /密码struct LNode *next; LNode;2、构造结点LNode *createNode(int m_num,int m_pwd)LNode *p;p = (LNode*)malloc(sizeof(LNode); /生成一个结点p-num = m_num; / 把实参赋给结点相应的数据域p-pwd = m_pwd;p-next = NULL; /指针域指向空return p;3、生成链表vo
4、id createList(LNode *ppHead,int n)int i,m_pwd;LNode *p, *cur; /cur : for(i = 1; i next = *ppHead; /cur 的指针域指向自身else /如果不为空，则插入结点p- next = cur- next;cur- next = p;cur = p; /cur指向新插入结点printf( 完成创建 !n ); /提示链表创建完成4、出队处理void jose(LNode *ppHead,int m_pwd) /count:记数、 tag: 标记 int count,tag;tag= 1; /1:出队 0:
5、 结束LNode *p, *cur, *p_del;p = cur = *ppHead; /指向头结点while(p- next != *ppHead) /如果不是尾结点，就移动一次p = p- next;while(tag) /标记为出队for(count = 1;count next = cur-next; / cur = cur-next;出队操作m_pwd = p_del-pwd; /获取最后一个出队结点的密码p = cur; /浮动指针指向移动一次后的结点cur = cur- next; /再移动到下一个结点，为出队准备if (p = cur) /tag = 0;else出队结束p_
6、del = cur; /把要出队的结点赋给p_del指针p- next = cur-next; / cur = cur-next;出队操作m_pwd = p_del-pwd; /获取出队结点的密码printf(第%d个人出列 , 密码 :%dn ,p_del-num,p_del-pwd);free(p_del); /释放结点*ppHead = NULL; /全部出列后，头指针指向空(5) 主函数模块int main(void) int n, m;LNode *pHead = NULL;printf( 请输入人数 n:);scanf( %d,&n);printf( 初始密码 m:);scanf( %d,&m);createList(&pHead,n);printf( n);jose(&pHead,m);return 0;四、程序演示
