1 #include <iostream>  2 using namespace std;  3   4   5 template<class T>  6 struct SLNode  7 {  8     T data;  9     SLNode<T>* next; 10     SLNode(SLNode<T>*nextNode=NULL){next=nextNode;} 11     SLNode(const T&item,SLNode<T>*nextNode=NULL) 12     { 13         data=http://www.mamicode.com/item; 14         next=nextNode; 15     } 16 }; 17  18 template<class T> 19 class SLList  20 { 21 public: 22        //构造函数 构造一个只有哨位结点的空表  23     SLList():length(0){head=tail=new SLNode<T>(); }  24     SLList(const T&item);       //构造函数  25     ~SLList();                  //析构函数 26          27     bool IsEmpty()const{return head->next==NULL;}//判断表是否为空  28     int Length()const{return length;};           //返回表的长度  29      30     //存取 将链表中第k个结点的字段值赋给item  31     bool Findk(int k,T&item)const;  32     //存取 当前结点的字段值赋给item  33     bool Findc(T&item)const;  34      35     //查找 在链表中查找字段值为x的结点并返回其在表中的位置  36     int Search(const T&item)const;  37       38     bool Delete(T& ITEM);                   //删除：删除当前结点并将其字段值赋给item 39     bool DeleteFromHead(T& ITEM);           //删除：删除表头结点并将其字段值赋给item 40     bool DeleteFromTail(T& ITEM);           //删除：删除表尾结点并将其字段值赋给item 41      42     void Insert(const T& item);            //插入：在当前结点后插入字段值为item的结点 43     void InsertFromTail(const T&item);     //插入：在表尾插入字段值为item的结点 44     void InsertFromHead(const T&item);     //插入：在哨位结点后插入字段值为item的结点  45      46     void output(); 47      48     void SetCH(){currptr=head;}   //设置当前指针为表头结点  49      50     bool SetCK(int k);          //设置当前指针为第k个结点  51      52 private: 53     int length;  54     SLNode<T>*head,*tail;//表头和表尾   55     SLNode<T>*currptr; 56 }; 57  58 //============================================================= 59 template<class T> 60 SLList<T>::SLList( const T&item)               //构造函数  61 { 62     tail=currptr=new SLNode<T>(item); 63     head=new SLNode<T>(currptr); 64     length=1; 65 } 66  67  68 template<class T> 69 SLList<T>::~SLList()                            //析构函数  70 { 71     while(head->next) 72     { 73         currptr=head->next; 74         head->next=currptr->next; 75         delete currptr; 76     } 77     delete head; 78     length=0; 79 } 80  81 //========================================================== 82  83  84 template<class T> 85 void SLList<T>::Insert(const T&item)        //插入：在当前结点后插入字段值为item的结点 86 { 87     if(currptr==head) 88     { 89         InsertFromHead(item); 90     } 91     if(currptr!=NULL) 92     {  93         currptr=new SLNode<T>(item,currptr->next); 94         if(tail==currptr)                95             tail=tail->next; 96         length++;  97     }  98     else cout<<"未指定当前结点!"<<endl;   99 }100 101 template<class T>102 void SLList<T>::InsertFromTail(const T&item)//插入：在表尾插入字段值为item的结点103 {104     tail->next=new SLNode<T>(item,NULL);105     tail=tail->next;106     length++;107 }108 109 template<class T>110 void SLList<T>::InsertFromHead(const T&item)//插入：在哨位结点后插入字段值为item的结点 111 {112     if(!length)113     {114         tail=head->next=new SLNode<T>(item,NULL);115         116     }117     else118         head->next=new SLNode<T>(item,head->next);119     length++;120 }121 122 //==========================================================123 124 template<class T>125 bool SLList<T>::Delete(T&ITEM)//删除：删除当前结点的后继节点并并将其字段值赋给item126 {127     if(currptr==tail||IsEmpty())128     {129         cout<<"没有后继节点 或者 是空表！\n";130         return 0; 131     }132     SLNode<T>*temp=currptr->next;133     currptr->next=temp->next;134     length--;135     ITEM=temp->data;136     delete temp;137     return 1;138 } 139 140 template<class T>141 bool SLList<T>::DeleteFromHead(T&ITEM)//删除：删除表头结点的后继节点并将其字段值赋给item142 {143     if(!length)144     {145         cout<<"空表!\n";146         return 0;        147     }148     SLNode<T>*temp=head->next;149     head->next=temp->next;150     length--;151     ITEM=temp->data;152     if(temp==tail) tail=head;153     delete temp;154     return 1;155 }156     157 template<class T>158 bool SLList<T>::DeleteFromTail(T& ITEM)//删除：删除表尾结点并将其字段值赋给item159 {160     if(IsEmpty())161     {162         cout<<"空表！\n";163         return 0; 164     }165     currptr=head;166     while(currptr->next!=tail)167     {168         currptr=currptr->next;169     }170     ITEM=currptr->data;171     delete tail;172     length--;173     tail=currptr;174     return 1;175     176 } 177 178 179 //===============================================================180 181 //存取 将链表中第k个结点的字段值赋给item 182 183 template<class T>184 bool SLList<T>::Findk(int k,T&item)const185 { 186     if(k>length) 187     {188         cout<<"表中没有第k个元素!"<<endl;  189         return 0;190     }191     SLNode<T>*temp=head;192     int i=0;193     while(k!=i)194     {195         temp=temp->next;196         i++;197     } 198     item=temp->data;199     return 1;200 }    201 202 203 //存取 当前结点的字段值赋给item 204 205 template<class T>206 bool SLList<T>::Findc(T&item)const207 {208     if(currptr!=NULL&&currptr!=head)209     {210         item=currptr->data;211         return 1;212     }213     cout<<"存取失败"<<endl; 214     return 0;215 }216     217     218 //========================================================= 219 template<class T> 220 void SLList<T>::output()221 {222     if(!IsEmpty()) 223     {224         currptr=head->next;225         while(currptr!=tail)226         {227             cout<<"["<<currptr->data<<"]"<<"->";228             currptr=currptr->next;229         }230         cout<<"["<<tail->data<<"]"<<endl;231     }232     else cout<<"空表！"<<endl; 233 }234 235 //======================================================236 template<class T>237 int SLList<T>::Search(const T&item)const238 { 239     SLNode<T>*temp=head;240     int i=0;241     while(temp->next!=NULL)242     {243         temp=temp->next;244         i++;245         if(temp->data=http://www.mamicode.com/=item)246             return i;247     } 248     cout<<"表中没有该元素"<<endl; 249 }    250 251 252 //=======================================================253 template<class T>254 bool SLList<T>::SetCK(int k)                //设置当前指针为第k个结点 255 {256     if(k>length) 257     {258         cout<<"表中没有第k个元素!"<<endl;  259         return 0;260     }261     SLNode<T>*temp=head;262     int i=0;263     while(k!=i)264     {265         temp=temp->next;266         i++;267     } 268     currptr=temp;    269     return 1;270 }271 272 //==========================================================273 int main()274 {275     SLList<int> A(5);276     A.InsertFromTail(6);277     A.InsertFromHead(2);278     A.SetCH();279     A.Insert(9);280     A.Insert(10);281     A.Insert(11);282     A.SetCK(2);283     int tmp;284     A.Findc(tmp);285     cout<<tmp<<endl;286     A.Findk(2,tmp);287     cout<<tmp<<endl;288     cout<<"6在第"<<A.Search(6)<<"个结点"<<endl; 289     A.output();290     A.SetCK(2);291     A.Delete(tmp);292     A.DeleteFromHead(tmp);293     cout<<tmp<<endl;294     A.DeleteFromTail(tmp);295     cout<<tmp<<endl;296     A.output();297 }