前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >线性表的顺序存储

线性表的顺序存储

作者头像
老齐
发布2023-03-02 16:52:48
1.5K0
发布2023-03-02 16:52:48
举报
文章被收录于专栏:老齐教室

线性表的顺序存储

线性表的定义和特点

n~(n\ge0)

个数据特性相同的元素构成的有限序列称为线性表

  • 元素的个数
n~(n\ge0)

为线性表的长度

n=0

时称为空表

  • 元素具有相同的特性,即属于同一数据对象
  • 相邻数据元素之间存在着序偶关系

特点:

  • 存在唯一的一个被称作“第一个”的数据元素
  • 存在唯一的一个被称为“最后一个”的数据元素
  • 除第一个之外,每个数据元素均只有一个前驱(直接前驱)
  • 除最后一个之外,每个数据元素均只有一个后继(直接后继)

顺序存储

定义和特点

线性表的顺序表示:用一组地址连续的存储单元依次存储线性表的数据元素,这种表示也称为线性表的顺序存储结构顺序映像。通常,称这种存储结构的线性表为顺序表(Sequential List)。

特点:

  • 逻辑上相连的数据元素,物理次序也是相邻的。
  • 随机存取的存储结构:只要确定了存储线性表的起始位置,线性表中任一数据元素都可以随机存取。

比较:

  • 线性表:逻辑结构。
  • 顺序表、链表:物理结构。

结构

设第一个数据元素

a_1

的存储地址是

\text{LOC}(a_1)

\text{LOC}

即 Location 的前三个字母,也将第一个数据元素的地址称为基地址,或起始位置),每个数据元素占用

L

个存储单元,并以所占的第一个单元的存储地址作为数据元素的存储起始位置,则线性表中第

i

个数据元素的存储位置:

\text{LOC}(a_i) = \text{LOC}(a_1)+(i-1)\times L,\quad(1\le i\le n)

高级语言中的数组类型也有随机存取的特性,因此,通常用数组来描述数据结构中的顺序存储结构。

顺序表的实现

静态分配:存储空间固定

代码语言:javascript
复制
#define MAXSIZE 100    //顺序表可能达到的最大长度
typedef struct {
    ElemType data[MAXSIZE];   // 顺序表中的数据元素
    int length;               //当前长度
}SqList;    // 顺序表的结构类型为 SqList

动态分配

代码语言:javascript
复制
#define InitSize 100    //初始化表的长度
typedef struct{
    ElemType *data;    // 动态分配数组的指针,存储空间的基地址
    int length, MaxSize;    // 当前长度和最大容量
}SqList;

注意 : 静态分配一旦空间占满后面再加入的数据会溢出;动态分配的空间一旦被占满,会先开辟一块比原来更大的空间用来存放原来的数据和新数据,再释放原来已满的空间,而不是直接在原来的空间上拓展新空间。因为顺序存储分配的存储空间都是连续的。

C 语言分配和释放内存空间

代码语言:javascript
复制
L.data = (ElemType*)malloc(sizeof(int)*InitSize); //分配空间

