猴子选大王的课程实验报告

任务：一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。

要求：

输入数据：输入m,n m,n 为整数，n<m

输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能

#include <stdio.h>

#include <stdlib.h>

typedef struct monkey

{

int num

struct monkey *next

} Monkey,*LINK

/*创建循环链表，容纳M个猴子。返回指向链表头结点的指针*/

LINK createList(int M)

{ LINK p,head1,p2

int i

head1=p=p2=(LINK)malloc(sizeof(Monkey))

for(i=1i<Mi++)

{

p=(LINK)malloc(sizeof(Monkey))

p2->next=p

p2=p

}

p2->next=head1

p=head1

printf("对猴子进行编号！\n")

for(i=1i<=Mi++)

{

p->num=i

printf("%d号猴子：%d\n",p->num,p->num)

p=p->next

}

return head1

}

/*形成循环链表*/

/*从headP指向的循环链表中选大王，数到N的猴子淘汰，将依次淘汰出来的猴子插入到headPtr2指向的链表中*/

void selectKing(LINK head,int N,int M)/*N>=2*/

{

LINK p,p2,head2=NULL

int i

i=0

p=head//p指向第一个结点

while(1)

{

i++

printf("%d号猴子报：%d\n",p->num,i)

if(p->next==p)

break//此为while循环的出口

if(i==N)//if语句中是删除结点的过程

{

i=0

printf("%d号猴被淘汰\n",p->num)

printf("\n")

p2->next=p->next//在此删除结点p

p=p2->next//p指向它的下一个结点

continue

}

else

{

if(i==N-1)

p2=p//保存将要退出结点的前一个结点（存到p2中）

p=p->next

}

}

}

int main()

{

LINK head=NULL

int M,N

printf("输入猴子数量:")

scanf("%d",&M)/*猴子个数*/

printf("输入选定的一个小于猴子总数的数:")

scanf("%d",&N)/*count＝3，表示每次数到3的猴子出局*/

head=createList(M)/*创建循环链表*/

selectKing(head,N,M)/*选大王*/

return 0

}

#include <stdio.h>

#include <stdlib.h>

typedef int status

typedef int ElemType

typedef struct NODE_MONKY

{

ElemType serial_number

struct NODE_MONKY *next

}LNode, *LinkList

void Build(LinkList L,int n){

LinkList p,q

p = L

for(int i=0i<ni++)

{

printf("%d\n",i+1)

q = (LinkList)malloc(sizeof(LNode))

q -> serial_number = i+1

q -> next = NULL

p -> next = q

p = q

}

p -> next = L->next

}

void Print(LinkList L,int x)//计算单链表的长度，然后输出单链表

{

    LinkList p

    p=L->next

    while(x--)

    {

        printf("%d ",p->serial_number)

        p=p->next

    }

}

void Delete(LinkList L,int x,int y)//删除值为x的结点

{

    LinkList p,q

p=L->next

for (int i = 1 i < y i++)

{

for(int j = 2 j < x  j++)

{

p = p->next

printf("serial_number change = %d\n",p->serial_number)

}

q = p->next

        p->next = q->next

        printf("delete %d success\n",q->serial_number)

        printf("p->serial_number = %d\n",p->serial_number)

        free(q)

        q = NULL

        p = p->next

        printf("p->serial_number now = %d\n",p->serial_number)

}

}

int main()

{

int m,n

LinkList L,p,q

L = (LinkList)malloc(sizeof(LNode))

L -> next = NULL

L -> serial_number = 1

printf("please input the number of mounky.\n")

scanf("%d",&n)

Build(L,n)

Print(L,n)

printf("Please input the number M\n")

scanf("%d",&m)

Delete(L,m,n)

}

---