顺序表（一篇带你掌握顺序表）

目录

一、顺序表是什么

1.1 概念

1.2 分类

1.3 结构

二、顺序表的基本操作

2.1 前绪准备

2.2 初始化

2.3  扩容

2.5 尾插

 2.6 打印

2.7 尾删

2.8 头插

 2.9 头删

 2.10 在pos位置插入

 2.11 删除pos位置的数据

 2.12 查找

三、完整代码

3.1 Test.c文件

3.2 SeqList.h文件

3.3 SeqList.c文件

四、与顺序表相关的例题

4.1 移除元素

4.1.1 题目描述

4.1.2 题目分析

4.2 删除有序数组中的重复项

4.2.1 题目描述

4.2.2 题目分析

4.3 合并两个有序数组

4.3.1 题目描述

4.3.2 题目分析

五、顺序表的缺陷

一、顺序表是什么

1.1 概念

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

1.2 分类

     顺序表可以分为静态顺序表和动态顺序表。

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

相对来说动态顺序表的优势大，静态顺序表，不太实用，局限性大。

1.3 结构

     顺序表需要对存储的数据进行管理，存储的数据本质上是使用数组存储，要对数据进行管理就需要知道顺序表中存储元素的个数，其次如果创建的是动态的顺序表，那么还需要记录下它的容量，对于动态顺序表，我们单用某一种类型的变量无法将他准确的描述出来，它包含顺序表有效元素个数，顺序表的容量以及顺序表开辟的空间的地址三个主要元素，无法使用某种单一的类型来表示，所以我们需要定义一个结构体类型。     

typedef struct SeqList
{SLDataType* a;   //开辟的空间的起始地址int size;     //有效数据的个数int capacity;   //空间容量
}SL;

一个简单的顺序表可以由下图来表示：

     

二、顺序表的基本操作

     在此处，我们分装成SeqList.h、SeqList.c以及Test.c这三个文件来实现顺序表的完整操作，在SeqList.h中定义顺序表需要的函数，SeqList.c中实现顺序表的操作，Test.c中实现主函数，完成一系列的操作，在本文章的第二部分，主要是对顺序表的每个操作进行讲解，整体实现在第三部分。

顺序表主要有以下操作：

void SeqInit(SL* s);    //初始化
void SeqDestory(SL* s);           //销毁
void SLPushBack(SL* s, SLDataType x);       //尾插
void SLPrint(SL* s);        //打印
void SLPopBack(SL* s);     //尾删
void SLCheckCapacity(SL* s);      //扩容
void SLPushFront(SL* s, SLDataType x);        //头插
void SLPopFront(SL* s);      //头删
void SLInsert(SL* s,int pos, SLDataType x);           //从pos位置插入
void SLErase(SL* s, int pos);        //删除pos位置的元素
int SLFind(SL* s, SLDataType x);             //找某个数在顺序表中的位置

2.1 前绪准备

     我们是创建的动态顺序表，即动态开辟空间，空间不够再进行扩容操作，为了我们写的顺序表有更广泛地使用，定义 INIT_CAPACITY 来表示容量大小，以便我们后续对容量进行改变。我们在此顺序表设置的起始开辟的容量为4（在本文章展示的顺序表存储的是int类型数据，这里指的是开辟4个int类型的空间，即16字节的空间）。

#define INIT_CAPACITY 4

     顺序表中可以存储不同类型的元素，为了使我们写的顺序表具有广泛性，在这里我们使类型重定义，用SLDataType代表某种类型。在本文章中我们存储的是int类型的数据。

typedef int SLDataType;

2.2 初始化

     对于一个顺序表，我们主要关注顺序表有效元素个数，顺序表的容量以及顺序表开辟的空间的地址三个主要元素，对他进行初始化，即对这三个要素进行初始化。

     对于顺序表的初始化函数，我们需要注意传参的时候需要传的是地址，我们在此函数中，需要改变结构体的内容，就要传结构体的指针，很多同学在这里会出现以下错误，我们通过图来解释：
 

void SeqInit(SL* ps)
{assert(ps);     //断言，ps为空时，顺序表不存在，再进行下面操作没有意义ps->a = (SLDataType*)malloc(INIT_CAPACITY * sizeof(SLDataType));     //动态开辟空间if (ps->a == NULL)         //判断开辟空间是否成功{perror("malloc fail");return;}ps->size = 0;ps->capacity = INIT_CAPACITY;
}

     上面开辟空间时，我们使用了malloc函数，对此函数不了解的可以参照下图：

2.3  扩容

     在对顺序表进行插入的时候，有可能存在将开辟的空间用完的情况即空间中存储的数据有效个数与容量相等，这个时候我们就需要进行扩容，一般是将容量扩充到当前的二倍。

     我们需要注意：

• realloc的第二个参数传的是扩容后的总字节数。
• realloc分为原地扩容和异地扩容，如果是原地扩容那么realloc调用后返回的地址与原空间的地址相同，如果是异地扩容，那么realloc将返回新的地址，所以在这里我们需要将tmp的值赋给ps->a。

