1.线性表

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

2.顺序表

2.1概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。本质上是数组，在此基础上，还要求数据是从头开始连续存储的，不能跳跃间隔。

首先打开VS，在源文件选项建立test.c(用来测试)和SeqList.c(用来写头文件里面的定义)的文件，在头文件选项里建立SeqList.h.

我们现在SeqList.h里面写好相关的信息，

#pragma once//避免二义性
#define N 100//宏定义便于修改N
typedef int SLDataType;//想存什么类型就把int改成什么类型

顺序表一般可以分为：

1. 静态顺序表：使用定长数组存储元素
2. 动态顺序表：使用动态开辟的数组存储。

2.2 静态顺序表

我们在SeqList.h这里使用结构体来表示静态顺序表:

struct SeqList
{int a[N];int size;//表示数组中存储了多少个数据
};

为了方便表示顺序表，我们使用typedef来重命名，然后在上面我们我们又把int修改了，这是为了提高顺序表代码的可读性。如下：

typedef struct SeqList
{SLDataType a[N];int size;//表示数组中存储了多少个数据
}SL;

静态顺序表的特点：如果满了不让插入。缺点：一开始很难确定给多少空间，N给小了不够用，N给大了浪费。

给出完整的SeqList.h的静态顺序表代码：

#pragma once//避免二义性
#define N 100//宏定义便于修改N
typedef int SLDataType;//想存什么类型就把int改成什么类型typedef struct SeqList
{SLDataType a[N];int size;//表示数组中存储了多少个数据
}SL;

2.3 动态顺序表

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

#pragma once//避免二义性
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define N 100//宏定义便于修改N
typedef int SLDataType;//想存什么类型就把int改成什么类型typedef struct SeqList
{SLDataType* a;int size;//表示数组中存储了多少个数据（有效数据个数）int capacity;//数组实际能存数据空间容量大小（容量大小）
}SL;

2.4 接口实现

下面给出顺序表一些常见的接口函数，命名风格都跟着STL走，方便后期学习C++。接口函数都写在SeqList.h里面

void SeqListInit(SL* ps);//初始化
void SeqListPushBack(SL* ps, SLDataType x);//尾插
void SeqListPopBack(SL* ps);//尾删
void SeqListPushFront(SL* ps, SLDataType x);//头插
void SeqListPopFront(SL* ps);//头删
void SeqListPrint(SL* ps);//打印
void SeqListDestory(SL* ps);//销毁
void CheckCapacity(SL* ps);// 检查空间，如果满了，进行增容
int SeqListFind(SL* ps, SLDataType x);//找到了返回下标
void SeqListInsert(SL* ps, int pos, SLDataType x);//在pos位置插入x

2.4.1 初始化

我们先来完成顺序表的初始化，在SeqList.c里面实现，由于形参是实参的临时拷贝，这里只能采用传址操作，所以用到了指针。

#include "SeqList.h"
void SeqListInit(SL* ps)
{ps->a = NULL;ps->size = ps->capacity = 0;
}

为了便于测试，我们可以现在test.c里面写函数进行测试：

#include "SeqList.h"
void TestSeqList1()
{SL sl;SeqListInit(&sl);
}
int main()
{TestSeqList1();return 0;
}

2.4.2 尾插

由于在头文件里面声明过了，我们只需在SeqList.c完成尾插的代码实现即可。

void SeqListPushBack(SL* ps, SLDataType x)
{ps->a[ps->size] = x;ps->size++;
}

这样写是有问题的，这种只适合空间足够，直接插入。其实还存在空间不够的情况：

void SeqListPushBack(SL* ps, SLDataType x)
{//如果没有空间或空间不足if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//最合适的处理SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));if (tmp == NULL){printf("realloc fail\n");exit(-1);}ps->a = tmp;ps->capacity = newcapacity;}ps->a[ps->size] = x;ps->size++;
}

关于realloc函数，我们在C语言阶段已经学过了，这里才说一下它的用法：

为了方便我们观察，我们还要在SeqList.c完成打印的代码实现：

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

接着我们在test.c里面测试：

