线性表-单链表

单链表（线性链表）：它用指针表示结点间的逻辑关系。一个存储结点包含data（数据域），link(指针域,链域)。它的特点是长度可以很方便的进行扩充。数据元素的顺序与其链表表示中结点的物理顺序可能不一致，一般通过指针将各数据元素按逻辑顺序链接起来
由于链接表的每个结点要带指针域，所以存储空间比顺序存储要付出较大的代价。
LinkedList.h

#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include"linearList.h"

/*
  带头结点的单链表
*/
template<typename T>
class LinkNode{
public:
    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<typename T>
class List:public LinearList<T>{
protected:
    LinkNode<T> *first;//头结点
    LinkNode<T> *last;//最后一个元素
public:
    List();
    List(const T& x);
    List(List<T>& L);
    ~List();
    void makeEmpty();
    int Size()const;
    int Length()const;
    LinkNode<T>* getHeader()const;
    int Search(T& x)const;
    LinkNode<T>* Search(T x)const;
    int Locate(int i)const;
    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;
    bool IsFull() const;
    void Sort();
    void input();
    void output();
    List<T>& operator=(List<T>& L);
    void push_back(const T &x);
};

#endif // LINKEDLIST_H

LinkedList.cpp

#include<iostream>
#include<stdlib.h>
#include"LinkedList.h"

using namespace std;

template<typename T>
List<T>::List()
{
    first = new LinkNode<T>;
    last = first;
}

template<typename T>
List<T>::List(const T &x)
{
    first = new LinkNode<T>(x);
}

template<typename T>
List<T>::~List()
{
    makeEmpty();
}

template<typename T>
List<T>::List(List<T> &L)
{
    T value;
    LinkNode<T> *srcptr = L.getHeader();
    LinkNode<T> *destptr = first = new LinkNode<T>;
    while(srcptr->link!=NULL){
        value = srcptr->link->data;//第一个结点的值
        destptr->link = new LinkNode<T>(value);
        destptr = destptr->link;
        srcptr = srcptr->link;
    }
    destptr->link = NULL;//不要忘了把最后一个点的值设成NULL
}

/*
  从前往后删除
*/
template<typename T>
void List<T>::makeEmpty()
{
    LinkNode<T> *p;
    while(first->link!=NULL){
        p = first->link;
        first->link = p->link;
        delete p;
    }
}

template<typename T>
int List<T>::Length()const
{
    int i=0;
    LinkNode<T> *p = first->link;
    while(p!=NULL){
        i++;
        p = p->link;
    }
    return i;
}

template<typename T>
int List<T>::Size() const
{
    return Length();
}

template<typename T>
LinkNode<T>* List<T>::getHeader()const
{
    return first;
}

template<typename T>
int List<T>::Search(T&)const
{
    return 0;
}

template<typename T>
LinkNode<T>* List<T>::Search(T x)const
{
    LinkNode<T> *p = first->link;
    while(p!=NULL){
        if(p->data==x){
            break;
        }
        p = p->link;
    }
    return p;
}

template<typename T>
int List<T>::Locate(int)const
{
   return 0;
}

template<typename T>
LinkNode<T>* List<T>::locate(int i)const
{
    if(i<0)
        return NULL;
    LinkNode<T> *p = first;
    int j=0;
    while(p!=NULL&&j<i){
        p = p->link;
        j++;
    }
    return p;
}

template<typename T>
bool List<T>::getData(int i, T &x) const
{
    if(i<0)
        return NULL;
    LinkNode<T> *p = locate(i);
    if(NULL!=p){
        x = p->data;
        return true;
    }else{
        return false;
    }
}

template<typename T>
void List<T>::setData(int i, T &x)
{
    if(i<=0)//0是头结点(first)
        return;
    LinkNode<T> *p = locate(i);
    if(NULL!=p){
        p->data = x;
    }
}

/*
  将x插入在第i个结点之后
*/
template<typename T>
bool List<T>::Insert(int i, T &x)
{
    if(i<=0)
        return false;
    LinkNode<T> *p = locate(i);
    if(NULL!=p){
        LinkNode<T> *newNode = new LinkNode<T>(x);
        if(NULL==newNode){
            cerr << "Memory allocation error" << endl;
            exit(1);
        }
        newNode->link = p->link;
        p->link = newNode;
        return true;
    }else{
        return false;
    }
}

template<typename T>
bool List<T>::Remove(int i, T &x)
{
    if(i<=0)
        return false;
    LinkNode<T> *current = locate(i-1);
    if(NULL!=current&&NULL!=current->link){
        LinkNode<T> *delPtr = current->link;
        current->link = delPtr->link;
        x = delPtr->data;
        delete delPtr;
        return true;
    }else{
        return false;
    }
}

template<typename T>
bool List<T>::IsEmpty() const
{
    return first->link==NULL?true:false;
}

template<typename T>
bool List<T>::IsFull() const
{
    return false;
}

template<typename T>
void List<T>::Sort()
{

}

template<typename T>
void List<T>::input()
{

}

template<typename T>
void List<T>::output()
{
    LinkNode<T> *current = first->link;
    while(NULL!=current){
        cout << current->data << " ";
        current = current->link;
    }
    cout << endl;
}

template<typename T>
List<T>& List<T>::operator=(List<T>& L)
{
    T value;
    LinkNode<T> *srcptr = L.getHeader();
    LinkNode<T> *destptr = first = new LinkNode<T>;
    while(srcptr->link!=NULL){
        value = srcptr->link->data;
        destptr->link = new LinkNode<T>(value);
        srcptr = srcptr->link;
        destptr = destptr->link;
    }
    destptr->link = NULL;
    return *this;
}

template<typename T>
void List<T>::push_back(const T &x)
{
    LinkNode<T> *newNode = new LinkNode<T>(x);
    last->link = newNode;
    last = last->link;
}

int main()
{
    List<int> l;
    int num = 0;
    for(int i=1;i<=10;i++){
        l.push_back(i);
    }
    l.Remove(3,num);
    cout << "num:" << num << endl;
    l.push_back(11);
    num = 120;
    l.Insert(6,num);
    l.getData(8,num);
    cout << "8:" << num << endl;
    l.output();
    cout << "Empty?" << l.IsEmpty() << endl;
}

num:3
8:8
1 2 4 5 6 7 120 8 9 10 11 
Empty?0