#yyds干货盘点#顺序表一发入魂 _干货

宝剑锋从磨砺出，梅花香自苦寒来。这篇文章主要讲述#yyds干货盘点#顺序表一发入魂相关的知识，希望能为你提供帮助。
顺序表线性表线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以==数组和链式结构==的形式存储。

文章图片

==但是今天这篇博客只讲顺序表==
顺序表（本质上就是数组）概念及结构
顺序表是用一段==物理地址连续==的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的==增删查改==。
顺序表一般可以分为：
1. 静态顺序表：使用定长数组存储元素。

文章图片

#pragma once//方便改数组的大小 #define N 100typedef int SLDataType; //这样会很方便修改//静态顺序表 typedef struct SeqListSLDataType a[N]; SLDataType size; //表示数组中存储了多少个数据 SL; void SeqListPushBack(SL* ps, SLDataType x);

==静态的特点是满了就不让插入，缺点就是我们不知道给多大的空间合适，给大了浪费，给小了“犯罪”，所以就出现了动态顺序表==
2. 动态顺序表：使用动态开辟的数组存储。==既然都动态了，那么也就没有空间大小N的必要了，我们用指针即可==

文章图片

//方便改数组的大小 //#define N 100typedef int SLDataType; //这样会很方便修改//动态顺序表 typedef struct SeqListSLDataType* a; int size; //表示数组中存储了多少个数据 int capacity; //数组实际能存数据的空间容量是多大 SL; void SeqListPushBack(SL* ps, SLDataType x);

接口函数（==这里教你闭坑，不然有时候你不知道怎么死的（值传递与址传递的区别）==）顺序表初始化 SeqListInit 值传递

文章图片

==这里有一个告诫就是vs13与vs19不同，vs13你sl不初始化也可以跑过去，而vs19sl不初始化是跑不过去的，我把vs19跑不过去的图放在下面==

文章图片

址传递==既然实参的是不能传给形参，那么我们就把地址传过去==、

文章图片

//顺序表初始化 void SeqListInit(SL* ps)ps-> a = NULL; ps-> size = ps-> capacity = 0;

尾插函数SeqListPushBack

文章图片

//尾插 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("开辟失败\\n"); //没有开辟成功 exit(-1); //异常结束//成功扩容后 ps-> a = tmp; //把新的地址给他 ps-> capacity = newcapacity; //容量给他//空间足够的情况 ps-> a[ps-> size] = x; ps-> size++;

==但是有时候一直调试去看我们接口写的怎么样，会很浪费时间，所以我们得写个打印函数==
顺序表打印函数SeqListPrint

文章图片

//顺序表打印 void seqListPrint(SL* ps)int i = 0; for (i = 0; i < ps-> size; i++)printf("%d ", ps-> a[i]); printf("\\n");

==我们做到这一步基本可以看成顺序表起步成功，现在我们需要对顺序表销毁，实际上我们是知道，最后的最后才是顺序表的销毁，但是我们这里可以实现了（你可以可理解成单片机的最小系统或者丐版微星一个意思）==
顺序表销毁函数SeqListDestory

文章图片

//顺序表销毁 void seqListDestory(SL* ps)//就是释放内存，防止内存溢出free(ps-> a); ps-> a = NULL; ps-> capacity = ps-> size = 0;

==最小系统板好了我们就一个一个加模块==
尾删函数SeqListPopBack==温柔==

文章图片

//尾删 void SeqListPopBack(SL* ps)//温柔做法 if (ps-> size > 0)ps-> size--;

==粗暴==（我一个大男人比较喜欢粗暴一点的做法，直接了当）

文章图片

//尾删 void SeqListPopBack(SL* ps)////温柔做法 //if (ps-> size > 0) // //ps-> size--; // //粗暴 assert(ps-> size > 0); //断言不为真直接报错，管你不轻 ps-> size--;

==在写头插之前，我们思考一下，你要插入，肯定要考虑到是否需要扩容，那么就与之前尾插里面的扩容重了，所以可以抽取出来单独写一个函数==
顺序表检查容量函数SeqListCheckCapacity

文章图片

//顺序表检查容量 void SeqListCheckCapacity(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("开辟失败\\n"); //没有开辟成功 exit(-1); //异常结束//成功扩容后 ps-> a = tmp; //把新的地址给他 ps-> capacity = newcapacity; //容量给他

==然后用那个检查容量就可以很轻松的扩容了==
头插函数SeqListPushFront

文章图片

//头插 void SeqListPushFront(SL* ps, SLDataType x)//检查增容 SeqListCheckCapacity(ps); //挪动数据 int end = ps-> size - 1; while (end> =0)ps-> a[end + 1] = ps-> a[end]; end--; ps-> a[0] = x; ps-> size++;

头删SeqListPopFront

文章图片

//头删 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--;

顺序表查找函数SeqListFind

文章图片

//顺序表查找函数 int SeqListFind(SL* ps, SLDataType x)int i = 0; for (i = 0; i < ps-> size; i++)if (ps-> a[i] == x) return i; return -1;

顺序表插入函数SeqListInsert

文章图片

//顺序表插入函数 void SeqListInsert(SL* ps, int pos, SLDataType x)//断言不在范围内直接结束 assert(pos> =0 & & pos< =ps-> size); //检查扩容 SeqListCheckCapacity(ps); //挪动数据 int end = ps-> size - 1; while (pos< =end)ps-> a[end + 1] = ps-> a[end]; end--; //然后再把数据给当前位置 ps-> a[pos] = x; ps-> size++;

==所以头插尾插就不需要写了，直接调用插入函数即可==
顺序表删除函数SeqListErase

文章图片

//顺序表删除函数 void SeqListErase(SL* ps, int pos)//断言不在范围内直接结束 assert(pos > = 0 & & pos < ps-> size); //删除不需要考虑扩容,直接挪动数据 int begin = pos; while (begin+1< ps-> size)ps-> a[begin] = ps-> a[begin + 1]; begin++; ps-> size--;

==所以头删尾删也就可以复用掉==
练习题例1移除元素

文章图片

文章图片

==我们先分析一下题，他对空间复杂度是有要求的，对时间复杂度没有什么要求==

文章图片

int removeElement(int* nums, int numsSize, int val) int i = 0; int* cur = nums; for(i = 0; i< numsSize; i++)if(val ^ nums[i])*cur++ = nums[i]; return cur-nums;

例2删除有序数组中的重复项

文章图片

文章图片

==我们不能空看我们得画图解决，题目直接把空间定死，不会给你开额外的数组了，也就只能多指针解决==
脑内模拟一番，一个定位指针，两个游标指针，应该可以解决

文章图片

int removeDuplicates(int* nums, int numsSize) if(numsSize == 0)//空数组跳出 return 0; int* cur = nums; //定位指针 int* head = nums; //游标头指针 int* tail = nums+1; //游标尾指针 while(tail< nums+numsSize)if(*head == *tail)tail++; else*cur = *head; cur++; head = tail; tail++; *cur = *head; //最后一个不管等不等都强制赋值 cur++; return (cur-nums);

例3合并两个有序数组

文章图片

文章图片

【#yyds干货盘点#顺序表一发入魂】

文章图片

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) int* p1 = nums1+m-1; int* p2 = nums2+n-1; int* cur = nums1+m+n-1; while(p1> =nums1 & & p2> =nums2)*cur-- = *p1> *p2 ? *p1-- : *p2--; //三目运算符while(p2> =nums2)*cur-- = *p2--;