//程序名：link2.cpp
//      程序功能：帶表頭結點單向鏈表類的實現（包括單向鏈表插入，刪除和查找操作的實現）
//          作者：william
//          日期：2006.10.1
//          版本：1.1
//      修改內容：在該版本是在link1.cpp的基礎上修改了讓鏈表帶有連頭結點
//      修改日期：2006.10.2
//      修改作者：william
//
//
//

#include<stdio.h>
#include<iostream.h>

typedef int DataType;      //為本程序定義所使用的具體數據類型

struct LinkNode {           //定義單向鏈表的結點結構
	DataType data;
	struct LinkNode *next;
};

class Link{         //  定義單向鏈表類

public:
     
    Link(void);    // 定義構造函數，初始化為帶表頭結點的空鏈
    int Insert(int i ,DataType x);    //插入
    int Delete(int i);    //刪除
    void TailCreate(int n);   //尾插入建立單向鏈表
    void HeadCreate(int n);   //頭插入建立單向鏈表
    void Print();    // 輸出整個單向鏈表中的數據
    ~Link(void);   //析構函數

private:
	struct LinkNode *head;    // 鏈頭結點

};

//////////////////////////////////////////////////////////////////////////////
//  構造函數
//  函數功能：將鏈頭指針初始化為帶表頭結點的空鏈
//函數參數：無
//參數返回值：無

Link::Link(void)
{
  head=new LinkNode;  // // head is the attribute of link class
  head->next=NULL;
}

//////////////////////////////////////////////////////////////////////////////
// 析構函數
// 函數功能：將鏈表所有結點的空間釋放(包括表頭結點)
//函數參數：無
//參數返回值：無

Link::~Link(void)
{
 struct LinkNode *p;
 
 while(head!=NULL)
 {
	 p=head;
	 head=head->next;
	 delete p;
 }
}

//////////////////////////////////////////////////////////////////////////////
//  插入函數
//  函數功能：將一個新值插入到某個位置的結點之后上,如果超過總結點個數，則做尾插入
//函數參數：
//       i 表示插入位置
//       x 表示待插入的元素值      
//參數返回值：
//     1： 表示插入成功
//     0：表示插入失敗     
int Link::Insert(int i ,DataType x)
{
 struct LinkNode *temp;
 struct LinkNode *p,*q;  // head is the attribute of link class
 

 if ( i<=0) 
  {
	cout<<"\n the position is error\n\n";
    return 0;   // error
  }
  
  int j=1;
  q=head; p=head->next; //q從表頭結點開始走,p則從鏈表的第一結點開始
  while(j <i && p!=NULL)     
  {
     q=p; p=p->next;
	 j++;
  }
  temp=new LinkNode;
  temp->data=x;
  temp->next=p;
  q->next=temp;
  return 1;  // ok
}

//////////////////////////////////////////////////////////////////////////////
//  刪除函數
//  函數功能：將鏈表中某個位置上的結點刪除
//函數參數：
//       i 表示刪除位置
//參數返回值：
//     1： 表示刪除成功
//     0：表示刪除失敗     
int Link::Delete(int i)
{
 struct LinkNode *q,*p;
 
 int j=1;

 if ( i<=0) 
  {
	cout<<"\n the position is error\n\n";
    return 0;   // error
  }
  
  q=head; p=head->next;
  while(j <i && p!=NULL)
  {
     q=p;
	 p=p->next;
	 j++;
  }
  if (p==NULL)
  {
	  cout<<"the position is our of range\n\n";
	  return 0;  // error
  }
  q->next=p->next;
  delete p;
  return 1; // ok
}

//////////////////////////////////////////////////////////////////////////////
//  尾插入建立鏈表函數
//  函數功能：用尾插入建立鏈表方法生成一個具有n個結點的鏈表
//函數參數：
//       n 表示結點個數
//參數返回值：無
void Link::TailCreate(int n)
{
  struct LinkNode *R,*p;
  R=head;
  for(int i=0;i<n;i++)
  {
	  p=new LinkNode;
	  cin>>p->data;
	  p->next=NULL;
	  R->next=p;
	  R=p;
  };
}

//////////////////////////////////////////////////////////////////////////////
//  頭插入建立鏈表函數
//  函數功能：用頭插入建立鏈表方法生成一個具有n個結點的鏈表
//函數參數：
//       n 表示結點個數
//參數返回值：無

void Link::HeadCreate(int n)
{
  struct LinkNode *p, *h=NULL;
  for(int i=0;i<n;i++)
  {
	  p=new LinkNode;
	  cin>>p->data;
	  p->next=h;
	  h=p;
  };
  head->next=p;   // head is the attribute of link class  因為帶表頭結點
}


//////////////////////////////////////////////////////////////////////////////
//  鏈表輸出函數
//  函數功能：從頭到尾的將鏈表中的所有結點一個一個輸出來（不包括表頭結點）
//函數參數：無
//參數返回值：無

void Link::Print(void)
{
 struct LinkNode *p=head->next;   //跳過表頭結點，表頭結點的值不能輸出
 cout<<"\n The data in the link are:\n";
 while ( p!=NULL)
 {
	 cout<<p->data<<"   ";   
	 p=p->next;
 }
 cout<<"\n\n\n";
}


//////////////////////////////////////////////////////////////////////////////
//  主函數
//參數返回值：無

void main()
{
	Link link1;  // link1 object   
	int finished=0;
    int choice , n ,pos;
	DataType x;

	while ( !finished )
    {
		cout<<"*********Menu*********\n";
		cout<<"1:Created by insert in head\n";
        cout<<"2:Created by insert in tail\n";
		cout<<"3:Insert\n";
		cout<<"4:Delete\n";
		cout<<"5:display all\n";
		cout<<"6:exit\n";
		cout<<"Please choose a choice(1-6):";
		cin>>choice;
		switch(choice)
		{
		case 1:
			   cout<<"\nplease enter the number of nodes(insert in head):";   //調用頭插入建立鏈表
			   cin>>n;
			   link1.HeadCreate(n);
			   link1.Print();
               break; 
        case 2:
		       cout<<"\nplease enter the number of nodes(insert in tail):";    //調用尾插入建立鏈表
			   cin>>n;
			   link1.TailCreate(n);
			   link1.Print();
               break;      
		case 3:
               cout<<"\nplease enter the position to insert:";     //調用鏈表插入函數
			   cin>>pos;
			   cout<<"\n please enter the data to insert\n";
			   cin>>x;
			   if ( link1.Insert(pos,x)==1)  // ok
				    link1.Print();
               break; 
		case 4:
               cout<<"\nplease enter the position to delete:";     //調用鏈表刪除函數
			   cin>>pos;
			   if ( link1.Delete(pos)==1 )
			      link1.Print();   //ok
               break; 
       case 5:
			  link1.Print();      //調用鏈表輸出函數
			  break;
		case 6:
			   finished=1;     //結束程序
			   break;
		}  // switch
	} // while 
}// main