约瑟夫问题算法及数据结构课程设计报告
线性表的操作及其应用
一、问题描述
线性表、队列是一种常用的数据结构，有顺序和链式两种存储结构，在实际中应用十分广泛，而链表又分为单链表和循环链表，队列又分为链式队列和循环队列。这些数据结构都可用来解决约瑟夫环问题。约瑟夫环问题是算法设计中的一个经典问题，是顺序编号的一组n个人围坐一圈，从第1个人按一定方向顺序报数，在报到m时该人出列，然后按相同方法继续报数，直到所有人出列。设计算法求约瑟夫环中人员的出列顺序。
二、基本要求
1、选择合适的存储结构，建立线性表；
2、利用顺序存储结构求解约瑟夫环问题；
3、利用单链表和循环链表分别求解约瑟夫环问题；
4、利用队列求解约瑟夫环问题。
三、测试数据
约瑟夫环的测试数据为7，报数为1至3。
四、算法思想
由于用到四种不同的存储结构，它们的算法思想依次是：
1、首先建立一个顺序表模拟整个约瑟夫环，手动输入顺序表长（即参加约瑟夫循环的人数）和循环的次数和表元素。用已经输出总人数和顺序表长作比较，作为外层循环条件。并对每一个输出后的元素重新赋值以为标记。对于每次循环，首先检查顺序表此次是不是我们设立的标记，如果不是则循环次数加1，当达到要求的循环次数时就将循环次数设置为0，输出该元素到屏幕并将总输出元素加1。每次外循环我们都会移到表的下一个位置，作为新的判断条件，每次报到表尾的时候，我们都将重新设置到表尾，作为下次循环的表元素。
2、首先采用链式循环链表建立整个约瑟夫环，手动输入第一次的循环次数和每个人所持下一个循环次数。设立判断指针指向表头，并将该指针是否为空作为外层循环条件。做一个内层循环，将判断指针移动到循环要输出的数，并设立一个前指针指向该指针的前一个位置，输出该元素后，将循环次数重新赋值成该元素。接着判断前指针和判断指针比较，如果相等说明整个表已经输出完毕，否则将删除该位置的元素。
3、用链式队列建立循环约瑟夫环，手动输入人数，第一次的循环次数和每个人所持下一个循环次数。并将每一个元素依次入队列，根据第一次循环次数，建立一个for循环，每一次循环都出队列，如果达到要求的循环次数就输出，否则进队列，这样这个数字就出现在队尾。第一个数输出后，以队列的非空作为循环条件，判断方式如上。
4、用循环队列建立约瑟夫环，将1-7个元素依次进入循环队列，以队列的长度作为与已输出的元素作为判断条件，对每一个输出后的元素重新赋值以为标记。对于每次循环，首先检查该该位置的元素是不是我们设立的标记-1，如果不是则循环次数加1，将队首指针移
到队列的下一个元素，结束此次循环，当达到要求的循环次数时就将重新循环次数设置为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)
取队头元素
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)
清空队列
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)
约瑟夫环
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(){
链式队列解决约瑟夫环问题
26、void ysf4()
循环队列解决约瑟夫环问题
27、void menu()
菜单
28、int main()
主函数
六、数据结构//(ADT)
typedef int ElemType;
/* 定义顺序表类型*/
typedef struct
{ ElemType *elem;
int length;
} SqList;
/* 定义循环链表类型*/
typedef struct LNode
{ int num;
int code;
struct LNode *next;
} *LinkList;
/* 定义循环队列类型*/
typedef struct
{ ElemType *base;
int front;
int rear;
} SqQueue;
/* 定义链式队列类型*/
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;
/* 定义顺序表类型*/
typedef struct
{ ElemType *elem;
int length;
} SqList;
/* 定义循环链表类型*/
typedef struct LNode
{ int num;
int code;
struct LNode *next;
} *LinkList;
/* 定义循环队列类型*/
typedef struct
{ ElemType *base;
int front;
int rear;
} SqQueue;
/* 定义链式队列类型*/
typedef struct QNode
{ ElemType data;
Struct QNode *next;
} QNode,*QueuePtr;
typedef struct
{ QueuePtr front;
QueuePtr rear;
} LQueue;
/* 初始化循环队列*/
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)
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)
{ 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; }
/* 遍历循环队列并输出元素*/
void QueueTraverse(SqQueue Q)
{ int i;
printf("\nQueue: ");
if (Q.rear for(i=Q.front; i printf("%d\t",Q.base[i%N]); } /* 初始化队列*/ void InitQueue(LQueue *Q) { Q->front=Q->rear=(QueuePtr)malloc(N*sizeof(QNode)); if(!(Q->front)) exit(0); Q->front->next=NULL; } /* 销毁队列*/ 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; 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; 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; 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; 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\t",p->data); 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++) { DeQueue(&Q,&x); if(i!=3) EnQueue(&Q,x); else printf("%4d",x); } } } /*建立顺序链表*/ int CreateList(LinkList &L,int n) { LNode *p,*q; printf("Input %d number:\n",n); L=q=(LinkList)malloc(sizeof(LNode)); if(L==NULL || q==NULL) return 0; for(int i=1;i<=n;i++) { p=(LinkList)malloc(sizeof(LNode)); scanf("%d",&p->code); p->num=i; if(i==1) L=p; else q->next=p; q=p; } p->next=L; L=p; return 1; } /*顺序链表解决约瑟夫环*/ 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",e); if(pre!=p) { tp=p; pre->next=p->next; p=p->next; p=pre; free(tp); }