在介绍今天的主角顺序表之前，我先给出一些必要的概念。

一、线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中⼴泛使 ⽤的数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。

其中两个概念：逻辑结构和物理结构：

逻辑结构：指的就是我们逻辑上的结构，也就是我们心里认为的或者假定的结构，简单来说也就是我们平时画的那些图上，这些结构是连续的。比如如下图中的数组，我们画的图都是连续的，不是说这里一块，那里一块的这种，是顺下去的没有断开的。其实就是我们逻辑上把他看成连续的。

包括下面的链表，虽然它的每个结点在（我们下个博客会知道）内存上它是不连续的，可能第一个是0x100，第二个就变成了0x200，而不是0x101。但是我们画图还是把它画成一个一个连起来的样子。逻辑上认为它是连续的。或者说它们都属于这个链表，虽然内存不相邻，但是在逻辑上是一个一个顺下去的。我们也是这么画的。

物理结构：其实就是内存中的地址，物理结构连续就是地址是连续的，比如字符数组如果第一个的地址是0x100，下一个就是0x101这样子。

二、顺序表

1.概念：

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

2.和数组的区别？

顺序表和数组不一样，但是顺序表是用数组实现的。它的底层结构是数组，对数组封装后，实现了增删改查的功能。打个比方，就像普通小饭馆里的玉米羹，加上特制料汁，小饰品并摆盘后就变成了米其林餐厅里的宫廷玉液羹。数组也是加上增删改查功能后就变成了顺序表。

3.静态顺序表和动态顺序表

静态顺序表：用定长数组来实现。

#define N 7
struct SeqList {
      int arr[N];
      int size;
}

size是代指存进去了几个元素。

但是这种顺序表我们可以看出明显不够灵活，你的N给大了就浪费空间，给少了就不够存。比如我现在要存50个，我给100个空间，那后面又要再存几百个数据怎么办，你给10000个空间就浪费太多了，再多空间也经不起这么折腾。所以我们很多时候需要动态顺序表

动态顺序表：

typedef int SLDataType;
typedef struct SeqList {
      SLDataType* arr;
      int size;
      int capacity;
}SL;

解释一下这个代码：

size表示现在存进去的数据个数（有效数据个数），capacity表示数据总大小（空间容量）。

第一行的typedef是因为我们存的数据不一定是int类型的，也有可能存字符型，浮点型，如果我们存其他类型的话我们就用typedef进行全部的替换更改就行了。比如要存char类型我们就

typedef char SLDataType;

也有人觉得为什么不用vs2026的全部替换功能，但是那样子会替换掉别的东西，造成误伤，比如你size和capacity的类型也被改了。所以我们新设一个SLDataType类型，size和capacity一定是int就不用改了，数组用SLDataType类型。

第三行我们存一个指针，后续要动态开辟内存。

对整个结构体typedef是为了后续写的少一些，写SL就行。

三、动态顺序表功能实现

我会一一实现并进行讲解。

建立一个项目三个文件，一个头文件SeqList.h（用来进行函数的声明，并且把studio.h等头文件都放在这里，后面两个源文件只要#include“SeqList.h”即可），两个源文件SeqList.c（用来实现函数，就是具体写函数），test.c（测试用例）

1.初始化顺序表：

//初始化顺序表
void InitSl(SL* ps) {
      assert(ps);
      ps->arr=NULL;
      ps->size=ps->capacity=0;
}

首先传进来的顺序表指针不能是空的，用assert判断，记得加assert.h，这里传进来的是地址，因为形参要改变实参需要传址调用，我们肯定要改变原顺序表的。把arr置空，别的置零即可。

2.检查增容

因为有时候空间不够用就要扩容，还有一开始没有空间也要开辟空间。我们整合成一个增容功能。

//检查增容
void SLCheckCapacity(SL* ps) {
       assert(ps);
       if(ps->capacity==ps->size)
       {
       ps->capacity=(ps->capacity==0?4:2*ps->capacity);
       
       SLDataType* ptr=(SLDataType *)realloc(ps->arr,ps->capacity*sizeof(SLDataType));
       if (ptr == NULL) {
           perror("realloc");
           exit(1);
       }
       ps->arr=ptr;
       }
}

第一个if就是判断空间够不够，不够我们就增容，如果空间是0就给它4个空间，不是0我们就扩容，我们一般习惯二倍扩容。

realloc如果空指针就会开辟空间，不是就会扩容，记得后面乘上sizeof（SLDataType）。

第二个if就是判断realloc是否失败，经典操作。

3.尾插

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

先判断空间是否足够，我们已经封装成了一个函数，判断完后，让最后一个是x就行，记得size要加一，有效元素多了一个。

4.头插

