/*	實驗內容
1．鏈表是有序的，現在刪除數據x，若x不存在，輸出一段提示信息。
（有頭結點）
2．線性表v的數據遞增有序，試將x插入表中并保持有序性
   (2)鏈表表示（有頭結點）
*/

#include <stdlib.h>
#include<iostream.h>
#include<stdio.h>
#include<conio.h>
typedef struct node
{  
	int data;
    node *next;

}LNode,*Listlink;


void wcreate(Listlink *head,int n)//尾插法實現鏈表的插入

{

    int i;

    Listlink p,q;

       cout<<"尾插法---請輸入元素: "<<endl;

    *head=(Listlink )malloc(sizeof(struct node));//生成一個頭結點

    (*head)->next=NULL;

    q=*head;//q始終指向終端結點，開始時指向頭結點

    for(i=0;i<n;i++)
	{

       p=(Listlink)malloc(sizeof(struct node));//生成一個新的結點

       scanf("%d",&(p->data));

       p->next=q->next;

       q->next=p;//將p插入到q之后

       q=p;

    }

}
/*LNode*creat(int tag)//創建鏈表，實現以tag的值作為結束標志
{
	int x;
	LNode*p,*r,*h=(LNode*)malloc(sizeof(LNode));
	r=h;
	printf("輸入元素：");
	scanf("%d",&x);
	while(x!=tag)
	{
		p=(LNode*)malloc(sizeof(LNode));
		p->data=x;
		r->next=p;
		r=p;
		scanf("%d",&x);
	}
	r->next=NULL;
	return h;
}
*/
/*void qcreate(Listlink *head,int n)//頭插法實現鏈表的創建

{

    int i;

    Listlink p;

       cout<<"前插法---請輸入元素: "<<endl;

    *head=(Listlink )malloc(sizeof(struct node));

    (*head)->next=NULL;

    for(i=0;i<n;i++)

    {

       p=(Listlink)malloc(sizeof(struct node));

       scanf("%d",&(p->data));

       p->next=(*head)->next;

       (*head)->next=p;

    }

}
*/
void printf(LNode *head)//輸出數據

{

     Listlink p;

     p=head->next;

     while(p!=NULL)

     {

       cout<<p->data<<" ";

       p=p->next;

     }

   cout<<endl;

}

LNode *find(LNode *h,int i,int m)//在鏈表h的m個數據中查找要插入的結點i
{

     LNode *p=h;

     int j=1;

     if(i>m+1||i<0)  return NULL;//要插入的結點不存在

     else
	 {

       while (p!=NULL&&j<i)
		 {
		   j++;
		   p=p->next;
		 }

        return p;

     }

}

LNode *insert(LNode *h,int i,int x,int m)//在鏈表h的第i個結點前插入數據x，總共有m個數據
{

     LNode *p,*s;
     
	 s=(LNode *)malloc(sizeof(LNode));
     
	 s->data=x;
	 
	 s->next=NULL;
     
	 if(i==0){s->next=h;h=s;}
       
	 else{

                p=find(h,i,m);

                if(p!=NULL)
				{

                       s->next=p->next;

                       p->next=s;

                }

        else cout<<"輸入的結點不存在！"<<endl;

        }

        return h;

}

LNode *del(LNode *h,int i,int m)//在鏈表h中刪除結點i，總共數據有m個
{

       LNode *p=h,*s;

       int j=1;

       if(i==1)
	   {
		   h=h->next;
		   free(p);
	   }

       else
	   {
		   p=find(h,i,m);//找到結點i

           if(p!=NULL&&p->next!=NULL)
	   
		   {
		       s=p->next;
		       p->next=s->next;//刪除s結點
		       free(s);
		   }

          else 
		    cout<<"輸入的結點不存在！"<<endl;
	   }

     return h;

}

void main()

{  

   Listlink a;

   int n,q,x,y,r,e,g;

   cout<<"請輸要創建的元素個數: ";

   cin>>n;

   /*cout<<"請選擇創建鏈表方法:1.前插法 2.尾插法 "<<endl;

   cin>>r;

   switch(r)
   {

   case 1:qcreate(&a,n);break;

   case 2:wcreate(&a,n);break; 
   }*/

   wcreate(&a,n);
   //creat(0);
   cout<<"創建成功!\n";

   printf(a);
   char yes;
   
   yes='y';
    do
	{
       cout<<"請選擇操作:1.插入結點 2.刪除結點"<<endl;

       cin>>e;
 
       switch(e)
	   {

          case 1: cout<<"請輸入要插入的元素值:";
	              cin>>q;
	              cout<<"請輸入要在那個結點前插入"; 
                  cin>>x;
		          a=insert(a,x,q,n);
		          cout<<"操作后的鏈表值為:"<<endl;
		          printf(a);
		          break;
          case 2: cout<<"請輸入你要刪除的結點: "<<endl;
	              cin>>y;
	     	      a=del(a,y,n);
		          cout<<"刪除成功,鏈表值為:";
		          printf(a);
		          break; 

	   }  
	 cout<<"是否要繼續？y/n"<<endl;
	 cin>>yes;
	}while(yes=='y');

}