文章目录
前言一、顺序表的概念1.顺序表是什么?2.顺序表和数组的区别
二、顺序表的实现1.顺序表的结构(1). 静态顺序表(2). 动态顺序表
2. 顺序表的初始化3. 顺序表的销毁4.顺序表尾插5. 顺序表头插6. 顺序表尾删7. 顺序表头删8. 顺序表获取元素下标9. 顺序表任意位置插入10. 顺序表任意位置删除11. 顺序表打印
三、小试牛刀，顺序表练习1. 移除元素2. 删除有序数组中的重复项3. 合并两个有序数组
四、 顺序表问题的思考总结
前言
在了解什么是顺序表之前，我们先来聊一聊什么是线性表?
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是⼀种数据结构，常⻅的线性表有：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，但是在物理结构上并不⼀定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。
如果底层结构使用的是数组来搭建，比如顺序表，那么开辟的就是一块连续的空间，线性表的物理结构就是连续的。如果底层结构是由指针来实现，每一个结构体中都有一个指向下一个数组地址的指针，如链表，那它的开辟的空间就不在一起，物理结构不连续。
一、顺序表的概念
1.顺序表是什么?
概念：顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采⽤数组存储。
这样看来顺序表是不是和数组很像？ 没错，顺序表的底层逻辑就是数组~
2.顺序表和数组的区别
那么顺序表和数组有什么区别呢?
顺序表就像是将数组包装起来了一样，在顺序表中有多种功能满足我们的需求。
二、顺序表的实现
1.顺序表的结构
(1). 静态顺序表
概念：使⽤定⻓数组存储元素。
//静态顺序表
typedef int SLDataType;
#define N 7
typedef struct SeqList
{
SLDataType a[N]; //开辟的数组为定长
int size; //记录数组中数据个数
}SL;
我们可以看到使用静态顺序表一个很大的弊端就是如果N太小了不够用还需要改变N，如果N太大了又会造成空间浪费。
(2). 动态顺序表
概念：动态申请空间的顺序表
typedef int SLDataType; //将顺序表中储存元素的类型命名为SLDataType,方便后续统一替换
//动态顺序表
typedef struct Seqlist
{
SLDataType* arr;
int size; //有效数据的多少
int capacity; //顺序表空间的大小
}SL;
因此我们推荐使用动态顺序表~
2. 顺序表的初始化
//初始化顺序表
void SLInit(SL* ps);
顺序表中有三个元素，我们默认初始顺序表为空，那它的元素个数和顺序表空间容量都为0.
//顺序表初始化
void SLInit(SL* ps)
{
ps->arr = NULL;
ps->size = 0;
ps->capacity = 0;
}
3. 顺序表的销毁
//顺序表的销毁
void SLDestroy(SL* ps);
我们下面给顺序表申请内存空间的时候动态的开辟了内存，因此销毁时要手动释放，别忘了free结束将arr置空~
//顺序表的销毁
void SLDestroy(SL* ps)
{
free(ps->arr);
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
4.顺序表尾插
//尾插
void SLPushBack(SL* ps, SLDataType x);
插入数据前我们要考虑到两个问题.
如果数据满了怎么办？如果顺序表空间为零怎么办？
这就需要我们再插入之前先进行扩容操作，确保有足够的空间可以插入数据。
//查看空间是否需要扩容
void SLCheckCapacity(SL* ps)
{
if (ps->size == ps->capacity)
{
//申请空间(增容用realloc)
//三目运算符，如果空间为零默认赋给4个空间大小
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newcapacity;
}
}
//尾插
void SLPushBack(SL* ps, SLDataType x)
{
assert(ps);
//插入数据前先看空间够不够
SLCheckCapacity(ps);
ps->arr[ps->size++] = x;
}
5. 顺序表头插
//头插
void SLPushFront(SL* ps, SLDataType 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++;
}
6. 顺序表尾删
void SLPopBack(SL* ps);
尾删的操作很简单，当前的size–就可以了~ 注意传过来的ps和ps->size不能为空！
//尾删
void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->size);
ps->size--;
}
7. 顺序表头删
//头删
void SLPopFront(SL* ps)
类似头插，头删需要顺序表所有元素向前移动覆盖掉第一个数据~
//头删
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--;
}
8. 顺序表获取元素下标
//顺序表的查找
int SLFind(SL* ps, SLDataType x)；
查找就是遍历，比较简单，我们就一笔带过了~
//顺序表的查找
int SLFind(SL* ps, SLDataType x)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (x == ps->arr[i])
{
//找到了
return i;
}
}
//没找到
return -1;
}
9. 顺序表任意位置插入
//在指定位置前插入
void SLInsert(SL* ps, int pos, SLDataType x);
类似于头插，但任意位置插入要对插入的位置pos做要求，pos范围是[0,ps->size]。在插入前，pos位置后的每一个数据都要向后挪一位。
//在指定位置前插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
assert(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++;
}
10. 顺序表任意位置删除
//删除指定位置的数据
void SLErase(SL* ps, int pos);
类比头删 删除同样对pos和ps->size有做要求，要进行断言。 删除要将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--;
}
11. 顺序表打印
//顺序表打印
void SLPrint(SL s);
最后来到我们顺序表的打印，顺序表打印遍历数组就可以做到啦~
//顺序表打印
void SLPrint(SL s)
{
for (int i = 0; i < s.size; i++)
{
printf("%d ", s.arr[i]);
}
printf("\n");
}
三、小试牛刀，顺序表练习
1. 移除元素
https://leetcode.cn/problems/remove-element/description/
方法1
解题思路：
1. 从前往后遍历nums，找到val第一次出现的位置
2. 将val之后的所有元素整体往前搬移，即删除该val
3. nums中有效元素个数减少一个
循环进行上述操作，直到nums中所有值为val的元素全部删除完
时间复杂度:O(N^2) 空间复杂度:O(1)
*/
#if 0
int removeElement(int* nums, int numsSize, int val){
//
while(1)
{
// 1. 在nums中找val出现的位置
int pos = 0;
for(; pos < numsSize; ++pos)
{
if(nums[pos] == val)
{
break;
}
}
// 2. 检测是否找到
if(pos == numsSize)
break;
// 3. 找到值为value的元素--将其删除
for(int j = pos+1; j < numsSize; ++j)
{
nums[j-1] = nums[j];
}
numsSize--;
}
return numsSize;
}
#endif
#if 0
/*
方法2：
解题思路:
1. 创建一个长度与nums相同的数组temp
2. 遍历nums，将nums中所有与val不同的元素搬移到temp中
3. 将temp中所有元素拷贝回nums中
时间复杂度: O(N) 空间复杂度: O(N)
*/
int removeElement(int* nums, int numsSize, int val){
// 1. 申请numSize个元素的新空间
int* temp = (int*)malloc(sizeof(int)*numsSize);
if(NULL == temp)
{
return 0;
}
// 2. 将nums中非value的元素搬移到temp中---尾插到temp中
int count = 0;
for(int i = 0; i < numsSize; ++i)
{
if(nums[i] != val)
{
temp[count] = nums[i];
++count;
}
}
// 3. 将temp中删除val之后的所有元素拷贝到nums中
memcpy(nums, temp, sizeof(int)*count);
free(temp);
return count;
}
#endif
2. 删除有序数组中的重复项
https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/
/*
解题思路：
1. 设置一个计数，记录从前往后遍历时遇到的不同元素的个数
由于不同的元素需要往前搬移，那count-1就是前面不同元素
搬移之后，最后一个元素的位置，下一次在遇到不同元素就应该
搬移到count位置
2. 遍历数组，如果nums[i]与nums[count-1]不等，就将nums[i]搬移
到nums[count]位置，不同元素多了一个，给count++
3. 循环结束后，返回count
*/
int removeDuplicates(int* nums, int numsSize){
int count = 0;
for(int i = 1; i < numsSize; ++i)
{
if(nums[i] != nums[count])
nums[++count] = nums[i];
}
++count;
return count;
}
3. 合并两个有序数组
https://leetcode.cn/problems/merge-sorted-array/description/
/*
解题思路:
1. 从后往前遍历数组，将nums1和nums2中的元素逐个比较
将较大的元素往nums1末尾进行搬移
2. 第一步结束后，nums2中可能会有数据没有搬移完，将nums2中剩余的元素逐个搬移到nums1
时间复杂度：O(m+n)
空间复杂度: O(1)
*/
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
// end1、end2：分别标记nums1 和 nums2最后一个有效元素位置
// end标记nums1的末尾，因为nums1和nums2中的元素从后往前往nums1中存放
// ，否则会存在数据覆盖
int end1 = m-1;
int end2 = n-1;
int index = m+n-1;
// 从后往前遍历，将num1或者nums2中较大的元素往num1中end位置搬移
// 直到将num1或者num2中有效元素全部搬移完
while(end1 >= 0 && end2 >= 0)
{
if(nums1[end1] > nums2[end2])
{
nums1[index--] = nums1[end1--];
}
else
{
nums1[index--] = nums2[end2--];
}
}
// num2中的元素可能没有搬移完，将剩余的元素继续往nums1中搬移
while(end2 >= 0)
{
nums1[index--] = nums2[end2--];
}
// num1中剩余元素没有搬移完 ---不用管了，因为num1中剩余的元素本来就在num1中
}
四、 顺序表问题的思考
顺序表问题与思考
• 中间/头部的插⼊删除，时间复杂度为O(N)
• 增容需要申请新空间，拷⻉数据，释放旧空间。会有不⼩的消耗。
• 增容⼀般是呈2倍的增⻓，势必会有⼀定的空间浪费。例如当前容量为100，满了以后增容到200， 我们再继续插⼊了5个数据，后⾯没有数据插⼊了，那么就浪费了95个数据空间。
总结
到这里相信大家对顺序表有一个深入的了解了，最后的总结顺序表实现的源码奉上需要的小伙伴们自取哦~
//SeqList.h
#pragma once
#include
#include
#include
typedef int SLDataType; //将顺序表中储存元素的类型命名为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 SLInit(SL* ps)
{
ps->arr = NULL;
ps->size = 0;
ps->capacity = 0;
}
//顺序表的销毁
void SLDestroy(SL* ps)
{
free(ps->arr);
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
//顺序表打印
void SLPrint(SL s)
{
for (int i = 0; i < s.size; i++)
{
printf("%d ", s.arr[i]);
}
printf("\n");
}
//查看空间是否需要扩容
void SLCheckCapacity(SL* ps)
{
if (ps->size == ps->capacity)
{
//申请空间(增容用realloc)
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
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);
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 (x == ps->arr[i])
{
//找到了
return i;
}
}
//没找到
return -1;
}
//测试代码
#include"SeqList.h"
void test01()
{
SL s;
SLInit(&s);
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPrint(s);
SLPushFront(&s, 0);
SLPushFront(&s, 0);
SLPrint(s);
SLInsert(&s, 0, 99);
SLInsert(&s, 2, 100);
SLInsert(&s, 6, 77);
SLPrint(s);
SLPopBack(&s);
SLPrint(s);
SLPopFront(&s);
SLPrint(s);
SLErase(&s, 3);
SLPrint(s);
}
void test02()
{
SL s;
SLInit(&s);
SLPushBack(&s, 0);
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
int tem = SLFind(&s, 2);
printf("%d\n", tem);
printf("%d\n", s.arr[tem]);
}
int main()
{
test01();
printf("----------------------------\n");
test02();
return 0;
}
真相永远只有一个！