C++实现单链表的构造

本文实例为大家分享了C++实现单链表的构造代码，供大家参考，具体内容如下

单链表的构造，包括最常用函数,setData(),Insert(),Remove(),getData(),Search()。

代码如下：

#include 
#include 
 
using namespace std;
 
template
struct linkNode{
  T data;
  linkNode *link;
  linkNode(linkNode *ptr=NULL){link=ptr;}
  linkNode(const T& item, linkNode *ptr=NULL){data=item; link=ptr;}
};
 
template
class List{
public:
  List(){first=new linkNode;}
  List(const T& x){first=new linkNode(x);}
  List(List &L);
  ~List(){makeEmpty();}
  void makeEmpty();
  int Length()const;
  linkNode *getHead()const{return first;}
  linkNode *Search(T x);
  linkNode *Locate(int i);
  bool getData(int i, T &x)const;
  void setData(int i,T &x);
  bool Insert(int i,T &x);
  bool Remove(int i, T &x);
  bool IsEmpty()const{return (first->link==NULL)?true:false;}
  bool IsFull()const{ return false;}
  void Sort();
  void inputFront(T endTag);
  void inputRear(T endTag);
  void output();
  List& operator=(List &L);
private:
  linkNode *first;
};
 
template
void List::makeEmpty(){
  //if(first->link==NULL)return;
  linkNode *p=first->link;
  while(p!=NULL){
   first->link=p->link;
   delete p;
   p=first->link;
  }
}
 
template
linkNode *List::Search(T x){
  linkNode *p=first->link;
  while(p!=NULL){
   if(p->data==x)break;
   p=p->link;
  }
  return p;//无论是否找到都返回p，若找到则返回p，没有则返回空指针
}
 
template
linkNode *List::Locate(int i){
  //这个定位函数的作用还是非常大的，方便后来的函数根据i定位到相应位置的节点
  if(i<0)return NULL;
  int sum=0;
  linkNode *p=first;
  while(p!=NULL&&sumlink;
  }
  return p;//无论是否为空指针，返回的都是到达i位置的指针，如果没有到达就是已经到结尾了
}
 
template
bool List::getData(int i, T& x)const{
  if(i<0)return false;
  linkNode *p=Locate(i);
  if(p==NULL)return false;
  else{
  x=p->data;
  return true;
  }
}
 
template
void List::setData(int i, T& x){
  if(i<0)return;
  linkNode *p=Locate(i);
  if(p==NULL)return;
  else{
   p->data=x;
  }
}
 
template
bool List::Insert(int i, T &x){
   //linkNode *pre=Locate(i-1);
   //这里是指插入到第i个元素之后的情况
   linkNode *cur=Locate(i);
   if(cur==NULL)return false;
   linkNode *p=new linkNode(x);
   if(p==NULL){cerr<<"存储分配错误!"<link=cur->link;
     cur->link=p;
     return true;
   }
}
 
template
bool List::Remove(int i, T& x){
  //删除第i个位置的元素
  linkNode *pre=Locate(i-1);
  if(pre==NULL)return false;
  linkNode *current=pre->link;
  if(current==NULL)return false;
  x=current->data;
  pre->link=current->link;
  delete current;
  return true;
}
 
template
void List::output(){
  linkNode *current=first->link;
  while(current!=NULL){
   cout<data<<" ";
   current=current->link;
  }
}
 
template
List& List::operator=(List& L){
  //这是赋值方法
  linkNode *srcptr=L.getHead(), *p=srcptr->link;
  linkNode *desptr=first=new linkNode;
  T value;
  while(p!=NULL){
   value=p->data;
   desptr->link=new linkNode(value);
   desptr=desptr->link;
   p=p->link;
  }
  return *this;
  //用上面这种方法可以更好地实现赋值
//  linkNode *pre=L.getHead();
//  if(pre==NULL){
//   first=NULL;
//   return *this;
//  }
//  linkNode *p=first=new linkNode;
//  first->link=p;
//  int sum=L.Length();
//  T &x;
//  int i=1;
//  while(i<=sum){
//   L.getData(i++,x);
//   p=new linkNode(x);
//   p=p->link;
//  }
//  return *this;
 
}
 
template
int List::Length()const{
  int sum=0;
  linkNode *p=first->link;
  while(p!=NULL){
   sum++;
   first->link=p->link;
   delete p;
   p=first->link;
  }
  return sum;
}
 
 
//前插法建立单链表
template
void List::inputFront(T endTag){
  linkNode *newNode;
  T value;
  makeEmpty();
  cin>>value;
  while(value!=endTag){
   newNode=new linkNode(value);
   if(newNode==NULL){cerr<<"内存分配错误！"<link=first->link;
   first->link=newNode;
   cin>>value;
  }
}
 
//后插法建立单链表
template
void List::inputRear(T endTag){
  linkNode *newNode=new linkNode, *last;
  T value;
  last=first=new linkNode;
  cin>>value;
  while(value!=endTag){
   newNode=new linkNode(value);
   if(newNode==NULL){cerr<<""<link=newNode;
   last=newNode;
   cin>>value;
  }
}
 
//复制构造函数
template
List::List(List &L){
  //复制构造函数
  T value;
  linkNode *srcptr=L.gethead(), p=srcptr->link;
  linkNode *desptr=first->link=new linkNode;
  while(p!=NULL){
   value=p->data;
   desptr=new linkNode(value);
   desptr=desptr->link;
   p=p->link;
  }
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持考高分网。