C++如何实现单链表的构造-创新互联

这篇文章主要讲解了C++如何实现单链表的构造，内容清晰明了，对此有兴趣的小伙伴可以学习一下，相信大家阅读完之后会有帮助。

公司主营业务：网站制作、网站设计、移动网站开发等业务。帮助企业客户真正实现互联网宣传，提高企业的竞争能力。成都创新互联公司是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化，感谢他们对我们的高要求，感谢他们从不同领域给我们带来的挑战，让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。成都创新互联公司推出株洲免费做网站回馈大家。

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

代码如下：

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

另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。

网页标题：C++如何实现单链表的构造-创新互联
URL链接：https://www.cdcxhl.com/article18/dijcgp.html

成都网站建设公司_创新互联，为您提供网站排名、网站营销、外贸网站建设、网站制作、定制网站、网站建设

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联