/*********************************************/
/***********    带头结点的方法     ***********/
/*******************************************/

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

/* 定义结构体 */
typedef struct Node
{
	int data;			//数据域
	struct Node * pNext;//指针域
}NODE, * PNODE;         //由于使用了typedef, 所以NODE <=> struct Node  ,  PNODE <=> struct Node * 

/* 函数声明 */
PNODE create_list();				//创建一个链表
void traverse_list(PNODE pHead);	        //遍历整个链表并输出
bool is_empty(PNODE pHead);			//判断链表是否为空
void search_list(PNODE pHead, int val);		//链表的查找
bool insert_list(PNODE pHead, int pos, int value);	//链表的插入
bool delete_list(PNODE pHead, int pos, int * pval);	//链表的删除

/* 主函数 */
int main()
{
	PNODE pHead = NULL;  //头指针为空，用来保存头结点的地址
	int val;			 //用来保存删除的元素
	int location;        //保存查找元素的位置 

	pHead = create_list(); //创建一个链表，并返回头结点的地址给pHead

	traverse_list(pHead);  //遍历整个链表

	if(is_empty(pHead))	   //判断链表是否为空
	{
		printf("\n链表为空\n");
	}
	else
	{
		printf("\n链表非空\n");
	}

	int s_val;
	printf("请输入你要查找的元素： ");
	scanf("%d", &s_val);
	search_list(pHead, s_val);

	int pos, i_val;
	printf("\n请输入你要插入的位置： ");
	scanf("%d", &pos); 
	printf("请输入你要插入的元素： ");
	scanf("%d", &i_val); 
	insert_list(pHead, pos, i_val);
	printf("链表插入后");
	traverse_list(pHead); 

	printf("\n请输入你要删除的位置： ");
	scanf("%d", &pos); 
	if( delete_list(pHead, pos, &val) )
	{
		printf("删除成功，您删除的元素是：%d\n", val);
	}
	else
	{
		printf("删除失败！您删除的元素不存在!\n");
	}
	printf("链表删除后");
	traverse_list(pHead); 

	return 0;
}

