#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;		}