int i;


link inil()   
{
	link L;
	L=(link)malloc(sizeof(node));
	L->next=NULL;
	return L;
}

void printl(link p)
{
	pr("單鏈表為：\n");
	for(p=L->next;p;)
	{
		pr("%4d",p->data);
		p=p->next;
	}
	cout<<kg;
}

void creatl(link q)
{
	link p;	
	cout<<"創(chuàng)建鏈表，0 結束!"<<endl;
	cout<<"例如：2 1 8 0 "<<endl;
	cout<<"依次輸入:  ";
	while (true)
	{    
		p = (link)malloc(sizeof(node));
		cin>>p->data;
		if (!p->data ) break;
		q->next=p;
		q=p;
	}
	q->next=NULL;
	pr("創(chuàng)建成功!");
	printl(L);
}


status getel(link L,int i,elemtypel &e)
{
	
	link p=L->next; 
	int j=1;
	while(p&&j<i)
	{p=p->next;
	++j;
	}
	if(!p)
		return ERROR;
	e=p->data;
	return OK;
}


status insl(link &L,int i,elemtypel e)
{
	int j=0;	
	link p,s;
	p=L;
	while(p&&j<i-1)
	{
		p=p->next;
		++j;
	}
	if(!p)
		return ERROR;
	s=(link)malloc(sizeof(node));
	s->data=e;
	s->next=p->next;
	p->next=s;
	return OK;
}


status del(link &L,int i,elemtypel &e)
{
	link p=L,q;
    int j=0;
	while(p->next&&j<i-1)
	{
		p=p->next;
		++j;
	}
	if(!(p->next))
		return ERROR;
	q=p->next;
	p->next=q->next;
	e=q->data;
	free(q);
	return OK;
}


void sort(link &L)
{
	link h,p,r,q,s;
	h=p=(link)malloc(sizeof(node));
	p->next=L->next;
	while(p->next)
	{
		r=p;
		q=p->next;
		while(q->next)
		{
			if(q->next->data<r->next->data)
				r=q;
			q=q->next;
		}
		if(r!=p)
		{
			s=r->next;
			r->next=s->next;
			s->next=p->next;
			p->next=s;
		}
		p=p->next;
	}
	L->next=h->next;
	free(h);
	printl(L);
}


void nixu(link s)
{
	link p,q;
	p=s->next;
	s->next=NULL;
	while(p)
	{
		q=p->next;
		p->next=s->next;
		s->next=p;
		p=q;
	}
	printl(L);
	
}

int lenl(link s)
{
	int i=0;
	while(s->next)
	{
		s=s->next;
		i++;
	}
	return i;
}

void charul()
{
	int b;
	pr("請輸入你要插入的位置：\n");
	scanf("%d",&b);
	pr("你想插入的數(shù):\n");
	scanf("%d",&e);
	s=insl(L,b,e);
	if(s==OK)
	{ 
		pr("插入成功\n");
		printl(L);
		cout<<kg;
		
	}
	else
	{
		pr("插入失敗!\n");
		printl(L);	
	}
}

void shanchul()
{
	int b;
	pr("請輸入你要刪除的位置：\n");
	scanf("%d",&b);
	s=del(L,b,e);
	if(s)
	{ 
		pr("刪除成功!\n");
		pr("刪除第%d個數(shù)，該數(shù)為%d\n",b,e);
		printl(L);
		cout<<kg;
		
	}
	else
	{
		pr("刪除失敗!\n");
		printl(L);
		cout<<kg;
		
	}
}

void chal()
{
	int b;
	pr("請輸入你要查找第幾個數(shù)：\n");
	scanf("%d",&b);
	s=getel(L,b,e);
	if(s==OK)
	{ 
		pr("%d是第%d個數(shù)\n",e,b);
		printl(L);
	}
	else
	{
		pr("你要查找的數(shù)不存在!\n");
		printl(L);	
	}
}

int selectl()
{
	int n;
	cout<<"   *********************************************************************** "<<endl;   
	cout<<"   *                         1.創(chuàng)建                                      * "<<endl;   
	cout<<"   *                         2.查找                                      * "<<endl;    
	cout<<"   *                         3.插入                                      * "<<endl; 
	cout<<"   *                         4.刪除                                      * "<<endl;
	cout<<"   *                         5.顯示                                      * "<<endl;
	cout<<"   *                         6.排序                                      * "<<endl;
	cout<<"   *                         7.逆序                                      * "<<endl;
	cout<<"   *                         8.求長                                      * "<<endl;
	cout<<"   *                         9.返回上一層                                * "<<endl;
	cout<<"   *                         0.退出                                      * "<<endl;
	cout<<"   *********************************************************************** "<<endl;       
	cout<<"                            選擇你想進行的操作:                            "<<endl;   
	cout<<"請選擇0~9!"<<endl;
	cin>>n;
	for(;;)
	{
		if(n<0||n>9)
		{
			cout<<"重選"<<endl;
			cin>>n;
		}
		else
			break;
	}
	return n;
	
}

int selectll()
{
	int t;
	switch(selectl())
	{
	case 0:end();break;
	case 1:L=inil();break;
	case 2:creatl(L);break;
	case 3:chal();break;
	case 4:charul();break;
	case 5:shanchul();break;
	case 6:printl(L);break;
	case 7:sort(L);break;
	case 8:nixu(L);break;
	case 9:pr("%d",lenl(L));break;
	}
	cout<<"請選擇0~9!"<<endl;
	cin>>t;
	for(;;)
	{
		if(t<0||t>9)
		{
			cout<<"重選"<<endl;
			cin>>t;
		}
		else
			break;
	}
	return t;
	
}