广州三星研究院 待遇:Josephus的解决方案

#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>

#define FALSE 0
#define TRUE 1
typedef int DataType; /* 定义元素类型为整型，也可定义为其他类型 */

struct Node; /* 单链表结点类型 */
typedef struct Node *PNode; /* 结点指针类型 */

struct Node /* 单链表结点结构 */
{
DataType info;
PNode link;
};
struct LinkList /* 单链表类型定义 */
{
PNode head; /* 指向单链表中的第一个结点 */
};

typedef struct LinkList *PLinkList; /* 单链表类型的指针类型 */

int insert_clink( PLinkList pclist, DataType x, PNode p )
/* 在pclist所指的循环单链表中最后一个结点p的后面插入元素x */
{
PNode q;
q = (PNode)malloc( sizeof( struct Node ) );
if( q == NULL )
{printf( "Out of space!!! \n" );
return ( FALSE );
}
else {
q->info = x;
q->link = pclist->head->link;
p->link = q;
return ( TRUE );
}
}

PLinkList createNullList_clink( void )
/* 创建带头结点的空循环链表*/
{ PLinkList pclist;
PNode p;
pclist = (PLinkList)malloc( sizeof( struct LinkList ) );
if( pclist != NULL )
{ p = (PNode)malloc(sizeof(struct Node)); /* 申请头结点 */
if (p!=NULL)
{ pclist->head = p;
p->link = NULL;
}
else
pclist->head = NULL;
}
else
printf( "Out of space!!\n" );
return pclist;
}

PNode next_clink( PNode p )
{
return p->link;
}

PNode find_clink( PLinkList pclist, int i )
/* 在带有头结点的循环单链表clist中求第i(i>0)个结点的位置 */
/* 当表为空循环单链表时，返回值为NULL */
{ PNode p;
int j;
p = pclist->head->link;
if (i<1)
{ printf("The value of i=%d is not reasonable.\n",i);
return NULL;
}
if ( p == NULL )
return NULL;
for ( j=1;j<i;j++ )
p = p->link;
return p;
}

void josephus_clink( PLinkList pclist, int s,int m )
{ PNode p,pre,tp;
int i;
p = find_clink(pclist,s); /* 找第s个结点 */
if (p==NULL) /* 无第s个结点 */
{ printf(" s = %d not exit.\n ",s);
exit(1);
}
while (pclist->head->link!=NULL)
{ for (i=1;i<m;i++) /* 找第m个结点 */
{ pre = p;
p = p->link;
}
printf(" out element: %i \n",p->info); /* 输出该结点 */
if (pre!=p) /* 当表中元素个数大于1时，删除该结点 */
{ pre->link = p->link;
tp = p;
p = p->link;
free(tp);
}
else /* 当表中元素个数等于1时，将头结点指针置空 */
{ free(pre);
pclist->head->link = NULL;
}
}
free(pclist->head);
free(pclist);
}

main( )
{ PLinkList jos_clist;
PNode p;
int i,n,s,m,k;

printf("\n please input the values of n = ");
scanf("%d",&n);
printf(" please input the values of s = ");
scanf("%d",&s);
printf(" please input the values of m = ");
scanf("%d",&m);
jos_clist = createNullList_clink( ); /* 创建空循环链表 */
if (jos_clist==NULL || jos_clist->head==NULL) return ( FALSE);
p = jos_clist->head ;
for( i = 1; i <= n; i++ ) /* 创建循环链表 */
{ k = insert_clink( jos_clist,i, p );
if (k==FALSE) return(FALSE);
p = next_clink( p );
}
josephus_clink(jos_clist,s,m);
return (TRUE);
}