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

struct Link
{	int data;
	struct Link *next;
};
struct Link *head;			/*建立一個指向鏈表頭的全局變量*/

struct Link *CreateNode(int nodeNumbers);
struct Link *InsertNode(struct Link *head, int tData );
void DispLink(struct Link *head);
struct Link *DelNode(struct Link *head, long num);
void DeleteMemory(struct Link *head);

void main()
{	int i=0;
	struct Link *pr;
	char c;
	head = NULL;/*開始時是空鏈表*/
	while(1)/*循環實現建立鏈表*/
	{	printf("\nPlease press 'y' to insert one new node,press 'n' to finish:");
		c = getchar();
		/* 如果鍵入既不是' y '，又不是'n'則循環繼續進行 */
		if ((c!='y'||c!='Y')&&(c!='n'||c!='N'))
		{   
			puts("you must input 'y' or 'n'");
			continue;		
		}
		if ((c=='n'||c=='N'))
			break;		/* 如果鍵入的是'n'循環退出 */
	    if (i==0)/* 如果是第一個節點,將新節點鏈至頭節點后*/
	    {   head=CreateNode(i); 
			pr = head;//使用pr跟蹤當前節點的前一個節點
		}
		else/* 不是第一個節點，將新建節點接到鏈表的結尾pr處 */
		{	pr->next = CreateNode(i);  
			pr = pr->next;//使用pr跟蹤當前節點的前一個節點
		}
	    	i++;
	}
	DispLink(head);
	DeleteMemory(head);
}

/*  函數功能：建立一個新的節點，并為該節點賦初值
	函數的參數：整型變量nodeNumbers，表示建立的節點個數
	函數的返回值：為指向該節點的指針
*/
struct Link *CreateNode(int nodeNumbers)
{
	struct Link *p;
/* 動態申請一段內存 */
	p = (struct Link *)malloc(sizeof(struct Link));  
	if(p == NULL)          /* 如果返回空指針，申請失敗，打印錯誤信息，退出程序 */
	{	printf("No enough memory to alloc");
		exit(0);						/*結束程序運行*/
	}
    /*為新建節點賦值*/
	p->next = NULL;					  	/* 新建的節點指針域賦空指針 */
	p->data = nodeNumbers * 10;	       	/* 為新建的節點數據區賦值 */
    /*返回指向新建節點的指針*/
	printf("\nCreate a new node!");
	return p;       
}

/*	函數功能：在鏈表中插入一個節點
 	函數參數：結構體指針變量head，表示指向鏈表頭指針
			整型變量tData，表示插入的節點的數據區的內容
 	返回參數：指向鏈表頭指針
*/
struct Link *InsertNode(struct Link *head, int tData )
{
	struct Link *pr,*p;

	/* 申請一段內存，建立一個新的節點*/
	p = (struct Link *)malloc(sizeof(struct Link));	
	if (p == NULL)    			/*如果申請失敗，則退出程序 */
	{	printf("Can`t enough memory to alloc");
		exit(0);			   								 
	}
	pr = head;
    /*為新節點賦值*/
	p->next = NULL;			  	/* 新的節點的指針域賦為空地值 */
	p->data = tData*10;			/* 新的節點數據區域賦值 */
	/*插入相應位置*/
if (head == NULL) /* 如果鏈表原為空的，新節點作為頭節點 */
	{	head = p;
  	}
	else 
	{	/* 找要插入的位置，pr指向插入位置的前一個節點。
設鏈表已經按由小到大排完序*/
		while (pr->data < tData*10 && pr->next != NULL)
       	{	pr = pr->next;	 
		}
		/*插入到頭節點的后邊*/
if (pr == head)       		/*如果是在第一個節點前插入新節點*/
		{
			p->next = head;
			head = p;
			return head;		   	/* 返回頭節點指針 */
		}
		/*插入到鏈表尾部，pr指向尾部*/
if (pr->next == NULL)	   	/*如果是在表尾插入新節點*/
		{
			pr->next = p;		               
		}
	/*插入到鏈表中間pr節點的后邊*/
else              			/*如果是在鏈表中間插入新節點*/
		{
			p->next = pr->next;		/* 插入到鏈表中間位置 */
			pr->next = p;
		}
	}
	return head;					/* 返回頭節點指針 */
}








/* 	函數的功能：顯示所有已經建立好的節點的節點號，和該節點中數據項內容
	函數的參數：結構體指針變量head，表示指向鏈表的頭指針
	函數的返回值：無
*/
void DispLink(struct Link *head)
{	struct Link *p;
	int j=1;
	p = head;
	do{
		printf("\n%5d%10d\n",j,p->data);
		p = p->next;
		j++;
	}while(p!=NULL);
}

/*	函數功能：從head指向的鏈表中刪除第一個含有數據成員num的節點
 	輸入參數：結構體指針變量head，表示指向鏈表頭指針
    		     長整型變量num，表示要查找的節點中包含的數據成員的數值
 	返回參數：指向鏈表頭指針
*/
struct Link *DelNode(struct Link *head, long num)
{
	struct Link *p,*pr;
	if (head == NULL)
	{
		printf("\nNo Linked Table");/* 如果head為空，意味著沒有鏈表存在 */
		return(head);
	}
	p = head;
    /*如果沒找到數據為num的節點，且鏈表還沒有結束，則繼續移動節點，
	  直到找到或者到鏈表的結尾為止*/	
	while (num != p -> data && p -> next != NULL) 		
	{				            		
		pr = p;
		p = p->next;
	}/*找到后pr指向要刪除節點的前一個節點，p指向要刪除的節點*/
	/*找到，則刪除*/
if (num == p->data)           /* 發現了節點，準備刪除 */
	{				     		
		if (p == head)   /*如果發現的是第一個節點，將第二個節點的地址賦予head */
			head = p -> next;  			
		
		else   /*如果發現的是中間節點，則將上個節點的指針指向本節點的下一個節點*/
			pr -> next = p->next;	  									  		
		free(p);			/*刪除節點后應將其動態分配的內存釋放掉*/
		printf("delete the node");
	}
	else 
    {/*沒找到給出提示*/
		printf("\nNot found the Node");
    }
	return head;
}

void DeleteMemory(struct Link *head)
{
	struct Link *p = head, *pr = NULL;

	while (p != NULL)           	/*若不是表尾，則釋放節點占用的內存*/
	{	
		pr = p;                  	/*在pr中保存當前節點的指針*/
		p = p->next;            	/*讓p指向下一個節點*/
		free(pr);                	/*釋放pr指向的當前節點占用的內存*/
	}            
}