約瑟夫環--連結清單實作

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


typedef struct Node
{
	int data;
	struct Node * next;
}NODE,*pnode;

typedef struct linklist
{
	pnode phead;
	pnode ptail;
	int len;
}LINK,*plink;

static pnode getnode(int i);
void init_list(plink list);
static void creat_list(plink list,int n);
void print_list(plink list);
void joseph(plink list,int m);

int main(void)
{
	int n,m;
	printf ("輸入隊列長度：");
	scanf ("%d",&n);
	printf ("輸入報數停止的數字：");
	scanf ("%d",&m);
	
	plink list;
	list = (plink)malloc(sizeof(LINK));
	
	init_list(list);
	creat_list(list,n);
	print_list(list);
	joseph(list,m);
	
	return 0;
}

static pnode getnode(int i) 	//建立并初始化結點 
{
	pnode node;
	node = (pnode)malloc(sizeof(NODE));
	if (!node)
	{
		printf ("配置設定記憶體錯誤\n");
		exit(-1);
	}
	node->data = i;
	node->next = NULL;
	return node;
}

void init_list(plink list)		//用第一個結點初始化循環連結清單 
{
	pnode ptr;
	ptr = getnode(1);
	list->phead = ptr;
	list->ptail = list->phead;
	ptr->next = list->phead;
	list->len = 1;
}

static void creat_list(plink list,int n) //将其餘資料存入循環單連結清單中 
{
	int i = 0;
	pnode pnew;
	for (i=2;i <= n;++i)
	{
		pnew = getnode(i);
		list->ptail->next = pnew;
		list->ptail = pnew;
		pnew->next = list->phead;
		list->len++;
	}
	printf ("原有隊列：\n");
}

void print_list(plink list)	//輸對外連結表内容	 
{
	pnode ptr;
	ptr = list->phead;
	do
	{
		printf ("%d ",ptr->data);
		ptr = ptr->next;
	}while(ptr != list->phead);
	printf ("\n隊列長度：%d\n",list->len);
}

void joseph(plink list,int m)	//約瑟夫回環函數 
{
	int i;
	pnode ptr1 = list->ptail;
	pnode ptr2 = list->phead;
	while(list->len != 1)
	{
		i = 1;
		while(i <= m-1)
		{
			ptr1 = ptr1->next;
			++i;
		}
		ptr2 = ptr1->next;
		ptr1->next = ptr2->next;
		free(ptr2);
		list->len--;
	}
	printf ("\n最後的數字：%d\n",ptr1->data);
}