//头插
void SLPushFront(SL*ps,SLDataType x) {
        assert(ps);
        SLCheckCapacity(ps);
        for (int i = ps->size;i > 0;i--) {
               ps->arr[i]=ps->arr[i-1];
        }
        ps->arr[0]=x;
        ps->size++;
}

头插的话我们就把所有元素后移一个，再放要插的元素即可。此处注意要从后往前移，如果从前往后移要移动的元素就被上一个覆盖了。记得有效元素个数加一。

5.打印顺序表

//打印整型顺序表
void SLPrint(SL* ps) {
    assert(ps);
    for (int i = 0;i < ps->size;i++) {
        printf("%d ",ps->arr[i]);
    }
    printf("\n");
}

有时候一下一下去调试比较麻烦，我们就打印出来看顺序表的内容。用循环打印即可。

6.尾删

//尾删
void SLPopBack(SL* ps) {
       assert(ps&&ps->size);
       ps->size--;
}

我现在把尾部要删的那个元素称为tail

尾删只需把有效元素个数减一即可，因为你打印，插入还是什么操作都不会有影响，（如果free必须free整个数组，不能单个free），你插入的话不管头插尾插你tail会被覆盖，相当于被删了之后再插入，如果打印只会打印到tail之前，也相当于被删了。也就是说有效元素个数减一之后就相当于tail被删了，没影响。

7.头删

//头删
void SLPopFront(SL* ps) {
    assert(ps&&ps->size);
    for (int i = 1;i < ps->size;i++) {
        ps->arr[i-1]=ps->arr[i];
    }
    ps->size--;
}

我把头部要删的元素称为head

assert防止传入空指针，头删只要把head之后的所有元素往前移一下把head给覆盖掉就行了。用循环实现即可。

8.删除特定（pos）位置

//删除pos位置数据
void SLErase(SL* ps,int pos) {
      assert(ps&&(pos>=0)&&(pos<ps->size));
      for (int i = pos+1;i < ps->size;i++) {
          ps->arr[i-1]=ps->arr[i];
      }
      ps->size--;
}

首先一样的，地址不能为空，pos要在范围内。

然后pos位置之后，全部往前移一个把pos覆盖掉就行。

9.在pos前插入数据

//在pos前插入数据
void SLInsert(SL* ps, int pos,SLDataType x) {
    assert(ps&&(pos>=0)&&(pos<=ps->size));
    SLCheckCapacity(ps);
    for (int i = ps->size;i > pos;i--) {
        ps->arr[i]=ps->arr[i-1];
    }
    ps->arr[pos]=x;
    ps->size++;
}

首先依旧assert断言判断，插入判断空间够不够，判断是否增容，然后循环，i=size，也就是数组最后一个的后面那个，你就把pos以及pos之后的元素一个个赋值搬运到右边一位，再把pos位置赋值为x，记得最后有效元素个数加一就行。

10.查找元素

//查找元素(1版)
int SLFind(SL* ps, SLDataType x) {
         assert(ps);
         for (int i = 0;i < ps->size;i++) {
             if (ps->arr[i] == x) {
                 printf("找到了\n");
                 return i;
             }
         }
         printf("没找到");
         return -1;

}

很简单的遍历，然后一个个==判断就行。

上面的是老师教的版本，我这里还有一个版本，就是如果有多个相同元素要查找咋办。

//查找元素(2版)
void My_SLFind(SL* ps,SLDataType x) {
    assert(ps);
    int flag=0;
    for (int i = 0;i < ps->size;i++) {
        if (ps->arr[i] == x) {
            printf("找到了！在下标为%d处\n",i);
            flag=1;
        }
      }
    if (flag == 0) {
        printf("没找到！");
      }
}

先弄一个flag变量，如果但凡有一个找到，就打印它的下标，并把flag置为1，之后每找到一次就打印一次，最后再flag判断是不是0，如果有找到，flag就不是0是1；没找到，flag就是0没有改变，判断后就打印没找到。

11.销毁顺序表

//销毁顺序表
void SLDestroy(SL* ps) {
     assert(ps);
     if(ps->arr){
     free(ps->arr);
     }
     ps->arr=NULL;
     ps->capacity=ps->size=0;
}

释放空间并将其指针置空，size和capacity置为0即可。

四、最后贴一下所有项目文件

SeqList.h：

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>


typedef int SLDataType;
typedef struct SeqList {
      SLDataType* arr;
      int size;
      int capacity;
}SL;
//初始化
void InitSl(SL* ps);
//增容
void SLCheckCapacity(SL * ps);
//尾插
void SLPushBack(SL * ps, SLDataType x);
//头插
void SLPushFront(SL * ps, SLDataType x);
//打印
void SLPrint(SL * ps);
//尾删
void SLPopBack(SL * ps);
//头删
void SLPopFront(SL * ps);
//删除pos位置数据
void SLErase(SL * ps, int pos);
//在pos前插入数据
void SLInsert(SL* ps, int pos, SLDataType x);
//销毁顺序表
void SLDestroy(SL* ps);
//查找元素(我)
void My_SLFind(SL* ps, SLDataType x);
//查找元素(老师版)
int SLFind(SL* ps, SLDataType x);

