#include "stdio.h"				
#include "stdlib.h"				//提供malloc()和free()
#include "string.h"				//提供strcpy()等

struct Node
{
	int a;				//數(shù)據(jù)域
	struct Node* next;	//指針域(指向節(jié)點(diǎn)的指針）
};

struct Node* head= NULL;
struct Node* end = NULL;

void AddListTill(int a )
{
		//創(chuàng)建一個(gè)節(jié)點(diǎn)
		struct Node* temp=(struct Node*)malloc(sizeof(struct Node));		//此處注意強(qiáng)制類型轉(zhuǎn)換

		//節(jié)點(diǎn)數(shù)據(jù)進(jìn)行賦值
		temp->a=a;
		temp->next=NULL;		
		
		//連接分兩種情況1.一個(gè)節(jié)點(diǎn)都沒有2.已經(jīng)有節(jié)點(diǎn)了，添加到尾巴上
		if(NULL==head)
		{	

			head=temp;
		//	end=temp;
		}
		else
		{
		end->next=temp;
	//	end=temp;			//尾結(jié)點(diǎn)應(yīng)該始終指向最后一個(gè)
		}
		end=temp;			//尾結(jié)點(diǎn)應(yīng)該始終指向最后一個(gè)
}

void ScanList()
{
	struct Node *temp =head;		//定義一個(gè)臨時(shí)變量來指向頭
	while (temp !=NULL)
	{
		printf("%d\n",temp->a);
		temp = temp->next;		//temp指向下一個(gè)的地址 即實(shí)現(xiàn)++操作
	}

}

struct Node* FindNode(int a )
{
	struct Node *temp =head;
	while(temp !=NULL)
	{
	if(a == temp->a)
	{
		return temp;
	}
	temp = temp->next;
	}
	//沒找到
		return NULL;
} 

void FreeList()
{
	//一個(gè)一個(gè)NULL
	struct Node *temp =head;		//定義一個(gè)臨時(shí)變量來指向頭
	while (temp !=NULL)
	{
	//	printf("%d\n",temp->a);
		struct Node* pt =temp;
		temp = temp->next;		//temp指向下一個(gè)的地址 即實(shí)現(xiàn)++操作
		free(pt);					//釋放當(dāng)前
	}
	//頭尾清空	不然下次的頭就接著0x10
	head =NULL;
	end =NULL;
}

void AddListRand(int index,int a)
{	

    if (NULL==head)
	{
		printf("鏈表沒有節(jié)點(diǎn)\n");
		return;
	}	
    struct Node* pt =FindNode(index);
	if(NULL==pt)    //沒有此節(jié)點(diǎn)
	{
		printf("沒有指定節(jié)點(diǎn)\n");
		return;
	}
    //有此節(jié)點(diǎn)
    //創(chuàng)建臨時(shí)節(jié)點(diǎn)，申請(qǐng)內(nèi)存
	struct Node* temp =(struct Node *)malloc(sizeof(struct Node));
	//節(jié)點(diǎn)成員進(jìn)行賦值
	temp->a=a;
	temp->next=NULL;
	//連接到鏈表上 1.找到的節(jié)點(diǎn)在尾部 2.找到的節(jié)點(diǎn)在中間 
	if (pt == end)
	{
	//尾巴的下一個(gè)指向新插入的節(jié)點(diǎn)
	end->next=temp;
	//新的尾巴
	end=temp;
	}else
	{
	// 先連后面 （先將要插入的節(jié)點(diǎn)指針指向原來找到節(jié)點(diǎn)的下一個(gè)）
	temp->next=pt->next;
	//后連前面
	pt->next=temp;
	}

}

void DeleteListTail()
{ 
	if (NULL == end)
	{
		printf("鏈表為空，無需刪除\n");
		return;
	}
	//鏈表不為空 
	//鏈表有一個(gè)節(jié)點(diǎn)
	 if (head==end)
	 {
		 free(head);
		 head=NULL;
		 end=NULL; 
	 }
	 else
	 {
		//找到尾巴前一個(gè)節(jié)點(diǎn)
		 struct Node* temp =head;
		 while (temp->next!=end)
		 {
			 temp = temp->next;
		 }
		 //找到了，刪尾巴
		//釋放尾巴
		 free(end);
		 //尾巴遷移
		 end=temp;
		 //尾巴指針為NULL
		 end->next=NULL;
	 }

}

void DeleteListHead()
{	//記住舊頭
	struct Node* temp=head;
	//鏈表檢測(cè) 
	if (NULL==head)
	{
			printf("鏈表為空\(chéng)n");
			return;
	}

	head=head->next;//頭的第二個(gè)節(jié)點(diǎn)變成新的頭
	free(temp);

}

void DeleteListRand(int a)
{

	//鏈表判斷 是不是沒有東西
	if(NULL==head)
	{
	printf("鏈表沒東西\n");
	return;
	}
    //鏈表有東西，找這個(gè)節(jié)點(diǎn)
	struct Node* temp =FindNode(a);
	if(NULL==temp)
	{
	printf("查無此點(diǎn)\n");
	return;
	}
	//找到了,且只有一個(gè)節(jié)點(diǎn)
	if(head==end)
	{
	free(head);
	head=NULL;
	end=NULL;
	}
	else if(head->next==end) //有兩個(gè)節(jié)點(diǎn)
	{
	//看是刪除頭還是刪除尾
	if(end==temp)
		{	DeleteListTail(); }
	else if(temp==head)
		{	DeleteListHead(); }	
	}
	else//多個(gè)節(jié)點(diǎn)
	{
		//看是刪除頭還是刪除尾
		if(end==temp)
			DeleteListTail();
		else if(temp==head)
			DeleteListHead();	
		else	//刪除中間某個(gè)節(jié)點(diǎn)
		{	//找要?jiǎng)h除temp前一個(gè)，遍歷
			struct Node*pt =head;
			while(pt->next!=temp)
			{
			pt=pt->next;
			}
			//找到了
			//讓前一個(gè)直接連接后一個(gè) 跳過指定的即可
			 pt->next=temp->next;
			 free(temp);
		
		}
	}
	

}

void main ()
{	
	struct Node *pFind ;
	//創(chuàng)建5個(gè)節(jié)點(diǎn)
	for(i=0;i<6;i++)
	AddListTill(i);
	
//	AddListRand(4,14);		//在指定位置4增加節(jié)點(diǎn)14
//	DeleteListTail();		//刪除一個(gè)尾結(jié)點(diǎn)
	DeleteListRand(4);		//刪除4節(jié)點(diǎn)
	ScanList();				//便利輸出鏈表
	FreeList();				//刪除鏈表
/*	pFind = FindNode(5);	//查找5節(jié)點(diǎn)

	if (pFind !=  NULL)
	{
		printf("找到%d\n",pFind->a);	//找到節(jié)點(diǎn)并且輸出該節(jié)點(diǎn)數(shù)據(jù)
	}
	else
	{
		printf("No Find!\n");
	}

*/

}