1 #include "stdafx.h" 2 #include<iostream> 3 using namespace std ; 4 template<typename Type> class SingleList; 5 template <typename Type> 6 class ListNode{ 7 private:  8     friend class SingleList<Type>; 9     ListNode():m_next(NULL){}10     ListNode(const Type item , ListNode<Type>*next=NULL):m_data(item),m_next(next){}11     ~ListNode(){m_next=NULL;}12 public:13     Type getData(){return m_data ; }14     friend ostream& operator<<(ostream&,ListNode<Type>&);15 private:16     Type m_data;17     ListNode *m_next;18 };19 template<typename Type>20 ostream& operator<<(ostream& os , ListNode<Type>& out){21     os << out.m_data;22     return os;23 }

  1 #include "ListNode.h"  2 template<typename Type>  3 class SingleList{  4 public:  5     SingleList(){head = new ListNode<Type>;}  6     ~SingleList(){  7     makeEmpty();  8     delete head;  9     } 10 public: 11     void makeEmpty(); 12     int length(); 13     ListNode<Type>* find(Type item , int n)const; 14     ListNode<Type>* find(int n)const; 15     bool insert(Type item, int n =0); 16     Type remove(int n); 17     bool removeAll(Type item); 18     Type get(int n); 19     void ReverseSinglyLinkedList(); 20     void print(); 21 private: 22     ListNode<Type> *head; 23 }; 24 template <typename Type> 25 void SingleList<Type>::makeEmpty(){ 26     ListNode<Type> * pdel = NULL; 27     while(head->m_next!=NULL){ 28         pdel = head->m_next; 29         head->m_next = pdel->m_next; 30         delete pdel; 31     } 32 } 33 template <typename Type> 34 int SingleList<Type>::length(){ 35     int count = 0 ; 36     ListNode <Type> *p = head->m_next; 37     while (p!=NULL){ 38         p = p->m_next; 39         count++; 40     } 41     return count; 42 } 43 template<typename Type> 44 ListNode<Type>*SingleList<Type>::find(int n)const{ 45     if(n<0){cout << "out of the boundary"<< endl ;return NULL;} 46     ListNode<Type>* p = head; 47     for(int i =0 ; i<=n&&p ;i++){ 48         p = p->m_next; 49     } 50     if(p==NULL){ 51         cout << "can‘t find the element"<<endl; 52         return NULL; 53     } 54     return p; 55 } 56 template<typename Type> 57 ListNode<Type>*  SingleList<Type>::find(Type item , int n)const{ 58     if(n<1){ 59         cout << "the n is illegal" << endl; 60         return NULL; 61     } 62     ListNode<Type> *p = head; 63     int count = 0; 64     while(count!=n && p){ 65         p=p->m_next; 66         if(p->m_data=http://www.mamicode.com/=item) 67         count++; 68     } 69     if(p==NULL){ 70         cout << "can‘t find the element"<<endl; 71         return NULL; 72     } 73     return p; 74 } 75 template<typename Type> 76 bool SingleList<Type>::insert(Type item, int n=0){ 77     ListNode<Type> *p = head; 78     if(n<0){ 79         cout << "the n is illegal"<<endl; 80         return false; 81     } 82     ListNode<Type>* pnode = new ListNode<Type>(item); 83     ListNode<Type>* pmove = head; 84     if(pnode==NULL){ 85         cout << "Application is error "<< endl; 86         return false; 87     } 88     for(int i = 0 ; i<n&&pmove; i++){ 89         pmove = pmove->m_next; 90     } 91     if(pmove==NULL){ 92         cout << "the n is illegal " << endl; 93         return false; 94     } 95     pnode->m_next = pmove->m_next; 96     pmove->m_next = pnode; 97     return true; 98 } 99 template<typename Type>100 Type SingleList<Type>::remove(int n){101     if(n<0){102         cout << "can‘t find th element"<<endl;103         exit(0);104     }105     ListNode<Type>* pmove=head ,*pdel;106     for(int i = 0 ; i<n&&pmove ; i++){107         pmove = pmove->m_next;108     }109     if(pmove->m_next==NULL){110         cout << "can‘t find the element" <<endl;111         exit(0);112     }113     pdel = pmove->m_next;114     pmove->m_next = pdel->m_next;115     Type item = pdel->m_data;116     delete pdel;117     return item;118 }119 template <typename Type>120 bool SingleList<Type>::removeAll(Type item){121     ListNode<Type> *pmove = head,*pdel = pmove->m_next;122     while(pdel!=NULL){123         if(pdel->m_data=http://www.mamicode.com/=item){124             pmove->m_next = pdel->m_next;125             delete pdel;126             pdel = pmove->m_next;127             continue;128         }129         pmove=pmove->m_next;130         pdel = pdel->m_next;131         pmove = pmove->m_next;132     }133     return true;134 }135 template<typename Type>136 Type SingleList<Type>::get(int n){137     if(n<0){138         cout << "can‘t find the element "<<endl;139         exit(0);140     }141     ListNode<Type> *pmove =head->m_next;142     for(int i =0 ; i<n ; i++){143         pmove = pmove->m_next;144         if(NULL == pmove){145             cout << "can‘t find the element "<<endl;146             exit(0);147         }148     }149     return  pmove->m_data;150 }151 template <typename Type>152 void SingleList<Type>::print(){153     ListNode<Type> *pmove = head->m_next;154     cout << "head";155     while (pmove!=NULL){156         cout << "->" << pmove->m_data;157         pmove = pmove->m_next;158     }159     cout << endl;160 }161 template<typename Type>162 void SingleList<Type>::ReverseSinglyLinkedList(){163     if(head->m_next==NULL)return;164     ListNode<Type> *pmove = head->m_next;165     ListNode<Type> *temp ;166     while(pmove->m_next!=NULL){167         temp = pmove->m_next;168         pmove->m_next = temp->m_next;169         temp->m_next = head->m_next;170         head->m_next = temp;171     }172 }