sd2.c

约瑟夫环问题的程序清单

/* Joseph cycle*/
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
} LNode,*POINTER,*LinkList;
void init_linklist(LinkList *l);
void release_linklist(LinkList *l);
void clear_linklist(LinkList l);
void crt_linklist(LinkList *l);
void disp_linklist(LinkList l);
void game(LinkList l);
void exitgame(void);
void init_linklist(LinkList *l)/*对循环单链表进行初始化*/
{
(*l)=(POINTER)malloc(sizeof(struct LNode));
(*l)->data=-1;
(*l)->next=(*l);
}
void clear_linklist(LinkList l)/*对循环单链表清空*/
{
POINTER p,useless;
p=l->next;
l->next=l;
while(p!=l)
{
useless=p;
p=p->next;
free(useless);
}
}
void crt_linklist(LinkList *l)/*输入数据创建约瑟夫环表*/
{
int num;
POINTER p;
clear_linklist(*l);
printf("\n\nInput some int numbers (ending with -1) :\n");
scanf("%d",&num);
while(num!=-1)
{
p=(POINTER)malloc(sizeof(struct LNode));
p->data=num;
p->next=(*l)->next;
(*l)->next=p;
scanf("%d",&num);
}
}
void disp_linklist(LinkList l)/*显示表中元素内容*/
{ int i=1,row=1;
POINTER p=l->next;
printf("\n\n");
while(p!=l)
{
if(row==7)
{
row=1;
printf("\n");
}
printf("%5d:%-5d|",i,p->data);
i++;
row++;
p=p->next;
}
}
void game(LinkList l)/*元素依次根据密码值出圈*/
{
int m,k=0;
POINTER p=l,pre,u;
printf("\n\nCount Number m==? ");
scanf("%d",&m);
printf("\n\n\n\n%40s\n\n","GAME START");
while(p->next!=p)
{
pre=p;
p=p->next;
if(p==l) { pre=p; p=p->next;}
++k;
if(k==m) { printf(" %d",p->data);
pre->next=p->next;
u=p;
free(u);
p=pre;
k=0;
}
}
printf("\n\n%40s","GAME OVER");
}
void exitgame()
{
printf("\n\n%40s","GOOD_BYE_GOOD !!");
}
void release_linklist(LinkList *l)/*销毁循环单链表（约瑟夫环）*/
{
clear_linklist(*l);
free(*l);
}
void main()/*主控函数*/
{
int select;
LinkList list;
init_linklist(&list);
do
{
printf("%s%15s%15s%15s%15s",
"\n\n\n\n\n\n",
"1:Create",
"2:Display",
"3:Game",
"4:Exit");
printf("\n\n%33c",' ');
select=getche();
switch(select)
{
case '1': crt_linklist(&list);
disp_linklist(list);
break;
case '2': disp_linklist(list);
break;
case '3': game(list);
break;
case '4': exitgame();
break;
default: printf("\nWrong select ! Try again. ");
}/*switch*/
}while(select!='4');
release_linklist(&list);
getch();
}