一、线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使

用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，

线性表在物理上存储时，通常以数组和链式结构的形式存储。

二、顺序表

2.1概念及结构

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

顺序表一般分为：

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

//静态顺序表
#define N 100
struct SeqList
{
  int a[N];//定长数组
  int size;//有效数据的个数
};

缺点：不是很灵活

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

2.2接口实现

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

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

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

所谓动态其实指的这个结构体里的指针是动态内存开辟来的，是可变的，用的时候动态开辟，不够的话继续开辟，程序结束的时候释放。

2.3动态顺序表的创建

typedef int SLDatatype;//将int重命名为SLDatatype
typedef struct SeqList
{
  SLDatatype* a;//指向动态开辟的数组
  SLDatatype capacity;//容量
  SLDatatype size;//有效数据的个数
}SL;//将结构体SeqList重命名为SL

2.3动态顺序表的初始化

2.3.1传值初始化

//传值初始化
void SLInit(SL s)
{
  s.a = NULL;
  s.size = 0;
  s.capacity = 0;
}

函数那个章节我们学过形参只是实参的临时拷贝，并没有实际作用，生命周期短，出了函数的作用域就会销毁，我们不考虑这种初始化方式。

2.3.2传址初始化

//传址初始化
void SLInit(SL* ps)
{
  ps->a = 0;
  ps->capacity = 0;
  ps->size = 0;
}

void SLInit(SL* ps)
{
  ps->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);//开辟了4个字节的空间
  if (ps->a == NULL)
  {
    perror("malloc failed");
    exit(-1);
  }
  ps->capacity = 4;//开辟了空间就要给容量赋值
  ps->size = 0;
}

上面两种初始化方式都可以给予结构体成员变量赋值，但是我们使用第二种，因为第二种为我们开辟了空间。

2.4动态顺序表的清空

void SLDestr(SL* ps)
{
  free(ps->a);
  ps->a = NULL;
  ps->capacity = 0;//内存释放，容量清零
  ps->size = 0;//内存释放，有效数据清零
}

2.5动态顺序表的扩容

void SLCheckcapacity(SL* 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;//扩容后修改原来的容量
  }
}

这就是所谓的动态，当我们空间不够时，就需要开辟新的空间，使用realloc函数要注意是否开辟成功，定义一个中间指针，当开辟成功时将这个指针赋值给动态数组中的指针。

2.6动态顺序表内容的打印

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

size为有效数据个数，使用循环打印其中的有效数据。

三、动态顺序表的使用

3.1尾插尾删

3.1.1尾插

void SLPushBack(SL* ps, SLDatatype x)
{
  SLCheckcapacity(ps);//检查空间是否足够插入
  ps->a[ps->size] = x;//赋值
  ps->size++;//插入一个有效数据，有效数据个数加一
}

首先一定要检查规矩是否足够，根据上面开辟的空间，容量为4，有效数据为size为0，所以从第一个空间开始插入数据。

3.1.2尾删

//尾删
void SLPopBack(SL* ps)
{
  assert(ps->size > 0);//判断是否会造成越界
  if (ps->size == 0)
  {
    return;
  }
  ps->size--;//删除一个数据，有效数据个数减一
}

插入数据后size的大小也会变化，数组中最后一个数字的下标刚好和size的大小一样我们只需要将size减1就行。

3.2头插头删

3.2.1头插

void SLPushFront(SL* ps, SLDatatype x)
{
  SLCheckcapacity(ps);//检查空间是否足够
  int end = ps->size;
  while (end > 0)
  {
    ps->a[end] = ps->a[end - 1];//将前一个数据后移动
    end--;
  }
  ps->a[0] = x;//将x赋给初始位置
  ps->size++;//加入一个数字，有效数据个数加1
}

老规矩一定要检查空间是否足够，头部插入数据我们只需要将原来的数据往后移动一格就将第一格的位置空出来，再将数值插入就行，插入一个数据，有效数据加1即可。

3.2.2头删

void SLPopFront(SL* ps)
{
  assert(ps->size > 0);//防止越界访问
  if (ps->size==0)
  {
    return;
  }
  int begin = 0;
  while (begin < ps->size)
  {
    ps->a[begin] = ps->a[begin+1];//将后一个数据往前移动
    begin++;
  }
  ps->size--;//减少一个数字，有效数据减1
}

这里的删除并不是真正意义上的删除，我们只需要将原来的数据往前移动一位使后一位的数据覆盖在前一位，这就做到了删除，顺便再将有效数据减1就行。

3.3在pos位置插入x

1. voidvoid SLInsert(SL* ps, int pos, int x)
{
  assert(pos >= 0 && pos <= ps->size);//防止越界访问
  SLCheckcapacity(ps);
  int end = ps->size;
  while (end >=pos)
  {
    ps->a[end] = ps->a[end-1];//和头插的思想差不多，将数据后移
    end--;
  }
  ps->a[pos] = x;//将x赋值给pos位置
  ps->size++;//有效数据加1
}

我们可以这样理解：将pos看成初始位置，是不是就转化为头插了？按照头插的思想就可以完成在pos位置上插入x。

3.4删除pos位置的值

void SLErase(SL* ps, int pos)
{
  assert(pos >= 0 && pos <= ps->size);//防止越界访问
  SLCheckcapacity(ps);
  int begin = pos;
  while (begin < ps->size)
  {
    ps->a[begin] = ps->a[begin + 1];//和头删的思想差不多，将数据前移
    begin++;
  }
  ps->size--;//有效数据减1
}

