C++链表类源代码（带头文件）

#include <iostream> #include <stdlib.h> using namespace std; template < class T > class LinkedList; ///////////////////////////// template < class T > class Node { friend class LinkedList < T >; //私有成员 protected: Node < T > * next; //指向后继结点 //公有成员 public: T data; //构造函数 Node ( const T & item, Node < T > * ptrnext = NULL ); void InsertAfter ( Node < T > * p ); Node < T > * DeleteAfter ( void ); Node < T > * NextNode ( void ) const; }; ///////////////////////////// template < class T > Node < T > :: Node ( const T & item, Node < T > * ptrnext ): data ( item ), next ( ptrnext ) {} template < class T > Node < T > * Node < T > :: NextNode ( void ) const { return next; } template < class T > void Node < T > :: InsertAfter ( Node < T > * p ) { p -> next = next; next = p; } template < class T > Node < T > * Node < T > :: DeleteAfter ( void ) { if ( next == NULL ) return NULL; Node < T > * tempptr = next; next = tempptr -> next; return tempptr; } //////////////////////////////// template < class T > class LinkedList { private: Node < T > * front, * rear; //当前和前驱结点 Node < T > * currptr, * prevptr; int size; //当前结点在链表中的位置 int position; Node < T > * GetNode ( const T & item, Node < T > * PtrNext = NULL ); void FreeNode ( Node < T > * p ); void CopyList ( const LinkedList < T > & L ); public: LinkedList ( void ); LinkedList ( const LinkedList < T > & L ); ~LinkedList ( void ); //重载赋值运算符 LinkedList < T > & operator = ( const LinkedList < T > & L ); int ListSize ( void ) const; int ListEmpty ( void ) const; //遍历链表的函数 void Reset ( int pos = 0 ); void Next ( void ); int ThisPosition ( void ) const; int EndOfList ( void ) const; //插入一个data域值为item的结点 void InsertFront ( const T & item ); void InsertRear ( const T & item ); void InsertAt ( const T & item ); void InsertAfter ( const T & item ); //删除函数 T DeleteFront ( void ); void DeleteAt ( void ); //返回当前结点的data域值 T & Data ( void ); //清空整个链表 void ClearList ( void ); //插入并保持有序 void InsertSequence ( const T & item ); Node < T > * GetFrontNode (); }; //////////////////////////////////////////////// template < class T > Node < T > * LinkedList < T > :: GetFrontNode () { return front; } template < class T > Node < T > * LinkedList < T > :: GetNode ( const T & item, Node < T > * PtrNext ) { Node < T > * newNode; newNode = new Node < T > ( item, PtrNext ); if ( newNode == NULL ) { cerr << "Memory allocation failure!" << endl; exit ( 1 ); } return newNode; } template < class T > void LinkedList < T > :: FreeNode ( Node < T > * p ) { delete p; } template < class T > void LinkedList < T > :: CopyList ( const LinkedList < T > & L ) { ///////////////////////////// } template < class T > LinkedList < T > :: LinkedList ( void ) { front = rear = currptr = prevptr = NULL; size = 0; position = -1; } template < class T > LinkedList < T > :: LinkedList ( const LinkedList < T > & L ) { ///////////////////////////////// } template < class T > LinkedList < T > :: ~LinkedList ( void ) { currptr = front; Node < T > * p; while ( currptr != NULL ) { p = currptr -> NextNode (); delete currptr; currptr = p; } } template < class T > LinkedList < T > & LinkedList < T > :: operator = ( const LinkedList < T > & L ) { ///////////////////////////////// } template < class T > int LinkedList < T > :: ListSize ( void ) const { return size; } template < class T > int LinkedList < T > :: ListEmpty ( void ) const { return size == 0; } template < class T > void LinkedList < T > :: Reset ( int pos ) { prevptr = currptr = front; position = 0; } template < class T > void LinkedList < T > :: Next ( void ) { if ( currptr == front ) { currptr = currptr -> NextNode (); position++; } else { prevptr = currptr; currptr = currptr -> NextNode (); position++; } } template < class T > int LinkedList < T > :: EndOfList ( void ) const { return currptr == NULL; } template < class T > int LinkedList < T > :: ThisPosition ( void ) const { return position; } template < class T > void LinkedList < T > :: InsertFront ( const T & item ) { front = GetNode ( item, front ); if ( rear == NULL ) rear = front; currptr = prevptr = front; position = 0; size++; } template < class T > void LinkedList < T > :: InsertRear ( const T & item ) { if ( rear != NULL ) { rear -> next = GetNode ( item ); rear = rear -> next; } else { rear = front = currptr = prevptr = GetNode ( item ); position = 0; } size++; } template < class T > void LinkedList < T > :: InsertAt ( const T & item ) { prevptr -> next = GetNode ( item, currptr ); if ( front == NULL ) front = rear; else prevptr = prevptr -> next; position++; size++; } template < class T > void LinkedList < T > :: InsertAfter ( const T & item ) { if ( currptr == NULL ) { InsertAt ( item ); } else { currptr -> next = GetNode ( item, currptr -> next ); prevptr = currptr; currptr = currptr -> next; position++; rear = front; while ( rear -> next != NULL ) rear = rear -> next; size++; } } template < class T > T LinkedList < T > :: DeleteFront ( void ) { T d; if ( currptr == front ) { cerr << "There is not a node before the current node!" << endl; exit ( 1 ); } if ( prevptr == front ) { d = front -> data; delete front; if ( size == 1 ) front = rear = currptr =prevptr = NULL; else front = prevptr = currptr; } else { Node < T > * q = front, * p = prevptr; while ( q -> next != prevptr ) { q = q -> next; } q -> next = currptr; d = p -> data; delete p; prevptr = q; } size--; position--; return d; } template < class T > void LinkedList < T > :: DeleteAt ( void ) { if ( currptr != NULL ) { if ( currptr == front ) { front = preptr= currptr -> next; delete currptr; currptr = front; } else { prevptr -> next = currptr -> next; delete currptr; currptr = prevptr -> next; } if ( front == NULL ) rear = front; else { rear = front; while ( rear -> next != NULL ) rear = rear -> next; } if ( currptr == NULL ) position = -1; size--; } } template < class T > T & LinkedList < T > :: Data ( void ) { if ( currptr == NULL ) { cerr << "The node is empty!" << endl; exit ( 1 ); } return currptr -> data; } template < class T > void LinkedList < T > :: ClearList ( void ) { currptr = front; Node < T > * p; while ( currptr != NULL ) { p = currptr -> next; delete currptr; currptr = p; } prevptr = currptr = front = rear = NULL; position = -1; size = 0; } ////////////////////////////////////////// //函数，使插入一个结点并保持连表有序 template < class T > void LinkedList < T > :: InsertSequence ( const T & item ) { for ( Reset () ; Data() < item && EndOfList () == 0 ; Next () ) ; InsertAt ( item ); }