约瑟夫问题.txt

数据结构的线性表及其应用

   约瑟夫问题用单链表实现：
先建立具有n个结点的循环单链表，表头结点为head,然后由q指向表头结点，开始循环，直到该项链表中只有一个结点（q->next==q）为止。在循环过程中，由计数器count计数扫描过的结点个数，当count等于m-1时，说明下一个结点便是要出队的结点故删除该结点，这样，链表中的结点个数越来越少，直到只有一个结点，它就是猴王。实现本题功能的程序如下：
/*单链表的应用*/
   #include <stdio.h>
   #include <malloc.h>
   struct Node
   {
      int data;
      struct Node *next;
   }
   main()
   {
     struct Node *head,*p,*q,*r;
     int n=0,m=0,count=0,i=0;
     printf("请输入猴子的总数n:");
     scanf("%d",&n);
     printf("数到哪个编号的猴子退出:");
     scanf("%d",&m);
     for (i=1;i<=n;i++)
     {
       p=(struct Node *)malloc(sizeof(struct Node)); /*建立结点p*/
       p->data=i;
       p->next=NULL;
       if (i==1)  /*建立表头结点*/
       {
	 head=p,q=head; /*head作为表头结点,q总是指向链表的最后一个结点*/
       }
       else  /*建立其他结点*/
       {
	 q->next=p;
	 q=q->next;
       }
     }
     q->next=head;  /*建立循环单链表*/
     
     q=head;  /*q先指向表头结点*/
     
     do
     {
       count++;  
       if (count==m-1) /*第i个猴子退出*/
       {
	  r=q->next;        /*r指向要删除的结点*/
	  q->next=r->next;  /*删除结点r*/
	  count=0;          /*计数器重置0*/
	  
	}
	q=q->next;
      } 
	 while (q->next!=q);    /*循环直到只剩一个结点*/
      printf("被选为猴王的猴子的编号:%d\n",q->data);  
    }