循环链表_约瑟夫环

约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时把编号从0~n-1，最后结果+1即为原问题的解。

clist.h文件

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<stdlib.h>

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

typedef struct Head
{
	int length;
	pnode next;
}*phead,Head;

phead Creat();//创建循环链表
int Init(phead ph, int pos, int value);
int Delete(phead ph, int pos, int value);
           

clist.c文件

#include "clist.h"

phead Creat()
{
	phead ph = (phead)malloc(sizeof(phead));
	ph->length = 0;
	ph->next = NULL;

	return ph;
}

int Init(phead ph, int pos, int value)
{
	pnode pva = (pnode)malloc(sizeof(Head));
	pva->data = value;
	pva->next = NULL;
	if (pva = NULL)
	{
		printf("结点创建错误！\n");
	}
	if (pos<0 || pos>ph->length)
	{
		printf("插入位置有误！\n");
	}

	if (pos == 1 || ph->length == 0)//插入到第一位
	{
		pnode plast;
		while (plast->next != ph->next)//让plast指针指向循环链表第一个结点上一个
		{
			plast = plast->next;
		}

		pnode pcur = ph->next;
		pva->next = pcur;
		ph->next = pva;
		plast->next = pva;
		ph->length++;
		return 1;
	}
	else
	{
		pnode pcur = ph->next;
		for (int i = 1; i < pos-1; i++)
		{
			pcur = pcur->next;
		}
		pva->next = pcur->next;
		pcur->next = pva;
		ph->length++;
		return 1;
	}
	return 0;
}

int Delete(phead ph, int pos, int value)
{
	phead ph = (phead)malloc(sizeof(Head));
	ph->length = 0;
	ph->next = NULL;

	return ph;
}

int Init(phead ph, int pos)
{
	if (pos<0 || pos>ph->length)
	{
		printf("删除位置有误！\n");
	}
	if (ph->length == 0) 
	{

	}
	if (pos == 1 )//删除到第一位
	{
		pnode plast;
		while (plast->next != ph->next)//让plast指针指向循环链表第一个结点上一个
		{
			plast = plast->next;
		}
		ph->next = ph->next->next;
		plast->next = ph->next;
		ph->length--;
		return 1;
	}
	else
	{
		pnode pcur = ph->next;
		for (int i = 1; i < pos-1; i++)
		{
			pcur = pcur->next;
		}
		pcur->next = pcur->next->next;
		ph->length--;
		return 1;
	}
	return 0;
}
           

Joseph.c

#include "clist.h"

int main()
{
	int man = 0; int n = 0;
	printf("输入约瑟夫环的数：\n");
	scanf("%d", man);
	printf("输入第几个数出局\n");
	scanf("%d", n);
	phead ph = Creat();
	printf("请逐个输入要插入的元素：\n");
	for (int i = 0; i < man;i++)
	{
		int num = 0;
		printf("请输入元素：\n");
		scanf("%d", num);
		int Re = Init(ph, 0, num);
		if (Re == 0)
		{
			printf("插入失败！\n");
		}
		else
		{
			printf("插入成功!请输入下一个>:\n");
		}
	}
	pnode pcur = ph->next;
	pnode ptmp;
	while (man != 1)
	{
		for (int i = 0; i < n-1; i++)
		{
			pcur = pcur->next;
		}
		ptmp = pcur->next;
		pcur->next = pcur->next->next;
		free(ptmp);//删除第n个元素

		pcur = pcur->next;
	}
	printf("最后剩下%d\n", pcur->data);

	system("pause");
	return 0;
}
           

2018.10.26