joseph.txt

数据结构实验指导书中关键算法的C语言实现

#define NULL 0
#include"stdio.h"
#include"malloc.h"
#include"string.h"
typedef struct LNode
               {int code;
                int position;
                struct LNode *next;
               }LNode,*LinkList;
int n;
/*尾插法建立单链表，返回表头指针*/
LinkList  CreateList_L(void)
{
	int code;
    	LinkList head,p1,p2;
    	p1=p2=(LinkList)malloc(sizeof(LNode));        /*生成开辟第一个空间*/
    	printf("请输入第1个人的密码");
	scanf("%d",&p1->code);
	p1->position=1;
    	head=NULL;
	while(p1->code!=0)                              /*0为输入结束符*/
    	{	n++;
 		if(n==1) head=p1;
		else p2->next=p1;
                p2=p1;
       		p1=(LinkList)malloc(sizeof(LNode));   /*生成新结点*/
		printf("请输入第%d个人的密码",n+1);
		scanf("%d",&p1->code);/*读下一结点*/
		p1->position=n+1;
       	}
    	p2->next=head;
    	return (head);
}
/*遍历线性表a中的元素*/
/*void output(LinkList head,int n)
{
    	LinkList p,q,k;
    	p=head;
        if(n!=0)
        do
    	{
		printf("%d",p->position);
       		p=p->next;
	}while(--n);
}*/
/*约瑟夫问题求解*/
void JosephSolution(int m,LinkList p1)
{   	LinkList p2;
        while(--m)
	{	p2=p1;
             	p1=p2->next;
	}
	printf("%d,",p1->position);
        p2->next=p1->next;
	if(p2->next!=p2)
	{	JosephSolution(p1->code,p2->next);
		free(p1);
	}
	else {printf("%d",p2->position);free(p2);}
}

main()
{ 	LinkList head;
	int m;
	clrscr();
	head= CreateList_L();
	/*output(head,n);*/
        printf("请输入报数上限值m:");
        scanf("%d",&m);
        printf("出列顺序为：")
        JosephSolution(m,head);

}