数据结构——链表——带头结点的单向循环链表

带头结点的单向循环链表

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

/*
	功能：创建一个空链表
	参数：无
	返回值：
		失败返回NULL
		成功返回头结点的地址
*/
List * createLkList()
{
	List * list = (List *)malloc(sizeof(List));
	if(list == NULL)
	{
		printf("malloc fail\n");
		return NULL;//失败返回NULL
	}

	list->first = NULL;
	list->last = NULL;
	list->n = 0;//现在还是空链表
	return list;
}

/*
	功能：往链表中插入一个元素
	参数：
		@list	头结点的地址
		@x		待插入的数据
	返回值：无
*/

void insert(List * list,ElemType x)
{

	//1，分配空间
	Node * p = (Node *)malloc(sizeof(Node));

	//2，保存数据
	p->data = x;
	p->next = NULL;

	//3，把该节点插入到链表中
	if(list->first == NULL)//if(list->n == n)
	{
		list->first = p;
		list->last = p; 
	}
	else
	{
		#if 1
			//尾插法
			list->last->next = p;
			list->last = p;
		#else
			//头插法
			p->next = list->first;
			list->first = p;
		#endif
		
	}
	//首尾相连
	list->last->next = list->first;
	list->n ++;
	
}

void printfLkList(List * l)
{
	Node * p = l->first;

	int i;
	for(i=0;i<l->n;i++)
	{
		printf("%d ",p->data);
		p = p->next;
	}
	
	printf("\n");
}


void cleanList(List *list)
{
	Node * p = list->first;
	Node * q = NULL;
	int i;
	for(i=0;i<list->n;i++)
	{
		q = p->next;
		p->next = NULL;
		free(p);
		p = q;
	}
	list->first=list->last=NULL;
	list->n = 0;
}

void destroyList(List * list)
{
	cleanList(list);
	free(list);
}

int find(List * list,ElemType x)
{
	Node * p = list->first;

	int i;
	for(i=0;i<list->n;i++)
	{
		if(p->data == x)
		{
			return 1;
		}
		p = p->next;
	}
	return 0;

}

//有序
void insertElem(List * list,ElemType x)
{
	Node * p = (Node *)malloc(sizeof(Node));

	p->data = x;
	p->next = NULL;

	Node * q = list->first;
	Node * r = NULL;
	int i;
	//找到第一个比他大的元素
	for(i=0;i<list->n;i++)
	{
		if(q->data > x)
		{
			break;
		}
		r = q;
		q = q->next;
	}

	if(i == list->n)//没找到
	{
		r->next = p;
		p->next = NULL;
		list->last = p;
		p->next = list->first;
	}
	else if(q == list->first)//第一个就比我大
	{
		p->next = list->first;
		list->first = p;
		list->last->next = p;
	}
	else//中间位置
	{
		r->next = p;
		p->next = q;
	}

	list->n ++;
}



void delete(List * list,ElemType x)
{
	Node * p = list->first;
	Node * r = NULL;
	int i;
	for(i=0;i<list->n;i++)
	{
		if(p->data == x)
		{
			break;
		}
		r = p;
		p = p->next;
	}

	if(i<list->n)//找到了
	{
		//分情况删除
		if(p == list->first)//删除的是第一个
		{
			list->first = p->next;
			p->next = NULL;
			free(p);
			list->last->next = list->first;
		}
		else if(p == list->last)//删除的是最后一个
		{
			list->last = r;
			r->next = NULL;
			p->next = NULL;
			free(p);
			list->last->next = list->first;
		}
		else//中间
		{
			r->next = p->next;
			p->next = NULL;
			free(p);
		}
		list->n --;
	}

}

//约瑟夫问题
int Joseph(int n,int m)
{
	List * list = createLkList();
	int i;
	for(i=1;i<=n;i++)
		insert(list,i);

	Node * p = list->first;
	Node * q = NULL;
	printfLkList(list);
	int conut = 0;
	while(list->n > 1)
	{
		conut++;
		q = p->next;
		if(conut == m)
		{
			
			delete(list,p->data);
			conut = 0;
		}

		p = q;

	}
	int x = list->first->data;
	printfLkList(list);
	destroyList(list);
	return x;
}