C++实现单链表的构造

2023-07-26 16:00:07 154

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

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

代码如下：

#include
#include

usingnamespacestd;

template
structLinkNode{
Tdata;
LinkNode*link;
LinkNode(LinkNode*ptr=NULL){link=ptr;}
LinkNode(constT&item,LinkNode*ptr=NULL){data=item;link=ptr;}
};

template
classList{
public:
List(){first=newLinkNode;}
List(constT&x){first=newLinkNode(x);}
List(List&L);
~List(){makeEmpty();}
voidmakeEmpty();
intLength()const;
LinkNode*getHead()const{returnfirst;}
LinkNode*Search(Tx);
LinkNode*Locate(inti);
boolgetData(inti,T&x)const;
voidsetData(inti,T&x);
boolInsert(inti,T&x);
boolRemove(inti,T&x);
boolIsEmpty()const{return(first->link==NULL)?true:false;}
boolIsFull()const{returnfalse;}
voidSort();
voidinputFront(TendTag);
voidinputRear(TendTag);
voidoutput();
List&operator=(List&L);
private:
LinkNode*first;
};

template
voidList::makeEmpty(){
//if(first->link==NULL)return;
LinkNode*p=first->link;
while(p!=NULL){
first->link=p->link;
deletep;
p=first->link;
}
}

template
LinkNode*List::Search(Tx){
LinkNode*p=first->link;
while(p!=NULL){
if(p->data==x)break;
p=p->link;
}
returnp;//无论是否找到都返回p，若找到则返回p，没有则返回空指针
}

template
LinkNode*List::Locate(inti){
//这个定位函数的作用还是非常大的，方便后来的函数根据i定位到相应位置的节点
if(i<0)returnNULL;
intsum=0;
LinkNode*p=first;
while(p!=NULL&&sumlink;
}
returnp;//无论是否为空指针，返回的都是到达i位置的指针，如果没有到达就是已经到结尾了
}

template
boolList::getData(inti,T&x)const{
if(i<0)returnfalse;
LinkNode*p=Locate(i);
if(p==NULL)returnfalse;
else{
x=p->data;
returntrue;
}
}

template
voidList::setData(inti,T&x){
if(i<0)return;
LinkNode*p=Locate(i);
if(p==NULL)return;
else{
p->data=x;
}
}

template
boolList::Insert(inti,T&x){
//LinkNode*pre=Locate(i-1);
//这里是指插入到第i个元素之后的情况
LinkNode*cur=Locate(i);
if(cur==NULL)returnfalse;
LinkNode*p=newLinkNode(x);
if(p==NULL){cerr<<"存储分配错误!"<link=cur->link;
cur->link=p;
returntrue;
}
}

template
boolList::Remove(inti,T&x){
//删除第i个位置的元素
LinkNode*pre=Locate(i-1);
if(pre==NULL)returnfalse;
LinkNode*current=pre->link;
if(current==NULL)returnfalse;
x=current->data;
pre->link=current->link;
deletecurrent;
returntrue;
}

template
voidList::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=newLinkNode;
Tvalue;
while(p!=NULL){
value=p->data;
desptr->link=newLinkNode(value);
desptr=desptr->link;
p=p->link;
}
return*this;
//用上面这种方法可以更好地实现赋值
//LinkNode*pre=L.getHead();
//if(pre==NULL){
//first=NULL;
//return*this;
//}
//LinkNode*p=first=newLinkNode;
//first->link=p;
//intsum=L.Length();
//T&x;
//inti=1;
//while(i<=sum){
//L.getData(i++,x);
//p=newLinkNode(x);
//p=p->link;
//}
//return*this;

}

template
intList::Length()const{
intsum=0;
LinkNode*p=first->link;
while(p!=NULL){
sum++;
first->link=p->link;
deletep;
p=first->link;
}
returnsum;
}


//前插法建立单链表
template
voidList::inputFront(TendTag){
LinkNode*newNode;
Tvalue;
makeEmpty();
cin>>value;
while(value!=endTag){
newNode=newLinkNode(value);
if(newNode==NULL){cerr<<"内存分配错误！"<link=first->link;
first->link=newNode;
cin>>value;
}
}

//后插法建立单链表
template
voidList::inputRear(TendTag){
LinkNode*newNode=newLinkNode,*last;
Tvalue;
last=first=newLinkNode;
cin>>value;
while(value!=endTag){
newNode=newLinkNode(value);
if(newNode==NULL){cerr<<""<link=newNode;
last=newNode;
cin>>value;
}
}

//复制构造函数
template
List::List(List&L){
//复制构造函数
Tvalue;
LinkNode*srcptr=L.gethead(),p=srcptr->link;
LinkNode*desptr=first->link=newLinkNode;
while(p!=NULL){
value=p->data;
desptr=newLinkNode(value);
desptr=desptr->link;
p=p->link;
}
}

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

声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

C++实现单链表的构造

热门推荐

随机推荐