【初阶数据结构】深入解析顺序表:探索底层逻辑-阿里云开发者社区

【初阶数据结构】深入解析顺序表:探索底层逻辑

2024-10-08 10

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

本文涉及的产品

公共DNS（含HTTPDNS解析），每月1000万次HTTP解析

云解析 DNS，旗舰版 1个月

全局流量管理 GTM，标准版 1个月

简介： 【初阶数据结构】深入解析顺序表:探索底层逻辑

一、线性表的概念

线性表（linear list）n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串等。线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储

二、顺序表的概念

顺序表属于线性表的其中一种。顺序表在逻辑、物理结构上是连续，顺序表底层逻辑实现一般是数组。关于物理结构上连续是指一段物理地址连续的存储单元依次存储数据元素的结构

三、顺序表的分类

顺序表分为两种：静态顺序表和动态顺序表，每一种都属于它自己的价值，在实际中。一般使用动态顺序表做的，比如我们经常用的通讯录(因为静态顺序表只适合事前知道需要多少内存的情况下，不然会出现申请多少内存问题)

四、实现顺序表的相关接口(Seqlist.h)

五、正式开始模拟实现顺序表

提前说明下:每一个接口都需要断言下传过来的指针是否为空指针去判断是否是一个有效的结构体变量。如果是第一次接触数据结构，首先需要搞清楚size代表了有效元素个数，而capacity代表的是这块空间的大小或者容量，这里两个东西不是一个意思。

小技巧:在循环中如果不知道结束条件的话，带入临界值去尝试是否符合条件

5.1 顺序表的初始化

void SLInit(SL* phead)
{
  assert(phead);
  phead->a = NULL;
  phead->size = phead->capacity = 0;
}

这里需要注意的是:空间上没有硬性要求不开空间，可以适当开辟空间，当空间不足时，需向系统申请空间。

5.2 顺序表的扩容(为插入数据提供保障)

void SLChekckCapacity(SL* phead)
{
  assert(phead);
  if (phead->size == phead->capacity)
  {
    int newcapacity =phead->capacity==0?4:phead->capacity * 2;
    SLDataType* pphead = (SLDataType*)realloc(phead->a, sizeof(SLDataType) * newcapacity);
    if (pphead == NULL)
    {
      perror("realloc fail!!");
      return 1;
    }
    phead->a = pphead;
    phead->capacity = newcapacity;
  }
}

这里需要注意的是:当有效元素个数等于当前空间容量为了下一次的插入元素，需要进行扩容操作。由于扩容功能需要多次调用，对此可以考虑设计为一个接口SLChekckCapacity进行复用。

在接口底层逻辑中，值得我们注意的是当capacity为空(零乘任何数为零)，会导致申请空间大小出现错误。这里有两种解决措施:提前开辟一定量空间或者使用新的变量newcapacity进行接收，防止数据丢失。最好不要phead直接接收扩容的地址，防止扩容(第二种情况)失败导致找不到之前空间地址。开辟以字符类型来维修开辟的空间，需要为‘\0‘开辟一个空间。

5.3 顺序表的插入数据

插入分为三类：头插\尾插\任意位置插入(其中任意位置插入，在实现查找功能先放着)

5.3.1 顺序表的尾插

void SLPlusBack(SL*phead, SLDataType x)
{
  assert(phead);
    if(phead->size == phead->capacity)
  SLChekckCapacity(phead);
  phead->a[phead->size] = x;
  phead->size++;
}

这里需要注意的是:这里主要利用下标赋值完成插入的操作

5.3.2 顺序表的头插

void SLPlusFront(SL* phead, SLDataType x)
{
  assert(phead);
    if(phead->size == phead->capacity)
  SLChekckCapacity(phead);
  for (int i = phead->size; i >0; i--)
  {
    phead->a[i] = phead->a[i - 1];
  }
  phead->a[0] = x;
  phead->size++;
}

这里需要注意的是:原数据整体向后移动，首次位置会数据重复，将首元素将其覆盖，实现头插的效果。

设置循环条件，数据向后移动(覆盖并数值不丢失)。如果是从前先后覆盖，比如1 2 3 4 5 变成 1 1 2 3 4 5，将i的值赋值给i+1，i从首元素下标开始并且覆盖方式nums[i+1]=nums[i]

5.4 顺序表的删除数据

删除分为三类：头删尾删任意位置删除(其中任意位置删除，在实现查找功能先放着)

