顺序表在C++中的应用

 顺序表是以数组为结构的线性表。由于数组中各元素的地址是可计算的，所以查找定位操作 有很高的执行效率。但是这种顺序结构的缺点也相当明显，要获得连续的内存空间就必须一次性申请，而在程序执行之前往往无法精确得到所需空间的大小。这时通常先确定一个合适的数组长度，如果后来空间不够，再重新申请一个更大的空间并把原先空间的数据转移过来。可以预见到，如果数据庞大的话，这个转移操作是相当耗费资源的。所以顺序表往往用在一些经常查找却很少改动的数据上。
程序清单：SeqList.h    SeqListTest.cpp
SeqList.h
/**//* SeqList.h */
/**//* Coding by nyzhl */

template 
class SeqList...{
    public:
        SeqList(int init=50, int incr=10);
        bool IsEmpty() const;
        int Locate(T dat) const;
        T GetData(int index) const;
        void Insert(int index, T dat);
        T Delete(int index);
    private:
        int size,increaseSize,last;
        T *data;
};
//构造函数
template 
SeqList::SeqList(int init, int incr) ...{
    size = init; //顺序表初始大小
    data = new T[size];
    increaseSize = incr; //顺序表递增大小
    last = -1;
}
//判断是否为空
template 
bool SeqList::IsEmpty() const ...{
    return last == -1;
}
//查找定位所找数据的下标
template 
int SeqList::Locate(T dat) const ...{
    for(int i=0; i<=size; i++)
        if(data[i] == dat) return i;
    return -1;
}
//读取指定位置的数据
template 
T SeqList::GetData(int index) const ...{
    return data[index];
}
//在指定位置插入数据
template 
void SeqList::Insert(int index, T dat) ...{
    if(last==size-1) ...{
        T *temp = new T[size+increaseSize];
        for(int i=0; i            temp[i] = data[i];
        T *garbage = data; [Page]
        data = temp;
        delete(garbage);
        size += increaseSize;
    } //increasement
    for(int i=last; i>=last; i--)
        data[i+1] = data[i];
    data[index] = dat;
    last ++;
}
//删除指定位置的数据
template 
T SeqList::Delete(int index) ...{
    if(IsEmpty()) return NULL;
    T dat = data[index];
    for(int i=index; i        data[i] = data[i+1];
    last --;
    return dat;
}
 
SeqListTest.cpp
/**//* SeqListTest.cpp */
/**//* Coding by nyzhl */

#include  
//我的编译器总是说找不到iostream.h郁闷~
#include \"SeqList.h\"

void main() ...{
    SeqList *sl = new SeqList(50,10);
    for(int i=0; i<100; i++)
        sl->Insert(i,i);
    for(int i=0; i<100; i++)
        printf(\"%d \",sl->GetData(i));
    sl->Delete(50);
    printf(\"%d \",sl->GetData(50));
    printf(\"%d \",sl->Locate(45));

    printf(\"%d \",sl->Locate(55));
    printf(\"%d \",sl->Locate(50));
}