约瑟夫问题算法分析.txt

数据结构算法之 约瑟夫算法

算法思想:在主函数中先建立一个有n个元素的循环链表,其中n由用户输入,用creat()函数创建.返回指向该链表的指针.表示为oldhead.
然后由用户输入开始数数的位置,以及所报数的大小.用start()函数开始游戏,在此函数中,用户输入开始数数的位置,以及所报数的大小,均以参数的形式调入
.后用一个双重循环,在删除出列元素的同时,把它连接到另外的一个链表,最终形成出列元素的链表.print()函数负责打印.
具体函数语句功能见注释.
#include <malloc.h>
#include <stdio.h>
#define LEN sizeof(struct student)
struct student
{int num;
 struct student * next;
 };//建立一个链表.
struct student *creat(int n)
{struct student *head,*p,*q;
 int i;
 p = (struct student*)malloc (LEN);
 head =p;
 p->next= p;
 p->num=1;
 for(i=2;i<=n;i++)
  {q = (struct student*)malloc (LEN);
   q->num=i;
   q->next = p->next;
   p->next =q;
   p= q;

  }
return (head);
}//创建一个有n个元素构成的循环链表.
struct student *start(struct student *head,int n,int k,int m)
{struct student *newhead, *p,*q,*temp;
 int i,j;
 p=head;
 while(p->num!=k)
   {p=p->next;} //找到第k个元素的位置
 for(i=1;i<=n;i++) 
  { for (j=1;j<m-1;j++)
	{p=p->next;
	 }//找到需要删除元素的位置
	 temp=p->next;
	 p->next=temp->next;//删除元素.
	 if(i==1){newhead=temp;q=temp;}//建立新的头结点,表示为newhead,用来指向出列元素形成的链表.
	 else
		{q->next =temp;
		 q=temp;
		}
	 p=p->next;
 }//if和else语句则建立出列元素形成的链表.
 return(newhead);//返回新的链表头结点.
}
//print()函数负责打印游戏开始前和游戏开始后的链表.
void print(struct student *head,int n)
{struct student *p;
 int i;
 p=head;
 for(i=1;i<=n ;i++)
  {printf("%d " ,p->num);
   p=p->next;}
}
//主函数负责整个程序的执行.
void main()
{struct student *oldhead,*newhead,stu;
 int n,m,k;
 printf("\n");
 printf("please enter the number of student in the game:\n");
 scanf("%d",&n);
 printf("please enter the start number:\n");
 scanf("%d",&k);
 printf("please enter the count number:\n");
 scanf("%d",&m);
 oldhead=creat(n);
 printf("the original sequence is:\n");
 print(oldhead,n);
 printf("\n");
 newhead=start(oldhead,n,k,m);
 printf("after the game,the sequence is:");
 print(newhead,n);
}

程序运行结果：
please enter the number of student in the game:
5
please enter the start number:
3
please enter the count number:
2
the original sequence is:
1 2 3 4 5
after the game,the sequence is:4 1 3 2 5