C++单链表的实现

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

template <class T>
struct LinkNode
{
    T data;
    LinkNode<T> *link;
    LinkNode(LinkNode<T> *ptr=NULL){link=ptr;}
    LinkNode(const T& item,LinkNode<T> *ptr=NULL){data=item;link=ptr;}
    //初始化的方式很有特性啊
};

template <class T>
class list
{
public:
    list();
    list(const T &x);
    list(list<T>& L);               //复制构造函数
    ~list(){makeEmpty();}
    void makeEmpty();
    int Length()const;
    LinkNode<T> *getHead()const {return first;}        //返回头结点的地址
    LinkNode<T> *Search(T &x);
    LinkNode<T> *Locate(int i);
    bool getData(int i,T &x);
    void setData(int i,T &x);
    bool Insert(int i,T &x);
    bool Remove(int i,T &x);
    void Sort();
    void inputFront(T endTag);
    void inputRear(T endTag);
    void output();
    list<T>& operator=(list<T>&L);
protected:
    LinkNode<T> *first;
};
#endif

View Code

  1 #include <iostream>
  2 #include <stdlib.h>
  3 #include "LinkedList.h"
  4 using namespace std;
  5 
  6 template <class T>
  7 list<T>::list()
  8 {
  9     first=new LinkNode<T>;                  //创建头结点
 10 };
 11 
 12 template <class T>
 13 list<T>::list(const T &x)
 14 {
 15     first=new LinkNode<T>(x);               //头节点中是链表的长度
 16 };
 17 
 18 template <class T>
 19 list<T>::list(list<T>& L)
 20 {
 21     T value;
 22     LinkNode<T> *srcptr=L.getHead();            //获取附加头节点
 23     LinkNode<T> *desptr=first=new LinkNode<T>;
 24     while(srcptr->link!=NULL)
 25     {
 26         value=srcptr->link->data;
 27         desptr->link=new LinkNode<T>(value);
 28         desptr=desptr->link;
 29         srcptr=srcptr->link;
 30     }
 31     desptr->link=NULL;
 32 };
 33 
 34 template <class T>
 35 void list<T>::makeEmpty()
 36 {
 37     LinkNode<T> *q;
 38     while(first->link!=NULL)
 39     {
 40         q=first->link;
 41         first->link=q->link;
 42         delete q;              //仅仅保留表头节点
 43     }
 44 };
 45 
 46 template <class T>
 47 int list<T>::Length()const                  //不能改变的最好还是用const修饰符
 48 {
 49     LinkNode<T> *p=first->link;            //从第一个节点开始算起
 50     int count=0;
 51     while(p->link!=NULL)
 52     {
 53         p=p->link;
 54         count++;
 55     }
 56     return count;
 57 };
 58 
 59 
 60 template <class T>
 61 LinkNode<T> *list<T>::Search(T &x)
 62 {
 63     LinkNode<T> *p=first->link;
 64     while(p->link!=NULL)
 65     {
 66         if(p->data==x)
 67             break;
 68         else
 69         {
 70             p=p->link;
 71         }
 72     }
 73     return p;              //最后位置而且没有找到的话，那么会返回NULL
 74     //返回值是一个地址啊。。。。
 75 };
 76 
 77 template <class T>
 78 LinkNode<T> *list<T>::Locate(int i)
 79 {
 80     if(i<0)
 81         cout<<"输入的位置不存在！"<<endl;
 82     LinkNode<T> *current=first->link;
 83     int k=0;
 84     while (current->link!=NULL&&k<i)
 85     {
 86         current=current->link;
 87         k++;
 88     }
 89     return current;
 90 };
 91 
 92 template <class T>
 93 bool list<T>::getData(int i,T& x)            //找到找不到，找到是否符合！
 94 {
 95     if (i<0)
 96     {
 97         cout<<"The "<<i<<"is not illegal!"<<endl;
 98         return false;
 99     }
100     LinkNode<T> *current=Locate(i);
101     if (current==false)
102     {
103         cout<<"The "<<i<<"is not exist"<<endl;
104         return false;
105     }
106     else
107     {
108         x==current->data;
109         return true;
110     }
111 };
112 
113 template <class T>
114 void list<T>::setData(int i,T &x)
115 {
116     if (i<0)
117     {
118         cout<<"i is illegal!";
119         return false;
120     }
121     LinkNode<T> *current=Locate(i);
122     if (current==NULL)
123     {
124         return false;
125     }
126     else
127     {
128         current->data=x;
129         return true;
130     }
131 };
132 
133 template <class T>
134 bool list<T>::Insert(int i,T &x)
135 {
136     LinkNode<T> *current=Locate(i-1);
137     if (current==NULL)
138     {
139         return false;
140     }
141     LinkNode<T> *newNode=new LinkNode<T>(x);            //新建节点
142     newNode->link=current->link;
143     current->link=newNode;
144     return true;
145 };
146 
147 template <class T>
148 bool list<T>::Remove(int i,T &x)                //删除节点！
149 {
150     LinkNode<T> *current=Locate(i-1);
151     if (current==NULL||current->link==NULL)
152     {
153         cout<<"i is not illegal!";
154         return false;
155     }
156     LinkNode<T> *del=new LinkNode<T>;
157     del=current->link;
158     current->link=del->link;
159     x=del->data;
160     delete del;
161     return true;
162 }
163 
164 template <class T>
165 void list<T>::output()
166 {
167     LinkNode<T> *current = first->link;
168     while(current!=NULL)
169     {
170         cout<<current->data<<endl;
171         current=current->link;
172     }
173 };
174 
175 template <class T>
176 list<T>& list<T>::operator=(list<T> &L)
177 {
178     T value;
179     LinkNode<T> *srcptr=L.getHead();
180     LinkNode<T> *destptr=first=new LinkNode<T>;
181     while(srcptr->link!=NULL)
182     {
183         value=srcptr->link->data;
184         destptr->link=new LinkNode<T>(value);
185         destptr=destptr->link;
186         srcptr=srcptr->link;
187     }
188     destptr->link=NULL;
189     return *this;
190     //当调用一个成员函数时，有一个指向请求这个调用的对象的指针作为一个参数将自动被传送给这个函数，这个指针叫做this.
191 };
192 
193 template <class T>
194 void list<T>::inputFront(T endTag)
195 {
196     LinkNode<T> *newNode;T val;
197     makeEmpty();
198 
199     cin>>val;
200     while(val!=endTag)
201     {
202         newNode=new LinkNode<T>(val);
203         if (newNode==NULL)
204         {
205             cout<<"存储分配错误！"<<endl;
206             exit(1);
207         }
208         newNode->link=first->link;
209         first->link=newNode;           //新建立元素总是在前面
210         cin>>val;
211     }
212 };
213 
214 template <class T>
215 void list<T>::inputRear(T endTag)
216 {
217     LinkNode<T> *newNode,*last;
218     T val;
219     makeEmpty();
220     cin>>val;
221     last=first;
222     while(val!=endTag)
223     {
224         newNode=new LinkNode<T>(val);
225         if (newNode==NULL)
226         {
227             cout<<"存储分配错误！"<<endl;
228             exit(1);
229         }
230         last->link=newNode;
231         last=newNode;
232         cin>>val;
233     }
234     last->link=NULL;
235 };
236 
237 #include <iostream>
238 #include "LinkedList.h"
239 
240 using namespace std;
241 
242 int main()
243 {
244     list<int> a;
245     list<int> b(10);
246     list<int> c(b);
247     cout<<"请输入b链表中的元素,并以0结束："<<endl;
248     b.inputFront(0);                                    //这里有一个问题，当输入的数据大于十个的时候，没有任何影响！
249     cout<<"b 中的元素输出为(结果反向输出了，注意！)："<<endl;
250     b.output();
251     cout<<"输出复制构造函数c"<<endl;
252     cout<<"请输入a 链表中的元素："<<endl;
253     a.inputRear(0);
254     cout<<"正向输出a 链表"<<endl;
255     a.output();
256     int lenth;
257     lenth=a.Length();
258     cout<<"a 链表的长度："<<a.Length()<<endl;
259     cout<<"查找表中的元素x "<<endl;
260     LinkNode<int> *p;
261     int n;                  //这个不好初始化
262     cout<<"请输入要查找的元素："<<endl;
263     cin>>n;
264     while(n<0||n>lenth)
265     {
266         cout<<"The n you input is illegal!"<<endl;
267         cout<<"please input n again:"<<endl;
268         cin>>n;
269     }
270     p=a.Search(n);
271     if(p==NULL)
272         cout<<"Can not find n!"<<endl;
273     else
274     {
275         cout<<"Successfully find it!"<<endl;
276         cout<<"find the n     "<<p<<endl;        //输出为地址
277     }
278     cout<<"请输入要插入的元素和位置:"<<endl;
279     int m;
280     int s;
281     cin>>m>>s;
282     if (a.Insert(s,m)==false)
283     {
284         cout<<"插入失败！"<<endl;
285     }
286     else
287     {
288         cout<<"插入成功！"<<endl;
289         a.output();
290     }
291     //关键程序已经测试完成了，剩下的不做啦
292     return 0;
293 }

View Code

以上是根据数据结构书上改写的，加入了测试程序，虽然不完全，但是主要用的几个都测试了，剩下的比较懒啦。。。。