其中 ElemType*malloc 函数返回的一个指针,后再将指针的类型转换为数据元素类型的指针。``sizeof(int)*InitSize` 是

数据类型的大小\times该类型数据的个数 = 分配的连续内存空间

代码语言:javascript
复制
free(p);    //释放指针 p 所指的内存空间

应用举例:

代码语言:javascript
复制
//malloc、free函数的头文件在stdlib.h中
#include <stdlib.h>
#define InitSize 10   //默认的最大长度
typedef struct{
    int *data;    //动态分配数组(顺序表)指针,即存储空间基地址
    int listsize;    //顺序表容量
    int length;    //顺序表当前长度
}SqList;

//初始化顺序表
void InitList(SqList &L){    // 构造空的顺序表 L
    L.data = (int *)malloc(InitSize*sizeof(int));    //申请一连续的内存空间
    L.length = 0;    // 空表的长度为 0
    L.listsize = InitSize;    //此处将顺序表容量(即最大长度)设置为默认值,后续有函数进行修改
}

//增加动态组的长度,传入的参数为指向顺序表的指针 L 和增加的容量 len
void IncreaseSize(SqList &L, int len){
    int *p = L.data;    //定义int类型的指针p,指向原顺序表的data指针,即初始化所分配的连续内存空间
    //重新分配一个连续的内存空间,大小为原顺序表大小+增加的容量
    L.data = (int *)malloc((L.MaxSize+len)*sizeof(int));   //扩容, 原data指针已经指向新的内存空间, 而原来的空间由p指针管理
    
    for(int i=0; i<L.length; i++){
        L.data[i] = p[i];    //将原顺序表的数据复制到新的内存空间
    }
    L.listsize = L.listsize + len;    //新顺序表容量
    free(p);    // 释放原来的内存空间
}

//向顺序表中追加数据
void AppendElem(SqList &L, int a){
    L.data[L.length] = a;    //将整数追加到顺序表中
    L.length++;
}

//主函数
int main(){
    SqList L;    //声明一个顺序表
    InitList(L);    //初始化顺序表,空表
    //追加10个整数
    for (int i=0; i<10; i++){
        AppendElem(L, i);
    }
    IncreaseSize(L, 5);    //顺序表扩容5个单位的空间
    return 0;
}

基本操作

创建动态分配顺序表类型

代码语言:javascript
复制
#define INITSIZE 10    //线性表存储空间的初始分配量
typedef struct
{
 ElemType *elem;     //存储空间基址
 int length;         //当前长度
 int listsize;        //当前分配的存储容量(以sizeof(ElemType)为单位) 
}SqList;

顺序表的初始化,即构造一个空的顺序表 L 。教材 [1] 的算法 2.1

代码语言:javascript
复制
void InitList(SqList &L){ 
    // 为顺序表分配一个大小为 INITSIZE*sizeof(ElemType) 的内存空间
    L.elem=(ElemType*)malloc(INITSIZE*sizeof(ElemType)); 
    // 教材中使用 L.elem = new ElemType[INITSIZE] ,亦可
    if(!L.elem){
        exit(OVERFLOW);    //存储失败,退出
    }
    L.length = 0;    //空表长度为 0
    L.listsize = INITSIZE;
}

销毁顺序表。

初始条件:顺序表 L 已存在。

操作结果:销毁顺序表 L

代码语言:javascript
复制
void DestroyList(SqList &L){
    free(L.elem);
    L.elem = NULL;
    L.length = 0;
    L.listsize = 0;
}

清空顺序表

初始条件:顺序表 L 已存在

操作结果:将顺序表设置为空表

代码语言:javascript
复制
void ClearList(SqList &L){
    L.length = 0
}

判断顺序表是否为空

初始条件:已知顺序表 L

操作结果:若顺序表为空表,则返回 TRUE;否则返回 FALSE

代码语言:javascript
复制
Status IsListEmpty(SqList L){
    if(L.length==0){
        return TRUE;
    }else{
        return FALSE;
    }
}

顺序表的长度

初始条件:已知顺序表 L

操作结果:返回顺序表中的数据元素个数,即顺序表长度

代码语言:javascript
复制
int ListLength(SqList L){
    return L.length;
}

顺序表的取值(教材 [1] 的算法 2.2)

初始条件:已知顺序表 L

操作结果:取出第

i

个(位序)数据元素(对应的数组下标是

i-1

,即 elem[i-1] 是第

i

个数据元素。数组下标,也说成是数据元素的索引)

代码语言:javascript
复制
Status GetElem(SqList L, int i, ElemType &e){
    if (i<1 || i>L.length) return ERROR;   // 判断 i 是否合理
    e = L.elem[i-1];
    return OK;
}

时间复杂度

O(1)

顺序表的查找(教材 [1] 的算法 2.3)

初始条件:已知顺序表 L

操作结果:根据指定元素值 e ,朝招顺序表中第一个与 e 相等的数据元素,若找到,则返回该数据元素的索引;若查找失败,返回 0

代码语言:javascript
复制
int LocateElem(SqList L, ElemeType e){
    for (i=0; i<L.length; i++){
        if(L.elem[i] == e) return i;    \\查找成功,返回索引,如果返回位置序号,则是 i+1
    return 0;
    }
}

最好时间复杂度:

O(1)

最坏时间复杂度:

O(n)

平均时间复杂度:

O(n)

顺序表的前驱

初始条件:已知顺序表 L 以及其中的一个元素 cur_e

操作结果:若 cur_e 不是第一个元素,返回 cur_e 的前驱;否则操作失败。

代码1:

代码语言:javascript
复制
Status PriorElem(SqList L, ElemType cur_e, ElemType &pre_e){
    for (i=1; i<L.length; i++){    //这里的 i 是索引,不是位序
        if(L.elem[i]==cur_e) {
            pre_e = L.elem[i-1];
            return OK;
        }else{
            return ERROR;
        }
        
    }
}

代码2:

代码语言:javascript
复制
Status PriorElem(SqList L,ElemType cur_e,ElemType *pre_e)
{   int i=2;    // 这里的 i 不是索引,是位序,对应着 while 中使用 i<=L.length
 ElemType *p=L.elem+1;
 while(i<=L.length&&*p!=cur_e)
 {
  p++;
  i++;
 }
 if(i>L.length)
  return INFEASIBLE; /* 操作失败 */
 else
 {
  *pre_e=*--p;
  return OK;
 }
}

顺序表的后继

初始条件:已知顺序表 L 以及其中的一个元素 cur_e

操作结果:若 cur_e 不是最后一个,则返回它的后继元素,否则操作失败。

代码1:

代码语言:javascript
复制
Status NextElem(SqList L, ElemType cure_e, ElemType &next_e){
    for (i=0; i<(L.length-1); i++){
        if (L.elem[i]==cure_e){
            next_e = L.elem[i+1];
            return OK;
        }else{
            return ERROR;
        }
    }
}

代码2:

代码语言:javascript
复制
Status NextElem(SqList L,ElemType cur_e,ElemType *next_e)
{   int i=1;
 ElemType *p=L.elem;
 while(i<L.length&&*p!=cur_e)
 {
  i++;
  p++;
 }
 if(i==L.length)
  return INFEASIBLE; /* 操作失败 */
 else
 {
  *next_e=*++p;
  return OK;
 }
}

向顺序表插入元素

初始条件:已知顺序表 L

操作结果:在第

i

个位置,插入一个新的数据元素 e (这里的

i

是位置序号,意思是讲原来顺序表的第

i

个到最后一个数据元素,依次向后移动一个位置,这样第 i 个位置就空出来了,然后将数据元素 e 放在此处。表现出来,就是将数据元素 e 插入到第

i

个位置的元素之前)

代码1:来自教材 [1] 的算法 2.4,此代码中当存储空间已满时,返回 ERROR

代码语言:javascript
复制
Status ListInsert(SqList &L, int i, ElemType e){
    if ((i<1) || (i>L.length+1)) return ERROR; //若 i 不合法,则报错
    if (L.length==INITSIZE) return ERROR;    //当前存储空间已满
    for (j=L.length-1; j>=i-1; j--){
        L.elem[j+1] = L.elem[j];    //插入位置之后的元素向后移
    }
    L.elem[i-1] = e;    //将新元素 e 放在第 i 个位置,索引是 i-1
    ++L.length;    //数据表长度加 1
    return OK;
}

代码2:考虑存储空间满的情况下,增加分配

代码语言:javascript
复制
#define INCREMENT 2  //增加的空间
Status ListInsert(SqList *L, int i, ElemType e){
    ElemType *newbase, *q, *p;
    if ((i<1)||(i>(*L).length+1)) return ERROR;  // i 不合法
    if ((*L).length>=(*L).listsize){    //当前存储空间已满,增加空间长度
        newbase = (ElemType *)realloc((*L).elem, ((*L).listsize+INCREMENT)*sizeof(ElemType));
        if (!newbase) exit(OVERFLOW);    //分配存储空间失败
        (*L).elem = newbase;             //新的基址
        (*L).listsize += INCREMENT;     //增加存储容量
    }
    q=(*L).elem+i-1;   //q为插入位置,此处与代码1中不同在于,采用了指针
 for(p=(*L).elem+(*L).length-1;p>=q;--p)   //插入位置及之后的元素右移
  *(p+1)=*p;
 *q=e;                 //插入e
 ++(*L).length;        //表长增1
 return OK;
}

最好时间复杂度:

O(1)

最坏时间复杂度:

O(n)

平均时间复杂度:

O(n)

删除顺序表指定元素(教材 [1] 的算法 2.5)

初始条件:已知顺序表 L

操作结果:删除顺序表中指定的第

i

个数据元素

代码语言:javascript
复制
Status ListDelete(SqList &L, int i){
   if ((i<1)||(i>L.length)) return ERROR;
   for (j=i; j<=L.length-1; j++){   // 删除指定元素之后,其他元素前移
       L.elem[j-1] = L.elem[j];
   }
   --L.length;    //表长减 1
   return OK;
}

最好时间复杂度:

O(1)

最坏时间复杂度:

O(n)

平均时间复杂度:

O(n)

合并两个顺序表(教材 [1] 的算法 2.15)

初始条件:已知顺序表 LA 和 LB

操作结果:如果将两个顺序表视为两个集合,则合并之后的集合中无重复元素。即,将 LB 中与 LA 中不相同的元素合并回到 LA 中(假设 LA 的容量足够)

算法步骤:

① 分别获取 LA 和 LB 的长度

m

n

② 从 LB 中第 1 个元素开始(这里是位序),循环

n

次,执行一下操作:

代码语言:javascript
复制
- 从 LB 中查找第 $i~(1\le i\le n)$ 个数据元素,并赋给 `e` ;
- 从 LA 中查找元素 `e` ,如果不存在,则将 `e` 插入到 LA 的最后。

算法描述:

代码语言:javascript
复制
void MergeList(SqList &LA, SqList &LB){
   m = LA.length;    //亦可使用 ListLength(LA) 得到顺序表长度
   n = LA.length;
   for (i=1; i<=n; i++){
       GetElem(LB, i, e); // 取得 LB 中位序 i 的数据元素(索引 i-1),并赋值给 e
       if (!LocateElem(LA, e)){  //如果 LA 中没有元素 e
           ListInsert(LA, ++m, e);  // 则将 e 插入到 LA 尾部
       }
   }
}

时间复杂度

O(m\times n)

顺序有序表合并(教材 [1] 的算法 2.16)

初始条件:已知两个用顺序表表示的有序表 LA 和 LB

操作结果:假设两个 LA 和 LB 非递减排列,将二者合并之后得到的 LC 亦非递减排列。

算法步骤:

① 创建空表 LC,其长度为 LA.length + LB.length

② 指针 pc 初始化,指向 LC 的第一个元素。

③ 指针 papb 分别指向 LA 和 LB 的第一个元素。

④ 当 papb 均未达到表尾时,依次比较二者所指向元素的值,并从对应的顺序表中读取相应的数据元素插入到 LC 的尾部。

⑤ 若 pb 已经到大 LB 的表尾,则依次将 LA 的剩余元素插入到 LC 的尾部。

⑥ 若 pa 已经到大 LA 的表尾,则依次将 LB 的剩余元素插入到 LC 的尾部。

算法描述:

代码1:

代码语言:javascript
复制
void MergeList_Sq(SqList LA, SqList LB, SqList &LC){
   LC.length = LA.length + LB.length; 
   LC.elem = new ElemType[LC.length]; //为合并后的新表分配一个数组空间
   pc = LC.elem;    //指针 pc 指向新表的第一个元素
   pa = LA.elem;
   pb = LB.elem;
   pa_last = LA.elem + LA.length - 1;    //指针 pa_last 指向 LA 的最后一个元素
   pb_last = LB.elem + LB.length -1;
   while ((pa<=pb_last) && (pb<=pb_last)){    //LA、LB 均未到表尾
       if (*pa <= *pb){    // 将两表中较小的元素插入到 LC
           *pc = *pa;      // 教材 [1] 中的写法更简洁:*pc++ = *pa++
           *pa++;
       }else{
           *pc = *pb;    // *pc++ = *pb++
           *pb++
       }
       *pc++;
   }
   while (pa<=pa_last){  // LB 已到表尾,依次将 LA 中剩余元素插入 LC 的尾部
       *pc++ = *pa++;
   }
   while (pb<=pb_last){  // LA 已到表尾,依次将 LB 中剩余元素插入 LC 的尾部
       *pc++ = *pb++;
   }
   //上述亦可以写成:
   //while (pa<=pa_last){
       //*pc = *pa;
       //*pa++;
       //*pc ++
   //}
   
}

时间复杂度

O(m+n)

;空间复杂度

O(m+n)

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2023-01-12,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 老齐教室 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 线性表的顺序存储
    • 线性表的定义和特点
      • 顺序存储
        • 定义和特点
        • 结构
        • 顺序表的实现
        • 基本操作
    相关产品与服务
    对象存储
    对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档