数据结构-顺序表-阿里云开发者社区

1.线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储

2.顺序表

2.1概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存

储。在数组上完成数据的增删查改。

顺序表一般可以分为：

1. 静态顺序表：使用定长数组存储元素。

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

2.2 接口实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空

间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间

大小，所以下面我们实现动态顺序表。

在头文件SeqList.h中声明定义一下这个顺序表，然后声明基本功能，那么顺序表的基本功能就是增删查改，头插头删，尾插尾删。

typedef int SLDataType;
typedef struct SeqList
{
  SLDataType* a;//动态开辟的的数组
  int size;//有效数据个数
  int capacity;//空间大小
}SL;
//管理数据-增删查改
void SLInit(SL* ps);
void SLDestory(SL* ps);
void SLPrint(SL* ps);
void SLCheckCapacity(SL* ps);
int SLFind(SL* ps, SLDataType x);
//头插头删，尾插尾删
void SLPushBack(SL* ps,SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);
//在pos位置上插入x
void SLInSert(SL* ps, int pos, SLDataType x);
//删除pos位置上的值
void SLErase(SL* ps, int pos);
//修改pos位置的值
void SLModify(SL* ps, int pos, SLDataType x);

2.3管理数据-增删查改

需要注意的是，这里的传参是传地址。

2.3.1初始化

首先我们要对顺序表进行初始化，先对这个数组动态开辟一块空间，判断是否成功，如果失败则退出程序，然后size置为0，capacity就是开辟的空间大小。

void SLInit(SL* ps)
{
  assert(ps);
  ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);
  if (ps->a == NULL)
  {
    perror("malloc failed");
    exit(-1);
    //return;
  }
  ps->size = 0;
  ps->capacity = 4;
}

2.3.2销毁

销毁就是把动态开辟给数组的空间释放，然后置为空指针，再把size和capacity置为0.

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

2.3.3尾插

尾删就是在数组的末尾插入需要的数据，首先我们要判断一下空间是否满了，满了的话就使用realloc进行扩容，使用另外一块空间tmp来接收，如果成功则将tmp这块空间给a，然后将capacity乘上2。数组的末尾也就是size元素个数，因为size是下标加1，所以直接在size这个位置上插入就行了，然后将size++。

void SLPushBack(SL* ps, SLDataType x)
{
  assert(ps);
    //满了要扩容
    if(ps->size==ps->capacity)
    {
       SLDataType* tmp=(SLDataType*)realloc(pa->a,ps->capacity*2*(sizeof(SLDataType)));
       if(tmp==NULL)
       {
          perror("realloc")
          exit(-1);
       }
       ps->a=tmp;
       ps->capacity*=2;
     }
  ps->a[ps->size] = x;
  ps->size++;
}

2.3.4打印

打印顺序表比较简单，需要注意的是要使用assert断言一下。

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

2.3.5尾删

很多人认为尾删要把那个数据置为0，其实这样是没有意义的，因为如果那个位置刚好是0的话，就多余了。其实正确的做法是直接size--就可以了，因为如果进行插入的话就直接覆盖了，置不置为0都是一样的效果。因为容量capacity没有变化，所以不需要改变。其实仅仅是这样做的话还是有问题的，因为如果尾删了太多再插入，就越界了，所以要进行检查，ps->size>0，才能正常进行。

void SLPopBack(SL* ps)
{
  assert(ps);
  // 暴力的检查
  assert(ps->size > 0);
  ps->a[ps->size - 1] = 0;
  ps->size--;
  SLErase(ps, ps->size - 1);
}

2.3.6头插

头插就是在下标为0的位置上插入一个数据，那么就需要从后面开始挪动数据，为这个数据腾出空间，end就是size-1的位置，将end位置的数据赋给end+1的位置，这个循环的最后一次执行是将0这个位置的值赋给1这个位置，所以循环条件是end>=0，然后将x这个数据放进0这个位置就行了，最后将size++。

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

2.3.7头删

头删就需要将数据从后往前挪动，所以写一个whil循环，结束的位置是size-1这个位置，循环结束后将size--即可，但需要注意的是这个顺序表可能存在是空的情况，所以使用assert判断。

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

2.3.8检查空间

这个函数的目的是检查空间是否满了，如果满了的话则扩容至2倍。

void SLCheckCapacity(SL* ps)
{
  assert(ps);
  // 满了要扩容
  if (ps->size == ps->capacity)
  {
    SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * (sizeof(SLDataType)));
    if (tmp == NULL)
    {
      perror("realloc failed");
      exit(-1);
    }
    ps->a = tmp;
    ps->capacity *= 2;
  }
}

2.3.8在pos位置插入x

首先要判断一下插入的这个pos是不是合理的，应该是>=0&&<=size，然后调用SLCheakCapacity检查一下空间是不是满了。挪动数据从前往后挪动，直到end=pos，然后将x赋给a[pos]，最后将size++。

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++;
}

那么当我们写了SLInsert这个函数之后，就可以复用一下了。

在头插中：

void SLPushFront(SL* ps, SLDataType x)
{
  assert(ps);
  //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);
}

在尾插中:

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

2.3.9删除pos位置的值

删除的话就不能等于size这个位置了，因为size这个位置是空的。删除的话就是将pos后的数据覆盖到pos这个位置，然后不停的往前挪，最后size--。

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

2.3.10修改

这里直接修改就是了。

1. void SLModify(SL* ps, int pos, SLDataType x)
2. {
3.  assert(ps);
4. 
5.  assert(pos >= 0 && pos < ps->size);
6. 
7.  ps->a[pos] = x;
8. }

数据结构-顺序表