梁涛0410101062 joseph环.c

数据结构课程设计

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define PeopleMax 100//变量，数据类型定义最多100人
int N;//表示总人数
int M;//表示起始的密码值，即m的值

struct people//表示每个人的信息结构体
{
   int No;//表示该人序号
   int Num;//表示报的数
   int code;//表示该人的密码
   struct people *next;//指向下一个人
}Head;//链表的头指针

struct Label//表示结果结构体
{
   int No;//存储序号
   struct Label *next;//指向下一个结果
}ResultHead;//存储结果的链表的头指针

void BuiltPeople()//建立有N个人的一个循环链表
{
   int i;
   struct people *newnode,*p;//newnode为新建结点,p指向下一个结点

   Head.No=0;//建立头结点
   Head.Num=0;
   Head.code=0;
   Head.next=&Head;
	p=&Head;

   for(i=1;i<=N;i++)
   {
      newnode=(struct people *)malloc(sizeof(struct people));//生成新结点
      newnode->No=i;
      newnode->Num=0;
      newnode->code=i;//初始随机密码rand()%100+1
      p->next=newnode;//移动指针
      newnode->next=Head.next;
      p=p->next;
   }
}

void BuiltResult_Link()//建立存储N个人出列顺序的链表
{
   int i;
   struct Label *newnode,*p;//newnode为新建结点,p指向下一个结点

   ResultHead.No=0;
   ResultHead.next=NULL;
	p=&ResultHead;
   for(i=1;i<=N;i++)
   {
      newnode=(struct Label *)malloc(sizeof(struct Label));
      newnode->No=0;//初始所有序号为0
      p->next=newnode;//移动指针
      newnode->next=NULL;
      p=p->next;
   }
}

void begin()//开始调用上面子函数实现任务
{
   struct people *p,*frontp;
   struct Label *q;
   int i=1;

   p=Head.next;
   frontp=Head.next;
   while(frontp->next!=p)//frontp指向p的前一结点
      frontp=frontp->next;
   q=ResultHead.next;

   while(1)
   {
      p->Num=i;

      if(p==frontp)//只剩一个人了
      {
         q->No=p->No;//最后一个人出列
         break;
      }

      if(i==M)//报到M了,p出列
      {
         frontp->next=p->next;
         M=p->code;//更新M

         q->No=p->No;//p的序号放入出列链表
         q=q->next;


         free(p);
         p=frontp->next;

         i=1;//从1开始继续报数
      }
      else
      {
         i++;
         p=p->next;
         frontp=frontp->next;
      }
   }
}

void link()
{
   struct Label *p;//newnode为新建结点,p指向下一个结点

   p=ResultHead.next;
   while(p!=NULL)
   {
      printf("%-4d",p->No);
      p=p->next;
   }
}

void joseph()
{
	struct people;
   printf("Joseph环：(请按以下提示录入信息)\n");
   printf("\n");
   printf("请输入总人数N:(并按Enter键结束)\n");
   scanf("%d",&N);
   BuiltPeople();//建立有N个人的一个循环链表
   BuiltResult_Link();//建立存储N个人出列顺序的链表
   printf("请输入M值:(并按Enter键结束)\n");
   scanf("%d",&M);
   begin();
   printf("依次出列的顺序:\n");
   link();
   
}

void main()
{
   joseph();
}