void SLCheckCapacity(SL* ps)             //扩容
{assert(ps);if (ps->size == ps->capacity){SLDataType * tmp = (SLDataType*)realloc(ps->a, ps->capacity * sizeof(SLDataType)*2);if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}
}

     上述函数中在扩容的时候我们使用的是realloc函数，对他使用不熟练的同学可以看下图：

2.5 尾插

      对于顺序表的尾插，我们主要需要注意以下两个问题：

• 需要考虑是否扩容，这里直接复用上面的扩容函数

     尾插的原理：

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

 2.6 打印

     我们对顺序表进行增删查改等操作后需要打印来观察顺序表是否进行了增删查改操作。

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

2.7 尾删

     对于顺序表的尾删，我们需要知道顺序表主要是通过size来看空间中的有效数据个数，对于尾删，只需要使size--即可。

     尾删有个前提条件就是空间中存在数据，如果空间中没有数据，那么删除就会出问题，在这里我们使用assert（断言），assert后面括号中的内容为假就会直接报错，为真操作忽略。

     

尾删的代码如下：

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

     注意：对于动态开辟的空间在释放时只能整块整块的释放，不能在中间随意位置进行释放。

2.8 头插

     顺序表的底层存储是数组，且是连续的地址进行存储，如果要在头部插入一个数据，那么就要移动后面的数据。

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

 2.9 头删

     顺序表的头删与头插正好相反，他需要从前向后挪动数据，具体情况如下：
 

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

 2.10 在pos位置插入

     在pos位置插入，我们首先要对pos位置是否合法进行判断，避免出现越界等问题，其次此函数也可以在头插，尾插函数中进行复用。

void SLInsert(SL* ps, int pos, SLDataType x)         //从pos位置插入
{assert(ps);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++;
}

 2.11 删除pos位置的数据

     删除pos位置的数据，首先也要判断pos位置是否合法，其次删除pos位置，要将pos位置之后的数据依次往前挪动。

void SLErase(SL* ps, int pos)        //删除pos位置的元素
{assert(ps);assert(pos>=0&&pos<ps->size);int begin = pos;while (begin < ps->size - 1){ps->a[begin] = ps->a[begin + 1];begin++;}ps->size--;
}

 2.12 查找

     我们有时候会在顺序表中找某一个值，就用到了查找函数。

int SLFind(SL* ps, SLDataType x)             //找某个数在顺序表中的位置
{assert(ps);int search = 0;while (search < ps->size){if (x == ps->a[search]){return search;}}return -1;
}

     在此函数中，如果找到，返回下标，没有找到，就返回-1.

三、完整代码

     注意由于顺序表的操作多，在每写完一个操作后，我们最好测试一下，所以在Test.c中有多个测试函数。

3.1 Test.c文件

