数据结构复习-线性表的顺序表示

1.顺序表的定义

线性表的顺序存储又称为顺序表。它是用一组地址连续的存储单元，依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。第1个元素存储在线性表的起始位置，第i个元素的存储位置后面紧接着存储的是第i+1个元素。因此，顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。
假设线性表L存储的起始位置为LOC(A)，sizeof(ElemType)是每个数据元素所占用存储空间的大小，则表L所对应的顺序存储如图。
假定线性表的元素类型为ElemType，线性表的顺序存储类型描述为

#define MaxSize 50  
typedef struct {
    ElemType data[MaxSize];
    int length;
} SqList;

一维数组可以是静态分配的，也可以是动态分配的。在静态分配时，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据将产生溢出，就会导致程序崩溃。
而动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，可以另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储数组空间的目的，而不需要一次性地划分所有所需空间给线性表。

#define InitSize 100
typedef struct {
    ElemType *data;
    int MaxSize,length;
} SeqList;

C的初始化动态分配语句为

L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);

C++的初始动态分配语句为

L.data=new ElemType[InitSize];

顺序表最主要的特点是随机访问，即通过首地址和元素序号可以在O(1)的时间内找到指定的元素。
顺序表的存储密度高，每个结点只存储数据元素。
顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。

2.顺序表上基本操作的实现

（1）插入操作
在顺序表L的第i（1≤i≤L.length+1）个位置插入新元素e。如果i的输入不合法，则返回false，表示插入失败；否则，将顺序表的第i个元素以及其后的所有元素右移一个位置，腾出一个空位置插入新元素e，顺序表长度加1，插入成功，返回true。

bool ListInsert(SqList &L,int i,ElemType e) {
    if(i<1 || i>L.length+1)
        return false;
    if(L.length>=MaxSize)
        return false;
    for(int j=L.length; j>=i; j--) 
        L.data[j] = L.data[j-1];
    L.data[i-1]=e;
    L.length++;
    return true;
}

最好情况：在表尾插入（即i=n+1），元素后移语句将不执行，时间复杂度为O(1)。
最坏情况：在表头插入（即i=1），元素后移语句将执行n次，时间复杂度为O(n)。
平均情况：假设pi(pi=1/(n+1))是在第i个位置上插入一个节点的概率，则在长度为n的线性表中插入一个结点时所需移动结点的平均次数为n/2。因此，线性表插入算法的平均时间复杂度为O(n)。 

（2）删除操作
删除顺序表L中第i（1≤i≤L.length）个位置的元素，成功返回true，并将被删除的元素用引用变量e返回，否则返回false。

bool ListDelete(SqList &L,int i,int &e) {
    if(i<1 || i>L.length)
        return false;
    e=L.data(i-1);
    for(int j=i;j<L.length;j++)
        L.data[j-1]=L.data[j];
    L.length--;
    return true;
}

最好情况：删除表尾元素（即i=n），无须移动元素，时间复杂度为O(1)。
最坏情况：删除表头元素（即i=1）,需要移动除第一个元素外的所有元素，时间复杂度为O(n)。
平均情况：假设pi(pi=1/n)是删除第i个位置上结点的概率，则在长度为n的线性表中删除一个结点时所需移动结点的平均次数为(n-1)/2。因此，线性表删除算法的平均时间复杂度为O(n)。

（3）按值查找（顺序查找）
在顺序表L中查找第一个元素值等于e的元素，并返回其位序。

int LocateElem(SqList L,ElemType e) {
    int i;
    for(i=0;i<L.length;i++)
        if(L.data[i]==e)
            return i+1;
    return 0;
}

最好情况：查找的元素就在表头，仅需要比较一次，时间复制度为O(1)。
最坏情况：查找的元素在表尾（或不存在）时，需要比较n次，时间复杂度为O(n)。
平均情况：假设pi(pi=1/n)是查找的元素在第i(i≤i≤L.length)个位置上的概率，则在长度为n的线性表中查找值为e的元素所需比较的平均次数为(n+1)/2。因此，线性表按值查找算法的平均时间复杂度为O(n)。