数据结构以前学过，现在能想起一些哈希搜索啊，使用栈来寻找迷宫路径啊之类的，现在在c++下实现，看的教程一般使用template，同时巩固c++的class部分。
以前在c语言中，数据结构是用strcut定义，配以一些常用的操作方法。在c++中使用class来定义——实际上，struct和class基本一样的，class的成员默认是private的，可能多了一些封装隐藏的思想在里面。

#include <iostream>
using namespace std;
const int DefaultListSize = 50;
template <class Elem> class List{
    public:
        virtual void clear() = 0;
        virtual bool insert(const Elem&) = 0;
        virtual bool append(const Elem&) = 0;
        virtual bool remove(Elem&) = 0;
        virtual void setStart() = 0;
        virtual void setEnd() = 0;
        virtual void prev() = 0;
        virtual void next() = 0;
        virtual int leftLength() const = 0;
        virtual int rightLength() const = 0;
        virtual bool setPos(int pos) = 0;
        virtual bool getValue(Elem&) const = 0;
        virtual void print() const = 0;
};

template <class Elem>
class AList : public List<Elem>{
    private:
        int maxSize;
        int listSize;
        int fence;
        Elem* listArray;
    public:
        AList(int size = DefaultListSize){
            maxSize = size;
            listSize = fence = 0;
            listArray = new Elem[maxSize];
        }
        ~AList(){ delete[] listArray; }
        void clear(){
            delete[] listArray;
            listSize = fence = 0;
            listArray = new Elem[maxSize];
        }
        bool insert(const Elem&){return true;}
        bool append(const Elem&){return true;}
        bool remove(Elem&){return true;}
        void setStart(){ fence = 0; }
        void setEnd(){ fence = listSize; }
        void prev(){ if (fence!=0) fence--;}
        void next(){ if(fence<=listSize) fence++; }
        int leftLength() const { return fence; }
        int rightLength() const { return listSize - fence; }
        bool setPos(int pos){
            if((pos>=0)&&(pos<=listSize)) fence = pos;
            return (pos>=0)&&(pos<=listSize);
        }
        bool getValue(Elem& it) const{
            if(rightLength()==0) return false;
            else{it=listArray[fence];return true;}
        }
        void print() const{
            int temp = 0;
            cout << "< ";
            while(temp<fence) cout << listArray[temp++] << " ";
            cout << "| ";
            while(temp<listSize) cout << listArray[temp++] << " ";
            cout << ">\n";
        }
};

int main()
{
    AList<int> a(10);
    return 0;
}

一个简单的线性表，其实就是数组。首先定义了一个baseclass List，描述了list的成员函数，且均为virtual，实现为空，称为为纯虚函数。
接着给出一个具体的实现AList，构造函数中申请新的空间，析构函数中有delete，new数组和delete[]配合使用。