#include "SeqList.h"void TestSeqList1()
{SL sl;SeqListInit(&sl);
}
void TestSeqList2()
{SL sl;SeqListInit(&sl);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPrint(&sl);
}int main()
{//TestSeqList1();TestSeqList2();return 0;
}

运行结果如下：

这个时候我们打开调试，

接着再测试一组：

#include "SeqList.h"
void TestSeqList1()
{SL sl;SeqListInit(&sl);
}
void TestSeqList2()
{SL sl;SeqListInit(&sl);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPushBack(&sl, 5);SeqListPrint(&sl);
}
int main()
{//TestSeqList1();TestSeqList2();return 0;
}

调试的结果符合我们的预期。

2.4.3 尾删

在SeqList.c完成代码实现：

void SeqListPopBack(SL* ps)
{ps->size--;
}

这种写法存在一定的风险，那就是size大小为负数的情况。这里我们给出暴力的解法——assert：

void SeqListPopBack(SL* ps)
{assert(ps->size > 0);ps->size--;
}

我们在test.c里面测试一下：

#include "SeqList.h"
void TestSeqList1()
{SL sl;SeqListInit(&sl);
}
void TestSeqList2()
{SL sl;SeqListInit(&sl);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPushBack(&sl, 5);SeqListPrint(&sl);SeqListPopBack(&sl);SeqListPrint(&sl);
}
int main()
{//TestSeqList1();TestSeqList2();return 0;
}

运行结果如下：

2.4.4 销毁

在SeqList.c完成代码实现：

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

我们在test.c里面测试一下：

#include "SeqList.h"
void TestSeqList1()
{SL sl;SeqListInit(&sl);
}
void TestSeqList2()
{SL sl;SeqListInit(&sl);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPushBack(&sl, 5);SeqListPrint(&sl);SeqListPopBack(&sl);SeqListPrint(&sl);SeqListDestory(&sl);SeqListPrint(&sl);
}
int main()
{//TestSeqList1();TestSeqList2();return 0;
}

运行结果：

2.4.5头插

在SeqList.c完成代码实现：

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

这种写法还是有问题的，因为头插要向后挪动，如果后面没有空间或者空间不够，该怎么办？我们应该提前检查一下空间是否足够大：

void CheckCapacity(SL* ps)
{//如果没有空间或空间不足if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//最合适的处理SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));if (tmp == NULL){printf("realloc fail\n");exit(-1);}ps->a = tmp;ps->capacity = newcapacity;}
}

整个头插代码如下：

void CheckCapacity(SL* ps)
{//如果没有空间或空间不足if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//最合适的处理SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));if (tmp == NULL){printf("realloc fail\n");exit(-1);}ps->a = tmp;ps->capacity = newcapacity;}
}
void SeqListPushFront(SL* ps, SLDataType x)
{CheckCapacity(ps);//挪动数据int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];end--;}ps->a[0] = x;ps->size++;
}

我们在test.c里面测试一下：

#include "SeqList.h"
void TestSeqList1()
{SL sl;SeqListInit(&sl);
}
void TestSeqList2()
{SL sl;SeqListInit(&sl);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPushBack(&sl, 5);SeqListPrint(&sl);SeqListPopBack(&sl);SeqListPrint(&sl);SeqListDestory(&sl);SeqListPrint(&sl);
}
void TestSeqList3()
{SL sl;SeqListInit(&sl);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPushBack(&sl, 5);SeqListPrint(&sl);SeqListPushFront(&sl, 6);SeqListPrint(&sl);
}
int main()
{//TestSeqList1();//TestSeqList2();TestSeqList3();return 0;
}

运行结果：

2.4.6 头删

在SeqList.c完成代码实现：类似于尾删，要确保size大小不为负数，这里还选用assert。

