循环链表的生成

在之前带有头结点的链表的基础上，构建链表的时候，最后一个结点的指针域指向头结点的后继，即尾结点的后驱为头结点的后继。在之后功能的Coding中，要注意遍历完整个链表一次的标志是到达头结点的后继！

要求

实验四、线性表应用--约瑟夫环问题

1 实验目的

用循环链表解决约瑟夫问题。

2 实验内容

约瑟夫问题是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各人的编号

3 实验过程

（1）：

（截图）

（2） ：

（截图）

（3） ：

（截图）

 

4 源代码

（附件）

 具体代码如下：

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

//******宏定义参数******
#define OK 1
#define NO 0
#define DATA_MAX_SIZE 20

//******定义数据类型别名******
typedef int Status;
typedef char Excelelem;
typedef int Numelem;

//******声明数据结构******
typedef struct Node
{
	Numelem book;
	struct Node *next;
}LNode,*LinkList;

typedef struct
{
	Excelelem name[100];
	Numelem length;
	LinkList next;
}HeadList,*HeadLinkList;

//******初始化链表******
LinkList init(Numelem *n)
{
	LinkList Head,p,q;
	Numelem i;
	Head=p=NULL;
	for(i=1;i<=*n;i++)
	{
		q=(LinkList)malloc(sizeof(LNode));
		q->book=i;
		if(i==1) Head=p=q;
		else
		{
			p->next=q;
			p=q;
		}
	}
	if(p) p->next=Head;
	return Head;
}

HeadLinkList HeadInit(int n)
{
	//省略表头信息  Head->name
	HeadLinkList Head;
	Head=(HeadLinkList)malloc(sizeof(HeadList));
	Head->length=n;
	Head->next=init(&Head->length);
	return Head;
}

void DATA_Joseph(HeadLinkList Head,int n,int k)
{
	LinkList p=Head->next,q;
	Excelelem i,cnt=1;
	if(!Head->length)
	{
		printf("该约瑟夫环已无操作元素!\n");
		return ;
	}
	while(n!=p->book)
	{
		p=p->next;
		if(p==Head->next)
		{
			printf("不存在编号为%d的入口!\n",n);
			return ;
		}
	}
	while(1)
	{
		for(i=1;i<k;i++)
			q=p,p=p->next;
		printf("第%d次时,第%d个元素出环!\n",cnt++,p->book);
		Head->length--;
		if(Head->length==0)
		{
			Head->next=NULL;
			free(p);
			break;
		}
		else
		{
			q->next=p->next;
			free(p);
			p=q->next;
		}
	}
	printf("该约瑟夫环已无操作元素!\n");
	return ;
}

int main()
{
	HeadLinkList Head;
	Numelem n,m;
	printf("**********start!**********\n");
	printf("请输入约瑟夫环的规模!\n");
	scanf("%d",&n);
	Head=HeadInit(n);
	printf("请输入约瑟夫环的入口!\n");
	scanf("%d",&m);
	printf("请输入约瑟夫环每次的出环规模!\n");
	scanf("%d",&n);
	printf("请检查约瑟夫环的操作情况!\n");
	DATA_Joseph(Head,m,n);
	free(Head);
	printf("**********End!**********\n");
	return 0;
}

总结：

在约瑟夫环问题中，链表的算法是一种朴素的模拟过程，在之前的顺序表（例如：数组），也可以模拟这个过程，这时就要用取模符号进行实现循环，类似于之后的顺序表循环队列的过程！当然，顺序表模拟的时候可以用个bool来判断该节点是否出环了。