#include <stdio.h>
#include <iostream.h>
typedef struct LNode{
	long  date;
    struct LNode *next;
} LNode,*LinkList;
void CreatList_L(LinkList &L);
int ListLength(LinkList L);
void ShowList_L(LinkList L);
void ListInsert_L(LinkList &L);
void ListDelete_L(LinkList &L);
void LocateList_l(LinkList &L);
void CreatList_L(LinkList &L){
	L = new LNode; 
	L->next=NULL;// 建立空表
	cout<<"1-正序輸入       2-逆序輸入"<<endl;
	int i;
	cin>>i;
	if(i==1)
	{
		LinkList p;
	    p=L;
	    cout<<"請輸入您要建立的單向鏈表的數據個數:"<<endl;
	    int n;
	    cin>>n;
	    for(int i=0;i<n;i++){
	    LinkList q=new LNode;//創建要插入的結點并初始化
	    q->next=NULL;
	    cout<<"請輸入數據:";
	    cin>>q->date;
	    p->next=q;p=q;}
	}
    if(i==2)
	{
        LinkList p;
		cout<<"請輸入您要建立的單向鏈表的數據個數:"<<endl;
	    int n;
	    cin>>n;
		for (i = n; i > 0; --i) {
        p = new LNode;
        cout<<"請輸入數據:";
		cin>>p->date;    
        p->next = L->next;  L->next = p;}

	}
}
int ListLength(LinkList L){
	LinkList p;
	p = L->next ;
	int j=1;
	while(p->next)
		++j;

	return j;
}
void ShowList_L(LinkList L){
    printf("此時您的單向鏈表是:");
    
	LinkList p;
	p=L->next;
	while(p)
	{   cout<<"|"<<p->date<<"|"<<"->";
	p=p->next;}
	cout<<"NULL"<<endl;
}
void ListInsert_L(LinkList &L){
	LinkList p;
	p=L;
	int i;
	cout<<"請輸入您要插入結點的位置:"<<endl;
	cin>>i;
	int j=0;
	while(p&&j<i-1){
		p=p->next;++j;
	}
	if(!p||j>i)
		cout<<"插入錯誤!"<<endl;
	else 
	{
		LinkList s=new LNode;
	    if(s==NULL)
		cout<<"創建結點失敗!"<<endl;
	    else 
		{
			cout<<"請輸入您要插入的結點數據 :"<<endl;
	        cin>>s->date;
			s->next=p->next;p->next=s;
		}
	}
}
void ListDelete_L(LinkList &L){
	cout<<"1-全部刪除!      "<<"2-刪除一個結點"<<endl;
	int i;
	cin>>i;
	LinkList p;
	if(i==1)
	{  while(L->next)
	   {p=L->next;L->next=p->next;delete(p);}
	   cout<<"鏈表已經清空!請重新建立新鏈表！"<<endl;
	}
	if(i==2)
	{
		int j,i=0;
		cout<<"請輸入您要刪除的結點的位置:"<<endl;
		cin>>j;
		p=L;
		while(p->next&&i<j-1){
		p=p->next;++i;
		}
		if(!p->next||i>j)
			cout<<"刪除錯誤!"<<endl;
		else 
		{LinkList q;
		q=p->next;p->next=q->next;delete(q);}
	}
}
void LocateList_L(LinkList &L){
	int i,j=1;
	LinkList p;
	// cout<<ListLength(L);
	cout<<"請輸入您要查找的元素的位置:"<<endl;
	cin>>i;
	p=L->next;
	while(p&&j<i){
		p=p->next;++j;
	}
	if(!p||j>i)
		cout<<"查找錯誤！"<<endl;
	else 
		cout<<"您要查找的元素是:"<<p->date<<endl;
	
}
	
void main()
{
	cout<<"帶頭結點的單向鏈表:"<<endl;
    LinkList L;
	int i;
	
    do
	{   
		cout<<"1-建立"<<"      "<<"2-插入"<<"       "<<"3-刪除"<<endl<<"4-查找      "<<"5-顯示"<<"       "<<"6-退出"<<endl<<"請選擇:1/2/3/4/5/6:";
		cin>>i;
		switch(i){
	    case 1: CreatList_L(L);ShowList_L(L);break;
		case 2: ListInsert_L(L);ShowList_L(L);break;
		case 3: ListDelete_L(L);ShowList_L(L);break;
		case 4: LocateList_L(L);break;
		case 5: ShowList_L(L);break;
	    default:break;}
	}
	while(i!=6);
}