#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <stdbool.h>
typedef int ElemType;

typedef struct Lnode{
	ElemType data;
	struct Lnode * next;
}LNode, * LinkList;

/*
	链表初始化 
*/
void InitList_L(LinkList L){
	L = (LinkList)malloc(sizeof(LNode));
	if(L == NULL)exit(-1);
	L->next = NULL;
}

/*
	判断链表是否为空 
*/
bool ListEmpty(LinkList L){
	if(L->next == NULL) return true;
	return false;
}

/*
	销毁单链表 
*/
void DestoryList_L(LinkList L){
	LinkList p;
	while(L){
		p = L;
		L = L->next;
		free(p);
	}
}

/*
	清空单链表 
*/ 
void ClearList_L(LinkList L){
	LinkList p, q;
	p = L->next;
	while(p){
		q = p->next;
		free(p);
		p = q;
	}
	L->next = NULL;
}

/*
	求单链表L的长度 
*/
int ListLength_L(LinkList L){
	int len = 0;
	LinkList p;
	p = L->next;
	while(p){
		p = p->next;
		len++;
	}
	return len;
}

/*
	取值：取单链表中第i个元素的内容 
*/
int  GetElem_L(LinkList L, int i, ElemType * e){
	LinkList p;
	p = L->next;
	int j = 1;
	while(p && i > j){
		p = p->next;
		j++;
	}
	if(!p || j > i ) return -1;
	*e = p->data;
	return 1;
}
/*
	查找：按值查找：根据指定数据获取数据所在位置（地址） 
*/
LinkList LocateElem_L(LinkList L, ElemType e){
	LinkList p;
	p = L->next;
	while(p && p->data != e){
		p = p->next;
	}
	return p;
}

/*
	查找：按值查找：根据指定数据获取数据所在位置（序号）
*/
int LocateElem_L2(LinkList L, ElemType e){
	LinkList p;
	p = L->next;
	int j = 1;
	while(p && p->data != e){
		p = p->next;
		j++;
	}
	if(p)return j;
	else return 0;
}

/*
	插入：在第i后结点插入新结点 
*/
int ListInsert_L(LinkList L, int i, ElemType e){
	LinkList p;
	p = L;
	int j = 0;
	while(p && i-1 > j){
		p = p->next;
		j++;
	}
	if(!p || j > i - 1) return -1;
	LinkList s = (LinkList)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return 1;
}

/*
	单链表的建立：头插法 
*/
LinkList CreateList_H(){
	int len;
	int val;
	LinkList L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;
	printf("请输入您要生成的链表节点个数:len=");
	scanf("%d", &len);
	int i;
	for(i = 0; i < len; i++){		
		printf("请输入第%d个节点的值:", i + 1);
		scanf("%d", &val);
		LinkList p = (LinkList)malloc(sizeof(LNode));
		p->data = val;
		p->next = L->next;
		L->next = p;
	}
	return L;
} 

/*
	单链表的建立：尾插法 
*/
LinkList CreateList_R(){
	LinkList L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;
	int len; 
	printf("请输入您要生成的链表节点个数:len=");
	scanf("%d", &len);
	int i;
	LinkList r = L;
	int val;
	for(i = 0; i < len; i++){		
		printf("请输入第%d个节点的值:", i + 1);
		scanf("%d", &val);
		LinkList p = (LinkList)malloc(sizeof(LNode));
		p->data = val;
		p->next = NULL;
		r->next = p;
		r = p;
	}
	return L;
}

/*
	删除：删除第i个结点 
*/
int ListDelete_L(LinkList L, int i, ElemType * e){
	LinkList p;
	p = L;
	int j = 0;
	while(p && j < i - 1){
		p = p->next;
		j++;
	}
	if(!p || j > i - 1) return -1;
	LinkList q;
	q = p->next;
	p->next = q->next;
	*e = q->data;
	free(q);
	return 1;
} 

/*
	链表的遍历 
*/
void traverse_list(LinkList L){
	LinkList p;
	p = L->next;
	while(p){
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
	return;
}
int main(){
	LinkList L;
	/***************头插法创建链表*************************/
	//L = CreateList_H();
	/***************尾插法创建链表*************************/
	L = CreateList_R(); 
	/***************销毁单链表*************************/
	//DestoryList_L(L); 
	/***************清空单链表 *************************/
	//ClearList_L(L);
	/***************求单链表的长度*************************/
	//printf("表长为：%d\n", ListLength_L(L));
	/*****取值：取单链表中第i个元素的内容,取到的放到e中 ****/
	/*
	ElemType e; 
	GetElem_L(L, 3, &e);
	printf("e = %d\n", e);	
	*/
	/*****查找：按值查找：根据指定数据获取数据所在位置(地址)****/
	//LocateElem_L(L, 3);
	/*****查找：按值查找：根据指定数据获取数据所在位置（序号）****/
	//printf("Locate = %d", LocateElem_L2(L, 45));	
	/***************求插入：在第i后结点前插入新结点***********************/
	 
	//printf("-----before------\n");
	//traverse_list(L);
	//ListInsert_L(L, 4, 999);//i等于0在第i之后插入，i等于1在i之前插入 
	//printf("-----after------\n");
	//traverse_list(L);
	//	-----before------
	//	23 43 56 67 87
	//	-----after------
	//	23 43 56 999 67 87
	//printf("ListEmpty = %d", ListEmpty(L)); //判断单链表是否为空
	int e;	
	ListDelete_L(L, 3, &e);
	traverse_list(L);
	return 0;
}