c++ list 实现 写着玩

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

原文链接: https://www.cnblogs.com/hylent/archive/2012/05/11/2496577.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