#include<stdio.h>
#include<iostream>
using namespace std;
#define MAX 100

//-----单链表的存储结构---- 
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

 //单链表的初始化
 int InitList(LinkList &L){
 	//构造一个空的单链表
	 L=new LNode;
	 L->next=NULL;
	 return 1;
 } 
 
 //判断链表是否为空
 int EmptyList(LinkList L){
 	if(L->next){
 		return 0;//非空 
 	}else{
 		return 1;//链表为空 
 	}
 } 
 
 //获取链表长度
 int ListLength(LinkList L){
 	int length=0;
 	struct LNode *p;
 	p=L->next;
 	while(p){
 		length++;
 		p=p->next;
 	}
 	return length;
 } 
 //遍历单链表
 void TraveList(LinkList L){
 	struct LNode *p;
 	p=L->next;
 	printf("链表结果如下:\n");
 	while(p){
 		printf("%d ",p->data);
 		p=p->next;
 	}
 	printf("\n");
 } 
 
 //查找
 //1.按序号查找
 int SelectByNo(LinkList L,int i,int &e){
 	//在带头结点的单链表中查找第i个值 
 	struct LNode *p;
 	p=L->next;//初始化，p指向第一个结点 
 	int j=1;//j用来计数
 	while(p&&j<i){//顺着链域扫描，直到p指向第i个元素，或者p为空 
 		p=p->next;
 		++j;
 	}
 	if(!p||j>i){
 		return 0;
 	}
 	e=p->data;
 	return 1;
 }
 
 //2.按值查找
 LNode *SelectByValue(LinkList L,int e){
 	//在带头结点的单链表中查找值为e的元素
	 struct LNode *p;
	 while(p&&p->data!=e){
	 	p=p->next; 
	 } 
	 return p;
 } 
 
 /*
 插入操作 
 */
 int ListInsert(LinkList &L,int &e){
 	//在单链表的第i个位置之前插入元素e
	 int j=0;
	 struct LNode *p;
	 p=L;
	 while(p&&j<i-1){//寻找第i-1个结点 
	 	p=p->next;
	 	++j;
	 } 
	 if(!p||j>i){
	 	return 0;
	 }
	 struct LNode *s;
	 s=new LNode;//生成新结点s
	 s->data=e; //将新结点的数据域置为e
	 s->next=p->next;//将新结点插入L中 
	 p->next=s;
	 return 1; 
 }
 
 /*
 删除操作 
 */
 int ListDelete(LinkList &L,int e){
 	//删除链表l中的第i个位置的元素，并用e返回其值
	 struct LNode *p;
	 p=L;
	 int j=0;
	 while(p&&j<i-1){//寻找地i-1个结点 
	 	p=p->next;
	 	++j;
	 } 
	 if(!(p->next)||j>i-1){
	 	return 0;
	 }
	 struct LNode *q;
	 q=p->next;//临时保存要删除的结点的地址以备释放
	 p->next=q->next;
	 e=q->data;
	 delete q;
	 return 1; 
 }
 //前插法创建单链表
 void CreateList(LinkList &L,int n){
 	 //建立带头结点的单链表L,输入n个元素的值
	 L=new LNode;//先建立一个带头结点的空的单链表
	 L->next=NULL;
	 printf("输入n个元素的值:\n");
	 for(int i=0;i<n;i++){
	 	struct LNode *p;
	 	p=new LNode;//生成新结点
		printf("请输入第%d个元素的值:",i+1);
		scanf("%d",&p->data);
		p->next=L->next;
		L->next=p; 
	 } 
	 
 }
 
 int main(){
 	LinkList L;
 	
 	InitList(L);
 	if(EmptyList(L)){
 		printf("链表为空.\n");
 	}else{
 		printf("链表非空.\n");
 	}
 	
 	printf("请输入链表中元素的个数:\n");
 	int n;
 	scanf("%d",&n);
 	CreateList(L,n);
 	
 	TraveList(L);
 	printf("当前链表长度是:%d\n",ListLength(L));
 	
 	printf("请输入要查找元素在链表中的位置:\n");
 	int location;
 	scanf("%d",&location);
	int e1;
	if(SelectByNo(L,location,e1)){
		printf("%d位置元素的值是:%d\n",e1);
	}else{
		printf("查找失败!\n");
	}
	
	printf("输入要查找元素的值:\n");
	int e2;
	scanf("%d",&e2);
	LNode *p;
	p=SelectByValue(L,e2);
	printf("位置:%d\n",p);
 	
 	printf("请输入插入元素的位置和值:\n");
 	int e,location1;
 	scanf("%d%d",&location,&e);
 	ListInsert(L,e);
 	TraveList(L);
 	
 	printf("请输入要删除元素的位置:\n");
 	int location2;
 	scanf("%d",&location2);
 	int e3;
 	ListDelete(L,location2,e3);
 	printf("要删除的元素值是:%d\n",e3);
 	TraveList(L);
 	
 	return 0;
 }