#include "SeqList.h"void TestSeqList1()
{SL s;SeqInit(&s);    //初始化SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPushBack(&s, 5);SLPrint(&s);SeqDestory(&s);           //销毁}void TestSeqList2()
{SL s;SeqInit(&s);    //初始化SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPushBack(&s, 5);SLPrint(&s);SLPopBack(&s);SLPrint(&s);SLPopBack(&s); SLPrint(&s);SLPopBack(&s);SLPopBack(&s);SLPopBack(&s);SLPrint(&s);SeqDestory(&s);           //销毁}void TestSeqList3()
{SL s;SeqInit(&s);    //初始化SLPushFront(&s, 1);SLPushFront(&s, 2);SLPushFront(&s, 3);SLPushFront(&s, 4);SLPushFront(&s, 5);SLInsert(&s, 2, 10);SLPrint(&s);SLErase(&s,2);SLPrint(&s);SLPopFront(&s);SLPrint(&s);SLPopFront(&s);SLPrint(&s);SLPopFront(&s);SLPopFront(&s);SLPopFront(&s);SLPrint(&s);SeqDestory(&s);           //销毁}int main() 
{TestSeqList3();return 0;}

3.2 SeqList.h文件

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1#include <stdlib.h>
#include<stdio.h>
#include<assert.h>typedef int SLDataType;
#define N 10
#define INIT_CAPACITY 4静态顺序表
//typedef struct SeqList
//{
//	SLDataType a[N];
//	int size;
//};//动态顺序表
typedef struct SeqList
{SLDataType* a;   //开辟的空间的起始地址int size;     //有效数据的个数int capacity;   //空间容量
}SL;void SeqInit(SL* s);    //初始化
void SeqDestory(SL* s);           //销毁
void SLPushBack(SL* s, SLDataType x);       //尾插
void SLPrint(SL* s);        //打印
void SLPopBack(SL* s);     //尾删
void SLCheckCapacity(SL* s);      //扩容
void SLPushFront(SL* s, SLDataType x);        //头插
void SLPopFront(SL* s);      //头删
void SLInsert(SL* s,int pos, SLDataType x);           //从pos位置插入
void SLErase(SL* s, int pos);        //删除pos位置的元素
int SLFind(SL* s, SLDataType x);             //找某个数在顺序表中的位置

3.3 SeqList.c文件

#include "SeqList.h"
void SeqInit(SL * ps)
{assert(ps);ps->a = (SLDataType*)malloc(INIT_CAPACITY * sizeof(SLDataType));if (ps->a == NULL){perror("malloc fail");return;}ps->size = 0;ps->capacity = INIT_CAPACITY;
}void SeqDestory(SL* ps)          //销毁
{free(ps->a);ps->a = NULL;ps->size = 0;ps->capacity = 0;
}void SLPushBack(SL* ps, SLDataType x)       //尾插
{assert(ps);SLCheckCapacity(ps);ps->a[ps->size] = x;ps->size++;
}void SLCheckCapacity(SL* ps)             //扩容
{assert(ps);if (ps->size == ps->capacity){SLDataType * tmp = (SLDataType*)realloc(ps->a, ps->capacity * sizeof(SLDataType)*2);if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}
}void SLPrint(SL* ps)        //打印
{assert(ps);int i = 0;for (i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");
}void SLPopBack(SL* ps)    //尾删
{assert(ps);assert(ps->size > 0);ps->size--;}void SLPushFront(SL* ps, SLDataType x)        //头插
{assert(ps);SLCheckCapacity(ps);int end = ps->size-1;while (end >= 0){ps->a[end+1] = ps->a[end];end--;}ps->a[0] = x;ps->size++;
}void SLPopFront(SL* ps)      //头删
{assert(ps);assert(ps->size > 0);int begin = 0;while (begin < ps->size - 1){ps->a[begin] = ps->a[begin + 1];begin++;}ps->size--;
}void SLInsert(SL* ps, int pos, SLDataType x)         //从pos位置插入
{assert(ps);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++;
}void SLErase(SL* ps, int pos)        //删除pos位置的元素
{assert(ps);assert(pos>=0&&pos<ps->size);int begin = pos;while (begin < ps->size - 1){ps->a[begin] = ps->a[begin + 1];begin++;}ps->size--;
}int SLFind(SL* ps, SLDataType x)             //找某个数在顺序表中的位置
{assert(ps);int search = 0;while (search < ps->size){if (x == ps->a[search]){return search;}}return -1;
}

四、与顺序表相关的例题

4.1 移除元素

4.1.1 题目描述

题目链接：https://leetcode.cn/problems/remove-element/

     给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

     不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

     元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

4.1.2 题目分析

思路一：

     以空间换时间，本方法主要是在创建一个数组arr，用一个指针遍历原数组，将原数组中不等于val的值依次存放在arr数组中，然后将arr数组中的内容拷贝到原数组中。

     注意此方法的时间复杂度是：O(n)，我们要对原数组遍历一遍，需要有一个循环，基本语句的执行次数是n次，此方法的空间复杂度是：O(n)，由于在力扣环境中不支持C99中的变长数组，所以我们这里创建的数组个数按照题目中nums数组的最大个数来看，但是它的量级依然属于n。

int removeElement(int* nums, int numsSize, int val) 
{int arr[100]={0};int src = 0;int dst = 0;while(src < numsSize){if (nums[src] == val){src++;}else{arr[dst++] = nums[src++];}}memcpy(nums,arr,dst*sizeof(int));return dst;
}

思路二：

     双指针，定义两个指针，src和dst，都从下标为0开始，如果src处的值不等于val，把它赋值到dst处，然后dst和src都加1，如果src处的值等于val，只对src加1，依次往后遍历，直到src=numsSize结束。

     此方法的时间复杂度为：O(n)，其中 n 为序列的长度。我们只需要遍历该序列至多两次。空间复杂度是：O(1)，我们只需要常数的空间保存若干变量。

int removeElement(int* nums, int numsSize, int val) 
{int src = 0;int dst = 0;while (src < numsSize){if (nums[src] == val){src++;}else{nums[dst] = nums[src];dst++;src++;}}return dst;
}

4.2 删除有序数组中的重复项

4.2.1 题目描述

题目链接：26. 删除有序数组中的重复项 - 力扣（LeetCode）

     给你一个升序排列的数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次 ，返回删除后数组的新长度。元素的 相对顺序应该保持一致 。  

4.2.2 题目分析

思路：

     双指针，如果src和dst下标对应的值相同那么dst加1，如果src和dst下标对应的值不相同src加1，然后那dst下标对应的值赋给src下标对应的值。

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

4.3 合并两个有序数组

4.3.1 题目描述

题目链接：88. 合并两个有序数组 - 力扣（LeetCode）

     给你两个按非递减顺序排列的整数数组nums1和nums2，另有两个整数m和n ，分别表示 nums1和nums2中的元素数目。

     请你合并nums2到nums1中，使合并后的数组同样按非递减顺序排列。

4.3.2 题目分析

思路：

     我们要将两个数组合并，如果都从前面即下标为0处开始比较，会涉及较多的移动数据问题，所以我们倒着比，用三个指针，其中dst是合并好数组的最后一个下标，end2是nums2数组的最后一个下标，end1是nums1数组的最后一个下标，如果nums[end2]大于nums[end1]则移动到nums1[dst]位置上。

     

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

五、顺序表的缺陷

顺序表有许多的问题：

1. 中间/头部的插入删除，时间复杂度为：O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗。
3. 增容一般呈2倍的增长，势必会有一定的空间浪费。