SeqList.c：

#include "SeqList.h"

//初始化顺序表
void InitSl(SL* ps) {
      assert(ps);
      ps->arr=NULL;
      ps->size=ps->capacity=0;
}


//检查增容
void SLCheckCapacity(SL* ps) {
       assert(ps);
       if(ps->capacity==ps->size)
       {
       ps->capacity=(ps->capacity==0?4:2*ps->capacity);
       
       SLDataType* ptr=(SLDataType *)realloc(ps->arr,ps->capacity*sizeof(SLDataType));
       if (ptr == NULL) {
           perror("realloc");
           exit(1);
       }
       ps->arr=ptr;
       }
}

//尾插
void SLPushBack(SL* ps,SLDataType x) {
        assert(ps);
        SLCheckCapacity(ps);
        ps->arr[ps->size]=x;
        ps->size++;
}
//头插
void SLPushFront(SL*ps,SLDataType x) {
        assert(ps);
        SLCheckCapacity(ps);
        for (int i = ps->size;i > 0;i--) {
               ps->arr[i]=ps->arr[i-1];
        }
        ps->arr[0]=x;
        ps->size++;
}
//打印整型顺序表
void SLPrint(SL* ps) {
    assert(ps);
    for (int i = 0;i < ps->size;i++) {
        printf("%d ",ps->arr[i]);
    }
    printf("\n");
}
//尾删
void SLPopBack(SL* ps) {
       assert(ps&&ps->size);
       ps->size--;
}
//头删
void SLPopFront(SL* ps) {
    assert(ps&&ps->size);
    for (int i = 1;i < ps->size;i++) {
        ps->arr[i-1]=ps->arr[i];
    }
    ps->size--;
}
//删除pos位置数据
void SLErase(SL* ps,int pos) {
      assert(ps&&(pos>=0)&&(pos<ps->size));
      for (int i = pos+1;i < ps->size;i++) {
          ps->arr[i-1]=ps->arr[i];
      }
      ps->size--;
}
//在pos前插入数据
void SLInsert(SL* ps, int pos,SLDataType x) {
    assert(ps&&(pos>=0)&&(pos<=ps->size));
    SLCheckCapacity(ps);
    for (int i = ps->size;i > pos;i--) {
        ps->arr[i]=ps->arr[i-1];
    }
    ps->arr[pos]=x;
    ps->size++;
}
//查找元素(我)
void My_SLFind(SL* ps,SLDataType x) {
    assert(ps);
    int flag=0;
    for (int i = 0;i < ps->size;i++) {
        if (ps->arr[i] == x) {
            printf("找到了！在下标为%d处\n",i);
            flag=1;
        }
      }
    if (flag == 0) {
        printf("没找到！");
      }
}
//查找元素(老师版)
int SLFind(SL* ps, SLDataType x) {
         assert(ps);
         for (int i = 0;i < ps->size;i++) {
             if (ps->arr[i] == x) {
                 printf("找到了\n");
                 return i;
             }
         }
         printf("没找到");
         return -1;

}
//销毁顺序表
void SLDestroy(SL* ps) {
     assert(ps);
     if(ps->arr){
     free(ps->arr);
     }
     ps->arr=NULL;
     ps->capacity=ps->size=0;
}

test.c：

就是测试文件，自己用一些例子测试一下就行。

#include"SeqList.h"
void test() {
      SL s1;
      InitSl(&s1);
      SLPushBack(&s1,1);
      SLPrint(&s1);
      SLPushBack(&s1, 2);
      SLPrint(&s1);
      SLPushBack(&s1, 3);
      SLPrint(&s1);
      SLPushBack(&s1, 4);
      SLPrint(&s1);
      SLPushBack(&s1,5);
      SLPrint(&s1);
      SLPushFront(&s1,6);
      SLPrint(&s1);
      SLPopBack(&s1);
      SLPrint(&s1);
      SLPopFront(&s1);
      SLPrint(&s1);
      SLErase(&s1,1);
      SLPrint(&s1);
      SLInsert(&s1,1,8);
      SLPrint(&s1);
      SLInsert(&s1,3,8);
      SLPrint(&s1);
      int ToFind=SLFind(&s1,8);
      printf("%d\n",ToFind);
      My_SLFind(&s1,8);

}



int main() {
      test();
      return 0;
}

如果觉得本文好的，记得点赞，评论好评一波哦。

如有错误，恳请指正！