《【初阶数据结构】从 0 到 1 速通顺序表：C 语言实现 + 手撕算法（附完整代码）》

本文详细介绍了线性表中的顺序表的概念以及以及其的接口如：增删查找等关键操作，最后通过算法题来感受顺序表的细节

文章目录

• 一、线性表是什么？
• 二、顺序表的概念及分类
• •   1.概念
  •   2.分类
• 三、动态顺序表的实现
• •   1. 顺序表的初始化
  •   2.顺序表的扩容
  •   3. 顺序的尾插
  •    4. 顺序表的头插
  •    5. 尾删
  •    6. 头删
  •    7. 在指定位置之前插入数据
  •    8. 删除指定位置的数据
  •    9. 查找
  •    10. 销毁顺序表
• 四、完整代码
• • SeqList.h
  • SeqList.c
  • test.c
• 五、算法的暴力美学
•     1. [移除元素](https://leetcode.cn/problems/remove-element/description/)
• • • 题目解释：
    • 思路 1：创立新数组
    • 思路 2：双指针法
  • 代码实现
•            2.[合并两个有序数组](https://leetcode.cn/problems/merge-sorted-array/)
• • • 题目解释：
    • 思路 1：
    • 思路 2：
    • 代码实现`
• 总结
• • 顺序表的问题
• 个人留言

一、线性表是什么？

       线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结
构，常见的线性表：顺序表、链表、栈、队列、字符串…
       线性表在逻辑上是线性结构，也就说是连续的一条直线。但是*物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。（理解为：线性表在逻辑结构上一定是连续的，而在物理结构上不一定是连续的）
       上面是书本的定义，我觉得可以这样理解逻辑结构和线性结构，举个例子：夏天喝奶茶去排队，我们把队伍看成“1”字形，也就是线性的，这里是人为抽象理解为是从第一个人到最后一个人一一对齐，也就是在逻辑结构上一定是线性的，而物理结构上，也就是在事实情况下，排队大概率是东边一个人，西边一个人，不是“1”字形，也就不连续（不是线性的），所以在物理结构上不连续。但也有素质高的队伍，完全成“1”字形，也就是说明线性表在物理结构上可能线性也可能不是线性的，但是在逻辑结果（也就是人为想象下）一定是线性的

二、顺序表的概念及分类

  1.概念

       顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构（在逻辑结构和物理结构上均是线性的），一般情况下采用数组存储。在数组上完成数据的增删查改。这里可以参照上面线性表我的理解，逻辑结构一定是线性的，物理结构上是数组，也是连续的
       顺序表的本质就是数组

  2.分类

       1.   静态顺序表

定义:使用定长数组存储元素

//宏定义常量#define N 7//类型别名声明，方便后续代码维护typedef int SLDataTypetypedef struct SeqList{ SLDataType a[N];//定长数组 int size;//有效数据个数}SeqList;

       2. 动态顺序表
       定义:使用动态开辟的数组存储

typedef int SLdataType;typedef struct Seqlist{ SLdataType* array ;//指向动态开辟的数组 int size;//有效数据个数 int capacity;//容量空间大小}SL;

这里顺序表绝大部分情况使用的是动态顺序表，因为静态顺序表如果空间给少了不够用，给多了会造成空间浪费。动态顺序表可以根据需要的多少来进行realloc来进行扩容，调整顺序表的大小。

三、动态顺序表的实现

  1. 顺序表的初始化

//顺序表的初始化void SLInit(SL*ps){ps->arr = NULL;//顺序表初始化为空ps->size = ps->capacity = 0;//有效数据个数和空间容量均置为0}

  2.顺序表的扩容

  在进行扩容前首先我们要分析下两种情况，1：capacity和size均为空
                                                                      2.capacity和size不为空
    在扩容的时候我们要判断在顺序表中它存储的元素和它的空间容量是否相等，如果相等话，那么我们再想继续存储元素就需要扩容。
    （1）使用if语句判断capacity和size是否相等·
    （2）使用三目操作符来对判断，情况1：给capacity开辟4个容量，情况2：capacity扩大两倍
    （3）为了防止realloc增容失败，导致原有数据缺失，所以选择临时变量 temp来存放realloc
    （4）使用if语句判断如果temp为NULL则扩容失败直接退出程序即可
    （5）代码走到这里，即可证明扩容成功，并把扩容的大小赋值给capacity

小细节1：扩容这里我们选择realloc进行扩容而不使用malloc扩容原因是：realloc可以调整已分配内存块的大小，并尽可能在原地完成扩容，时间复杂度为O（1），malloc需要手动实现，时间复杂度为O（n）

小细节2：这里扩容为什么选择2倍扩容而不是其他，大家可以想一下，百度上也有相关证明哦！！！

代码如下：

void SLCheckCapacity(SL*ps){if (ps->size == ps->capacity){//capacity可能初始为0，所以要把他存放到临时的newcapacity中int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//如果realloc扩容失败，则返回null，如果直接赋值给arr，则会丢失之前存储的数据，所以用临时变量来存储SLdataType* temp = (SLdataType*)realloc(ps->arr, newcapacity * 2 * sizeof(SLdataType));//??????if (temp == NULL){perror(\"realloc faile!\");exit(1);//直接退出程序}ps->arr = temp;ps->capacity = newcapacity;}}

  3. 顺序的尾插

    在进行尾插前需要断言，防止顺序表传入空指针，如若是空指针则不能对其解引用，下图中共有五个数字，size为5，a[5]对应的是原本顺序表最后一个元素的下一个位置，所以尾插后的数据x应存放在a[5]中，最后存放完x后不能忘记把size++。

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

   4. 顺序表的头插

    这里和尾插一样，都需要断言，后面的实现方法就不解释了，原因是一样的。思路：在头插前，我们显而易见需要把原本顺序表中的所有元素往后移动，假设我们从0这个数字开始往后移动，会把后面数字1给覆盖掉，所以从前往后移动是不行的，需要从后把最后一个数字4移动到空白位置a[5],3移动到a[4]位置，然后前面的数字依次这样移动。

    上面的移动方法我们通过使用for循环来实现，原顺序表中所有元素均移动完成后，将新的数据存放到已经空出来的a[0]位置，则实现了顺序表的头插

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. 尾删

      这里除了要断言ps还要断言ps->next不能为空，因为如果链表为空不能尾删。断言完后尾删完要让size–。

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

   6. 头删

      头删如下图，删除a[0]位置的元素0，则后面的1-4均要向前移动，这里我们要使用for循环从头遍历，让a[i+1]的数据赋值给a[i]，这里要注意for循环的结束条件为size-1，最后别忘了让size–啦

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

   7. 在指定位置之前插入数据

      插入数据前，要让pos及其后面位置的数据往后移动，在这里通过从后往前遍历，把pos位置空出来，然后在pos位置插入数据，最后别忘让size++啦。

void SLInsert(SL* ps, int pos, SLdataType x){assert(ps); assert(pos >= 0 && pos <=ps->size);//插入数据要判断空间是否够SLCheckCapacity(ps);//让pos及之后的数据往后移动for (int i = ps->size;i>pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;}

   8. 删除指定位置的数据

      这里除了断言顺序表存在和存储的数据不为0以外，还要确保删除的位置大于0并且不能等于size，因为这两种情况数据均不存在，因此需要再次断言。之后使用for循环让pos及其之后数据均往前移动。

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

   9. 查找

         这个方法就很easy啦，使用for循环遍历判断存储数据是否等于x，如果找到就返回

//顺序表的查找int SLFind(SL* ps, SLdataType x){assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){//找到了return i;}}return -1;}

   10. 销毁顺序表

         之前动态申请的内存当然需要释放啦，防止内存泄漏，释放之后，还要将指针置为NULL避免出现野指针，避免后续代码误操作已释放的内存。同时将 size 和 capacity 置零，使顺序表恢复到初始空状态，确保状态一致性。

void SLDestroy(SL* ps){if (ps->arr){free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;}

四、完整代码

   以下代码非唯一，仅供参考

SeqList.h

头文件

#define _CRT_SECURE_NO_WARNINGS 1#include#include#include#include\"Contact.h\"//typedef int SLdataType;typedef peoInfo SLdataType;typedef struct Seqlist{SLdataType* arr;int size;int capacity;}SL;void SLInit(SL* ps);void SLDestroy(SL* ps);void SLPrint(SL ps);void SLPushBack(SL* ps,SLdataType x);void SLPushFront(SL* ps, SLdataType X);void SLPopBack(SL* ps);void SLPopFront(SL* ps);//指定位置之前插入数据void SLInsert(SL* ps, int pos, SLdataType x);//删除指定位置的数据void SLErase(SL* ps, int pos);//顺序表的查找int SLFind(SL* ps, SLdataType x);

SeqList.c

#include\"Seqlist.h\"//顺序表的打印//void SLPrint(SL s)//{//for (int i = 0; i < s.size; i++)//{//printf(\"%d \", s.arr[i]);//}//printf(\"\\n\");//}//顺序表的初始化void SLInit(SL*ps){ps->arr = NULL;ps->size = ps->capacity = 0;}void SLDestroy(SL* ps){if (ps->arr){free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;}void SLCheckCapacity(SL*ps){if (ps->size == ps->capacity){//capacity可能初始为0，所以要把他存放到临时的newcapacity中int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//如果realloc扩容失败，则返回null，如果直接赋值给arr，则会丢失之前存储的数据，所以用临时变量来存储SLdataType* temp = (SLdataType*)realloc(ps->arr, newcapacity * 2 * sizeof(SLdataType));//??????if (temp == NULL){perror(\"realloc faile!\");exit(1);//直接退出程序}ps->arr = temp;ps->capacity = newcapacity;}}//顺序表的尾插void SLPushBack(SL* ps, SLdataType x){ assert(ps);SLCheckCapacity(ps);ps->arr[ps->size++] = x;} 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 SLPopBack(SL* ps){assert(ps);assert(ps->size);--ps->size;}//头删void SLPopFront(SL* ps){assert(ps);assert(ps->size);for (int i = 0; i < ps->size-1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;}//在指定位置之前插入数据void SLInsert(SL* ps, int pos, SLdataType x){assert(ps); assert(pos >= 0 && pos <=ps->size);//插入数据要判断空间是否够SLCheckCapacity(ps);//让posj及之后的数据往后移动for (int i = ps->size;i>pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;}//删除指定位置的顺序void SLErase(SL* ps, int pos){assert(ps);assert(ps->size);assert(pos >= 0 && pos < ps->size);for (int i = pos;i<ps->size-1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;}//顺序表的查找int SLFind(SL* ps, SLdataType x){assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){//找到了return i;}}return -1;}

test.c

测试代码

#include\"SeqList.h\" void test(){SL s;SeqListInit(&s);SeqListPushBack(&s, 1);SeqListPushBack(&s, 2);SeqListPushBack(&s, 3);SeqListPushBack(&s, 4);SeqListPrint(&s);int find = SeqListFind(&s, 2);if (find < 0){printf(\"所查找的数据不存在！\\n\");}else{printf(\"所查找的数据存在，该数据所在位置下标为%d\\n\", find);}SeqListInsert(&s, find, 100);SeqListPrint(&s);SeqListErase(&s, find);SeqListPrint(&s);} int main(){test();return 0;}

五、算法的暴力美学

    1. 移除元素

题目解释：

    将数组中存储的数据等于val的数据移除，最后返回新数组的长度

思路 1：创立新数组

          重新定义一个新的数组，遍历原数组，把值不等于val存放在新数组中 。如下图中，我们要把值等于3的数据移除，则我们遍历nums数组，如果i不等于3，则存放到新数组tmp[]中，最后返回数组长度2

思路 2：双指针法

    顾名思义双指针法就是定义两个指针，这里我们定义src（源数据）和dst（目标数据）两个指针初始状态下都指向数组的第一个位置3

• （1）若src指向的值为val，src++，dst不动
• （2）若src指向的值不是val，nums[dst]=nums[src],src++,dst++
• (3) 当src等于数组长度的时候跳出循环，dst的值便是数组长度

代码实现

int removeElement(int* nums, int numsSize, int val) { //思路：双指针 ：创建两个变量指向数组的起始位置 //nums[src]==val;src++ //nums[src]!=val,赋值给dst，src和dst都++ int dst=0,src=0; while(src<numsSize) { if(nums[src]!=val) { nums[dst++]=nums[src]; // src++,dst++; } /*else { src++; }*/ src++; } //此时dst的值刚好就是新数组的有效长度 return dst;}

           2.合并两个有序数组

题目解释：

        给了两个数组nums1和nums2（均递增），需求是把nums2的数据全部存放到num1中（num1数组容量正好可以存放下num1和num2的所有元素） 并且顺序为升序，题目提到不能开辟新的数组

思路 1：

放到nums1数组的后面中，再使用冒泡排序算法对nums1进行升序，但是冒泡排序的时间复杂度为O（n^2）,不推荐

思路 2：

定义三个个指针l1（指向nums1的最后一个有效数据），l2（指向nums2的最后一个有效数据），l3（指向nums1的最后位置）

• 情况 1：l2先出循环，如下图

  
  从后往前比较大小：比谁大，谁大谁往后放。在图中是比较l1和l2指向的数据谁大，l2大，则把l2的数据6给l3，然后l2- -，l3- -，按照这个规律进行下去，直到l1或者l2中某一个指针出了数组（ji小于0），跳出循环，结果如下图：

• 情况2：l1先出循环，如下图

比较完的图如下：发现nums2中还有数据未放到nums1中，

*所以我们需要循环nums2中剩余的数据放到l3中，如下图

代码实现`

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { //从后往前找：比谁大，谁大谁往后放 int l1=m-1;//放在第一个数组最后一个有效元素对应的下标 int l2=n-1;//放在第二个数组最后一个有效元素对应的下标 int l3=m+n-1;//放在第一个数组下标为第一个数组加第二个数组有效元素的下标处 // 比较l1和l2对应元素的大小，谁大,l3放谁，然后l3和大的元素对应的下标-- while(l1>=0&&l2>=0)//只要有一个为假就跳出循环 { if(nums1[l1]>nums2[l2]) { nums1[l3--]=nums1[l1--]; } else { nums1[l3--]=nums2[l2--]; } }//l1已经越界，nums2中还有数据没有放到nums1中while(l2>=0){ nums1[l3--]=nums2[l2--];}}

这里不存在l1和l2都越界的情况，假设nums1中l1和nums2中l2存放的数据一样，让其中任意一个为大即可
大家可能纠结可不可以从前往后比较大小呢？答案是否定的，因为从前往后比较会把原本数据覆盖，这里就不再详细介绍，大家可以画图来判断下

总结

顺序表的问题

• 1）中间/头部的插入效率地下，时间复杂度为O（n）

• 2）realloc增容效率低下，要申请新空间，拷贝数据，释放旧空间

• 3）增容以二倍扩大造成空间浪费

  思考：有没有一种新的数据结构可以解决以上问题呢？敬请期待下节分解…

个人留言

    这是我第一次写技术性博客，如有不足之处欢迎大家私信留言指正，期待你的一键三连啦，最后感谢大家一路的陪伴！！！