Alex_McAvoy

想要成为渔夫的猎手

顺序表

发表于 分类于 ， ，
本文字数： 5.9k 阅读时长 ≈ 5 分钟

【顺序表】

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

顺序表具有以下特点：

1.支持随机访问：通过 data[i-1] 即可访问第 i 个元素，在 $O(1)$ 的时间复杂度内即可完成

2.存储密度高：只存储数据元素

3.扩展容量不方便：静态分配方式无法扩展，动态分配方式扩展要消耗大量的时间

4.插入、删除数据元素不方便

实现类如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#define N 50 + 5 //最大表长
template <typename T> class SeqList {
  public:
    SeqList();                              //无参构造函数，初始化表
    SeqList(T m_data[], int m_len);         //有参构造函数，对表赋初值
    ~SeqList();                             //析构函数，销毁表
    void increaseList(int increaseLen);     //扩充线性表长度
    int getLen();                           //求表长
    bool empty();                           //判空
    bool full();                            //判满
    bool print();                           //输出
    bool insertElement(int pos, T elem);    //第pos个位置插入元素elem
    bool deleteElement(int pos, T &elem);   //删除第pos个元素，通过引用返回元素值
    int getNodeByValue(T elem);             //查找与elem相同的第一个元素位置，不存在返回-1
    bool getNodeByPosition(int pos, T &elem); //查找第pos个元素，通过引用返回元素值
  private:
    T *data;
    int len;    //当前表长
    int maxLen; //最大表长
};

【初始化表与销毁表】

在 C 语言中，连续的地址空间有两种分配方式：静态分配、动态分配

静态分配

静态分配事先规定好表长，表长声明后无法更改，之后根据表长的大小申请数组空间，一旦空间占满，再加入新的数据将会发生溢出

1
2
3
4
5
6
7
8
9
10
11
12
#define maxLen 50 + 5 //最大表长
class SeqList {
  public:
    SeqList();        //构造函数，初始化表
  private:
    int data[maxLen];
    int len;          //当前表长
};

SeqList::SeqList() { //构造函数，初始化表
    len = 0;         //初始长度为0，空表
}

动态分配

动态分配时，顺序表的存储空间是通过动态存储分配语句分配的，当存储空间占满，可以另外开辟一块更大的存储空间，以替换原来的存储空间，从而达到扩充顺序表空间的目的

也就是说，在动态分配中，顺序表表长声明后可更改

在 C 语言中，使用 malloc() 函数与 free() 函数来进行空间的动态分配与回收；在 C++ 语言中，除了继承自 C 语言标准库的 malloc() 函数与 free() 函数，还引入了 new 操作符与 delete 操作符

相较于 malloc() 要手动计算类型大小，同时要强制转换成所需的返回类型（malloc()默认返回类型为 void*），new 操作符会自动计算类型大小，并返回对应类型指针

但从系统层面来说，真正开辟和回收空间的是 malloc() 函数与 free() 函数，new 操作符与 delete 操作符的实现依赖于内存管理接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#define N 50+5 //最大表长
template <typename T> 
class SeqList {
  public:
    SeqList();                           //无参构造函数，初始化表
    SeqList(T m_data[], int m_len);      //有参构造函数，对表赋初值
    ~SeqList();                          //析构函数，销毁表
    void increaseList(int increaseLen);  //扩充线性表长度
  private:
    T *data;
    int len;    //当前表长
    int maxLen; //最大表长
};

template <typename T> 
SeqList<T>::SeqList() { //无参构造函数，初始化表
    len = 0;            //初始长度为0，空表
    maxLen = N;         //最大表长为N

    // 使用malloc开辟空间
    data = (T *)malloc(maxLen * sizeof(T)); //申请连续的maxLen个存储单元
    // 使用new开辟空间
    // data = new int(maxLen);
}
template <typename T>
SeqList<T>::SeqList(T data[], int len) { //有参构造函数，对表赋初值
    maxLen = N;                          //最大表长为N
    this->len = len;
    this->data = (T *)malloc(maxLen * sizeof(T)); //申请连续的maxLen个存储单元
    for (int i = 0; i < len; i++)
        this->data[i] = data[i];
}
template <typename T> 
SeqList<T>::~SeqList() { //析构函数，销毁表
    free(data);          //使用free回收malloc分配的空间
    // delete data;      //使用delete回收new分配的空间
}

在动态分配顺序表空间时，若需要对顺序表进行扩充，则可先使用 malloc() 重新分配空间，然后再将原有数据复制到新空间，最后再将原空间释放即可

此外，也可使用 realloc() 重新分配空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <typename T>
void SeqList<T>::increaseList(int increaseLen) { //扩充线性表长度
    maxLen = maxLen + increaseLen;               //表长增加increaseLen

    //使用malloc重新分配空间
    T *p = data;
    data = (T *)malloc(maxLen * sizeof(T)); //重新开辟空间
    for (int i = 0; i < len; i++)           //将原有数据复制到新开辟空间
        data[i] = p[i];
    free(p);                                //释放原空间

    //使用realloc重新分配空间
    // data = (T *)realloc(data, maxLen * sizeof(T));
}

【基本操作】

求表长

为避免使用顺序表 L 的表长时操作失误导致线性表表长更改，借助 OOP 中的 getter 思想，将获取顺序表表长封装成函数

1
2
3
4
template <typename T> 
int SeqList<T>::getLen() { //求表长
    return len;
}

判空

当顺序表 L 表长为 $0$ 时，表为空表

1
2
3
4
5
6
template <typename T> 
bool SeqList<T>::empty() { //判空
    if (len == 0)
        return true;
    return false;
}

判满

当顺序表 L 表长为最大长度 maxLen 时，表为满表

