#include<stdio.h>
#include<malloc.h>

typedef struct LNode
{
	int data;
	struct LNode *next;
}LNode,*LinkList;
 

void CreateList(LinkList &L);          //創建鏈表
void Locate(LinkList L);               //查詢數值
void InsertList(LinkList &L);          //插入數值
void DeleteList(LinkList &L);          //選擇刪除
void Deleterepeat(LinkList &L);        //刪除重復結點
void DeleteEven(LinkList &L);          //刪除數值為偶數的結點
void Rotate(LinkList &L);              //變為循環鏈表
void Divide(LinkList &L);              //分解成兩個鏈表
int LengthList(LinkList L);            //求鏈表長度
void PrintList(LinkList L);            //輸出鏈表
 
/**********************************************************************
                            主函數
**********************************************************************/
void main(void)
{   
	char operate;
	LinkList L;
	int n;
	for( n=0;n<40;n++)
	{
		printf("\n輸入字符選擇鏈表操作類型\nA:創建 B:查詢 C:插入 D:選擇刪除 E:刪除重復 F:刪除偶數 \nG:變為循環鏈表 H:分解為兩個鏈表\n");
        label:scanf("%c",&operate);
		switch (operate)
		{
	      case 'a':
          case 'A': CreateList(L);break;
		  case 'b':
		  case 'B': Locate(L);break;
		  case 'c':
		  case 'C': InsertList(L); break;
		  case 'd':
		  case 'D': DeleteList(L);break;
		  case 'e':
		  case 'E': Deleterepeat(L);break;
		  case 'f':
		  case 'F': DeleteEven(L);break;
		  case 'g':
		  case 'G': Rotate(L);break;
		  case 'h':
		  case 'H': Divide(L);break;
		  case '\n':goto label;          //排除換行鍵的影響
          default: printf("輸入有誤，請重新輸入！");break;
		}
        
    }

}

