约瑟夫问题(算法与数据结构课程设计)

线性表的操作及其应用

一、问题描述

线性表、队列是一种常用的数据结构，有顺序和链式两种存储结构，在实际中应用十分广泛，而链表又分为单链表和循环链表，队列又分为链式队列和循环队列。这些数据结构都可用来解决约瑟夫环问题。约瑟夫环问题是算法设计中的一个经典问题，是顺序编号的一组n个人围坐一圈，从第1个人按一定方向顺序报数，在报到m时该人出列，然后按相同方法继续报数，直到所有人出列。设计算法求约瑟夫环中人员的出列顺序。

二、基本要求

1、选择合适的存储结构，建立线性表；

2、利用顺序存储结构求解约瑟夫环问题；

3、利用单链表和循环链表分别求解约瑟夫环问题；

4、利用队列求解约瑟夫环问题。

三、测试数据

约瑟夫环的测试数据为7，报数为1至3。

四、算法思想

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

由于用到四种不同的存储结构，它们的算法思想依次是：

1、首先建立一个顺序表模拟整个约瑟夫环，手动输入顺序表长（即参加约瑟夫循环的人数）和循环的次数和表元素。用已经输出总人数和顺序表长作比较，作为外层循环条件。并对每一个输出后的元素重新赋值以为标记。对于每次循环，首先检查顺序表此次是不是我们设立的标记，如果不是则循环次数加1，当达到要求的循环次数时就将循环次数设置为0，输出该元素到屏幕并将总输出元素加1。每次外循环我们都会移到表的下一个位置，作为新的判断条件，每次报到表尾的时候，我们都将重新设置到表尾，作为下次循环的表元素。

2、首先采用链式循环链表建立整个约瑟夫环，手动输入第一次的循环次数和每个人所持下一个循环次数。设立判断指针指向表头，并将该指针是否为空作为外层循环条件。做一个内层循环，将判断指针移动到循环要输出的数，并设立一个前指针指向该指针的前一个位置，输出该元素后，将循环次数重新赋值成该元素。接着判断前指针和判断指针比较，如果相等说明整个表已经输出完毕，否则将删除该位置的元素。

3、用链式队列建立循环约瑟夫环，手动输入人数，第一次的循环次数和每个人所持下一个循环次数。并将每一个元素依次入队列，根据第一次循环次数，建立一个for循环，每一次循环都出队列，如果达到要求的循环次数就输出，否则进队列，这样这个数字就出现在队尾。第一个数输出后，以队列的非空作为循环条件，判断方式如上。

4、用循环队列建立约瑟夫环，将1-7个元素依次进入循环队列，以队列的长度作为与已输出的元素作为判断条件，对每一个输出后的元素重新赋值以为标记。对于每次循环，首先检查该该位置的元素是不是我们设立的标记-1，如果不是则循环次数加1，将队首指针移到队列的下一个元素，结束此次循环，当达到要求的循环次数时就将重新循环次数设

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

置为0，输出该元素到屏幕并将总输出元素加1。

五、模块划分

1、void InitQueue(SqQueue *Q)

初始化循环队列

2、void DestroyQueue(SqQueue *Q)

销毁循环队列

3、void ClearQueue(SqQueue *Q)

清空循环队列

4、int QueueEmpty(SqQueue Q)

判断空队列

5、int QueueLength(SqQueue Q)

求循环队列长度

6、void GetHead(SqQueue Q, ElemType *e)

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

取队头元素

7、int EnQueue(SqQueue *Q, ElemType e)

入队列

8、int DeQueue(SqQueue *Q, ElemType *e)

出队列

9、void QueueTraverse(SqQueue Q)

遍历循环队列并输出元素

10、void InitQueue(LQueue *Q)

初始化队列

11、void DestroyQueue(LQueue *Q)

销毁队列

12、void ClearQueue(LQueue *Q)

清空队列

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

13、int QueueEmpty(LQueue Q)

判断空队列

14、int QueueLength(LQueue Q)

求队列长度

15、ElemType GetHead(LQueue Q, ElemType *e)

取队头元素

16、void EnQueue(LQueue *Q, ElemType e)

入队列

17、void DeQueue(LQueue *Q, ElemType *e)

出队列

18、void QueueTraverse(LQueue Q)

