123.cpp

约瑟夫问题 编号为1,2,3,…,n的n个人按顺序针方向围坐一张圆桌旁

#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
	int data;
	struct node *next;
} ListNode;
typedef ListNode *LinkList;
void main()
{ 
     LinkList R;
     int n,k;
     LinkList initRing(int n,LinkList R);
     LinkList DeleteDeath(int n,int k,LinkList R);
      printf("总人数n=，报数上限k=");
      scanf("%d%d",&n,&k);
      R=initRing(n,R);
      R=DeleteDeath(n,k,R);
        }
     /*   建立单循环链表        */
          LinkList initRing(int n,LinkList R)
          {
             ListNode *p,*q;
             int i;
             R=q=(ListNode *)malloc(sizeof(ListNode));
             for (i=1;i<n;i++)  {
                p=(ListNode *)malloc(sizeof(ListNode));
                q->data=i; q->next=p;q=p;
                }
                p->data=n; p->next=R;R=p;  return R;
              }
     LinkList DeleteDeath(int n,int k,LinkList R)
      {
          int i,j;
          ListNode *p,*q;
          p=R;
          for(i=1;i<=n;i++)
		   //删除结点
             for(j=1;j<=k-1;j++)   //沿链前进k-1步
               p=p->next;
               q=p->next;
               p->next=q->next;    //删除q指向的结点
               printf("%4d",q->data);
               if (i%10==0) printf("\n");
               free(q);
		  
	 }
             printf("\n");
             R=p;return R;
           }