好久不见啊~大家，今天为大家带来的主题是：顺序表的实现。
目录
前言
一、线性表的定义
二、线性表的顺序结构
1 顺序表的定义
2 顺序表的基本操作
2.1 初始化函数
2.2 顺序表的销毁
2.3 顺序表的扩容
2.4 顺序表的尾插
2.5 顺序表的尾删
2.6 顺序表的头插
2.7 顺序表的头删
2.8 顺序表的查找
2.9 顺序表的修改
2.10 顺序表的插入
2.11 顺序表的删除
2.12 顺序表的打印
三、总代码的实现
四、相关面试题
1 移除元素
2 删除有序数组中的重复项
3 合并两个有序数组
4 旋转数组
五、顺序表的缺陷
前言
我们知道，线性表、栈、队列、串和数组都属于线性结构。线性结构的基本特点是除首元素没有直接前驱，尾元素没有直接后继之外，其它每个数据元素都有一个前驱和后继。
一、线性表的定义
线性表的数据元素虽然不同，但同一线性表中的元素必定具有相同的属性，即数千同一数据对象，相邻数据元素之间存在序偶关系。顾名思义，线性表在逻辑上是线性结构，也就是说是连续的一条直线。但在物理结构上并不一定是连续的，线性表在物理上存储时，一般以数组和链式结构的形式存储。把线性表中元素的个数n（n>=0）定义为线性表的长度，当n=0时称为空表。
那么我们来了解一下非空的线性表或线性结构的特点：
- 存在唯一的一个被称为”第一个“的数据元素；
- 存在唯一的一个被称为”最后一个“的数据结构；
- 除第一个数据元素之外，结构中的每个数据元素仅有一个前驱；
- 除最后一个数据元素之外，结构中的每个数据元素仅有一个后继。
二、线性表的顺序结构
1 顺序表的定义
线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，这种表示也称作线性表的顺序存储结构或顺序映像。把这种存储结构的线性表称为顺序表（Sequential List）。顺序表可以分为静态顺序表（使用定长数组存储）和动态顺序表（使用动态开辟的数组存储）。一般情况下采用数组存储，在数组上完成数据的增删查改。其特点是：逻辑上相邻的数据元素，其物理次序也是相邻的。简而言之，顺序表的物理结构和逻辑结构是一致的。
附：当确定了存储线性表的起始位置时，线性表中任一数据元素都可以随机存取，因此线性表的顺序存储结构是一种随机存取的存储结构。
下面我们来用代码实现：
静态顺序表：
//静态的顺序表，并不实用
#define N 100
struct SeqList
{
int a[N];
int size;
};动态顺序表：
struct SeqList
{
int* n;
int size; //表示n中有多少个有效数据
int capacity; //表示n的空间大小
}；画图理解动态顺序表：
此时的顺序表存在一些问题，它只能存int类型的变量，如果想要修改会比较麻烦，所以我们优化一下代码：
typedef int SeqDataType;
//若要修改只需修改此处
typedef struct SeqList
{
SeqDataType* n;
int size;
int capacity;
}SeqList,SEQ;2 顺序表的基本操作
2.1 初始化函数
- 功能：对结构体内成员进行初始化操作，即构造一个空的顺序表。
代码实现：
//初始化
void InitSeqList(SeqList* p)
{
assert(p); //断言，防止传入空指针
p->a = (SLDateType* )malloc(sizeof(SLDateType) * 4);
if (p->a == NULL) //这里最开始开辟四个存储数据类型的大小
{
perror("malloc fail");
exit(-1);
}
p->size = 0; //存储的有效数据个数为0
p->capacity = 4; //空间置成4
}2.2 顺序表的销毁
- 功能：对开辟的动态空间进行销毁，将空间释放。
代码实现：
//销毁
void SeqListDestory(SeqList *p)
{
free(p->a); //释放开辟的动态空间
p->a = NULL; //置空
p->capacity = p->size = 0;
}2.3 顺序表的扩容
- 前提：检查是否需要扩容
代码实现：
//扩容
void SeqCheckCapacity(SeqList* p)
{
//如果满了，便需要增容
if (p->size == p->capacity)
{
//int newcapacity = p->capacity * 2;
//这样会存在问题，当一开始插入数据时，capacity为0，乘2后还是为0
int newcapacity = p->capacity == 0 ? 4 : pq->capacity * 2;
//如果capacity等于0了,则开辟4个空间
SeqDataType* newA = realloc(p->a, sizeof(SeqDataType*) * newcapacity);
if (newA == NULL)
{
printf("realloc fail\n");
exit(-1);
}
p->a = newA;
p->capacity = newcapacity;
}
}2.4 顺序表的尾插
- 功能：在顺序表的最后插入一个数据
代码实现：
//尾插
void SeqListPushBack(SeqList* p, SeqDataType x)
{
assert(p);
SeqCheckCapacity(p);//检查空间是否已满，如果满了，便需要增容
p->a[p->size] = x; //直接插入到数组的最后
p->size++; //有效数据个数++
}2.5 顺序表的尾删
- 功能：删除顺序表的最后一个元素
代码实现：
//尾删
void SeqListPopBack(SeqList* p)
{
assert(p);
assert(p->size > 0); //当数组中有效数据个数为0时，不能再删除
p->size--; //数据个数--
}2.6 顺序表的头插
- 功能：在顺序表的最前面插入一个数据
代码实现：
//头插
void SeqListPushFront(SeqList* p, SeqDataType x)
{
assert(p);
SeqCheckCapacity(p);//检查是否已满，如果满了，便需要增容
//头插操作
int end = p->size - 1;
while (end >= 0) //当end=-1时终止
{
p->a[end] = p->a[end - 1]; //前面的元素依次向后移动
end--;
}
p->a[0] = x;
p->size++;
}附图解：
分析：头插一个数据，首先需要将全部数据依次往后挪一个位置，时间复杂度：O(N) 。由于是在原数组上进行挪动的，故空间复杂度：O(1) 。
2.7 顺序表的头删
- 功能：删除顺序表中第一个元素
代码实现：
//头删
void SeqListPopFront(SeqList* p)
{
assert(p);
assert(p->size > 0);
int begin = 0;
while (begin<p->size - 1) //从下标1开始依次前移一个
{
p->a[begin] = p->a[begin + 1];
begin++;
}
p->size--;
}附图解：
分析：头删一个数据，首先需要将全部数据一次往前挪一个位置，将第一个元素覆盖掉，时间复杂度：O(N) 。由于是在原数组上进行挪动的，故空间复杂度：O(1) 。
2.8 顺序表的查找
- 功能：查找顺序表中某个元素，返回下标
代码实现：
//查找
int SeqListFind(SeqList* p, SeqDataType x)
{
assert(p);
int i = 0;
for (i = 0; i<p->size; i++)
{
if (p->a[i] == x)//若查找成功，返回下标
return i;
}
return -1;
}性能分析：将数组中的数据遍历一遍；时间复杂度：O(N)，空间复杂度：O(1) 。
2.9 顺序表的修改
- 功能：修改数组中某个元素
代码实现：
//修改
void SeqListModify(SeqList* p, int pos, SeqDataType x)
{
assert(p);
assert(pos >= 0 && pos < p->size);
p->a[pos] = x; //通过下标访问进行修改
}2.10 顺序表的插入
- 功能：在某个位置插入一个数据
代码实现：
//中间位置插入
void SeqListInsert(SeqList* p, int pos, SeqDataType x)
{
assert(p);
assert(pos >= 0 && pos <= pq->size);
//当pos = 0时 => 头插
//当pos = size时 => 尾插
//如果已满，需要增容
SeqCheckCapacity(p);
//把pos后面的数全部前移
int end = p->size - 1;
while (end >= pos)
{
p->a[end + 1] = p->a[end];
end--;
}
//pos处放入x
p->a[pos] = x;
p->size++;
}附图解：
分析：中间插入一个数据和头插差不多，首先需要将该位置后面的全部数据依次往后挪一个位置，将该位置空出来，再将该数据插入，时间复杂度：O(N) 。由于是在原数组上进行挪动的，故空间复杂度：O(1) 。
2.11 顺序表的删除
- 功能：删除数组中任意位置的元素
代码实现：
//中间位置删除
void SeqListErase(SeqList* p, int pos)
{
assert(p);
assert(pos >= 0 && pos < p->size);
//当 pos = size - 1 => 尾删
//当 pos = 0 => 头删
int begin = pos;
while (begin < p->size - 1)
{
p->a[begin] = p->a[begin + 1];
begin++;
}
p->size--;
}附图解：
分析：删除一个数据与头删差不多，首先需要待删数据位置后面全部数据依次往前挪一个位置，将待删元素覆盖掉，时间复杂度：O(N) 。由于是在原数组上进行挪动的，故空间复杂度：O(1) 。
2.12 顺序表的打印
代码实现：
//打印
void SeqListPrint(SeqList* p)
{
assert(p);
for (int i = 0; i < p->size; ++i)
{
printf("%d", p->a[i]);//遍历依次打印
}
printf("\n"); //打印后换行
}三、总代码的实现
静态顺序表只适用于确定知道需要存储具体数据元素的场景。它的定长数组是一个不确定的值，若是将N定大了，空间开辟多了便会浪费，若是开辟少了便不够用。因此我们在现实中基本都是使用动态顺序表，根据所需动态进行分配空间大小。
Seqlist.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
静态的顺序表，并不实用
//#define N 100
//struct SeqList
//{
// int a[N];
// int size;
//};
//顺序表的动态存储
typedef int SeqDataType; //如果要修改则只需要修改这一处
typedef struct SeqList
{
SeqDataType* a;
int size; //表示a中有多少个有效数据
int capacity; //表示a的空间到底有多大
}SeqList, SEQ;
//增删查改
//初始化
void SeqListInit(SeqList *p);
//销毁
void SeqListDestory(SeqList *p);
//扩容
void SeqCheckCapacity(SeqList* p);
//尾插
void SeqListPushBack(SeqList* p, SeqDataType x);
//尾删
void SeqListPopBack(SeqList* p);
//头插
void SeqListPushFront(SeqList* p, SeqDataType x);
//头删
void SeqListPopFront(SeqList* p);
//查找
int SeqListFind(SeqList* p, SeqDataType x);
//修改
void SeqListModify(SeqList* p, int pos, SeqDataType x);
//中间位置插入
void SeqListInsert(SeqList* p, int pos, SeqDataType x);
//中间位置删除
void SeqListErase(SeqList* p, int pos);
//打印
void SeqListPrint(SeqList* p);
SeqList.c
#include"SeqList.h"
//初始化
void InitSeqList(SeqList* p)
{
assert(p); //断言，防止传入空指针
p->a = (SLDateType* )malloc(sizeof(SLDateType) * 4);
if (p->a == NULL) //这里最开始开辟四个存储数据类型的大小
{
perror("malloc fail");
exit(-1);
}
p->size = 0; //存储的有效数据个数为0
p->capacity = 4; //空间置成4
}
//销毁
void SeqListDestory(SeqList *p)
{
free(p->a); //释放开辟的动态空间
p->a = NULL; //置空
p->capacity = p->size = 0;
}
//扩容
void SeqCheckCapacity(SeqList* p)
{
//如果满了，便需要增容
if (p->size == p->capacity)
{
//int newcapacity = p->capacity * 2;
//这样会存在问题，当一开始插入数据时，capacity为0，乘2后还是为0
int newcapacity = p->capacity == 0 ? 4 : p->capacity * 2;
//如果capacity等于0了,则开辟4个空间
SeqDataType* newA = realloc(p->a, sizeof(SeqDataType*) * newcapacity);
if (newA == NULL)
{
printf("realloc fail\n");
exit(-1);
}
p->a = newA;
p->capacity = newcapacity;
}
}
//尾插
void SeqListPushBack(SeqList* p, SeqDataType x)
{
assert(p);
SeqCheckCapacity(p);//检查空间是否已满，如果满了，便需要增容
p->a[p->size] = x; //直接插入到数组的最后
p->size++; //有效数据个数++
}
//尾删
void SeqListPopBack(SeqList* p)
{
assert(p);
assert(p->size > 0); //当数组中有效数据个数为0时，不能再删除
p->size--; //数据个数--
}
//头插
void SeqListPushFront(SeqList* p, SeqDataType x)
{
assert(p);
SeqCheckCapacity(p);//检查是否已满，如果满了，便需要增容
//头插操作
int end = p->size - 1;
while (end >= 0) //当end=-1时终止
{
p->a[end] = p->a[end - 1]; //前面的元素依次向后移动
end--;
}
p->a[0] = x;
p->size++;
}
//头删
void SeqListPopFront(SeqList* p)
{
assert(p);
assert(p->size > 0);
int begin = 0;
while (begin<p->size - 1) //从下标1开始依次前移一个
{
p->a[begin] = p->a[begin + 1];
begin++;
}
p->size--;
}
//查找
int SeqListFind(SeqList* p, SeqDataType x)
{
assert(p);
int i = 0;
for (i = 0; i<p->size; i++)
{
if (p->a[i] == x)//若查找成功，返回下标
return i;
}
return -1;
}
//修改
void SeqListModify(SeqList* p, int pos, SeqDataType x)
{
assert(p);
assert(pos >= 0 && pos < p->size);
p->a[pos] = x; //通过下标访问进行修改
}
//中间位置插入
void SeqListInsert(SeqList* p, int pos, SeqDataType x)
{
assert(p);
assert(pos >= 0 && pos <= p->size);
//当pos = 0时 => 头插
//当pos = size时 => 尾插
//如果已满，需要增容
SeqCheckCapacity(p);
//把pos后面的数全部前移
int end = p->size - 1;
while (end >= pos)
{
p->a[end + 1] = p->a[end];
end--;
}
//pos处放入x
p->a[pos] = x;
p->size++;
}
//中间位置删除
void SeqListErase(SeqList* p, int pos)
{
assert(p);
assert(pos >= 0 && pos < p->size);
//当 pos = size - 1 => 尾删
//当 pos = 0 => 头删
int begin = pos;
while (begin < p->size - 1)
{
p->a[begin] = p->a[begin + 1];
begin++;
}
p->size--;
}
//打印
void SeqListPrint(SeqList* p)
{
assert(p);
for (int i = 0; i < p->size; ++i)
{
printf("%d", p->a[i]);//遍历依次打印
}
printf("\n"); //打印后换行
}
test.c
#include "SeqList.h"
//测试头插、尾插、头删、尾删
void TestSeqList1()
{
SeqList s;
SeqListInit(&s);
SeqListPushBack(&s, 1);
SeqListPushBack(&s, 2);
SeqListPushBack(&s, 3);
SeqListPushBack(&s, 4);
SeqListPushBack(&s, 5);
//SeqListPrint(&s); //1 2 3 4 5
SeqListPushFront(&s, 0);
//SeqListPrint(&s); //0 1 2 3 4 5
SeqListPopBack(&s);
//SeqListPrint(&s); //0 1 2 3 4
SeqListPopFront(&s);
//SeqListPrint(&s); //1 2 3 4
SeqListDestory(&s);
}
//测试中间插入、删除、修改
void TestSeqList2()
{
SeqList s;
SeqListInit(&s);
SeqListPushBack(&s, 1);
SeqListPushBack(&s, 2);
SeqListPushBack(&s, 3);
SeqListPushBack(&s, 4);
SeqListPushBack(&s, 5);
SeqListInsert(&s, 2, 20);
//SeqListPrint(&s);//1 2 20 3 4 5
SeqListErase(&s, 0);
//SeqListPrint(&s);//2 20 3 4 5
SeqListModify(&s, 1, 3);
SeqListPrint(&s);//2 3 3 4 5
SeqListDestory(&s);
}
int main()
{
TestSeqList1();
return 0;
}四、相关面试题
1 移除元素
题目描述：
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
int removeElement(int* nums, int numsSize, int val)
{
int src = 0;
int dst = 0;
while(src != numsSize)
{
if(nums[src] != val)
{
nums[dst] = nums[src];
dst++;
src++;
}
else
{
src++;
}
}
return dst;
}2 删除有序数组中的重复项
题目描述：
给你一个升序排列的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
int removeDuplicates(int* nums, int numsSize)
{
//如果是空数组,直接返回0
if(numsSize== 0)
return 0;
int cur = 0;
int dst = 0;
int next = 1;
while(next < numsSize)
{
if(nums[cur] != nums[next])//前后不相等，直接把值赋给dst
{
nums[dst++] = nums[cur++];
next++;
}
else
{
//前后相等时，next继续往后找，直到两者不相等为止
//在该循环也需要限制next范围，否则容易出现越界
while(next < numsSize && nums[cur] == nums[next])
{
next++;
}
nums[dst] = nums[cur];
dst++;
cur = next; //cur跳过已经判断出相等的部分
next++;
}
}
if(cur < numsSize)//如果不进行判断，可能会出现越界访问
{
nums[dst] = nums[cur]; //把最后一个值赋给dst
dst++;
}
return dst;
}3 合并两个有序数组
题目描述：
给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目(nums1Size、numsSize2分别表示nums1、nums2当前的空间大小)。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
//两个变量分别指向两个数组的最后一个元素
int end1 = m - 1;
int 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--];
}
}
//循环结束后:
//1.如果end2还没结束，说明nums2中还有数据。需要把nums2剩余数据继续挪动到nums1中
//2.如果end1还没结束，不需要挪动了，因为本身就在nums1中从后往前操作
while(end2 >= 0)
{
nums1[end--] = nums2[end2--];
}
}4 旋转数组
题目描述：
给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
void reverse(int* arr, int begin, int end)
{
while(begin < end)
{
int tmp = arr[begin];
arr[begin] = arr[end];
arr[end] = tmp;
begin++;
end--;
}
}
//思路:
//1.对原数组的后k个数逆置
//2.对原数组的前n-k个数逆置
//3.对原数组整体逆置
void spin(int* nums, int numsSize, int k)
{
//如果所给k的长度超过了元素个数，则取模，没有超过，取模也不会影响结果
k %= numsSize;
int left = 0;
int right = numsSize - 1;
reverse(nums, numsSize-k, right);
reverse(nums, left, numsSize-k-1);
reverse(nums, left, right);
}五、顺序表的缺陷
顺序表可以随机存取表中任一元素，其存储位置可用一个简单、直观的公式来表示。然而，从另一方面来看，这个特点也造成了这种存储结构的缺点：在做插入或删除操作时，需移动大量元素。 另外由于数组有长度相对固定的静态特性， 当表中数据元素个数较多且变化较大时，操作过程相对复杂，必然导致存储空间的浪费。 面对这些问题，都可以通过线性表的另一种表示方法链式存储结构来解决。
相信大家看到这里，已经对顺序表有了更好的认识。那么今天的分享到这里就结束了，如果本篇文章对你们有所帮助，记得给博主留下一个三连哈~你们的支持是我创作的最大动力！我们在下期链表结构再会啦 ！
