单链表模版

以下是C++类模版，存起来，以后想用，修改下就OK
View Code

template<class T>
struct Node{
    T data;                          //数据域，存放表元素
    Node *next;                      //指针域，指向下一个节点
};
template<class T>
class LinkList{
private:
    Node<T>*Head;
public:
    LinkList();                       //构造函数
    ~LinkList();                      //析构函数
    void CreateList(int n);           //创建具有n个元素的线性链表
    void Insert(int i,T e);           //在表中第i个位置插入元素
    T Delete(int i);                  //删除表中第i个元素
    T GetElem(int i);                 //获取第i个元素的值
    int Locate(T e);                  //在链表中查找值为e的元素
    T prior(T e);                     //放回e的前驱
    int Empty();                      //测试表空
    int Length();                     //测表长
    void ListDisplay();               //输入表的元素
};
template<class T>
LinkList<T>::LinkList(){
    Head=new Node<T>;
    Head->next=NULL;
}
template<class T>
LinkList::~LinkList(){      //析构函数，释放链表所占的空间
    Node<T>*p;
    while(Head){            //从头节点开始，依次释放节点
        p=Head;
        Head=Head->next;
        delete p;
    }
    Head=NULL;              //头节点指向空
}
template<class T>
void LinkList<T>::CreateList(int n){
    //为插法，正序创建n个元素的线性表
    Node<T>*p,*s;            //设置工作职责，p指向为节点
    p=Head;
    cout<<"请依次输入"<<n<<"个元素的值："<<endl;
    for (int i=1;i<=n;i++)
    {
        s=new Node<T>;      //新建元素的节点
        cin>>s->data;       //输入元素数据的值
        s->next=p->next;    //新节点链入表尾
        p->next=s;
        p=s;
    }
}
template<class T>
void LinkList<T>::Insert(int i,T e){ //在指定位置插入元素，前插法
    int j=0;
    Node<T>*p;
    p=Head;
    while(p&&j<i-1){                //定位到指点节点的前节点
        p=p->next;
        j++;
    }
    if (!p||j>i-1)                 //如果插入位置不合理，i<0或者i>表长
       throw"位置异常";
    else{
        Node<T>*s;
        s=new Node<T>;             //创建一个新节点
        s->data=e;
        s->next=p->next;           //节点s链接到p节点之后
        p->next=s;
    }
}
template<class T>
T LinkList<T>::Delete(int i){        //删除指定位置的元素  
    T x;
    Node<T>*p,*q;                    //设置工作指针，既指向该节点的前驱和后驱
    p=Head;
    int j=0;
    while(p->next&&j<i-1){           //定位到删除节点的前驱
        p=p->next;
        j++;
    }
    if (!p||j>i-1)                  //位置不合理
       throw"位置异常";
    else{
        q=p->next;                  //暂存删除节点位置
        p->next=q->next;            //从链表中摘除删除节点
        x=q->data;                  //删除数据元素的值
        delete q;                   //释放删除节点
        return x;                   //放回删除节点的值
    }
}
template<class T>                //按元素值查找，放回元素在表中的位序，否则放回0
int LinkList<T>::Locate(T e){
    int j=1;
    Node<T>*p;
    p=Head->next;                //首元节点为查找的起始节点
    while(p&&p->data!=e){
        p=p->next;
        j++;
    }
    if(p==NULL) 
        return 0;                 //未找到，放回0
    else 
        return j;                 //找到，返回位序
}
template<class T>
T LinkList<T>::GetElem(int i){//获取第i个元素的值
    Node<T>*p;
    p=Head->next;
    int j=1;
    while(p&&j<i){//定位到第i个节点
        p=p->next;
        j++;
    }
    if(!p||j>i)
        throw"异常位置";
    else
        return p->data;
}
template<class T>
int LinkList::Empty(){
    if (Head->next==NULL)
       return 1;
    else
        return 0;
}
template<class T>
T LinkList<T>::prior(T e){//返回元素的前驱
    Node<T>*p,*q;
    p=Head;
    q=p->next;
    while(q&&q->data!=e){
        p=q;
        q=q->next;
    }
    if(p==Head)
        throw"首元素，无前驱";
    else if(q==NULL)
        throw"元素不存在";
    else
        return p->data;
}
template<class T>
int LinkList<T>::Length(){//测表长
    int len=0;
    Node<T>*p;
    p=Head;
    while(p->next){
        len++;
        p=p->next;
    }
    return len;
}
template<class T>
void LinkList<T>::ListDisplay(){
    Node<T>*p;
    p=Head->next;
    int i=1;
    while(p){
        cout<<i<<"t";
        cout<<p->data<<endl;
        p->next;
        i++;
    }

}

原文链接: https://www.cnblogs.com/aijianiula/archive/2012/12/15/2819408.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