单链表 c++实现

/*#include<iostream.h> #include"LinkedList.h" template<class T> List<T>::List(List<T>&L) { T value; LinkNode<T>*p=L.getHead(); LindNode<T>*q=first=new LinkNode<T>; while(p->link!=NULL) { value=p->link->data; q->link=new LinkNode<T>(value); q=q->link; p=p->link; } q->link=NULL; } template<class T> void List<T>::makeEmpty() { LinkNode<T>*q; while(first->link!=NULL) {q=first->link;first->link=q->link;delete q;} } template<class T> int List<T>::Length()const { LinkNode<T>*p=first->link; int count=0; while(p!=NULL) {count++;p=p->link;} return count; } template<class T> LinkNode<T>* List<T>::Search(T x) { LinkNode<T>*p=first->link; while(p!=NULL) {if(p->data==x) break; p=p->link; } return p; } template<class T> LinkNode<T>* List<T>::Locate(int i) { if(i<0) return NULL; LinkNode<T>*p=first;int k=0; while(p!=NULL&&k<i) {p=p->link;k++;} return p; } template<class T> T List<T>::getData(int i) { if(i<=0)return NULL; LinkNode<T>*p=Locate(i); if(p==NULL){cerr<<"i太大"<<endl;return -1;} else return p->data; } template<class T> void List<T>::setData(int i,T&x) { if(i<=0)return; LinkNode<T>*p=Locate(i); if(p==NULL)return; else p->data=x; } template<class T> bool List<T>::Insert(int i,T&x) { LinkNode<T>*p=Locate(i); if(p==NULL)return false; LinkNode<T>*newNode=new LinkNode<T>(x); if(newNode==NULL){cerr<<"存储分配错误"<<endl;exit(1);} newNode->link=p->link; p->link=newNode; return true; } template<class T> bool List<T>::Remove(int i,T&x) { LinkNode<T>*p=Locate(i-1); if(p==NULL||p->link==NULL)return false; LinkNode<T>*del=p->link; p->link=del->link; x=del->data; delete del; return true; } template<class T> void List<T>::output() { LinkNode<T>*p=first->link; while(p!=NULL) {cout<<p->data<<endl;p=p->link;} } template<class T> void List<T>::input()//后插,end为输入结束标志 { LinkNode<T>*newNode,*last; T val; first=new LinkNode<T>; if(first==NULL){cerr<<"存储分配错误"<<endl;exit(1);} cout<<"现在建链表,请依次输入结点的值(输入-1结束):"<<endl; cin>>val; last=first; int end=-1; while(val!=end) { newNode=new LinkNode<T>(val); if(newNode==NULL){cerr<<"存储分配错误"<<endl;exit(1);} last->link=newNode; last=newNode; cin>>val; } last->link=NULL; } /*template<class T> List<T> & List<T>::operate=(List<T>&L) { T value; LinkNode<T>*p=L.getHead(); LindNode<T>*q=first=new LinkNode<T>; while(p->link!=NULL) {value=p->link->data; q->link=new LinkNode<T>(value); q=q->link; p=p->link; } q->link=NULL; return *this; }*/