数据结构（4）顺序表的定义和实现_变长型顺序表存储结构定义

在文章开头想再强调一个概念：线性表是一个逻辑结构，顺序表和链表属于存储结构。

目录

1、顺序表的定义

2、顺序表的特点

3、顺序表上基本操作的实现

3.1、插入操作

3.2、删除操作

3.3、按值查找（顺序查找）

---

1、顺序表的定义

线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

假定线性表的元素类型为ElemType,则线性表的顺序存储类型描述为：

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

一维数组可以是静态分配的，也可以是动态分配的。在静态分配时，由于数组的大小和空间事先已经固定好，一旦空间占满，再加入新的数据将会产生溢出，进而导致程序奔溃甚至引起其他未知异常。

而在动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦存储空间占满，就另外开辟一块更大的存储区间，将原来的元素复制过去，从而达到扩充存储数组空间的目的，而不需要一次性分配很大的空间。

#define InitSize 100
 
typedef struct
{
    ElemType* dataPtr;
    int length;
    int size;  
}SqList;

C语言的初始动态分配语句为：L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);

C++语言的初始化动态分配语句为：L.data=new ElemType[InitSize];

注意：动态存储并不是练市存储，它同样属于顺序存储，物理结构没有变化，还是和逻辑结构一样保持相邻，只是分配的空间不再是编译器决定，而是运行时分配。

2、顺序表的特点

随机访问：可通过首地址和元素序号在单位时间O(1)内找到指定的元素。

存储密度高：存储密度高是因为每个结点存储空间指用来存储数据元素，没有别的额外开销。

物理位置相邻：物理位置和逻辑位置一样，保持相邻，因此插入和删除元素需要移动大量元素，比较耗时。这是物理结构相邻的所有数据结构的通病，虽然访问快，但是如果有频繁的增删移动操作，就会效率很低。

3、顺序表上基本操作的实现

仅展示查、增、删三种操作，其余的在线性表中较为简单，在后续更复杂的链表中展示。

3.1、插入操作

在顺序表L的第i（1<=i<=L.length+1）位插入新元素e。

bool ListInsert(SqList &L, int i, ElemType e) 
{
    if (i<1 || i>L.length + 1)  //判断i要插入的位置是否有效
        return false;
    if (L.length >= MaxSize)   //判断是否超出存储空间
        return false;
    for (int j = L.length; j >= i; j--)  //将第i个元素以及之后的元素后移一位
        L.data[j] = L.data[j - 1];
    L.data[i - 1] = e;   //在第i位插入元素e
    L.length++;     //顺序表长度加1
    return true;
}

最好情况：在表尾插入（即i=n+1）,原本的元素不移动，时间复杂度为O(1)。

最坏情况：在表头插入（即i=1），所有元素需要后移一位，元素后移语句执行n次，时间复杂度为O(n)。

平均情况：假设Pi(Pi=1/(n+1))是在第i个位置上插入一个结点的概率，则在长度为n的顺序表中插入一个结点时，所需要移动结点的平均次数为n/2，时间复杂度为O(n)。

3.2、删除操作

删除顺序表L中第i（1<=i<=L.length）个位置的元素。

bool ListDelete(SqList &L, int i, ElemType& e) 
{
    if (i<1 || i>L.length)  //判断i要插入的位置是否有效
        return false;
    e = L.data[i - 1];     //保存要删除的数据到e
    for (int j = i-1; j <= L.length; ++j)  //将第i个元素以及之后的元素后移一位
        L.data[j] = L.data[j + 1];
    L.length--;     //顺序表长度加1
    return true;
}

时间复杂度与插入一样（平均时间复杂度上，插入始终每一步比删除多一次操作，即插入操作，但是不会引起量级变化，所以平均时间复杂度依旧为O(N)）

3.3、按值查找（顺序查找）

在顺序表中查找第一个元素值等于e的元素的位置，未查找到返回-1

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

最好情况：在表头找到（即i=1）,时间复杂度为O(1)。

最坏情况：在表尾插入（即i=n），时间复杂度为O(n)。

平均情况：时间复杂度为O(n)。

 

人，总是要有一点精神的，不是吗