时间:2021-05-20
本文实例为大家分享了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)?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; }}以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
C++实现静态单链表的实例利用数组实现的静态单链表,与严蔚敏书实现略有不同,不另设回收空间。有任何BUG或错误,希望各位朋友多多反馈~~感激不尽/*Author
双向链表C++的实现本文是通过C++的知识实现数据结构中的双向链表,这里不多说了,代码注释很清楚,实现代码://doubleLinkListimplementw
本文实例讲述了C++双向循环列表用法。分享给大家供大家参考。具体如下:#includeusingnamespacestd;//结构体构造链表
本文实例为大家分享了C++使用模板实现单链表的具体代码,供大家参考,具体内容如下这一篇可以和上一篇点击打开链接模板实现单链表进行对比看类外实现和类内实现的区别代
本文以实例详细描述了C#定义并实现单链表的过程及原理。一般来说C#定义并实现单链表,代码包括构成链表的结点定义、用变量来实现表头、清空整个链表、链表复位,使第一