线性表的链表描述VS2008编译实现

LinearList.h

#ifndef LINEARLIST_H
#define LINEARLIST_H
#include <iostream>
using std::ostream;

template <typename T>
class Chain;

template <typename T>
ostream & operator<<(ostream & out, const Chain<T> & x);


template <typename T>
class ChainNode
{
    friend class Chain<T>;
private:
    T data;
    ChainNode<T> *link;
};
template<typename T>
class Chain {
    friend ostream & operator << <T> (ostream & out , const Chain<T>& x);
public:
    Chain() {first = 0;}
    ~Chain();
    bool IsEmpty() const {return first == 0;}
    int Length() const;
    bool Find(int k, T& x) const;
    int Search(const T& x) const;
    Chain<T>& Delete(int k, T& x);
    Chain<T>& Insert(int k, const T& x);
    void Output(ostream & out) const;
private :
    ChainNode<T> *first;
};

template<typename T>
Chain<T>::~Chain( )
{
    ChainNode<T> *next;
    while (first) {
        next = first->link;
        delete first;
        first = next;
    }
}

template<typename T>
int Chain<T>::Length() const
{
    ChainNode<T> *current = first;
    int len = 0;
    while (current) {
        len++ ;
        current = current->link;
    }
    return len;
}

template<typename T>
bool Chain<T>::Find(int k, T& x) const
{
    if (k < 1) return false;
    ChainNode<T> *current = first;
    int index = 1;
    while (index < k && current) {
        current = current->link;
        index++ ;
    }
    if (current)
    {x = current->data; return true;}
    return false;
}

template<typename T>
int Chain<T>::Search(const T& x) const
{
    ChainNode<T> *current = first;
    int index = 1;
    while (current && current->data != x)
    {
        current = current->link;
        index++;
    }
    if (current) return index;
    return 0;
}

template<typename T>
void Chain<T>::Output(ostream& out) const
{
    ChainNode<T> *current;
    for (current = first; current; current = current->link)
        out << current->data <<  "   ";
}

template<typename T>
Chain<T>& Chain<T>::Delete(int k, T& x)
{
    if (k < 1 || !first)
        //throw OutOfBounds();
        std::cout<<"OutOfBounds"<<std::endl;
    ChainNode<T> *p = first;

    if (k == 1)
        first = first->link;
    else {
        ChainNode<T> *q = first;
        for (int index = 1; index < k - 1 && q;  index++)
            q = q->link;
        if (!q || !q->link)
            //throw OutOfBounds();
            std::cout<<"OutOfBounds"<<std::endl;
        p = q->link;
        q->link = p->link;
    }
    x = p->data;
    delete p;
    return *this;
}

template<typename T>
Chain<T>& Chain<T>::Insert(int k, const T& x)
{
    if (k < 0)
        //throw OutOfBounds();
        std::cout<<"OutOfBounds"<<std::endl;
    ChainNode<T> *p = first;

    for (int index = 1; index < k && p;  index++)
        p = p->link;
    if (k > 0 && !p)
        //throw OutOfBounds();
        std::cout<<"OutOfBounds"<<std::endl;
    ChainNode<T> *y=new ChainNode<T>;
    y->data = x;
    if (k)
    {
        y->link = p->link;
        p->link = y;
    }
    else
    {
        y->link = first;
        first = y;
    }
    return *this;
}

template <typename T>
ostream& operator<< (ostream& out, const Chain<T>& x)
{
    x.Output(out);
    return out;
}

#endif

main.cpp

#include <iostream>
#include "LinearList.h"

using namespace std;

int  main()
{
    Chain<int> bob;
    cout<<bob.IsEmpty()<<endl;
    cout<<bob.Length()<<endl;
    bob.Insert(0,33);
    cout<<bob.Length()<<endl;
    cout<<bob<<endl;
    return 0;
}

很奇怪的是这里没有LinearList.cpp文件，原因如下：
将类的定义和类成员函数的定义（实现文件）分别放入不同的文件，目标代码根据实现文件生成（和客户代码无关），并且和客户代码链接，这种做法对于类模板是不适用的。因为为函数传递参数在运行时起作用，而给类模板传递参数则在编译阶段起作用。由于类模板的实际参数在客户代码中指定，并且没有实际参数的编译器无法实例化一个函数模板，所以必须依赖客户代码才可编译模板的实现文件部分。

解决方案1：将类定义和函数模板定义直接包含在用户文件中，或者将类定义和函数模板定义都放在同一个头文件中；

解决方案2：将类定义的函数定义话在不同的文件中，但在头文件的末尾处包含实现文件。

不管用什么方法，客户代码要和函数定义一起编译。