1
2
3
4
5
6
template <typename T> 
bool SeqList<T>::full() { //判满
    if (len == maxLen)
        return true;
    return false;
}

输出

对于顺序表 L，按序输出其元素，首先为防止脏读的出现，应先判断表是否为空表，之后，从表头枚举到表尾即可

1
2
3
4
5
6
7
8
9
10
11
template <typename T> 
bool SeqList<T>::print() { //输出
    if (empty())           //判表空，防脏读
        return false;

    int len = getLen();   //表长
    for (int i = 0; i < len - 1; i++)
        cout << data[i] << " ";
    cout << data[len - 1] << endl;
    return true;
}

关于脏读

在分配内存空间后，内存空间中可能存在数据，若不使用表长来制约循环，可能会出现脏读的情况

假设顺序表 L 表长为 $2$，其中仅有两个数据，分别为 $1$、$3$，且顺序表允许的最大表长为 $5$

当采用以下输出方式时，输出可能为：1,3,0,318,0，其中 $318$ 即为原有内存空间的脏数据

1
2
3
for (int i = 0; i < 4 ;i++)
    printf("%d,",L.data[i]);
printf("%d\n",L.data[4]);

【插入】

在顺序表 L 上的 pos 位置插入新元素 elem 时，首先要进行越界判断与表满判断，防止溢出

之后将最后一个元素到原 pos 个元素间的所有元素后移一位，最后，将新元素 elem 插入到 pos 位置上，再将表长 len 加 $1$

需要注意的是，数组索引从 $0$ 开始，线性表索引从 $1$ 开始，因此 pos-1 为对应的数组位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <typename T>
bool SeqList<T>::insertElement(int pos, T elem) { //第pos个位置插入元素elem
    if (pos < 1 || pos > len + 1)                 //越界判断
        return false;
    if (full())                                   //判表满，防溢出
        return false;

    //从最后一个元素到第pos个元素的所有元素后移
    for (int i = len; i >= pos; i--)
        data[i] = data[i - 1];

    data[pos - 1] = elem;
    len++;

    return true;
}

时间复杂度分析

1.最好时间复杂度

最好的情况是在表尾 i=n+1 插入，此时后移语句不需要执行，时间复杂度为：$O(1)$

2.最坏时间复杂度

最坏的情况是在表头 i=1 插入，此时后移语句执行 $n$ 次，时间复杂度为：$O(n)$

3.平均时间复杂度

对于平均情况而言，在第 i 个位置插入概率为：

那么，在各位置上需要执行后移语句 $n-i+1$ 次，平均移动次数为：

此时，时间复杂度为：$O(n)$

【删除】

删除顺序表 L 上的 pos 位置的元素时，首先要进行越界判断与表空判断，防止溢出

之后将要删除的元素值赋给引用变量以最终返回元素值，最后，将要删除的元素 elem 到最后的元素间的所有元素前移一位，再将表长 len 减 $1$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <typename T>
bool SeqList<T>::deleteElement(int pos, T &elem) { //删除第pos个元素，通过引用返回元素值
    if (pos < 1 || pos > len)                      //越界判断
        return false;
    if (empty())                                   //判表空
        return false;

    elem = data[pos - 1];           //要删除元素
    for (int i = pos; i < len; i++) //要删除元素之后元素前移
        data[i - 1] = data[i];
    len--;

    return true;
}

时间复杂度分析

1.最好时间复杂度

最好的情况是在表尾 i=n 删除，此时后移语句不执行，时间复杂度为：$O(1)$

2.最坏时间复杂度

最坏的情况是在表头 i=1 删除，此时后移语句执行 $n$ 次，时间复杂度为：$O(n)$

3.平均时间复杂度

对于平均情况而言，在第 i 个位置删除概率为：

那么，在各位置上需要执行后移语句 $n-i$ 次，平均移动次数为：

此时，时间复杂度为：$O(n)$

【查找】

按值查找

在顺序表 L 中寻找与给定元素值 elem 相同的第一个元素的位置时，需要进行表空判断，防止溢出

之后，从前向后对顺序表的元素进行枚举，若匹配成功，则直接返回对应位置

若对顺序表扫描完毕，没有匹配，说明匹配不成功，返回 -1

1
2
3
4
5
6
7
8
9
10
11
template <typename T>
int SeqList<T>::getNodeByValue(T elem) { //查找与elem相同的第一个元素位置，不存在返回-1
    if (empty())                         //判表空
        return -1;

    for (int i = 0; i < len; i++)
        if (data[i] == elem)
            return i + 1;

    return -1;
}

时间复杂度分析

1.最好时间复杂度

最好的情况是在表头 i=1 查找，此时仅需比较 $1$ 次，时间复杂度为：$O(1)$

2.最坏时间复杂度

最好的情况是在表尾 i=n 查找，此时需要比较 $n$ 次，时间复杂度为：$O(n)$

3.平均时间复杂度

对于平均情况而言，查找元素在第 i 个位置的概率为：

那么，要在各位置上执行后移语句 $i$ 次，平均移动次数为：

此时，时间复杂度为：$O(n)$

按位查找

在顺序表 L 中查找第 pos 个位置的元素时，需要进行越界判断与表空判断，防止溢出

由于顺序表支持随机访问，因此直接读取 data[pos-1] 的值即可

1
2
3
4
5
6
7
8
9
template <typename T>
bool SeqList<T>::getNodeByPosition(int pos, T &elem) { //查找第pos个元素，通过引用返回元素值
    if (pos < 1 || pos > len)   //越界判断
        return false;
    if (empty())                //判表空，防脏读
        return false;
    elem = data[pos - 1];
    return true;
}

时间复杂度分析

由于顺序表支持随机访问，因此，时间复杂度为：$O(1)$

感谢您对我的支持，让我继续努力分享有用的技术与知识点！