约瑟夫环

1.实试验目的

1、复习C语言程序设计中的知识。 2、熟悉线性表的逻辑结构。

3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操 为侧重点。 2.问题描述

约瑟夫（Joseph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针 方向围坐一圈，每人可有代表本人的序号。一开始任选一个正整数m，从 一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的 出列，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直 所有人全部出列为止。试设计一个程序求出出列顺序。 3.基本要求

利用单向链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 1.详细设计

一、 程序设计

1.定义结构体Node struct Node { int data; struct Node *next; };

2.创建循环链表，尾节点指向头节点，返回值为链表的头结点的地址 Node *Creat(int n ) { int i; Node *q=NULL,*p,*head=NULL; for(i=1;i<=n;i++) { p=new Node; p->data=i; if(i==1) head=p; else q->next=p; q=p; }

q->next=head; return head; }

3.从头节点开始遍历循环链表，并打印各个数据元素 void Visit(Node *p,int m) int i; Node *q=p; while(p->next!=p) { for(i=1;inext; if(p->next!=p) { q=p->next; printf(\"%2d\\ p->next=q->next; delete q; } p=p->next; } printf(\"%2d\\n\}

4. 从当前节点开始，遍历链表并打印链表的各个数据元素 void Disp(Node *p) { Node *q=p; printf(\"%2d\\ q=q->next; while(q!=p) { printf(\"%2d\\ q=q->next; } printf(\"\\n\"); }

5.主函数，对其他三个函数进行调用，来完成约瑟夫环的具体实现 int main() { int m,n; Node *head; printf(\"请输入约瑟夫环的总人数n：\"); scanf(\"%d\ head=Creat(n); //调用node *Creat(int n)，创建链表 Disp(head); //调用void Disp(node *p) ，显示链表元素

}

printf(\"请输入初始报数人m：\"); scanf(\"%d\

Visit(head,m); //调用void Visit(node *p,int m)，遍历链表，并打印各个元素 return 0;

6.调试及测试结果

当输入的n值为7时，运行结果如图表1所示

图表 1

当输入的m值为5时，运行结果如图表2所示

图表 2

二、 实验小结

约瑟夫环需要用到循环链表，链表涉及到指针。用到指针，不免碰到内存泄漏的问题，通过此次试验，明白了使用指针时一定要慎重，要密切注意指针的移动。 在循环链表中，头指针和尾指针的移动需要密切注意。在初始化时，头指针和尾指针指向同一片内存，随着数据元素的增加，尾指针逐步向后移动，待元素满时，尾指针指向头指针。在此次试验中，我获益匪浅。