不带头节点的单链表创建

【核心代码】

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;
typedef int T;

struct LinkNode //结点定义
{
          T data;//数据域
      LinkNode* next;//链域
      LinkNode(const T& item, LinkNode* ptr=NULL)
      {
            data=item;
            next=ptr;
      }
      LinkNode(LinkNode* ptr=NULL)
      {
            next=ptr;
      }
};
bool compare (const LinkNode* a,const LinkNode *b);
class List
{
private:
      LinkNode * first;
public:
      List(){
        first=NULL;
      }
      List(const List& L){
          first=NULL;
          LinkNode * p;
          for(p=L.first;p!=NULL;p=p->next){
            this->InputRear(p->data);
          }
      }
      List& operator=(const List& L){
          if(&L==this)return *this;
          MakeEmpty();
          LinkNode * p;
          for(p=L.first;p!=NULL;p=p->next){
            this->InputRear(p->data);
          }
          return *this;
      }
      ~List(){
          MakeEmpty();
      }
      void InputFront(const T& elem){
          LinkNode * newnode=new LinkNode (elem,first);
          first=newnode;
      }
      void InputRear(const T& elem){
          LinkNode * newnode=new LinkNode (elem,NULL);
          LinkNode *p=first;
          if(p==NULL){
            InputFront(elem);
            return ;
          }

          for(;p->next!=NULL;p=p->next){
                ;
          }
          p->next=newnode;
      }
      void MakeEmpty(){
          LinkNode *tem;
          LinkNode *p=first;
          if(p==NULL){
            return;
          }
          for(;p->next!=NULL;p=tem){
            tem=p->next;
            delete p;
          }
          delete p;
          first=NULL;
      }
      int Length() const{
          int i=0;
          for(LinkNode *p=first;p!=NULL;p=p->next){
            i  ;
          }
          return i;
      }
      LinkNode* Search(const T& x){
          for(LinkNode*p=first;p!=NULL;p=p->next){
            if(p->data==x)return p;
          }
          return NULL;
      }
      LinkNode* Locate(int i){
        if(i>=1&&i<=this->Length()){
            for(LinkNode*p=first;p!=NULL;p=p->next){
                i--;
                if(i==0)return p;
            }
            return NULL;
        }
        else
            return NULL;
      }
      bool GetData(int i, T& x){
          if(this->Locate(i)==NULL)
                return false;
          else{
                LinkNode * p=this->Locate(i);
                x=p->data;
                return true;
          }

      }
      void SetData(int i, const T& x){
          LinkNode * p=this->Locate(i);
          p->data=x;
      }
      bool Insert(int i, const T& x){
          if(i<1)return false;
          if(i==1)this->InputFront(x);
          else if(i<=this->Length() 1){
                LinkNode * p=this->Locate(i-1);
                if(p==NULL)return false;
                LinkNode *newnode=new LinkNode(x);
                newnode->next=p->next;
                p->next=newnode;
                return true;
          }
          return false;
      }
      bool Remove(int i, T& x){
          if(this->IsEmpty()==true)return false;
          if(i==1){
                LinkNode *p=first;
                first=first->next;
                x=first->data;
            delete p;
            return false;
          }
          LinkNode *p=this->Locate(i-1);

          if(p==NULL)return false;
          else {
                LinkNode *de=p->next;
                p->next=(de)->next;
          x=de->data;
            delete de;
            return true;
          }

      }
      bool IsEmpty() const{
          if(first==NULL)return true;
          return false;
      }
      bool IsFull() const;
      void CopyList(const List& L){
          T tem;
          this->MakeEmpty();
          for(LinkNode * p=L.first;p!=NULL;p=p->next){
                tem=p->data;
                this->InputRear(tem);
          }
      }
      void Sort(){
          LinkNode *a[Length()];
          int i=0;
          if(first==NULL)return;
          for(LinkNode*p=first;p!=NULL;p=p->next){
                a[i]=new LinkNode ;
                a[i]->data=p->data;
                i  ;
          }
          sort(a,a i,compare);
          for(int j=0;j<i-1;j  ){
            a[j]->next=a[j 1];
          }
          a[i-1]->next=NULL;
          MakeEmpty();
          first=a[0];
      }
      friend ostream& operator<<(ostream& out, const List& L){
          for(LinkNode *p=L.first;p!=NULL;p=p->next){
            out<<p->data<<" ";
          }
          out<<endl;
            return out;
      }
      friend istream& operator>>(istream& in, List& L){
          T t;
          L.MakeEmpty();
            while(in>>t){
                L.InputRear(t);
                char c=cin.get();
                 if(c=='\n')break;
            }
            return in;
      }
};

int main()
{
      List lst;

      srand(time(NULL));
      for(int i=1; i<=2; i  )
            lst.Insert(i,rand()%50);
      lst.Sort();
      cout<<lst;
      int val;
      lst.Remove(2,val);
      cout<<lst;
      List lst1=lst;
      lst.MakeEmpty();
      lst=lst1;
      cout<<lst;
return 0;
}
bool compare (const LinkNode* a,const LinkNode *b){
    return a->data<b->data;
}