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

		template <class Type> class List;					//前視的類定義

		template <class Type> class ListNode {					//鏈表結點類的定義
		friend class List<Type>;							//List類作為友元類定義
		public:
		   ListNode ( );								//不給數據的構造函數
		   ListNode ( const Type& item );					//給數據的構造函數
		   ListNode ( const Type& item, ListNode<Type>* next );
		   ListNode<Type> *NextNode ( ) { return link; }			//給出當前結點的下一個結點地址
		   void InsertAfter ( ListNode<Type> *p );				//當前結點插入
		   ListNode<Type> *GetNode ( const Type& item, ListNode<Type> *next );	//建立一個新結點
		   ListNode<Type> *RemoveAfter ( );					//刪除當前結點的下一結點
		private:
		   Type data;								//數據域
		   ListNode<Type> *link;						//鏈指針域
		};

		template <class Type> class List {					//單鏈表類定義
		public:
		   List ( ) { last =first = new ListNode<Type> ( ); }	//構造函數, 建立一個空鏈表
		   ~List ( );									//析構函數
		   void MakeEmpty ( );							//將鏈表置為空表
		   int Length ( ) const;							//計算鏈表的長度
		   ListNode<Type> *GetNode ( const Type& item, ListNode<Type> *next );	//建立一個新結點
		   ListNode<Type> *FindValue ( Type value );				//在鏈表中搜索含數據value的結點
		   ListNode<Type> *FindPosition ( int i );					//搜索鏈表中第i個元素的地址
		   int Insert ( Type value, int i );					//將新元素value插入在鏈表中第i個位置
		   Type *Remove ( int i );						//將鏈表中的第i個元素刪去
		   Type *Get ( int i );							//取出鏈表中第i個元素
		   void Print();
		private:
		   ListNode<Type> *first, *last;					//鏈表的表頭指針, 表尾指針
		};

		template <class Type> void ListNode<Type>::ListNode ( ) : link (NULL) { }
		//構造函數, 僅初始化指針成員。

		template <class Type> void ListNode<Type>::ListNode ( const Type& item ) : data (item), link (NULL) { }
		//構造函數, 初始化數據與指針成員。

		template <class Type> void ListNode<Type>::ListNode ( const Type& item, ListNode<Type>* next ) : data (item), link (next) { }

		template <class Type> void ListNode<Type>::InsertAfter ( ListNode<Type> *p ) {
		//將p所指示的結點鏈接成為當前結點(*this)的后繼結點。
			 p->link = link;  link = p;
		}

		template <class Type> ListNode<Type>* List<Type>::GetNode ( const Type& item,
		ListNode<Type> * next ){
		//以數據成員item和指針next為參數, 建立一個新結點, 函數返回新結點地址。
		   ListNode<Type> *newnode = new ListNode<Type> ( item, next );
		   return newnode;
		}

		template <class Type> ListNode<Type> *ListNode<Type>::RemoveAfter ( ) {
		//從鏈中摘下當前結點的下一結點, 并為刪除它而返回其地址。
		   ListNode<Type> *tempptr = link;					//保存要被刪除結點的地址
		   if ( link == NULL ) return NULL;					//當前結點無后繼, 返回NULL
		   link = tempptr->link;							//將被刪結點從鏈中摘下
		   return tempptr;
		}

		template <class Type> List<Type>::~List ( ) { MakeEmpty ( );  delete first;  first = last = NULL; }
		//析構函數

		template <class Type> void List<Type>::MakeEmpty ( ) {
		//將鏈表置為空表
		   ListNode<Type> *q;
		   while ( first->link != NULL ) {					//當鏈不空時, 刪去鏈中所有結點
			 q = first->link;  first->link = q->link;
			 delete q;								//循鏈逐個刪除，保留一個表頭結點
		   }
		   last = first;								//表尾指針指向表頭結點
		}

		template <class Type> int List<Type>::Length ( ) const {
		//計算帶表頭結點的單鏈表的長度
		   ListNode<Type> *p = first->link;  int count = 0;
		   while ( p != NULL ) { p = p->link;  count++; }			//循鏈掃描, 尋找鏈尾
		   return count;
		}

		template <class Type> ListNode<Type> *List <Type>::FindValue ( Type value ) {
		//在單鏈表中搜索含數據value的結點, 搜索成功時, 函數返回該結點地址; 否則返回NULL值。
		   ListNode<Type> *p = first->link;
		   while ( p != NULL && p->data != value )  p = p->link;	//循鏈找含k結點
		   return p;
		}

		template <class Type> ListNode<Type> *List<Type>::FindPosition ( int i ) {
		//定位函數。函數返回鏈表中第i個元素的地址。若i<-1或i超出表中結點個數，則返回NULL。
		   if ( i < -1 ) return NULL;						// i值不合理
		   if ( i == -1 ) return first;						// i = -1時函數返回表頭結點地址
		   ListNode<Type> *p = first->link;  int j = 0;			//檢測指針p指向表中第一個結點
		   while ( p != NULL && j < i ) { p = p->link;  j = j++; }	//尋找第i個結點的地址
		   return p;				 //函數返回第i個結點地址, 若返回NULL, 表示i值太大
		}

		template <class Type> int List<Type>::Insert ( Type value, int i ) {
		//將新元素value插入在鏈表中第i個位置。
		   ListNode<Type> *p = FindPosition ( i-1 );					//定位第i-1個元素 (i ( 0)
		   if ( p == NULL ) return 0;						//參數i的值不合理，函數返回0
		   ListNode<Type> *newnode = GetNode ( value, p->link );	//創建含value的結點
		   if ( p->link == NULL ) last = newnode;
		   p->link = newnode;							//插入成功，函數返回1
		   return 1;
		}

		template <class Type> Type *List<Type>::Remove ( int i ) {
		//將鏈表中的第i個元素刪去, 通過函數返回該元素。若i不合理, 則返回NULL。
		   ListNode<Type> *p = FindPosition (i-1), *q;				// p定位于第i-1個元素
		   if ( p == NULL || p->link == NULL ) return NULL;		// i的值不合理或空表，返回NULL
		   q = p->link;  p->link = q->link;					// q指向被刪結點，重新拉鏈
		   Type value = q->data;						//取出被刪結點中的數據值
		   if ( q == last ) last = p;						//刪表尾結點時, 表尾指針修改
		   delete q;  return &value;
		}

		template <class Type> Type *List<Type>::Get ( int i ) {
		//取出鏈表中第i個元素。
		   ListNode<Type> *p = FindPosition ( i );					//定位于第i個元素
		   if ( p == NULL || p == first ) return NULL;			//空表或參數i的值不合理
		   else return & p->data;
		}

		template < class Type > void List<Type> :: Print() {
		    int i = 0;
		    Type *p = Get (i);
		    while ( p != NULL ) {
			cout << *p << "  " ;
			p = Get ( ++i );
		    }
		    if ( i == 0 ) cout << " empty!!!! ";
		    cout << endl;
		}