/**********************************************************************
                            創建鏈表
**********************************************************************/
void CreateList(LinkList &L)
{  
   int temp;
   printf("創建鏈表：\n請輸入創建鏈表所需的整數值(以-1結束):\n");
   L = (LinkList)malloc(sizeof(LNode)); 
   L->next = NULL;
   LinkList q=L;
   scanf("%d",&temp);
   while(temp!=-1) 
   {
       LinkList p;
       p = (LinkList)malloc(sizeof(LNode));  
       p->data = temp;
       p->next = NULL;
       q->next = p;
       q = q->next;  
       scanf("%d",&temp);
	}
    L->data = LengthList(L);
    PrintList(L);

}
/**********************************************************************
                            查詢元素
**********************************************************************/
void Locate(LinkList L)
{   if(!L)printf("錯誤：鏈表未創建！");
	int element;
	printf("查詢數值：\n輸入要查詢的數值：");
    scanf("%d",&element);
	LinkList p=L->next;
	int i =1;
    while(p->data!=NULL)
	{ 
      if(p->data==element)
	  {  
         printf("找到了，它是鏈表的第%d個元素。\n",i);
         return ;
	  }
	  p=p->next;
	  i++;
	}
    printf("找不到。\n");
}
/**********************************************************************
                            插入數值
**********************************************************************/
void InsertList(LinkList &L)
{
  int x,i;
  printf("插入數值：\n輸入要插入的數值和插入的位置：");
  scanf("%d",&x);
  scanf("%d",&i);
  LinkList p = L;   
  int j = 0;
  while (p && j < i-1)
  {  
    p = p->next;
    ++j;
  } 
  if (!p || j > i-1) 
  {
	  printf("輸入位置錯誤!") ;
	  return;
  }
  LinkList s = (LinkList)malloc(sizeof(LNode));  
  s->data = x;  
  s->next = p->next;      
  p->next = s;
  L->data = LengthList(L);
  PrintList(L);
} 
/**********************************************************************
                            選擇位置刪除節點
**********************************************************************/
void DeleteList(LinkList &L)
{ 
  int i;
  LinkList p = L;
  printf("選擇位置刪除結點：\n輸入要刪除數值的位置：");
  scanf("%d",&i);
 
  int j = 0;
  while (p->next && j < i-1)
  {  
    p = p->next;
    ++j;
  }
  if (!(p->next) || j > i-1)
  {
	  printf("輸入位置錯誤!") ;
	  return;
  }
  LinkList q = p->next;
  p->next = q->next;          
  free(q);
  L->data = LengthList(L);
  PrintList(L);
} 
/**********************************************************************
                            刪除重復結點
**********************************************************************/
void Deleterepeat(LinkList &L)
{
    printf("刪除重復結點后的鏈表為：\n");
	int n=1;
	int a[20];
	LinkList q=L->next;
	LinkList p=q->next;
    a[0]=q->data;
	while(p)
	{
		for(int i=0;i<n;i++)
		{
			if(p->data==a[i])
			{
			    LinkList r=p;
			    q->next=p->next;
				p=p->next;
				free(r);
				break;
			}
		}
		if(i==n)
		{
			a[n++]=p->data;
            p=p->next;
			q=q->next;
		}
		
		
	}
    L->data = LengthList(L);
    PrintList(L);
}
/**********************************************************************
                            刪除數值為偶數的結點
**********************************************************************/
void DeleteEven(LinkList &L)
{
    printf("刪除偶數結點后的鏈表為：\n");
	LinkList q=L;
	LinkList p=L->next;
    while(p)
	{
		if(p->data%2==0)
		{
			LinkList r=p;
			q->next=p->next;
			p=p->next;
			free(r);
		}
	    else
		{
		    p=p->next;
			q=q->next;
		}
	}
    L->data = LengthList(L);
    PrintList(L);
}
/**********************************************************************
                            變為循環鏈表
**********************************************************************/
void Rotate(LinkList &L)
{
    printf("變為循環鏈表：\n");
	LinkList p=L;
	while(p->next)p=p->next;
	p->next=L;

    LinkList t=L->next;
	printf("長度：%d\t",L->data);
    printf("各個結點數值為：");
	while(t!=L)
	{
		printf("%d\t",t->data); 
		t=t->next;
	}
    printf("\n");
	printf("已經變為循環鏈表，其他操作將受影響,程序結束！\n");
	
}
/**********************************************************************
                          分解成兩個鏈表
**********************************************************************/
void Divide(LinkList &L)
{
    printf("分解成兩個鏈表：\n");
	LinkList A=L;
	LinkList B=(LinkList)malloc(sizeof(LNode));
	B->next=NULL;
	LinkList Lb=B;
    int i=1;
    LinkList La=L;
	LinkList p=L->next;
	while(p)
	{
       if(i++%2==0)
	   {   
          La->next=p->next;
		  p->next=NULL;
		  Lb->next=p;
		  Lb=Lb->next;
		  p=La->next;
	   }
	   else
	   {
          p=p->next;
		  La=La->next;
	   }
	 }
	 A->data = LengthList(A);
	 printf("鏈表A:");
     PrintList(A); 
	 B->data = LengthList(B);
     printf("鏈表B:");
     PrintList(B);
	 printf("已經分解成兩個鏈表，其他操作將受影響,程序結束！\n");
	 
}
/**********************************************************************
                            求鏈表長度
**********************************************************************/
int LengthList(LinkList L)
{
	int i=0;
	LinkList p=L->next;
	while(p)
	{
		p=p->next;
		i++;
	}
	return i;
}
/**********************************************************************
                            輸出鏈表
**********************************************************************/
void PrintList(LinkList L)
{   
    LinkList t=L->next;
	printf("長度:%d\t",L->data);
    printf("結點數值:");
	while(t)
	{
		printf("%d ",t->data); 
		t=t->next;
	}
    printf("\n");
}