我们会发现3.4和3.5不仅可以做到某个位置值的插入和删除，也可以做到尾插尾删和头插头删。

3.5修改某个位置的值

void SLModify(SL* ps, SLDatatype pos, SLDatatype x)
{
  assert(pos >= 0 && pos < ps->size);//防止越界
  ps->a[pos] = x;
}

这样修改某个位置的值看起来是挺麻烦，但是是为了安全考虑。

四、完整代码

#define _CRT_SECURE_NO_WARNINGS 67
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
//静态顺序表
//#define N 100
//struct SeqList
//{
//  int a[N];//定长数组
//  int size;//有效数据的个数
//};
//动态顺序表
//创建
typedef int SLDatatype;
typedef struct SeqList
{
  SLDatatype* a;//指向动态开辟的数组
  SLDatatype capacity;//容量
  SLDatatype size;//有效数据的个数
}SL;
//传值初始化
//void SLInit(SL s)
//{
//  s.a = NULL;
//  s.size = 0;
//  s.capacity = 0;
//}
//传址初始化
//void SLInit(SL* ps)
//{
//  ps->a = 0;
//  ps->capacity = 0;
//  ps->size = 0;
//}
void SLInit(SL* ps)
{
  ps->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);//开辟了4个字节的空间
  if (ps->a == NULL)
  {
    perror("malloc failed");
    exit(-1);
  }
  ps->capacity = 4;
  ps->size = 0;
}
//清空
void SLDestr(SL* ps)
{
  free(ps->a);
  ps->a = NULL;
  ps->capacity = 0;
  ps->size = 0;
}
//打印
void SLprint(SL* ps)
{
  int i = 0;
  for (i = 0; i < ps->size; i++)
  {
    printf("%d ", ps->a[i]);
  }
  printf("\n");
}
//检查容量
void SLCheckcapacity(SL* 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;
  }
}
//尾插
void SLPushBack(SL* ps, SLDatatype x)
{
  SLCheckcapacity(ps);
  ps->a[ps->size] = x;
  ps->size++;
}
//尾删
void SLPopBack(SL* ps)
{
  assert(ps->size > 0);
  if (ps->size == 0)
  {
    return;
  }
  ps->size--;
}
//头插
void SLPushFront(SL* ps, SLDatatype x)
{
  SLCheckcapacity(ps);
  int end = ps->size;
  while (end > 0)
  {
    ps->a[end] = ps->a[end - 1];
    end--;
  }
  ps->a[0] = x;
  ps->size++;
}
//头删
void SLPopFront(SL* ps)
{
  assert(ps->size > 0);
  if (ps->size==0)
  {
    return;
  }
  int begin = 0;
  while (begin < ps->size)
  {
    ps->a[begin] = ps->a[begin+1];
    begin++;
  }
  ps->size--;
}
//在pos位置插入x
void SLInsert(SL* ps, int pos, int x)
{
  assert(pos >= 0 && pos <= ps->size);
  SLCheckcapacity(ps);
  int end = ps->size;
  while (end >=pos)
  {
    ps->a[end] = ps->a[end-1];
    end--;
  }
  ps->a[pos] = x;
  ps->size++;
}
//删除pos位置的值
void SLErase(SL* ps, int pos)
{
  assert(pos >= 0 && pos <= ps->size);
  SLCheckcapacity(ps);
  int begin = pos;
  while (begin < ps->size)
  {
    ps->a[begin] = ps->a[begin + 1];
    begin++;
  }
  ps->size--;
}
int SLFind(SL* ps, int x)
{
  int i = 0;
  for (i = 0; i < ps->size; i++)
  {
    if (ps->a[i] == x)
      return i;
  }
  return -1;
}
void SLModify(SL* ps, SLDatatype pos, SLDatatype x)
{
  assert(pos >= 0 && pos < ps->size);
  ps->a[pos] = x;
}
int main()
{
  SL s1;
  //传值初始化
  //SLInit(s1);
  //传址初始化
  SLInit(&s1);
  //尾插
  SLPushBack(&s1, 1);
  SLPushBack(&s1, 2);
  SLPushBack(&s1, 3);
  SLPushBack(&s1, 4);
  SLPushBack(&s1, 5);
  SLPushBack(&s1, 6);
  SLPushBack(&s1, 7);
  //尾插测试
  printf("尾插:\n");
  SLprint(&s1);
  //尾删
  SLPopBack(&s1);
  //尾删测试
  printf("尾删:\n");
  SLprint(&s1);
  //头插
  SLPushFront(&s1,10);
  //头插测试
  printf("头插:\n");
  SLprint(&s1);
  //头删 
  SLPopFront(&s1);
  //头删测试
  printf("头删:\n");
  SLprint(&s1);
  //在pos位置插入x
  SLInsert(&s1, 0, 100);
  //pos插入x测试
  printf("pos位置插入x\n");
  SLprint(&s1);
  //删除pos位置的值
  SLErase(&s1, 0);
  //测试
  printf("删除pos位置的值\n");
  SLprint(&s1);
  //改
  SLModify(&s1, 2, 1);
  printf("修改某个位置上的值:\n");
  //
  SLprint(&s1);
  //清空
  SLDestr(&s1);
  return 0;
}

详解初阶数据结构之顺序表（SeqList）——单文件实现SeqList的增删查改