线性表的顺序存储的特性

线性表的顺序存储的特性

1）随机访问，由于逻辑上相邻的元素在物理存储上也相邻。因此每个元素的存储地址是可知的。

2）插入和删除操作在概率上要移动50％的元素。

在Java编程中我们经常使用Vector。到底Vector是一种什么样的数据结构呢？看了源代码才发现，原来Vector就是一种顺序动态存储的线性表结构。C＋＋中的Vector估计也是如此。

为什么叫做vector 呢？

vector
[5vektE]
n. [数]向量, 矢量,

矢量在数学上的定义是有大小和方向的物理量。

vector源于拉丁文，有搬运的意思。唉，用来描述顺序存储结构的线性表真是贴切啊。

Java 的Vector还有许多其它特性（比如线程安全、异常处理和支持范型编程等等）。这些特性是实际应用中必须考虑的因素。因此本文介绍的顺序动态结构存储的 线性表仅仅是个模型，距离真正应用还差的远。由此看来，目前各种语言都在丰富和支持内建工具库（Utilities）绝对有必要。对于学习C＋＋和 Java，深入到这些基础工具类内部探究其工作原理对熟练掌握使用语言本身有很大益处。

关于数据结构的书本上一般只介绍一些常用方 法，实际上Java中Vector的操作方法有很多。例如add/addElement方法就比较实用。毕竟大家使用习惯上，往表尾插数据的时候较多，尤 其是在Vetor的构造时期。实际上add/addElement方法是insert的一种较多见的应用场景。

下面介绍以C＋＋表示的顺序动态存储结构的线性表。

//SqList.h

//引入范型编程的好处由下一行import代码也应该看出

//#include <ElemType.h>

//
class SqList{
public:
    SqList();

    SqList(int capacity,int increment);

   ~SqList();

public:

    bool init(int capacity,int increment);

    int getSize();

    ElemType getAt(int i);

    bool insert(int i,ElemType& e);

    bool delete(int i);

    void clear();

    //others methods

protected:

    ElemType* data; //ElemType类型的指针，表示一组存储地址的首地址

    int size; //表示已容纳的元素个数

    int capacity; //当前的可容纳的元素个数
};

//SqList.cpp

#include <sqlist.h>

SqList::SqList(){

    init(10);//默认存放10个元素

}

SqList::SqList(int capacity,int increment){

    init(capacity,increment);

}

SqList::init(int capacity,int increment){

    //validate capacity and increment

    this.data = (ElemType*)new ElemType[capacity];

    this.increment = increment;

}

bool SqList::insert(int i, ElemType e){
    if(i<1 || i> size+1) return false;
    if(size==capacity){

         if(increment>0) {//说明设置了每次增长的长度

              data = (ElemType*) new ElemType[capacity+increment];
        }

        else{

            data = (ElemType*) new ElemType[capacity*2];

        }

        //copy old elements to new buffer

        memcpy(data,...);

    }

    data[size++]=e;

}