动态顺序表

//数组顺序表的结构定义
typedef int SLDataType;
typedef struct SeqList {
  SLDataType* a;
  int size;//有效数据
  int capacity;//空间容量
}SL;

//动态顺序表的初始化
void SLInit(SL* psl)
{
    assert(psl);
  psl->a = NULL;
  psl->size = 0;
  psl->capacity = 0;
}

//动态顺序表的打印
void SLPrint(SL psl)
{
  for (int i = 0; i < psl.size; i++)
  {
    printf("%d ", psl.a[i]);
  }
  printf("\n");
}

//动态顺序表的尾插
void SLPushBack(SL* psl, SLDataType x)
{
    assert(psl);
  if (psl->size == psl->capacity)
  {
    //SLDataType* p = (SLDataType*)realloc(psl->a, psl->capacity == 0 ? 4 : 2 * psl->capacity * sizeof(SLDataType));
    int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
    SLDataType* p = (SLDataType*)realloc(psl->a, newcapacity * sizeof(SLDataType));
    if (p == NULL)
    {
      perror("realloc fail");
      exit(-1);
    }
    else
    {
      psl->a = p;
      psl->capacity = newcapacity;
    }
  }
  psl->a[psl->size++] = x;
}

//封装扩容函数
void checkcapacity(SL* psl)
{
  assert(psl);
  if (psl->size == psl->capacity)
  {
    int newcapacity = psl->capacity == 0 ? 4 : 2 * psl->capacity;
    SL* p = (SLDataType*)realloc(psl->a, newcapacity * sizeof(SLDataType));
    if (p == NULL)
    {
      perror("realloc fail");
      exit(-1);
    }
    else
    {
      psl->a = p;
      psl->capacity = newcapacity;
    }
  }
}

//动态顺序表头插
void SLPushFront(SL* psl, SLDataType x)
{
    assert(psl);
  checkcapacity(psl);
  for (int i = psl->size; i > 0; i--)
  {
    psl->a[i] = psl->a[i - 1];
  }
  psl->a[0] = x;
  psl->size++;
}

//动态顺序表的尾删
void SLPopBack(SL* psl)
{
    assert(psl);
  assert(psl->size > 0);
  psl->size--;
}

//动态顺序表的头删
void SLPopFront(SL* psl)
{
    assert(psl);
  assert(psl->size > 0);
  for (int i = 0; i < psl->size - 1; i++)
  {
    psl->a[i] = psl->a[i + 1];
  }
  psl->size--;
}

//动态顺序表任意位置插入
void SLInsert(SL* psl, int pos, SLDataType x)
{
    assert(psl);
  assert(pos >= 1 && pos <= psl->size);
  checkcapacity(psl);
  for (int i = psl->size; i > pos - 1; i--)
  {
    psl->a[i] = psl->a[i - 1];
  }
  psl->a[pos - 1] = x;
  psl->size++;
}

//动态顺序表任意位置删除
void SLErase(SL* psl, int pos)
{
    assert(psl);
  assert(pos >= 1 && pos <= psl->size);
  for (int i = pos - 1; i < psl->size - 1; i++)
  {
    psl->a[i] = psl->a[i + 1];
  }
  psl->size--;
}

//动态顺序表销毁
void SLDestroy(SL* psl)
{
  assert(psl);
  if (psl->a != NULL)
  {
    free(psl->a);
    psl->a = NULL;
    psl->capacity = 0;
    psl->size = 0;
  }
}

void test01()
{
    //定义动态顺序表
    SL psl;
    //初始化动态顺序表
    SLInit(&psl);
    //尾插
    SLPushBack(&psl, 1);
    SLPushBack(&psl, 2);
    SLPushBack(&psl, 3);
    SLPushBack(&psl, 4);
    SLPushBack(&psl, 5);
    //打印
    SLPrint(psl);
    //头插
    SLPushFront(&psl, 1);
    SLPushFront(&psl, 2);
    SLPushFront(&psl, 3);
    SLPushFront(&psl, 4);
    SLPushFront(&psl, 5);
    //打印
    SLPrint(psl);
    //尾删
    SLPopBack(&psl);
    SLPopBack(&psl);
    SLPopBack(&psl);
    //打印
    SLPrint(psl);
    //头删
    SLPopFront(&psl);
    SLPopFront(&psl);
    SLPopFront(&psl);
    //打印
    SLPrint(psl);
    //任意位置插入
    SLInsert(&psl, 2, 10);
    SLInsert(&psl, 2, 11);
    SLInsert(&psl, 2, 12);
    //打印
    SLPrint(psl);
    //任意位置删除
    SLErase(&psl, 2);
    SLErase(&psl, 2);
    SLErase(&psl, 2);
    //打印
    SLPrint(psl);
    //销毁
    SLDestroy(&psl);
}
int main()
{
    test01();
    return 0;
}