单链表

  1 //2016.9.6
  2 #include <iostream>
  3 #include <cstdio>
  4 
  5 using namespace std;
  6 
  7 template<class T>
  8 struct node
  9 {
 10     T date;
 11     node<T> *next;
 12     node(node<T> *p = NULL){next = p;}
 13     node(T a, node<T> *p = NULL){date = a; next = p;}
 14 };
 15 
 16 template<class T>
 17 class List
 18 {
 19 private:
 20     node<T> *head;
 21 public:
 22     List(){head = new node<T>;}
 23     List(const T& a){head = new node<T>(a);}
 24     List(List<T>& L);
 25     ~List();
 26     node<T>* get_head(){return head;}
 27     node<T>* Locate(int pos);
 28     node<T>* Search(T x);
 29     int Length();
 30     bool get_date(int pos, T& x)const;
 31     void set_date(int pos, T& x);
 32     bool Insert(int pos, T& x);
 33     bool Remove(int pos, T& x);
 34     bool Empty(){return head->next == NULL;}
 35     void output();
 36     List<T>& operator=(List<T> &L);
 37 };
 38 
 39 template<class T>
 40 List<T>& List<T>::operator=(List<T> &L)
 41 {
 42     T tmp;
 43     head = new node<T>;
 44     node<T>* p = head;
 45     node<T>* srcptr = L.get_head();
 46     while(srcptr->next != NULL)
 47     {
 48         tmp = srcptr->next->date;
 49         p->next = new node<T>(tmp);
 50         p = p->next;
 51         srcptr = srcptr->next;    
 52     }
 53     p->next = NULL;
 54     return *this;
 55 }
 56 
 57 template<class T>
 58 void List<T>::output()
 59 {
 60     node<T>* p = head->next;
 61     while(p != NULL)
 62     {
 63         cout<<p->date<<" ";
 64         p = p->next;
 65     }
 66     cout<<endl;
 67 }
 68 
 69 template<class T>
 70 List<T>::List(List<T>& L)
 71 {
 72     T tmp;
 73     head = new node<T>;
 74     node<T>* p = head;
 75     node<T>* srcptr = L.get_head();
 76     while(srcptr->next != NULL)
 77     {
 78         tmp = srcptr->next->date;
 79         p->next = new node<T>(tmp);
 80         p = p->next;
 81         srcptr = srcptr->next;
 82     }
 83     p->next = NULL;
 84 }
 85 
 86 template<class T>
 87 List<T>::~List()
 88 {
 89     node<T> *p;
 90     while(head->next != NULL)
 91     {
 92         p = head->next;
 93         head->next = p->next;
 94         delete p;
 95     }
 96 }
 97 
 98 template<class T>
 99 node<T>* List<T>::Search(T x)
100 {
101     node<T>* cur = head->next;
102     while(cur->next != NULL)
103     {
104         if(cur->date == x)return cur;
105         cur = cur->next;
106     }
107     return NULL;
108 }
109 
110 template<class T>
111 node<T>* List<T>::Locate(int pos)
112 {
113     if(pos < 0)return NULL; 
114     node<T>* p = head;
115     for(int i = 0; i < pos && p->next != NULL; i++, p = p->next)
116     ;
117     return p;
118 }
119 
120 template<class T>
121 int List<T>::Length()
122 {
123     int cnt = 0;
124     node<T> p = head-next;
125     while(p->next != NULL)
126     {
127         cnt++;
128         p = p->next;
129     }
130     return cnt;
131 }
132 
133 template<class T>
134 bool List<T>::get_date(int pos, T& x)const
135 {
136     if(pos < 0)return false;
137     node<T>* cur = Locate(pos);
138     if(cur==NULL)return false;
139     x = cur->date;
140     return true;
141 }
142 
143 template<class T>
144 void List<T>::set_date(int pos, T& x)
145 {
146     if(pos < 0)return ;
147     node<T>* cur = Locate(pos);
148     if(cur == NULL)return;
149     cur->date = x;
150 }
151 
152 template<class T>
153 bool List<T>::Insert(int pos, T& x)
154 {
155     node<T>* cur = Locate(pos);
156     if(cur == NULL)return false;
157     node<T>* p = new node<T>(x);
158     if(p == NULL)exit(1);
159     p->next = cur->next;
160     cur->next = p;
161     return true;
162 }
163 
164 template<class T>
165 bool List<T>::Remove(int pos, T& x)
166 {
167     node<T>* cur = Locate(pos-1);
168     if(cur == NULL || cur->next == NULL)return false;
169     node<T>* p = cur->next;
170     cur->next = p->next;
171     x = p->date; delete p;
172     return true;
173 }
174 
175 int main()
176 {
177     List<int> lis;
178     int a;
179     for(int i = 0; i < 10; i++)
180     {
181         lis.Insert(0, i);
182     }
183     lis.output();
184     lis.Remove(1, a);
185     lis.output();
186     a = 300;
187     lis.set_date(3, a);
188     lis.output();
189     List<int> lis2 = lis;
190     lis2.output();
191     cout<<"OK"<<endl;
192     return 0;
193 }