void SeqListPopFront(SL* ps)
{assert(ps->size > 0);//挪动数据int begin = 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}

我们在test.c里面测试一下：

#include "SeqList.h"
void TestSeqList1()
{SL sl;SeqListInit(&sl);
}
void TestSeqList2()
{SL sl;SeqListInit(&sl);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPushBack(&sl, 5);SeqListPrint(&sl);SeqListPopBack(&sl);SeqListPrint(&sl);SeqListDestory(&sl);SeqListPrint(&sl);
}
void TestSeqList3()
{SL sl;SeqListInit(&sl);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPushBack(&sl, 5);SeqListPrint(&sl);SeqListPushFront(&sl, 6);SeqListPrint(&sl);SeqListPopFront(&sl);SeqListPrint(&sl);
}
int main()
{//TestSeqList1();//TestSeqList2();TestSeqList3();return 0;
}

运行结果：

2.4.7 找到后并返回下标

在SeqList.c完成代码实现：

int SeqListFind(Sl* ps, SLDataType x)
{for (int i = 0; i < ps->size; i++){if (ps->a[i] == x){return i;}}return -1;
}

2.4.8 在pos位置插入x

在SeqList.c完成代码实现，在插入前应当检查空间是否充足：

void SeqListInsert(SL* ps, int pos, SLDataType x)
{assert(pos >= 0 && pos <= ps->size);CheckCapacity(ps);int end = ps->size - 1;while (end >= pos){ps->a[end + 1] = ps->a[end];end--;}ps->a[pos] = x;ps->size++;
}

我们在test.c里面测试一下：

#include "SeqList.h"
void TestSeqList1()
{SL sl;SeqListInit(&sl);
}
void TestSeqList2()
{SL sl;SeqListInit(&sl);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPushBack(&sl, 5);SeqListPrint(&sl);SeqListPopBack(&sl);SeqListPrint(&sl);SeqListDestory(&sl);SeqListPrint(&sl);
}
void TestSeqList3()
{SL sl;SeqListInit(&sl);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPushBack(&sl, 5);SeqListPrint(&sl);SeqListPushFront(&sl, 6);SeqListPrint(&sl);SeqListPopFront(&sl);SeqListPrint(&sl);
}
void TestSeqList4()
{SL sl;SeqListInit(&sl);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPushBack(&sl, 5);SeqListPrint(&sl);SeqListInsert(&sl, 3,99);SeqListPrint(&sl);
}
int main()
{//TestSeqList1();//TestSeqList2();//TestSeqList3();TestSeqList4();return 0;
}

运行结果：

2.4.9 删除pos位置的值

在SeqList.c完成代码实现：

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

我们在test.c里面测试一下：

#include "SeqList.h"
void TestSeqList1()
{SL sl;SeqListInit(&sl);
}
void TestSeqList2()
{SL sl;SeqListInit(&sl);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPushBack(&sl, 5);SeqListPrint(&sl);SeqListPopBack(&sl);SeqListPrint(&sl);SeqListDestory(&sl);SeqListPrint(&sl);
}
void TestSeqList3()
{SL sl;SeqListInit(&sl);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPushBack(&sl, 5);SeqListPrint(&sl);SeqListPushFront(&sl, 6);SeqListPrint(&sl);SeqListPopFront(&sl);SeqListPrint(&sl);
}
void TestSeqList4()
{SL sl;SeqListInit(&sl);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPushBack(&sl, 5);SeqListPrint(&sl);SeqListInsert(&sl, 3,99);SeqListPrint(&sl);SeqListErase(&sl, 3);SeqListPrint(&sl);
}
int main()
{//TestSeqList1();//TestSeqList2();//TestSeqList3();TestSeqList4();return 0;
}

运行结果：

3.完整代码展示

SeqList.h：

#pragma once//避免二义性
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define N 100//宏定义便于修改N
typedef int SLDataType;//想存什么类型就把int改成什么类型typedef struct SeqList
{SLDataType* a;int size;//表示数组中存储了多少个数据（有效数据个数）int capacity;//数组实际能存数据空间容量大小（容量大小）
}SL;void SeqListInit(SL* ps);//初始化
void SeqListPushBack(SL* ps, SLDataType x);//尾插
void SeqListPopBack(SL* ps);//尾删
void SeqListPushFront(SL* ps, SLDataType x);//头插
void SeqListPopFront(SL* ps);//头删
void SeqListPrint(SL* ps);//打印
void SeqListDestory(SL* ps);//销毁
void CheckCapacity(SL* ps);// 检查空间，如果满了，进行增容
int SeqListFind(SL* ps, SLDataType x);//找到了返回下标
void SeqListInsert(SL* ps, int pos, SLDataType x);//在pos位置插入x
void SeqListErase(SL* ps, int pos);//删除pos位置的值

SeqList.c

#include "SeqList.h"
void SeqListInit(SL* ps)
{ps->a = NULL;ps->size = ps->capacity = 0;
}
void SeqListPushBack(SL* ps, SLDataType x)
{//如果没有空间或空间不足if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//最合适的处理SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));if (tmp == NULL){printf("realloc fail\n");exit(-1);}ps->a = tmp;ps->capacity = newcapacity;}ps->a[ps->size] = x;ps->size++;
}
void SeqListPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");
}void SeqListPopBack(SL* ps)
{assert(ps->size > 0);ps->size--;
}void SeqListDestory(SL* ps)
{free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;
}void CheckCapacity(SL* ps)
{//如果没有空间或空间不足if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//最合适的处理SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));if (tmp == NULL){printf("realloc fail\n");exit(-1);}ps->a = tmp;ps->capacity = newcapacity;}
}void SeqListPushFront(SL* ps, SLDataType x)
{CheckCapacity(ps);//挪动数据int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];end--;}ps->a[0] = x;ps->size++;
}void SeqListPopFront(SL* ps)
{assert(ps->size > 0);//挪动数据int begin = 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}int SeqListFind(SL* ps, SLDataType x)
{for (int i = 0; i < ps->size; i++){if (ps->a[i] == x){return i;}}return -1;
}void SeqListInsert(SL* ps, int pos, SLDataType x)
{assert(pos >= 0 && pos <= ps->size);CheckCapacity(ps);int end = ps->size - 1;while (end >= pos){ps->a[end + 1] = ps->a[end];end--;}ps->a[pos] = x;ps->size++;
}void SeqListErase(SL* ps, int pos)
{assert(pos >= 0 && pos < ps->size);int begin = pos + 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}

test.c

#include "SeqList.h"
void TestSeqList1()
{SL sl;SeqListInit(&sl);
}
void TestSeqList2()
{SL sl;SeqListInit(&sl);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPushBack(&sl, 5);SeqListPrint(&sl);SeqListPopBack(&sl);SeqListPrint(&sl);SeqListDestory(&sl);SeqListPrint(&sl);
}
void TestSeqList3()
{SL sl;SeqListInit(&sl);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPushBack(&sl, 5);SeqListPrint(&sl);SeqListPushFront(&sl, 6);SeqListPrint(&sl);SeqListPopFront(&sl);SeqListPrint(&sl);
}void TestSeqList4()
{SL sl;SeqListInit(&sl);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPushBack(&sl, 5);SeqListPrint(&sl);SeqListInsert(&sl, 3,99);SeqListPrint(&sl);SeqListErase(&sl, 3);SeqListPrint(&sl);
}int main()
{//TestSeqList1();//TestSeqList2();//TestSeqList3();TestSeqList4();return 0;
}

4.顺序表相关的习题

【题目1】： 删除排序数组中的重复项

链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

int removeDuplicates(int* nums, int numsSize){if(numsSize==0){return 0;}int i=0,j=1,dst=0;while(j<numsSize){if(nums[i]==nums[j]){++j;}else{nums[dst]=nums[i];++dst;i=j;++j;}}nums[dst]=nums[i];++dst;return dst;
}

【题目2】：合并两个有序数组

链接：https://leetcode.cn/problems/merge-sorted-array/

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){int end1=m-1,end2=n-1;int end=m+n-1;while(end1>=0&&end2>=0){if(nums1[end1]>nums2[end2]){nums1[end--]=nums1[end1--];}else{nums1[end--]=nums2[end2--];}}while(end2>=0){nums1[end--]=nums2[end2--];}
}

5.顺序表的问题及思考

问题：
1. 中间/头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们
再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
思考：如何解决以上问题呢？下篇文章给出了链表的结构。