顺序表

定义

顺序表：用顺序存储的方式实现线性表

顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现

顺序表的实现

静态分配

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

void InitList(SqList &L){
    for(int i = 0; i < MaxSize; i++){
        L.data[i] = 0;		//将所有数据元素设置为默认初始值
    }
    L.length = 0;			//顺序表初始长度为0
}

int main(){
    SqList L;		//声明一个顺序表
    InitList(L);	//初始化顺序表
    //...
    return 0;
}

动态分配

#define InitSize 10				//顺序表的初始长度
typedef struct{
    ElemType *data;				//指示动态分配数组的指针
    int MaxSize;				//顺序表的最大容量
    int length;					//顺序表的当前长度
}SeqList;						//顺序表的类型定义（动态分配方式）

void InitList(SeqList &L){
    //用 malloc 函数申请一片连续的存储空间（在 stdlib.h 头文件中）
    L.data = (int *)malloc(InitSize*sizeof(int));
    L.length = 0;
    L.MaxSize = InitSize;
}

//增加动态数组的长度
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);						//释放原来的内存空间
}

int main{
    SeqList L;			//声明一个顺序表
    InitList(L);		//初始化顺序表
    //...往顺序表中随便插入几个元素...
    IncreaseSize(L, 5);
    return 0;
}

顺序表的特点

1. 随机访问：可以在 O(1) 时间内找到第 i 个元素
2. 存储密度高：每个节点只存储数据元素（无需存储地址元素）
3. 拓展容量不方便：采用动态分配的方式实现，拓展长度的时间复杂度也比较高
4. 插入、删除操作不方便：需要移动大量元素

顺序表的插入 & 删除

顺序表插入操作

(演示的代码都是基于“静态分配”的实现方式之上，“动态分配”也类似)

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

ListInsert(&L,i,e)：插入操作，在表L中的第 i 个位置上插入指定元素 e

int ListInsert(SqList &L, int i,int e){
    //先决条件：先判断顺序表是否有插入该元素的条件
    if(i < 1 || i > L.length + 1){	//判断 i 的范围是否有效
        return 0;
    }
    if(L.length >= MaxSize){	//当存储空间已满，不能插入
        return 0;
    }
    
    for(int j = L.length; j >= i; j--){
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;
    L.length++;
    return 1;
}

时间复杂度分析

• 最好情况：新元素插入到表尾，不需要移动元素

  $i=n+1$ ，循环 0 次；最好时间复杂度 = $O(1)$

• 最坏情况：新元素插入到表头，需要将原有的 n 个元素全都向后移动

  $i=1$ ，循环 n 次；最坏时间复杂度 = $O(n)$

• 平均情况：新元素插入到任何一个位置的概率相同，即 $i=1,2,3,\dots ,length+1$ 的概率都是 $p=\frac{1}{n+1}$

  $i=1$ 循环 n 次；$i=2$ 时，循环 n-1 次；… $i=n+1$ 时，循环 0 次

  平均循环次数 = $\frac{n}{2}$ ➡️ 平均时间复杂度 = $O(n)$

顺序表的删除操作

ListDelete(&L,i,&e)：删除操作，删除表L中第 i 个位置的元素，并用 e 返回删除元素的值

int ListDelete(SqList &L, int i, int &e){
    if(i < 1 || i > L.length){			//判断 i 的范围是否有效
        return 0;
    }
    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 1;
}

时间复杂度分析

• 最好情况：删除表尾元素，不需要移动元素

  $i=n+1$ ，循环 0 次；最好时间复杂度 = $O(1)$

• 最坏情况：删除表头元素，需要将原有的 n-1 个元素全都向前移动

  $i=1$ ，循环 n-1 次；最坏时间复杂度 = $O(n)$

• 平均情况：删除任何一个位置的元素的概率相同，即 $i=1,2,3,\dots ,length$ 的概率都是 $p=\frac{1}{n}$

  $i=1$ 循环 n-1 次；$i=2$ 时，循环 n-2 次；… $i=n$ 时，循环 0 次

  平均循环次数 = $\frac{n-1}{2}$ ➡️ 平均时间复杂度 = $O(n)$

顺序表的查找

按位查找

GetElem(L,i)：按位查找操作，获取表L中第 i 个位置的元素的值

”静态分配“查找

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

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

”动态分配“查找

#define InitSize 10				//顺序表的初始长度
typedef struct{
    ElemType *data;				//指示动态分配数组的指针
    int MaxSize;				//顺序表的最大容量
    int length;					//顺序表的当前长度
}SeqList;						//顺序表的类型定义（动态分配方式）

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

时间复杂度：$O(1)$ —— 顺序表“随机存取”的特性

按值查找

LocateElem(L,e)：按值查找操作，在表L中查找具有给定关键字值的元素

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

// 在顺序表L中查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SeqList L, ElemType e) {
    for (int i = 0; i < L.length; i++) {
       if (L.data[i] == e) {
           return i + 1;     // 返回的位序是数组下边+1
       }
    }
    return 0;
}

注意：不可以使用a==b这样的形式来判定结构体数据类型是否相等

时间复杂度分析

• 最好情况：目标元素在表头

  循环 1 次；最好时间复杂度 = $O(1)$

• 最坏情况：目标元素在表尾

  循环 n 次；最坏时间复杂度 = $O(n)$

• 平均情况：目标元素在任何一个位置的概率相同，即 $i=1,2,3,\dots ,length$ 的概率都是 $p=\frac{1}{n}$

  目标元素在第 1 位，循环 1 次；目标元素在第 2 位，循环 2 次；… 目标元素在第 n 位，循环 n 次；

  平均循环次数 = $\frac{n+1}{2}$ ➡️ 平均时间复杂度 = $O(n)$