约瑟夫生者死者游戏 数据结构作业

题目1：约瑟夫生者死者游戏 实验类型（验证/设计/创新）：设计 学时：10
课程设计内容：
有N个旅客同乘一条船，因为严重超载，加上风高浪大，危险万分；因此船长告诉乘客，只有将全船一半的旅客投入海中，其余人才能幸免于难；无奈，大家只得同意这种办法，并议定N个人围成一圈，由第一个人开始，依次报数，数到第9人，便把他投入大海中，然后再从他的下一个人开始，数到第9人，再把他投入大海中，如此循环地进行，直到剩下N/2个乘客为止。问哪些乘客是将被投入大海的？输出这些乘客的姓名和位置。
课程设计要求：
掌握单循环链表结构下的基本操作实现算法；能够运用单循环链表的结构特点实现本游戏规则。
重点难点：
【本课程设计重点】单循环链表的结构特点和存储。
【本课程设计难点】单循环链表的建立和表中结点的删除。

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

typedef struct node {
	int data;
	struct node* next;
}ListNode, * LinkList;


LinkList InitRing(int n, LinkList R)
{
	ListNode* p=NULL, * q;
	int i;
	R = q = (ListNode*)malloc(sizeof(ListNode));
	for (i = 1; i < n; i++) {
		p = (ListNode*)malloc(sizeof(ListNode));
		q->data = i;
		q->next = p;
		q = p;
	}
	p->data = n;
	//P->data=n;
	p->next = R;
	R = p;
	return R;
}


LinkList DeleteDeath(int n, int k, LinkList R)
{
	int i, j;
	ListNode* p, * q;
	p = R;
	printf("抛入大海者的编号如下：\n");
	for (i = 1; i <= n / 2; i++)
	{
		for (j = 1; j <= k - 1; j++)
		{
			p = p->next;
		}
		q = p->next;
		p->next = q->next;
		printf("%4d", q->data);
		if (i % 10 == 0) printf("\n");
		free(q);
	}
	printf("\n");
	R = p;
	return R;
}

void OutRing(int n, LinkList R)
{
	int i;
	ListNode* p;
	p = R;
	printf("幸存者的编号如下：\n");
	for (i = 1; i <= (n + 1) / 2; i++, p = p->next)
	{
		printf("%4d", p->data);
		if (i % 10 == 0) printf("\n");
	}
	printf("\n");
}


int main(void)
{
	LinkList R = NULL;
	int n, k;
	LinkList InitRing(int n, LinkList R);
	LinkList DeleteDeath(int n, int k, LinkList R);
	void OutRing(int n, LinkList R);
	printf("输入总人数 n 及报数上限 k :");
	scanf_s("%d%d", &n, &k);
	R = InitRing(n, R);
	R = DeleteDeath(n, k, R);
	OutRing(n, R);
	//scanf_s("%d", &n);
}

结果：