提前说明:空表无法进行删除数据，需要在删除操作之前进行断言检查assert(phead->a)

5.4.1 顺序表的尾删

void SLPopBack(SL* phead)
{
  assert(phead);
  assert(phead->a);
  phead->size--;
}

这里需要注意的是:这里删除不是将数据设为0就是删除数据。正确的做法，通过size（有效数据个数）个数控制。顺序表不访问size外的无效数据，那么从某种意义上是删除了数据（班里有位同学退学，班里人数少一位，同学还是存在，只是座位没有它），不需要空间是否浪费，尾插数据时，可能下次还是用到那个空间。

5.4.2 顺序表的头删

void SLPopFront(SL* phead)
{
  assert(phead);
  assert(phead->a);
  for (int i = 0; i < phead->size-1; i++)
  {
    phead->a[i] = phead->a[i + 1];
  }
  phead->size--;
}

这里需要注意的是:数组删除数据的方式就是覆盖数据，那么只需要从后向前覆盖，首元素将被覆盖或者被删除

设置循环条件，数据向前移动(覆盖并数值不丢失)。如果是从后先前覆盖，比如1 2 3 4 5变成 2 3 4 5 5，将i+1的值赋值给i，i从首元素下标开始并且覆盖方式nums[i]=nums[i+1]

5.5 查找指定位置的下标

int SLFind(SL* phead, SLDataType x)
{
  assert(phead);
  assert(phead->a);
  for (int i = 0; i < phead->size; i++)
  {
    if (phead->a[i] == x)
            return i;
  }
  return -1;
}

这里需要注意的是:遍历顺序表，如果满足条件返回当前位置的下标，没有找到返回一个负数表示找不到。

5.5 顺序表的任意位置插入(pos是下标)

void SLInsert(SL* phead, int pos, SLDataType x)
{
  assert(phead);
  assert(0 <= pos && pos <= phead->size);
    SLChekckCapacity(phead);
    for (int i = phead->size; i>pos;i--)
    {
      phead->a[i] = phead->a[i-1];//pos+1 pos-->注意覆盖的顺序,向后就是后面开始
    }
    phead->a[pos] = x;  
    phead->size++;
}

这里需要注意的是:任意位置上的修改(任意是相对的，需要对pos进行限制)。具体流程就是以下标pos为界，pos之后的数据向后移动（跟头插类似，主要是在循环条件略显差异）

5.6 顺序表的任意位置删除(pos是下标)

void SLErase(SL* phead, int pos)
{
  assert(phead);
  assert(pos >= 0 && pos < phead->size);
  for (int i = pos;i<phead->size-1;i++)
  {
    phead->a[i] = phead->a[i + 1];
  }
  phead->size--;
}

这里需要注意的是:任意位置上的修改(任意是相对的，需要对pos进行限制)。具体流程就是以下标pos为界，pos之后的数据向前移动(跟头删是类似的，主要是在循环条件略显差异)

小总结:顺序表通过任意位置插入\删除去取代头尾的插入\删除操作，至于为什么需要了解头尾的插入\删除操作，虽然相当于基础，也是需要学习的(只有学会1+1，才能学会7+8)

5.7 顺序表的判空(主要是否存在有效元素)

bool SLEmpty(SL*phead)
{
  assert(phead);
    assert(phead->a);
    return phead->size==0;
}

5.8 顺序表的打印

void SLPrintData(SL*phead)
{
  assert(phead);
  for (int i = 0; i < phead->size; i++)
  {
    printf("%d ", phead->a[i]);
  }
  printf("\n");
}

5.9 顺序表的销毁

void SLDestory(SL*phead)
{
    assert(phead);
    if (phead->a)
    {
        free(phead->a);//free该前顺序表的动态开辟的空间
        phead->a = NULL;
        phead->size = phead->capacity = 0;
    } 
}

六、顺序表的优缺点

顺序表的优点:支持下标随机访问(时间复杂度O(1))

顺序表的缺点:

在实现插入和删除操作过程中，通过大量的移动数据，效率较低
空间不足需要扩容并且需要付出一定的代价，可能存在空间浪费
只适合尾插尾删

七、顺序表和链表的区别

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(1)	不支持：O(N)
任意位置插入或者删除元素	可能需要搬移元素，效率低 O(N)	只需修改指针指向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁
缓存利用率	高	低

不管是哪一种数据结构都有他的优点和缺点，对此在使用数据结构中应该知道它的优缺点是什么，加以合理地利用解决实际中的问题。