数据结构—顺序表

2023-06-14 35

版权

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

简介： 数据结构—顺序表

1.顺序表概念

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

2.顺序表分类：

2.1 静态顺序表：使用定长数组存储元素。（不实用）

2.2动态顺序表：使用动态开辟的数组存储。

3.实现动态顺序表

3.1 初始化顺序表 SLInit

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

3.2 检查顺序表容量 SLCheckCapacity

void SLCheckCapacity(SL* ps)
{
  assert(ps != NULL);
  // 检查容量空间，满了扩容
  if (ps->size == ps->capacity)
  {
    int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
    if (tmp == NULL)
    {
      printf("realloc fail\n");
      //exit(-1);
      return;
    }
    ps->a = tmp;
    ps->capacity = newCapacity;
  }
}

3.3 打印顺序表 SLPrint

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

3.4 尾插 SLPushBack

void SLPushBack(SL* ps, SLDataType x)
{
  assert(ps != NULL);
  SLCheckCapacity(ps);
  ps->a[ps->size] = x;
  ps->size++;
  //SLInsert(ps, ps->size, x);
}

3.5 头插 SLPushFront

void SLPushFront(SL* ps, SLDataType x)
{
  assert(ps != NULL);
  SLCheckCapacity(ps);
  // 挪动数据
  int end = ps->size - 1;
  while (end >= 0)
  {
    ps->a[end + 1] = ps->a[end];
    --end;
  }
  ps->a[0] = x;
  ps->size++;
  //SLInsert(ps, 0, x);
}

3.7 头删 SLPopFront

void SLPopFront(SL* ps)
{
  assert(ps != NULL);
  assert(ps->size > 0);
  int begin = 1;
  while (begin < ps->size)
  {
    ps->a[begin - 1] = ps->a[begin];
    ++begin;
  }
  ps->size--;
  //SLErase(ps, 0);
}

3.8 顺序表查找 SLFind

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

3.9 顺序表修改 SLModify

void SLModify(SL* ps, int pos, SLDataType x)
{
  assert(ps);
  assert(pos >= 0 && pos < ps->size);
  ps->a[pos] = x;
}

4. 顺序表总结

4.1 顺序表优化

使用SLInsert函数实现尾插，头插

使用SLErase函数实现尾删，头删

void SLInsert(SL* ps, int pos, SLDataType x)
{
  assert(ps);
  assert(pos >= 0 && pos <= ps->size);
  SLCheckCapacity(ps);
  // 挪动数据
  int end = ps->size - 1;
  while (end >= pos)
  {
    ps->a[end + 1] = ps->a[end];
    --end;
  }
  ps->a[pos] = x;
  ps->size++;
}

void SLErase(SL* ps, int pos)
{
  assert(ps);
  assert(pos >= 0 && pos < ps->size);
    //两种方法实现
  //int begin = pos;
  //while (begin < ps->size-1)
  //{
  //  ps->a[begin] = ps->a[begin + 1];
  //  ++begin;
  //}
  int begin = pos + 1;
  while (begin < ps->size)
  {
    ps->a[begin - 1] = ps->a[begin];
    ++begin;
  }
  ps->size--;
}

4.2 顺序表的缺点

由于头插和头删需要移动数据，所以时间复杂度为O(N），所以后面引入链表实现。