线性表的顺序表示——顺序表

1、顺序表的定义

? 顺序表是用一组地址连续的存储单元依次存储线性表中的数据元素。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。顺序存储结构如下图所示：

注意：线性表中的位序是从1开始的，而数组元素的下标是从0开始的。

2、顺序表的实现

2.1 静态分配

#define MaxSize 10  //定义最大长度
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize];  //用静态数组存放数据元素
    int length;              //顺序表的当前长度
} SqList;                    //顺序表的类型定义

/**
 * 基本操作-初始化一个顺序表
 * @param L
 */
void InitList(SqList &L) {
    for (int i = 0; i < MaxSize; ++i) {
        L.data[i] = 0;  //将所有数据设为默认初始值,否则会有脏数据
    }
    L.length = 0;  //顺序表初始长度为0
}

? 在静态分配时，数组的大小和空间是固定的，无法更改，一旦空间占满，再加入新的数据就会产生溢出，进而导致程序崩溃。

思考：如果一开始就申请很大的内存空间呢 ？？？会存在什么问题 ？？？ 浪费！!

2.2 动态分配

#define InitSize 10  //默认的最大长度
typedef int ElemType;
typedef struct {
    ElemType *data;    //指示动态分配数组的指针
    int MaxSize;  //顺序表的最大容量
    int length;   //顺序表的当前长度
} SeqList;

void InitList(SeqList &L) {
    //用malloc函数申请一片连续的内存空间
    L.data = (int *) malloc(InitSize * sizeof(int));
    L.length = 0;
    L.MaxSize = InitSize;
}

用malloc函数申请一片连续的存储空间。malloc函数返回一个指针，需要强制转型为你定义的数据元素类型指针。

增加数组空间的方法：

/**
 * 扩容
 * @param L
 * @param len
 */
void IncreaseSize(SeqList &L, int len) {
    int *p = L.data;
    L.data = (int *) malloc((L.MaxSize + len) * sizeof(int));
    for (int i = 0; i < L.length; i++) {
        L.data[i] = p[i];         //将数据复制到新区域
    }
    L.MaxSize = L.MaxSize + len;  //顺序表最大长度增加len,事件开销大
    free(p);                      //释放原来的内存空间
}

注意：动态分配并不是链式存储，它同样属于顺序存储结构，物理结构没有变化，依然是随机存取方式，只是分配的空间大小可以在运行时动态决定。

3、顺序表的特点

①随机访问，即可以通过首地址和元素序号在O(1) 时间内找到第 i 个元素；

②存储密度高，每个节点只存储数据元素；

③逻辑上相邻的元素物理上也相邻，扩容、插入、删除操作不方便。

4、顺序表上基本操作的实现(以静态分配的顺序表为例)

4.1 插入操作

在顺序表的第 i 个位置插入新元素，要将第 i 个及其后的所有元素往后移动一个位置，腾出一个空位插入新的元素

逻辑结构：

代码实现：

/**
 * 插入的代码，能处理异常情况
 * @param L
 * @param i
 * @param e
 * @return
 */
bool ListInsert(SeqList &L, int i, int e) {
    if (i < 1) {  //判断i的范围是否有效
        return false;
    }
    if (L.length >= L.MaxSize) {       //当前存储空间已满，要扩容
        IncreaseSize(L, 1);
    }
    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，循环0次，O(1)

最坏情况：新元素插入到表头，需要移动全部元素，i = 1，循环n次，O(n)

平均情况：假设新元素插入到任何一个位置的概率相同，即 i = 1,2,3,4......length+1的概率都是 1/(n+1)，平均时间 复杂度 O(n)

4.2 删除操作

删除第 i 个元素，需要将第 i + 1 个元素及其后面的所有元素往前移动一个位置

逻辑结构：

代码实现：

/**
 * 删除数据
 * @param L 要操作的列表
 * @param i 删除第i个元素，从1开始计数
 * @param e 保存删除的元素
 * @return
 */
bool ListDelete(SeqList &L, int i, int &e) {
    if (i < 1 || i > L.length) {  //判断i的范围是否有效
        return false;
    }
    e = L.data[i - 1];           //将被删除的元素赋值给e
    for (int j = i; j < L.length; j++) {  //将第i个位置后的元素前移
        L.data[j - 1] = L.data[j];
    }
    L.length--;                //线性表长度减1
    return true;
}

时间复杂度：

最好情况：删除表尾元素，不需要移动其他元素，i = n ，循环0次，O(1)

最坏情况：删除表头元素，需要将后续的 n + 1 个元素全部向前移动，i = 1，循环 n - 1 次，O(n)

平均情况：假设删除任何一个元素的概率相同，即 i = 1,2,3,4......length+1的概率都是 1/n，平均时间复杂度 O(n)

4.3 按位查找

获取表中第 i 个位置的元素值

ElemType GetElem(SqList L, int i) {
    return L.data[i - 1];
}

时间复杂度 O(1)

4.4 按值查找

在表中查找元素值等于指定值的元素，并返回其位序

/**
 * 按值查找
 * @param L
 * @param e
 * @return
 */
int LocateElem(SqList L, int e) {
    for (int i = 0; i < L.length; ++i) {
        if (L.data[i] == e) {
            return i + 1;
        }
    }
    return 0;
}

时间复杂度：

最好情况：目标元素在表头，循环 1 次，O(1)

最坏情况：目标元素在表尾，循环 n 次，O(n)

平均情况：假设目标元素出现在任何一个位置的概率相同，都是 1/n，平均时间复杂度 O(n)

谢谢观看！

线性表的顺序表示——顺序表

原文：https://www.cnblogs.com/studentyang/p/14791179.html