monkey.cpp

来自「数据结构课上练习的有趣问题：一群猴子围成一圈通过报数选出猴王」· C++ 代码 · 共 69 行

#include<stdio.h>
#include<stdlib.h>
#define null 0
#define ok 1
#define error 0
#define overflow -2
typedef int status;
typedef int elemtype;/*定义数据元素类型*/
typedef struct cnode
{
  elemtype data;
  struct cnode *next;
}cnode;
cnode *mon;//定义一个全局变量

status creat_clist(cnode*clist,int n)
{
 cnode *p,*q;
 int i;
 clist=null;
 for(i=n;i>=1;i--)
 {
   p=(cnode*)malloc(sizeof(cnode));
   if(p==null)return overflow;//存储分配失败
   p->data=i;
   p->next=clist;
   clist=p;
   if(i==n)q=p;//用指向链表的最后一个结点
 }
 q->next=clist;//把链表的最后一个结点的链域指向链表的第一个结点，构成循环链表
 mon=clist;//把创建好的循环链表头指针赋给全局变量
 return ok;
}  

status monkey(cnode*clist,int n)
{
  int i;
  cnode*p,*q;
  if(!creat_clist(clist,n))
	  return error;//循环链表创建失败
  p=mon;//p指向创建好的循环链表
  int j=13;
  while(p->next!=p)
  {
	  for(i=1;i<j-1;i++)
		 p=p->next;//找出第j-1个结点
	  q=p->next;
	  p->next=q->next;
	  p=p->next;
	  free(q);
	  j--;
	  if(j==1)j=13;
  }
  printf("%d",p->data);
  clist=null;
}

void main()
{
  int n,i;
  cnode*clist;
  clist=null;//初始化clist
  printf("\n请输入猴子的总数n：");
  scanf("%d",&n);
  creat_clist(clist,n);//创建一个有n个结点的循环链表clist
  printf("\n该当猴王的猴子是：\n");
  monkey(clist,n);
  getchar();
}