单链表（C++）

  1 #include<iostream>
  2 using namespace std;
  3 template<class T>
  4 struct Node
  5 {
  6     T data;
  7     Node<T> *next;
  8 };
  9 template<class T>
 10 class LinkList
 11 {
 12     public:
 13         LinkList();
 14         LinkList(T a[],int n);
 15         ~LinkList();
 16         int length();
 17         T Get(int i);
 18         void Insert(int i,T x);
 19         void Delete(int i);
 20         void PrintList();
 21         int Locate(T x);
 22     private:Node<T> *first;//单链表的头指针；
 23 };
 24 template<class T>
 25 LinkList<T>::LinkList()//无参构造函数
 26 {
 27     first=new Node<T>;   
 28     first=NULL;           
 29 }
 30 /*template<class T>
 31 LinkList<T>::LinkList(T a[],int n)//头插法
 32 {   
 33     first=new Node<T>;
 34     first->next=NULL;
 35     
 36     for( int i=0;i<n;i++)
 37     {
 38         Node<T> *s;
 39         s=new Node<T>;
 40         s->data=a[i];
 41         s->next=first->next;
 42         first->next=s;
 43 
 44     }
 45 }*/
 46 template<class T>
 47 LinkList<T>::LinkList(T a[],int n)//尾插法
 48 {
 49     first=new Node<T>;
 50     first->next=NULL;
 51 
 52     Node<T> *p;
 53     p=first;
 54 
 55     for( int i=0;i<n;i++)
 56     {
 57         Node<T> *s=new Node<T>;
 58 
 59         s->data=a[i];
 60 
 61         s->next=p->next;
 62 
 63         p->next=s;
 64 
 65         p=p->next;
 66 
 67     }
 68 }
 69 
 70 template<class T>
 71 LinkList<T>::~LinkList()
 72 {
 73     Node<T> *q=new Node<T>;
 74     while(first!=NULL)
 75     {
 76         q=first;
 77         first=first->next;
 78         delete q;
 79     }
 80 }
 81 template<class T>
 82 void LinkList<T>::PrintList()
 83 { 
 84     Node<T> *current;
 85     current=first->next;
 86     while(current!=NULL)        //遍历操作；
 87     {
 88         cout<<current->data<<" ";
 89         current=current->next;
 90     }
 91     cout<<endl;
 92 
 93 }
 94 template<class T>
 95 int LinkList<T>::length()
 96 {
 97     Node<T> *p;
 98     p=first->next;
 99     int count=0;
100     while(p!=NULL)
101     {
102         p=p->next;
103         count++;
104     }
105     return count;
106 }
107 template<class T>
108 T LinkList<T>::Get(int i)
109 {
110     Node<T> *p;
111     p=first->next;
112     int count =1;
113     while(count<i&&p!=NULL)
114     {
115         p=p->next;
116 
117         count++;
118 
119     }
120     if(p==NULL)
121         cout<<"位置输入错误"<<endl;
122     else
123         return p->data;
124 
125 }
126 template<class T>
127 void LinkList<T>::Delete(int i)
128 {
129     Node<T> *p;
130     p=first;
131     int count=0;
132     while(p!=NULL&&count<i-1)//找到指向要删除的结点的指针；
133     {
134         p=p->next;
135         count++;
136     }
137     if(p==NULL||i<0)
138     {
139         cout<<"输入错误"<<endl;
140     }
141     else                        //删除过程；
142     {
143         Node<T> *q;
144         q=p->next;
145         p->next=q->next;
146         delete q;
147     }
148 }
149 template<class T>
150 void LinkList<T>::Insert(int i,T x)
151 {
152     Node<T> *p;
153     p=first;
154     int count=0;
155     while(count<i-1&&p!=NULL)//找到要插入的位置
156     {
157         p=p->next;
158         count++;
159     }
160     if(i<0||p==NULL)
161     {
162         cout<<"输入错误"<<endl;
163     }
164     else                    //插入过程
165     {   Node<T> *s;
166         s=new Node<T>;
167         s->data=x;
168         s->next=p->next;
169         p->next=s;
170     }    
171 }
172 template<class T>
173 int LinkList<T>::Locate(T x)
174 {
175     Node<T> *p;
176     p=first->next;
177     int count =1;
178     while(p!=NULL)
179     {
180         p=p->next;
181         
182         count++;
183         if (p->data==x)
184         {
185             break;
186         }
187     }
188     if(p==NULL)
189         cout<<"位置输入错误"<<endl;
190     else
191         return count;
192 }
193 
194 void main()
195 {    
196     int a[10]={0,1,2,3,4,5,6,7,8,9};
197 
198     LinkList<int> c(a,10);
199     cout<<"打印链表:";
200     c.PrintList();
201 
202     cout<<"输出位置2的元素:"<<endl;
203     cout<<c.Get(2)<<endl;
204     
205     cout<<"在位置3插入0后:"<<endl;
206     c.Insert(3,0);
207     c.PrintList();
208 
209     cout<<"删除位置2的元素后:"<<endl;
210     c.Delete(2);
211     c.PrintList();
212 
213     cout<<"输出元素5的位置:"<<endl;
214     cout<<c.Locate(5)<<endl;
215     
216 }