數三出局 (鏈表實現,超詳細!)

1、通過單向鏈表實現約瑟夫問題（數三出局），然後數到三就把該節點剔除然後釋放掉該節點(基於有頭節點的情況下)

2、思路：先初始化一個頭節點，讓指針域指向自己；輸入需要參加的人數，然後新建節點，把數據放入新節點中，再把新節點插入到鏈表中，每次就插入到鏈表的末尾，插入完畢後就開始數三出局，每次跳過頭節點（必須跳過頭節點，不然會將頭節點算進來）

/*
	數三出局

 */

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

//=================設計頭節點======================
typedef struct node
{
	int data;
	struct node *next;

}loop_list,*loop_list_p;
//=================================================

//=================函數宣告=========================
loop_list_p init_list();//初始化鏈表
loop_list_p creat_node(int people);//新建節點
int insert_list(loop_list_p head,loop_list_p new);//把新節點插入到鏈表
bool list_null(loop_list_p head);//判斷鏈表是否爲空
int three_out(loop_list_p head,int num);//數三出局的程式碼
void show_list(loop_list_p head);//遍歷鏈表中的數據
void free_list(loop_list_p head);//釋放鏈表中的所有堆空間
//=================================================

int main(int argc,char **argv)
{

	while(1)
	{
		//初始化頭節點
		loop_list_p head = init_list();

		//先輸入參加的人數
		printf("please enter the number of people!\n");

		//輸入參加的人數
		int num;
		scanf("%d",&num);

		//如果輸入0就跳出回圈
		if(num==0)
		{
			break;
		}

		//回圈輸入參加的人數	
		int i,people;
		for(i=0;i<num;i++)
		{
			printf("please enter the number\n");
			scanf("%d",&people);

			//新建節點
			loop_list_p new = creat_node(people);

			//把新結點插入到鏈表
			insert_list(head,new);

			//遍歷一下鏈表
			show_list(head);
		}

		//開始數三出局
		three_out(head,num);
		free_list(head);//防止執行結束後沒有釋放完所有的堆空間

	}
}

//初始化頭節點
loop_list_p init_list()
{
	//爲頭結點申請一個堆空間記憶體
	loop_list_p head = calloc(1,sizeof(loop_list));
	if(head == NULL)
	{
		perror("apply memory failed");
		return NULL;
	}

	//初始化指針域，讓指針域指向自己
	head->next = head;

	//返回頭結點地址
	return head;
}

//新建節點
loop_list_p creat_node(int people)
{
	//爲新節點申請一個堆空間記憶體
	loop_list_p new = calloc(1,sizeof(loop_list));
	if(new == NULL)
	{
		perror("apply memory failed");
		return NULL;
	}

	//初始化數據域和節點域
	new->data = people;//把傳進來的數據存到數據域
	new->next = new;//初始化指針域，指向自己

	//返回新建節點的地址
	return new;
}

//把節點插入到鏈表
int insert_list(loop_list_p head,loop_list_p new)
{
	//判斷鏈表與新節點是否爲空
	if(list_null(head) && list_null(new))
	{
		printf("the list or new is null\n");
		return -1;
	}

	

	//鏈表不爲空的時候
	loop_list_p p = head;
	//找到最後一個
	while(p->next != head)
	{
		//不爲空就把p的下一個賦值給p
		p=p->next;
	}

	//新節點指向頭節點
	new->next = head;//新節點的下一個指向頭結點
	p->next = new;//最後一個節點p的下一個指向新節點

	return 0;
}

//判斷鏈表是否爲空
bool list_null(loop_list_p head)
{
	return head == NULL;
}

//數三出局
int three_out(loop_list_p head,int num)
{
	//判斷鏈表是否爲空
	if(list_null(head))
	{
		printf("the list or new is null\n");
		return -1;
	}

	//鏈表不爲空時,數三出局
	int i=0;
	//定義兩個變數用於遍歷鏈表
	loop_list_p p = head->next;
	loop_list_p p1 = head;

	while(1)
	{
		//每次加1
		i++;
		//如果p下一個的下一個就是自己證明只剩下自己和一個頭結點	
		if(p->next->next == p)
		{
				break;
		}
	
		
		//每次加1，直到3的時候
		if(i%3==0)
		{
		
		
			//把p的前一個指向p的下一個，然後p的下一個儲存NULL，最後釋放p
			p1->next = p->next;
			p->next  = NULL;//把p的指針域置空

			//把p釋放掉
			free(p);
			
			//判斷p1的下一個是否爲空，防止把頭結點賦值給p
			if(p1->next == head)
			{
				p = head->next;
			}
		
			//然後把p重新賦值爲p1的下一個，跳過這次回圈
			else
			{
				//如果p1的下一個不是頭結點就把p1的下一個賦值給p
				p = p1->next;
			}
		
		}	

		//如果i%3！=0就跳到下一個
		else
		{
			//只要p下一個時head就跳過head
			if(p->next == head)
			{

				p = head;
			}
			//如果p1的下一個是頭結點就跳過頭結點
			if(p1->next == head)
			{

				p1 = head;
			}

			//回圈遍歷，把下一個賦值過來
			p=p->next;
			p1=p1->next;
		}
		
		
	}
system("clear");
	//列印生還者
	printf("生還者爲：");
	printf("%d\n",p->data);

	//最後把p釋放掉
	free(p);
	return 0;
}

//遍歷鏈表
void show_list(loop_list_p head)
{
	//判斷鏈表是否爲空
	if(list_null(head))
	{
		printf("the list or new is null\n");
		return ;
	}

	//鏈表不爲NULL
	loop_list_p p = NULL;
	for(p=head->next;p!=head;p=p->next)
	{
		printf("%d\t",p->data);
	}

	printf("\n");

	return ;
}

//釋放所有節點
void free_list(loop_list_p head)
{
	//判斷鏈表是否爲空
	if(list_null(head))
	{
		printf("the list is null\n");
		return ;
	}

	//只要不爲空，定義兩個變數遍歷鏈表
	loop_list_p p = NULL;
	loop_list_p p1 = NULL;
	//如果p不等於頭結點，就釋放p，然後把p1的值賦值過來，p1繼續調到下一個
	for(p = head,p1=head->next;p!=head;p=p1,p1=p1->next)
	{
		p=p->next;
		free(p);
	}

	//返回空
	return ;
}

我這裏爲防止最後沒有釋放完鏈表中的數據，因此加多了一個函數來判斷是否釋放完所有節點，如果沒有釋放完就把它釋放掉