数据结构C语言版（清华大学

//数据结构C语言版（清华大学_唐国民_第3版）
//单链表,书 P36 例子2.5.1 约瑟夫问题，与书上代码有些许出入，不用在意，重要的是思路
#include 
#include 

typedef int ElementType;
typedef struct LNode* List;
struct LNode {
	ElementType Data;
	List Next;
};

void Joseph(List Prtl,int n, int s, int m);
void Create(List Prtl,int n);

int main()
{
	int n, s, m;
	List Prtl = (List)malloc(sizeof(struct LNode));
	Prtl->Next = NULL;
	printf("总人数为？\n");
	scanf("%d", &n);
	printf("从第几个人开始报数？\n");
	scanf("%d", &s);
	printf("数到数字几的人出列？\n");
	scanf("%d", &m);
	printf("输出如下：\n");
	if (n <= 0 || s <= 0 || m <= 0 || n < s) {
		printf("不合法!\n");
		return 0;
	}
	Create(Prtl, n);
	Joseph(Prtl, n, s, m);
	return 0;
}

void Create(List Prtl, int n)
{
	List q = Prtl;
	List p;
	int i;
	for (i = 1; i <= n; ++i) {
		p = (List)malloc(sizeof(struct LNode));
		p->Data = i;
		p->Next = NULL;
		q->Next = p;
		q = p;
	}
}

void Joseph(List Prtl,int n,int s,int m)
{
	int i, j;
	List p, q;
	q = Prtl;
	for (i = 1; i <= s - 1; ++i) {
		q = q->Next;
	}
	p = q->Next;
	for (i = 1; i <= n - 1; ++i) {
		for (j = 1; j <= m - 1; ++j) {
			if (p->Next != NULL && q->Next != NULL) {
				p = p->Next;
				q = q->Next;
			}
			else if (p->Next == NULL && q->Next != NULL) {
				p = Prtl->Next;
				q = q->Next;
			}
			else {
				p = p->Next;
				q = Prtl->Next;
			}
		}
		printf("%d\n", p->Data);
		List r = p;
		if (p->Next == NULL) {
			p = Prtl->Next;
			q->Next = NULL;
		}
		else {
			p = p->Next;
			if (q->Next != NULL) {
				q->Next = p;
			}
			else {
				Prtl->Next = p;
			}
		}
		free(r);
	}
	printf("%d\n",(Prtl->Next)->Data);
}