(三)单向循环链表

1.概念

2.初始化

3.插入、删除同单项链表一样

4.遍历

5.实例（用单向循环链表实现“数3出局”游戏（Josephu问题）。首先建立一个包含若干整数的单项循环链表，然后从第一个节点开始数，把数到3的那个节点删除，接着下一个节点开始数，数到3继续删除，以此类推，打印出最后剩余的那个节点）

// linklist.h
#ifndef _LINKLIST_H_
#define _LINKLIST_H_
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int datatype;

typedef struct linklist_node {
	datatype data;
	struct linklist_node *next;
} link_list, *link_plist;

extern void init_linklist(link_plist *H);

extern int length_linklist(link_plist l);

extern bool inster_linklist(link_plist l, int i, datatype data);

extern bool empty_linklist(link_plist l);

extern bool del_linklist(link_plist l, int i);

extern void show_linklist(link_plist l);

#endif

// linklist.c
#include "linklist.h"

void init_linklist(link_plist *H)
{
	*H = (link_plist)malloc(sizeof(link_list));
	if ((*H) == NULL) {
		perror("malloc");
		exit(1);
	}

	(*H)->next = *H;
}

// 计算链表的长度
int length_linklist(link_plist l)
{
	int i = 0;
	link_plist p = l->next;

	while (p) {
		i++;
		p = p->next;
	}

	return i;
}

// 向链表i位置插入数据data,成功返回true,失败返回false
bool inster_linklist(link_plist l, int i, datatype data)
{
	int j, length;
	link_plist new, p = l;

	length = length_linklist(l);

	// 判断i是否合法，不合法返回false
	if (i < 0 || i >length + 1) {
		printf("插入位置不合法");
		return false;
	}

	// 找到要插入新结点的位置
	for (j = 0; j < i; j++)
		p = p->next;

	// 插入数据	
	new = (link_plist)malloc(sizeof(link_list));
	if (new == NULL) {
		perror("malloc");
		return false;
	}

	new->data = data;
	new->next = p->next;
	p->next = new;

	return true;
}

// 判断链表是否为空
bool empty_linklist(link_plist l)
{
	if (l->next == l)
		return true;
	else
		return false;
}

// 向链表i位置删除数据data,成功返回true,失败返回false
bool del_linklist(link_plist l, int i)
{
	int j, length;
	link_plist p, q;

	// 判断插入位置是否合法
	length = length_linklist(l);
	if (i < 0 || i > length) {
		printf("位置不合法\n");
		return false;
	}

	// 判断是否为空
	if (empty_linklist(l)) {
		printf("链表为空\n");
		return false;
	}

	// 删除i位置的数据data
	for (j = 0, p = l; j < i; j++)
		p = p->next;

	q = p->next;
	p->next = q->next;
	free(q);

	return true;
}

// 遍历
void show_linklist(link_plist l)
{
	link_plist p;

	for (p = l->next; p == l; p = p->next)
		printf("%d\t", p->data);

	printf("\n");
}

//josephu_mian.c
#include "linklist.h"

void create_josephu(link_plist h,int n);
void show_josephu(link_plist h);
link_plist josephu(link_plist h,int n);

int main(void)
{
	link_plist h = NULL;
	link_plist p = NULL;
	int n = 0;

	init_linklist(&h);

	printf("请输入科学家人数:");
	scanf("%d", &n);
	create_josephu(h, n);
	p = josephu(h, 4);
	printf("Ths last is %d\n", p->data);

	return 0;
}

void create_josephu(link_plist h,int n)
{
	link_plist p = h;
	link_plist new = NULL;

	for (int i = 0; i < n; ++i) {
		if (i == 0) {
			h->data = i + 1;
		} else {
			new = (link_plist)malloc(sizeof(link_list));
			if (NULL == new) {
				perror("malloc");
				exit(1);
			}
			new->data = i+1;

			// 将new指向的结点插入到单项循环链表表尾
			new->next = p->next;
			p->next = new;

			// 让p指向表尾
			p = p->next;
		}

		show_josephu(h);	
	}
}


void show_josephu(link_plist h)
{
	link_plist p;
	for(p = h; p->next != h; p = p->next)
		printf("%d\t",p->data);
	printf("%d\n",p->data);
}

link_plist josephu(link_plist h, int n)
{
	link_plist p, q;
	int i;

	for(p = h; p->next != p; p = p->next){
		// 让p指向要出局的那个结点的前一个结点
		for(i = 0; i < n-2;i++)
			p = p->next;
		q = p->next;
		p->next = q->next;
		printf("%d\t",q->data);
		free(q);
	}
	printf("\n");
	return p;
}