数据结构与算法实验报告-约瑟夫环(2)

n、s、m的值分别为100、3、5时所得结果如下：

经过手算比较，程序运行正确。

六、附录

带注释的源程序为： #include #include #define ERROR -1 #define OK 0

typedef int LElemType; typedef int Status; typedef struct LNode {

LElemType data; struct LNode *next; }LNode,*LinkList;

LNode *CreateLinkList(int n)//顺序建立链表,L为头结点 {

int i,x;

LNode *p; LNode *s; LNode *L;

L=(LNode*)malloc(sizeof(LNode)); p=(LNode*)malloc(sizeof(LNode)); L->next=p;//循环链表空表 p->next=L->next;//p为尾结点 p->data=1; x=1;

for(i=0;i<=n-2;i++) { x++;

s=(LNode*)malloc(sizeof(LNode)); s->data=x;//插入表尾 p->next=s; p=s;

// printf(\ }

p->next=L->next; return L; }

Status ListDelete_L(LNode *L,LElemType *e)

{//删除队列当前位置的元素q，并用e返回其值， LNode *p; LNode *q;

p=L;

if(!(p->next)) return ERROR; if (p->next==p) {

// printf(\ //printf(\ L->next=NULL; } else

{q=p->next;

p->next=q->next; *e=q->data; free(q); }

return OK;

}//ListDelete_L int main(void) {

int s,m,n; int j,e,cc; LNode *L; cc=1;

printf(\ scanf(\

printf(\ scanf(\ printf(\ scanf(\

L=CreateLinkList(n);

if(L->next->next= =L->next) return OK;//空表 else {

for(j=1;jnext;

//从第s个人开始报数 }

while(L->next!=NULL) {

if (cc==1) //CC用于判断是否刚开始报数，1为刚开始 2为已经有人离开队列， {

for(j=1;j

L=L->next;

//printf(\ //用于调试，观察开始报数的顺序，正式运行时可以注释掉 }

ListDelete_L(L,&e);//删数第m个 printf(\ //出队列的数打印 ++cc; } else {

for(j=2;j<=m;j++) //有人离开队列后，报数为1的数向前移动了一位，因此，循环从2开始 {

L=L->next;

//printf(\ //用于调试，看开始报数的顺序，正式运行时可以注释掉 }

ListDelete_L(L,&e);//删数第m个

printf(\ //出队列的数打印 } }

return OK; }

getchar();//循环不自动结束 }