/*鏈表的各種功能*/
#include<stdio.h>
typedef char datatype;
typedef struct node
{
	datatype data;
	struct node *next;
} linklist;

linklist *head_cha();
linklist *bottom_cha();
linklist *bottom_cha1();
linklist *get(linklist *head,int i);
linklist *deletedata(linklist *head,int i);
linklist *insertdata(linklist *head,datatype ch,int i);
linklist *nixu(linklist *head);
linklist *nixu1(linklist *head);
void lianbiao()
{
	linklist *h,*p,*q,*r,*s,*t;
	int x,i;
	scanf("%d",&x);
	switch(x)
	{
	case 1:
		h=head_cha();
		printf("反序打印字符:\n");
		break;
	case 2:	
		h=bottom_cha();
		printf("正序打印字符:\n");
		break;
	case 3:
		h=bottom_cha1();
		printf("正序打印字符:\n");
		break;
	default:
		printf("error!");
		break;
	}

	r=h;
	while(r!=NULL)
	{
		printf("%c",r->data);
		r=r->next;
	}
	printf("\n");

	printf("enter the number:\n");
	scanf("%d",&i);

	p=get(h,i);
	printf("%c",p->data);
	printf("\n");

	s=insertdata(h,'o',i);
	while(s!=NULL)
	{
		printf("%c",s->data);
		s=s->next;
	}
	printf("\n");

	q=deletedata(h,i);
	while(q!=NULL)
	{
		printf("%c",q->data);
		q=q->next;
	}
	

	printf("\n");

	t=nixu1(h);
	while(t!=NULL)
	{
		printf("%c",t->data);
		t=t->next;
	}
	printf("\n");
//	nixu1(h);
/*	while(h!=NULL)
	{
		printf("%c",h->data);
		h=h->next;
	}
	printf("\n");
*/

}

linklist *head_cha()//頭插法
{
	char ch;
	linklist *head,*s;
	head=NULL;
	printf("（頭插法）請輸入字符：\n");
	ch=getchar();
	while(ch!='#')
	{
		s=(linklist*)malloc(sizeof(linklist));
		s->data=ch;
		s->next=head;
		head=s;
		ch=getchar();
	}

	return head;

}
linklist *bottom_cha()//尾插法
{
	 char ch;
	 linklist *head,*s,*r;
	 head=NULL;
	 r=head;
	 printf("（尾插法）請輸入字符：\n");
	 ch=getchar();
	 while(ch!='#')
	 {
		s=(linklist*)malloc(sizeof(linklist));
		s->data=ch;
		if(head==NULL) head=s;
		else r->next=s;
		r=s;
		ch=getchar();
	 }
	 if(r!=NULL)
		 r->next=NULL;
	 return head;
	
}
linklist *bottom_cha1()//帶接點的尾插法
{
	 char ch;
	 linklist *head,*s,*r;
	 head=(linklist*)malloc(sizeof(linklist));
	 r=head;
	 printf("（帶頭接點的尾插法）請輸入字符：\n");

	 ch=getchar();
	 while(ch!='#')
	 {
		s=(linklist*)malloc(sizeof(linklist));
		s->data=ch;
//		if(head==NULL) head=s;
//		else 
		r->next=s;
		r=s;
		ch=getchar();
	 }
	 if(r!=NULL)
		 r->next=NULL;
	 return head;
}

linklist *get(linklist *head,int i)//獲取第i個元素
{
	linklist *p;
	int j=0;
	p=head;
	if(p==NULL)
		printf("the lianbiao is NULL!");
	while((p!=NULL)&&(j<i))
	{
		p=p->next;
		j++;
	}
	if(j==0)
		printf("the number overflow !");
	return p;


}
linklist *deletedata(linklist *head,int i)//刪除第i個元素
{
	linklist *p,*q;
	int j=0;
	p=head;
	if(p==NULL)
		printf("the lianbiao is NULL!");
	while((p!=NULL)&&(j<i))
	{	

		p=p->next;
		j++;
	}
	if(!(p->next)||j==0)
		printf("the number overflow !");
	q=p->next;
	p->next=q->next;


	return head;
}
linklist *insertdata(linklist *head,datatype ch,int i)//將元素插入第i個元素
{
	linklist *p,*s;
	int j=0;
	p=head;
	if(p==NULL)
		printf("the lianbiao is NULL!");
	while((p!=NULL)&&(j<i))
	{	

		p=p->next;
		j++;
	}
	if(!(p->next)||j==0)
		printf("the number overflow !");
	s=(linklist *)malloc(sizeof(linklist));
	s->data=ch;
//	q=p->next;
	s->next=p->next;
	p->next=s;
//	free(q);
//	p->next=q->next;


	return head;

}

linklist *nixu(linklist *head) //逆序輸出單鏈表
{
	linklist *p,*r,*s;
	r=head;
	p=NULL;
	while(r->next!=NULL)
	{
		s=(linklist*)malloc(sizeof(linklist));
		s->data=r->data;
		r=r->next;
		s->next=p;
		p=s;
	}
	return p;
}

linklist *nixu1(linklist *head)//逆序輸出單鏈表
{
	linklist *s,*r,*p; //定義三個指向鏈表頭三個節點的指針
	s=head;
	p=s->next;
	r=p->next;
	if(r==NULL)
	{
		p->next=s;
		s=p;
	}
	while(r!=NULL)
	{
		if(s==head)
		{
			s->next=NULL;
		}
		p->next=s;
		s=p;
		
		p=r;
		r=r->next;
	}
//	p=head;
	return s;
}