/* 调用函数 */
/*———————————————————————————————————————————————————————*/
PNODE create_list()
{
	int len;      //用来存放有效节点的个数
	int i;
	int temp_val; //临时存放用户输入结点数据域的值

	PNODE pNew;   //新结点先定义好，防止浪费空间
	
	//分配一个不存放有效数据的头结点
	PNODE pHead = (PNODE)malloc(sizeof(NODE));
	if(NULL == pHead)    {printf("分配失败，程序终止！"); exit(-1);}

	PNODE pTemp = pHead; //临时存放头结点的地址
	pTemp->pNext = NULL;

	printf("请输入您要生成的链表节点的个数： len = ");
	scanf("%d", &len);

	for(i = 0; i<len; i++)
	{
		printf("请输入第%d个节点数据域的值 ：", i+1);
		scanf("%d", &temp_val);
		
		//循环一次分配一个存放有效数据的结点
		pNew = (PNODE)malloc(sizeof(NODE));
		if(NULL ==pNew)     {printf("分配失败，程序终止！"); exit(-1);}

		//尾插法
		pNew->data = temp_val;
		pTemp->pNext = pNew;
		pNew->pNext = NULL;  //每分配一个结点,这个结点就是最后一个,所以它的指针域（pNext）为空
		pTemp = pNew;        //保证前一个结点的指针域都指向后一个结点
	}

	return pHead;  //返回头结点的地址
}
/*———————————————————————————————————————————————————————*/
void traverse_list(PNODE pHead)
{
	PNODE p = pHead->pNext;  //头结点的指针域赋给p,即首结点赋给p 【注意区分头结点和首结点】

	printf("链表的数据为：\n");
	while(NULL != p)
	{
		printf("%d ", p->data);
		p = p->pNext;        //下一个结点赋给p
	}

	printf("\n");
}
/*———————————————————————————————————————————————————————*/
bool is_empty(PNODE pHead)
{
	if(NULL == pHead->pNext)
	{
		return true;
	}
	else
	{
		return false;
	}
}
/*———————————————————————————————————————————————————————*/
/*第一版	
	while (NULL != p)       //只要指针域指向的不是空结点就不结束
	{
		if (p->data != val)
		{
			count++;
			status = 0;
		}
		if (p->data == val)
		{
			printf("找到了！\n");
			printf("%d的位置是: %d\n\n", val, count + 1);
			status = 1;
			break; 	  //核心语句 
		}

		p = p->pNext;
	}

	if (status == 0)
	{
		printf("没找到！\n");
	}
*/
	//第二版
	//while (NULL != p)       //只要指针域指向的不是空结点就不结束
	//{
	//	if (p->data != val)
	//	{
	//		count++;
	//		status = 0;
	//	}
	//	if (p->data == val)
	//	{
	//		printf("找到了！\n");
	//		printf("%d的位置是: %d\n\n", val, count + 1);
	//		break; 	  //核心语句 
	//	}
	//	p = p->pNext;
	//}

	//if (status == 0)
	//{
	//	printf("没找到！\n");
	//}
	
	//最终版 
	while (NULL != p)       //只要指针域指向的不是空结点就不结束
	{
		count++;
		if (p->data == val)
		{
			printf("找到了！\n%d的位置是: %d\n\n", val, count);
			break; 	  //核心语句 
		}
		p = p->pNext;
	}
	if (NULL == p || p->data != val)
	{
		printf("没找到！\n");
	}
}
/*———————————————————————————————————————————————————————*/
//数组与链表存储方式虽不同，但是它们的算法是一样的
/*———————————————————————————————————————————————————————*/
//在pHead所指向链表的第pos个节点的前面插入一个新的结点,假定pos为3
bool insert_list(PNODE pHead, int pos, int value)
{
	int i = 0;
	PNODE p = pHead;

	while(NULL != p && i<pos-1) //i<3-1=2, 取值为0、1，循环执行了两次，p指向了第二个有效结点
	{
		p = p->pNext;
		i++;
	}
	if(NULL == p || i>pos-1)
	{
		return false;
	}

	//如果程序能执行到这一行说明p已经指向了第pos-1个结点,但第pos-1个节点是否存在无所谓
	//分配需要插入的结点
	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	if(NULL == pNew)    {printf("动态分配内存失败！"); exit(-1);}

	pNew->data = value;

	//将新的结点存入p节点的后面【即第pos个节点的前面】，若没明白请回头学习如何插入节点
	PNODE q;
	q = p->pNext;
	p->pNext = pNew;
	pNew->pNext = q;

	return true;
}
/*———————————————————————————————————————————————————————*/
//删除第pos个结点，假定pos为3
bool delete_list(PNODE pHead, int pos, int * pval)
{
	int i = 0;
	PNODE p = pHead;

	while(NULL != p->pNext && i<pos-1)//i<3-1=2, 取值为0、1，循环执行了两次，p指向了第二个结点
	{
		p = p->pNext;
		i++;
	}
	if(NULL == p->pNext && i>pos-1)
	{
		return false;
	}

	//如果程序能执行到这一行说明p已经指向了第pos-1个结点，并且第pos个节点是存在的
	//这里的指向解释一下：通俗的说就是等于这个结点的意思

	PNODE q = p->pNext; //q指向待删除的结点

	*pval = q->data;    //返回删除的值

	//删除p节点后面的结点，若没明白请回头学习如何删除节点
	p->pNext = p->pNext->pNext;
	free(q);			//释放q所指向的节点所占的内存
	q = NULL;			//q = p->pNext = NULL，表示p指针域指向的结点已被删除
	
	return true;
}
/*———————————————————————————————————————————————————————*/