[数据结构]线性表之单链表的类模板实现

本文主要是介绍[数据结构]线性表之单链表的类模板实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

类的具体实现如下：

/
#include"LinearList.h"
#include <iostream>
#include <cstdlib>
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  //class List:public LinearList<T> 使用继承，有诸多问题
{
protected:LinkNode<T>* first;
public:List():first(new LinkNode<T>){}List(const T& item):first(new LinkNode<T>(item)){}List(const List& L);~List(){makeEmpty();delete first;}void makeEmpty();   //新增成员int Size()const{return 0;}   //空实现，这里没有实际意义int Length()const;LinkNode<T>* getHead()const{return first;}  //新增成员LinkNode<T>* Search(T& x)const;             //这2个与基类相比，返回值不同.不能进行覆盖。说明在继承类中，若基类函数和继承类函数的返回值不同，视为不同的函数，不能同名覆盖，相当于重载LinkNode<T>* Locate(int i)const;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 output();void inputFront(T endTag);void inputRear(T endTag);List<T>& operator=(const List<T>& L);
};template<class T>
List<T>::List(const List& L)
{LinkNode<T>* src=L.first->link;LinkNode<T>* dest=first=new LinkNode<T>;while(src!=NULL){dest->link=new LinkNode<T>(src->data);dest=dest->link;src=src->link;}//dest->link=NULL;
}template<class T>
List<T>& List<T>::operator=(const List<T>& L)
{LinkNode<T>* src=L.first->link;LinkNode<T>* dest=first=new LinkNode<T>;while(src!=NULL){dest->link=new LinkNode<T>(src->data);dest=dest->link;src=src->link;}//dest->link=NULL;return *this;
}template<class T>
void List<T>::makeEmpty()//删除了除头结点以外的所有节点，有头结点内存泄露的问题
{LinkNode<T>* del;while(first->link!=NULL){del=first->link;first->link=del->link;delete del;}
}template<class T>
int List<T>::Length()const
{int count=0;LinkNode<T>*  current=first->link;while(current!=NULL){++count;current=current->link;}return count;
}template<class T>
LinkNode<T>* List<T>::Search(T& x)const
{LinkNode<T>* current=first->link;while(current!=NULL&¤t->data!=x){current=current->link;}return current;
}template<class T>
LinkNode<T>* List<T>::Locate(int i)const
{LinkNode<T>* current=first->link;if(i<1||i>Length()){cerr<<"err"<<endl;exit(1);}int k=1;while(current!=NULL&&k<i){current=current->link;++k;}return current;
}template<class T>
bool List<T>::getData(int i,T& x)const
{if(i<1||i>Length()){cerr<<"err"<<endl;exit(1);}LinkNode<T>* current=Locate(i);if(current!=NULL){x=current->data;return true;}else{return false;}
}template<class T>
void List<T>::setData(int i,T& x)
{if(i<1||i>Length()){cerr<<"err"<<endl;exit(1);}LinkNode<T>* current=Locate(i);if(current!=NULL){current->data=x;}else{cerr<<"err"<<endl;exit(1);}
}template<class T>
bool List<T>::Insert(int i,T& x)
{LinkNode<T>* current=first;if(i<0||i>Length()){cerr<<"err"<<endl;exit(1);}int k=0;while(current!=NULL&&k<i){++k;current=current->link;}LinkNode<T>* newNode=new LinkNode<T>(x);if(newNode==NULL){cerr<<"err"<<endl;exit(1);}newNode->link=current->link;current->link=newNode;return true;
}template<class T>
bool List<T>::Remove(int i,T& x)
{LinkNode<T> *current=first,*del;if(i<=0||i>Length()){cerr<<"err"<<endl;exit(1);}int k=0;while(current!=NULL&&k<i-1){++k;current=current->link;}del=current->link;current->link=del->link;x=del->data;delete del;return true;
}template<class T>
void List<T>::output()
{LinkNode<T>* current=first->link;while(current!=NULL){cout<<"# :"<<current->data<<" ";current=current->link;}cout<<endl;
}template<class T>
void List<T>::inputFront(T endTag)
{LinkNode<T>* newNode;T val;makeEmpty();cin>>val;while(val!=endTag){newNode=new LinkNode<T>(val);if(newNode==NULL){cerr<<"err"<<endl;exit(1);}newNode->link=first->link;first->link=newNode;cin>>val;}
}template<class T>
void List<T>::inputRear(T endTag)
{LinkNode<T> *newNode,*last;T val;makeEmpty();last=first;cin>>val;while(val!=endTag){newNode=new LinkNode<T>(val);if(newNode==NULL){cerr<<"err"<<endl;exit(1);}newNode->link=last->link;last->link=newNode;last=newNode;cin>>val;}
}

测试程序如下：

int main(int argc, char* argv[])
{int val1=10;List<int> L1;List<int> L2(val1);cout<<"getHead(): "<<L1.getHead()->data<<endl;cout<<"getHead(): "<<L2.getHead()->data<<endl;int endTag=-1;L1.inputRear(endTag);L1.output();cout<<"Length(): "<<L1.Length()<<endl;int data=111,data1;LinkNode<int>* ptr=L1.Locate(2);cout<<"Locate: "<<ptr->data<<endl;L1.setData(2,data);L1.getData(2,data1);cout<<"getData(): "<<data1<<endl;int val2=3;ptr=L1.Search(val2);cout<<"Search(): "<<ptr->data<<endl;int data3=33;L1.Remove(3,val2);L1.Insert(3,data3);L1.output();List<int> L3(L1);L3.output();List<int> L4;L4=L1;L4.output();//L2.inputFront(endTag);// L2.output();//L2.makeEmpty();//L2.output();system("pause");return 0;
}

测试结果如下：

getHead(): -842150451
getHead(): 10
1 2 3 4 5 6 7 8 9 -1
# :1 # :2 # :3 # :4 # :5 # :6 # :7 # :8 # :9
Length(): 9
Locate: 2
getData(): 111
Search(): 3
# :1 # :111 # :4 # :33 # :5 # :6 # :7 # :8 # :9
# :1 # :111 # :4 # :33 # :5 # :6 # :7 # :8 # :9
# :1 # :111 # :4 # :33 # :5 # :6 # :7 # :8 # :9
请按任意键继续. . .

注意事项：

1。采用附加头结点的单链表的实现方法。可以统一插入和删除操作，从而不用区分是否是在第一个节点（或者空表）或者是其他位置处插入或者删除。

2.可以采用继承LinearList基类的方法生成派生类，但是实现比较复杂，没有必要。因为要完全覆盖基类纯虚函数的接口。

3.在继承体系结构中，即使只有返回值不同。也当作不同的函数，是不能同名覆盖的，相当于函数的重载。

4.遍历链表是要用一个current指针来遍历，让他指向不同的节点。如果有两个链表至少需要定义两个这样的指针来遍历。

5.删除节点时，需要用del指针保存要删除的节点，最后在删除。删除时当前指正指向前一个节点，插入时当期指针指向要插入的位置。

6.写程序时多画图，想清楚了在动手。可以适当举例验证。

这篇关于[数据结构]线性表之单链表的类模板实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---