用顺序表和单链表分别实现约瑟夫问题

（一）下面是顺序表方法的解答程序，代码较少。我已经加了注释，可以自己写几个数对着程序的过程操作，这样就很容易理解。 程序在win-tc和Dev-c++下都调试通过。
# include "stdlib.h"
# include "stdio.h"
# include "conio.h"
# define nmax 255
main()
{
int i,j,k,m,n,num[nmax],*p;
printf("\nInput number n and m:\n"); /* 输入总人数，退出的编号 */
scanf("%d%d",&n,&m);
p=num;
for(i=0;i*(p+i)=i+1; /* 人的位置编号从1开始到n */
i=0; /* i为扫描一遍计数器，初值置为0，最大值为n，计到n归0再次重计 */
k=0; /* k是计m计数器，记满m个归0重计 */
j=0; /* j表示从圈子中退出的总人数 */
while(j{
if(*(p+i)!=0) /* 从第一个值不为0的人开始计数 */
k++;
if(k==m)
{
*(p+i)=0; /* 每记满m个将第m个人的值置0，表示该人退出圈子 */
k=0; /* k记满m个归0重计 */
j++; /* 退出圈子人数加1 */
}
i++; /* 一遍循环计数器加1，指向下一个人 */
if(i==n) /* 如果一遍计数完成 */
i=0; /* 归0从数组开始重新循环,跳过值为0的那些位置为m的倍数的编号 */
}
while(*p==0) /* 跳过值为0的位置编号,使p指向值不为零即最后留在圈子中的人 */
p++;
printf("The last one is NO.%d.\n",*p);
getch();
}

（二）本题用单链表实现的c程序如下,程序在win-tc和Dev-c++下都调试通过。
#include
#include

struct count{
int num;
struct count *link;
}

main()
{
int n,m,i;
struct count *head,*p,*q;
clrscr();
printf("Please input n&m:\n");
scanf("%d%d",&n,&m);/*输入n和m*/
head=q=(struct count *)malloc(sizeof(struct count));/*形成首表元*/
head->num=1;
for(i=2;i<=n;i++)/*形成其余的n-1个表元*/
{
q->link=(struct count *)malloc(sizeof(struct count));
q=q->link;
q->num=i;/*第i个表元置编号i*/
}
q->link=head;/*末表元后继首表元，形成环*/
puts("\nThe numbers of who will quit the cycle in turn are:");
while(n)
{
for(i=1;iq=q->link;
p=q->link;/*p指向第m个表元*/
q->link=p->link;/*第m个表元从环中脱钩*/
printf("%4d",p->num);
free(p);/*释放第m个表元占用的空间*/
n--;
}
printf("\n\nThe king number(the last one) is:%4d",q->link->num);
printf("\n\n Press any key to quit...\n");
getch();
}

# include "stdlib.h"
# include "stdio.h"
# include "conio.h"
# define nmax 255
main()
{
int i,j,k,m,n,num[nmax],*p;
printf("\nInput number n and m:\n"); /* 输入总人数，退出的编号 */
scanf("%d%d",&n,&m);
p=num;
for(i=0;i*(p+i)=i+1; /* 人的位置编号从1开始到n */
i=0; /* i为扫描一遍计数器，初值置为0，最大值为n，计到n归0再次重计 */
k=0; /* k是计m计数器，记满m个归0重计 */
j=0; /* j表示从圈子中退出的总人数 */
while(j{
if(*(p+i)!=0) /* 从第一个值不为0的人开始计数 */
k++;
if(k==m)
{
*(p+i)=0; /* 每记满m个将第m个人的值置0，表示该人退出圈子 */
k=0; /* k记满m个归0重计 */
j++; /* 退出圈子人数加1 */
}
i++; /* 一遍循环计数器加1，指向下一个人 */
if(i==n) /* 如果一遍计数完成 */
i=0; /* 归0从数组开始重新循环,跳过值为0的那些位置为m的倍数的编号 */
}
while(*p==0) /* 跳过值为0的位置编号,使p指向值不为零即最后留在圈子中的人 */
p++;
printf("The last one is NO.%d.\n",*p);
getch();
}

（二）本题用单链表实现的c程序如下,程序在win-tc和Dev-c++下都调试通过。
#include
#include

struct count{
int num;
struct count *link;
}

main()
{
int n,m,i;
struct count *head,*p,*q;
clrscr();
printf("Please input n&m:\n");
scanf("%d%d",&n,&m);/*输入n和m*/
head=q=(struct count *)malloc(sizeof(struct count));/*形成首表元*/
head->num=1;
for(i=2;i<=n;i++)/*形成其余的n-1个表元*/
{
q->link=(struct count *)malloc(sizeof(struct count));
q=q->link;
q->num=i;/*第i个表元置编号i*/
}
q->link=head;/*末表元后继首表元，形成环*/
puts("\nThe numbers of who will quit the cycle in turn are:");
while(n)
{
for(i=1;iq=q->link;
p=q->link;/*p指向第m个表元*/
q->link=p->link;/*第m个表元从环中脱钩*/
printf("%4d",p->num);
free(p);/*释放第m个表元占用的空间*/
n--;
}
printf("\n\nThe king number(the last one) is:%4d",q->link->num);
printf("\n\n Press any key to quit...\n");
getch();
!

#include
struct T_M{
int num;
struct T_M *next;
};
void main(void)
{
int m,n;
int i;
struct T_M* boot = (struct T_M *)malloc(sizeof(struct T_M));
struct T_M* p = boot;
struct T_M* out;
scanf("%d %d",&m,&n);
for(i = 0; i < n; i++){
p->next = (struct T_M *)malloc(sizeof(struct T_M));
p = p->next;
p->num = i+1;
}
p->next = boot->next;
p = boot->next;
while(p->next != p){
for(i = 1; i < m - 1; i++)p = p->next;
out = p->next;
p->next = out->next;
printf("%d ",out->num);
free(out);
p = p->next;
}
printf("%d",p->num);
free(p);
free(boot);
}