前言： 刷题和面试兼顾还得看你啊-牛客网

近几年互联网受疫情影响，许多互联网都使用牛客网在线笔试招人

很多同学因为不熟悉牛客网的环境和使用，最后在线笔试面试中屡屡受挫

牛客网提供了语言巩固，算法提高等在线OJ题，更有面试真题，大厂内推！

链接附上点击链接注册牛客网

牛客网这么好用，但是下面几个关于牛客网的知识你了解过吗？

你知道你OJ过不了，牛客网几种经典的英文报错提示的含义吗？

你知道牛客网的OJ分为IO型和接口型吗？

你使用过牛客网的调试功能吗？

一.基本介绍

线性表 （linklist list） 是 数据结构 的一种，一个线性表是n个具有相同特性的数据元素的有限序列

顾名思义：线性表就像一条线,不会分叉(学到树和图你自然就明白了)

线性表分为:顺序表,链表,栈和队列

线性表的两种存储方式：顺序储存和链式存储

1-2顺序表(sequence list-----通常缩写为SeqList)

顺序表分类:静态顺序表和动态顺序表

(1)静态顺序表缺点:初始时开辟定长数组,在进行插入操作时容易超出预分配的空间长度,造成溢出等

(2)动态顺序表优点:初始时动态分配内存,在进行插入操作时可灵活扩充存储空间等,推荐使用

0.动态顺序表的动态分配结构体的定义:

typedef  int SeqDateType; 
typedef struct SeqList
{
  SeqDataType* a;
  int size;      // 有效数据的个数
  int capacity;  // 容量
}SeqList;

二、基本操作

1.顺序表的初始化

你要打开冰箱拿雪糕的前提就是你得先拥有一个冰箱（顺序表）,所以操作顺序表前我们得先创建一个顺序表啊

void SeqListInit(SeqList* pq)
{
  assert(pq);//等价于assert(pq != NULL)
  pq->a = NULL;
  pq->size = pq->capacity = 0;
}

2.顺序表的销毁

顺序表的数组是动态开辟的,占用的是堆上的空间,需要程序员手动去释放,防止长时间占用内存,这既符合谁开辟谁释放的原则,更是一个毋庸置疑的好习惯!

void SeqListDestory(SeqList* pq)
{
  assert(pq);
  free(pq->a);
  pq->a = NULL;
  pq->capacity = pq->size = 0;
}

备注:销毁同样改变了主函数内实参那个顺序表,所以依旧是传址调用

3.顺序表的打印

打印就是将顺序表展示在输出窗口的,但是这一步和打印数组一毛一样!

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

4.顺序表插入时检查是否需要扩容

顺序表插入时检查是否需要扩容在每次插入操作时都会用到，所以建议封装成函数，模块化代码，需要时直接调用

void SeqCheckCapacity(SeqList* pq)
{
  if (pq->size == pq->capacity)
  {
    int newcapacity = pq->capacity == 0 ? 4 : pq->capacity * 2;
    SeqDataType* newA = realloc(pq->a, sizeof(SeqDataType)*newcapacity);
    if (newA == NULL)
    {
      printf("realloc fail\n");
      exit(-1);
    }
    pq->a = newA;
    pq->capacity = newcapacity;
  }
}