遍历队列并输出元素

19、void joseffer(int n)

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

约瑟夫环

20、int CreateList(LinkList &L,int n)

建立顺序链表

21、void josephus_clist(LinkList &L,int m)

顺序链表解决约瑟夫环

22、void InitList(SqList *L)

初始化链表

23、void ysf1()

链表解决约瑟夫环

24、void ysf2()

循环链表解决约瑟夫环

25、void ysf3(){

链式队列解决约瑟夫环问题

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

26、void ysf4()

循环队列解决约瑟夫环问题

27、void menu()

菜单

28、int main()

主函数

六、数据结构//(ADT)

typedef int ElemType;

/* 定义顺序表类型 */

typedef struct

{ ElemType *elem;

int length;

} SqList;

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

/* 定义循环链表类型 */

typedef struct LNode

{ int num;

int code;

struct LNode *next;

} *LinkList;

/* 定义循环队列类型 */

typedef struct

{ ElemType *base;

int front;

int rear;

} SqQueue;

/* 定义链式队列类型 */

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

typedef struct QNode

{ ElemType data;

struct QNode *next;

} QNode,*QueuePtr;

typedef struct

{ QueuePtr front;

QueuePtr rear;

} LQueue;

七、源程序

#include \"stdlib.h\"

#include \"stdio.h\"

#define N 100

typedef int ElemType;

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

/* 定义顺序表类型 */

typedef struct

{ ElemType *elem;

int length;

} SqList;

/* 定义循环链表类型 */

typedef struct LNode

{ int num;

int code;

struct LNode *next;

} *LinkList;

/* 定义循环队列类型 */

typedef struct

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

{ ElemType *base;

int front;

int rear;

} SqQueue;

/* 定义链式队列类型 */

typedef struct QNode

{ ElemType data;

Struct QNode *next;

} QNode,*QueuePtr;

typedef struct

{ QueuePtr front;

QueuePtr rear;

} LQueue;

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

/* 初始化循环队列 */

void InitQueue(SqQueue *Q)

{ Q->base=(ElemType*)malloc(N*sizeof(ElemType));

Q->front=Q->rear=0; }

/* 销毁循环队列 */

void DestroyQueue(SqQueue *Q)

{ free(Q->base); }

/* 清空循环队列 */

void ClearQueue(SqQueue *Q)

{ Q->front=Q->rear=0; }

/* 判断空队列 */

int QueueEmpty(SqQueue Q)

{ if (Q.front==Q.rear)

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

return 1;

else

return 0; }

/* 求循环队列长度 */

int QueueLength(SqQueue Q)

{ return (Q.rear+N-Q.front)%N; }

/* 取队头元素 */

void GetHead(SqQueue Q, ElemType *e)

{ if (Q.front!=Q.rear)

*e=Q.base[Q.front];

}

/* 入队列 */

int EnQueue(SqQueue *Q, ElemType e)

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

{ if ((Q->rear+1)%N==Q->front)

return 0;

Q->base[Q->rear]=e;

Q->rear=(Q->rear+1)%N;

return 1; }

/* 出队列 */

int DeQueue(SqQueue *Q, ElemType *e)

{ if (Q->front==Q->rear)

return 0;

*e=Q->base[Q->front];

Q->front=(Q->front+1)%N;

return 1; }

/* 遍历循环队列并输出元素 */

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

void QueueTraverse(SqQueue Q)

{ int i;

printf(\"\\nQueue: \");

if (Q.rearfor(i=Q.front; iprintf(\"%d\\

}

/* 初始化队列 */

void InitQueue(LQueue *Q)

{ Q->front=Q->rear=(QueuePtr)malloc(N*sizeof(QNode));

if(!(Q->front)) exit(0);

Q->front->next=NULL;

}

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

/* 销毁队列 */

void DestroyQueue(LQueue *Q)

{ while(Q->front)

{ Q->rear=Q->front->next;

free(Q->front);

Q->front=Q->rear;}

}

/* 清空队列 */

void ClearQueue(LQueue *Q)

{ QueuePtr p;

p=Q->front->next;

while(p)

{ Q->front->next=p->next;

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

free(p);

Q->rear=Q->front;}

}

/* 判断空队列 */

int QueueEmpty(LQueue Q)

{ if (Q.front==Q.rear)

return 1;

else

return 0; }

/* 求队列长度 */

int QueueLength(LQueue Q)

{ QueuePtr p; int n=0;

p=Q.front;

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

while(p!=Q.rear)

{ n++;p=p->next;}

return n;

}

/* 取队头元素 */

ElemType GetHead(LQueue Q, ElemType *e)

{ if (Q.front!=Q.rear)

return Q.front->next->data;

else return 0;

}

/* 入队列 */

void EnQueue(LQueue *Q, ElemType e)

{ QueuePtr p;

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

p=(QueuePtr)malloc(N*sizeof(QNode));

if(!p) exit(0);

p->data=e;

p->next=NULL;

Q->rear->next=p;

Q->rear=p;

}

/* 出队列 */

void DeQueue(LQueue *Q, ElemType *e)

{ QueuePtr p;

if(Q->front!=Q->rear)

{ p=Q->front->next;

*e=p->data;

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

Q->front->next=p->next;

if(Q->rear==p)

Q->rear=Q->front;

free(p);

}

}

/* 遍历队列并输出元素 */

void QueueTraverse(LQueue Q)

{ QueuePtr p;

printf(\"\\nQueue:\");

p=Q.front->next;

while(p)

{ printf(\"%d\\

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

p=p->next;

}

}

/*约瑟夫环*/

void joseffer(int n)

{ LQueue Q;

int i;

ElemType x;

InitQueue(&Q);

for(i=1;i<=n;i++)

EnQueue(&Q,i);

while(!QueueEmpty(Q))

{ for(i=1;i<=3;i++)

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

{ DeQueue(&Q,&x);

if(i!=3) EnQueue(&Q,x);

else printf(\"%4d\

}

}

}

/*建立顺序链表*/

int CreateList(LinkList &L,int n)

{ LNode *p,*q;

printf(\"Input %d number:\\n\

L=q=(LinkList)malloc(sizeof(LNode));

if(L==NULL || q==NULL)

return 0;

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

for(int i=1;i<=n;i++)

{ p=(LinkList)malloc(sizeof(LNode));

scanf(\"%d\

p->num=i;

if(i==1)

L=p;

else

q->next=p;

q=p;

}

p->next=L;

L=p;

return 1;

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

}

/*顺序链表解决约瑟夫环*/

void josephus_clist(LinkList &L,int m)

{ int e=m,k;

LinkList p,pre,tp;

p=L;

while(p!=NULL)

{ for(int j=0;j{ pre=p;

p=p->next;}

e=p->code;

k=p->num;

printf(\"The output number is %d\\n\

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

if(pre!=p)

{ tp=p;

pre->next=p->next;

p=p->next;

p=pre;

free(tp);

}

else

{ free(pre);

p=NULL;}

}

}

/*初始化链表*/

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

void InitList(SqList *L)

{ L->elem=(ElemType*)malloc(N*sizeof(ElemType));

L->length=0; }

/*链表解决约瑟夫环*/

void ysf1()

{ SqList L;int m,i,d,k;

InitList(&L);

printf(\"元素个数和报到第几出\");

scanf(\"%d%d\

printf(\"输入元素\");

for(i=0;iscanf(\"%d\

m=0;k=0;i=0;

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

while(m｛ if(L.elem[i]!=N)k++;

if(k==d)

{ printf(\"%3d\

L.elem[i]=N;k=0;m++;}

i++;

if(i==L.length) i=0;

}

}

/*循环链表解决约瑟夫环*/

void ysf2()

{ int m,n;

LinkList jos_clist;

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

printf(\"Input the beginging number:\\n\");

scanf(\"%d\

printf(\"Input n people:\\n\");

scanf(\"%d\

CreateList(jos_clist,n);

josephus_clist(jos_clist,m);

}

/*链式队列解决约瑟夫环问题*/

void ysf3()

{ LQueue Q;

int i; ElemType x; int n;

printf(\"number:n=\");

scanf(\"%d\

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

InitQueue(&Q);

for(i=1;i<=n;i++)

EnQueue(&Q,i);

printf(\"len:%d\\n\

while(!QueueEmpty(Q))

{ DeQueue(&Q,&x);

printf(\"%d\\

QueueTraverse(Q);

joseffer(n);

}

/*循环队列解决约瑟夫环问题*/

void ysf4()

{ SqQueue Q; int i,m,k,j;

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

k=0;m=0;

InitQueue(&Q);

for(i=1; i<=7; i++)

EnQueue(&Q,i);

j=QueueLength(Q);

printf(\"len=%d\

QueueTraverse(Q);

printf(\"\\nJoseffer:\\");

while(m<=QueueLength(Q))

{ if(Q.base[Q.front]!=-1)

{k++;}

if(k==3)

{ printf(\"%d\\

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

Q.base[Q.front]=-1;

k=0;

m++;}

Q.front=(Q.front+1)%j；}

}

/*菜单*/

void menu()

{ int choice;

do{

printf(\"\\n====================================\");

printf(\"\\n 主菜单 \");

printf(\"\\n 1.顺序表实现约瑟夫环问题 \");

printf(\"\\n 2.循环链表表实现约瑟夫环问题 \");

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

printf(\"\\n 3.链式队列实现约瑟夫环问题 \");

printf(\"\\n 4.循环队列实现约瑟夫环问题 \");

printf(\"\\n 5.退出程序 \");

printf(\"\\n====================================\");

printf(\"\\n 请输入您的选择(1,2,3,4,5) choice=\");

scanf(\"%d\

switch(choice)

{ case 1:ysf1();break;

case 2:ysf2();break;

case 3:ysf3();break;

case 4:ysf4();break;

case 5:exit(0);}

} while(choice<=5);

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

}

/*主函数*/

int main()

{ menu();

System(\"pause\");

return 0;

}

八、测试情况

程序的测试结果如下：

1、顺序表实现约瑟夫环问题

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

测试结果正确。

2、循环链表实现约瑟夫环问题

测试结果正确。

3、链式队列实现约瑟夫环问题

测试结果正确。

4、链式队列实现约瑟夫环问题

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

测试结果正确。

九、参考文献

1、严蔚敏，《数据结构 C语言》，清华大学出版社。

2、谭浩强，《c语言程序设计》，清华大学出版社。

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

小结

约瑟夫环问题讲的是：n个人围成一圈报数，报m的人自动离开，然后下位重新从1开始报数，一直循环直至结束。本次课程设计是对于约瑟夫环基于不同存储方式的实现。首先我们对此算法可以进行伪代码的语言描述，这样可以在以后的设计中有清晰的思路，从而不引起在写代码时期的混乱。具体实现期间我们可以通过“程序=算法+数据”的公式，知道我们首先该考虑的是约瑟夫的数据模型，在这里表现的就是C语言的结构体变量，有了数据模型我们就可以在上面进行各种各样的操作，结构体成员变量的思考是本次设计很重要的一部分。至于约瑟夫环的算法可以通过上面先请描述的伪代码一步一步换成函数或者程序语言之类。

程序编写好后，在排除了编译错误之后，如果出现运行结果的不对，这就可以通过VC的Debug模式下进行单步调试，通过按F10一步一步的执行，分析出错代码的位置，然后进行排除。一般的可能数组越界或者指针之类的问题最为突出。

通过本次课程设计加强了我们对于C语言的编写能力，锻炼了我们编写一个小型项目的能力，在以后遇到类似的项目时有了清晰的解决思路，也体会到了团队合作的力量。我们也学到了很多课内学不到的东西，比如思考解决问题，出现差错的随机应变，和与人合作共同提高，都受益非浅，今后的应该更轻松，自己也都能扛的起并高质量的完成项目。同时我们发现考试并不是最重要的，只有理论知识是远远不够的，能运用所学的理论知识解决遇到的实际问题才是最重要的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和思考的能力。本次设计的过程中遇到很多问题，可以说得是困难重重，这毕竟第一次做的，难免会遇到

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

过各种各样的问题，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固。最后，我们真正体会到什么是团队协作，真正的了解到团队合作的有利之处，在我们完成课程设计过程中学会积极的同团队成员交流，取长补短，共同进步。只有和同学多交流多学习才能不断的提高自身水平真正感受到团队成员为了共同的目标联合在一起时的强大力量。

最后要感谢在课程设计过程中给予帮助的老师和同学！

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802