【数据结构】顺序表

顺序表

文章目录

  • 顺序表
    • 定义
    • 顺序表的实现
      • 静态分配
      • 动态分配
      • 顺序表的特点
    • 顺序表的插入 & 删除
      • 顺序表插入操作
      • 顺序表的删除操作
    • 顺序表的查找
      • 按位查找
      • 按值查找

定义

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

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

顺序表的实现

静态分配

#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 i=n+1 i=n+1 ,循环 0 次;最好时间复杂度 = O ( 1 ) O(1) O(1)

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

    i = 1 i=1 i=1 ,循环 n 次;最坏时间复杂度 = O ( n ) O(n) O(n)

  • 平均情况:新元素插入到任何一个位置的概率相同,即 i = 1 , 2 , 3 , … , l e n g t h + 1 i=1,2,3,…,length+1 i=1,2,3,,length+1 的概率都是 p = 1 n + 1 p=\frac{1}{n+1} p=n+11

    i = 1 i=1 i=1 循环 n 次; i = 2 i=2 i=2 时,循环 n-1 次;… i = n + 1 i=n+1 i=n+1 时,循环 0 次

    平均循环次数 = n 2 \frac{n}{2} 2n ➡️ 平均时间复杂度 = O ( n ) O(n) 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 i=n+1 i=n+1 ,循环 0 次;最好时间复杂度 = O ( 1 ) O(1) O(1)

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

    i = 1 i=1 i=1 ,循环 n-1 次;最坏时间复杂度 = O ( n ) O(n) O(n)

  • 平均情况:删除任何一个位置的元素的概率相同,即 i = 1 , 2 , 3 , … , l e n g t h i=1,2,3,…,length i=1,2,3,,length 的概率都是 p = 1 n p=\frac{1}{n} p=n1

    i = 1 i=1 i=1 循环 n-1 次; i = 2 i=2 i=2 时,循环 n-2 次;… i = n i=n i=n 时,循环 0 次

    平均循环次数 = n − 1 2 \frac{n-1}{2} 2n1 ➡️ 平均时间复杂度 = O ( n ) O(n) 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 ) O(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 ) O(1) O(1)

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

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

  • 平均情况:目标元素在任何一个位置的概率相同,即 i = 1 , 2 , 3 , … , l e n g t h i=1,2,3,…,length i=1,2,3,,length 的概率都是 p = 1 n p=\frac{1}{n} p=n1

    目标元素在第 1 位,循环 1 次;目标元素在第 2 位,循环 2 次;… 目标元素在第 n 位,循环 n 次;

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

上一篇:K8s: 持久化存储之卷, NFS卷


下一篇:【代码】jetson+OLED屏幕+显示mp4视频