顺序表（数据结构初阶）

欢迎大家来到我的博客，给生活来点impetus

今天我们主要学习顺序表（数据结构初阶）

顺序表

一：线性表

1.1概念：

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是⼀种在实际中⼴泛使⽤的数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

理解：
相同特性：分为物理结构和逻辑结构，物理结构指数据元素在计算机存储器中的存储方式。它主要包括顺序存储结构（底层逻辑是数组）和链式存储结构。理解链式结构具体可参考单链表（SList）
逻辑结构指用户角度看到的数据结构，与数据的存储无关，带主观因素.

二：顺序表

2.1概念与结构：

概念：顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采⽤数组存储。

从定义我们可以明白：
1:顺序表在物理结构和逻辑结构上都是连续的
2：顺序表的底层逻辑就是数组.

那么数组与顺序表的区别体现在哪里呢？
顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接⼝
看下方的图解你就明白了：

这样是不是就能够清晰的明白数组与顺序表的区别了。

2.2分类：

2.2.1静态顺序表

概念：使用定长数组存储元素
来看一下基本代码：

静态顺序表缺点：，空间不灵活。空间给少了不够用，给多了空间浪费。
结论：只有知道了总共的数据大小后，才可能会使用静态顺序表。

2.2.2动态顺序表

概念：使用了变长数组来存储元素。
来看一下基本代码：

1:下方int不使用typedef定义后的名字是因为有效数据和空间容量只可能是整数。
2：在绝大多数的情况下，动态顺序表比静态顺序表要更好。

2.3动态顺序表的实现

在这里，我们将会实现在顺序表中将实现声明（初始化），检查空间容量，申请空间，销毁空间，尾插，头插，尾删，头删，查找，指定位置之前插入数据，指定位置之后插入数据。

声明（初始化）

检查空间容量

扩容？那么究竟按照几倍来扩容呢？
结论：按照两倍来扩容。当按照很低倍数扩容：编译器频繁的寻找新空间，拷贝旧空间，释放旧空间，使得编译效率大大减低，当按照很高倍数扩容，容易造成空间的浪费。
使用二倍扩容，利用数学概率论的知识，能够更好的描述数据个数的变化趋势，这里仅做了解，知道结论就好。

来看一下这部分的代码：

在这里容易犯错的几个点：
1：malloc创建空间的大小单位是字节，所以要利用sizeof计算动态结构体的大小。
2：创建空间要使用判断语句判断是否开辟成功
3：要在函数中完成对实参的修改需要传地址
4：考虑特殊情况，如这里的初始值都为0的情况。

最后，只要是数据的插入（增加）都需要事先判断空间是否需要扩容（追加）。

尾插

代码如下：

以下对数据进行操作都需要断言传过来的指针是否为空指针。

头插

来看代码：

总结:时间复杂度：o（n），相较于链表中的头插，该处时间复杂度还是较高，效率还是较低。

尾删

代码如下：

总结
1：删除必须断言是否有元素
2：利用size（有效数据个数）对尾删进行操作

头删

这里的细节仍然是断言

查找

指定位置之前插入数据

这里需要注意判断pos（插入的位置是否是正确的）。

指定位置之后插入数据

与上一个操作的区别在于：pos是否需要移动。

销毁

到这里，我们对顺序表中的数据进行基本的增删查改操作就有一定的认识了。
下面我们来刷几道题来巩固一下吧！！！

2.4顺序表算法题

2.4.1移除元素

https://leetcode.cn/problems/remove-element/description/
说明一下思路：

方法一：
1. 从前往后遍历nums，找到val第一次出现的位置
2. 将val之后的所有元素整体往前搬移，即删除该val
3. nums中有效元素个数减少一个
循环进行上述操作，直到nums中所有值为val的元素全部删除完
时间复杂度:O(N^2) 空间复杂度:O(1)

方法二：
1. 创建一个长度与nums相同的数组temp
2. 遍历nums，将nums中所有与val不同的元素搬移到temp中
3. 将temp中所有元素拷贝回nums中
时间复杂度: O(N) 空间复杂度: O(N)
优化:
因为题目说了，数组中元素个数最大为100，所以不用动态申请，至二级创建100个元素数组即可

方法三：
解题思路:
1. 设置一个变量count，用来记录nums中值等于val的元素的个数
2. 遍历nums数组，对于每个元素进行如下操作：
a. 如果num[i]等于val，说明值为val的元素出现了一次，count++
b. 如果nums[i]不等于元素，将nums[i]往前搬移count个位置
因为nums[i]元素之前出现过count个值等于val的元素，已经被删除了
因此次数需要将nums[i]往前搬移
3. 返回删除之后新数组中有效元素个数
时间复杂度：O(N) 空间复杂度：O(1)

2.4.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

2.4.3合并两个有序数组

https://leetcode.cn/problems/merge-sorted-array/description/
说明一下思路：

方法一：
解题思路:
1. 从后往前遍历数组，将nums1和nums2中的元素逐个比较
将较大的元素往nums1末尾进行搬移
2. 第一步结束后，nums2中可能会有数据没有搬移完，将nums2中剩余的元素逐个搬移到nums1
时间复杂度：O(m+n）空间复杂度: O(1)

2.5顺序表的问题与思考

• 中间/头部的插⼊删除，时间复杂度为O(N)
• 增容需要申请新空间，拷⻉数据，释放旧空间。会有不⼩的消耗。
• 增容⼀般是呈2倍的增⻓，势必会有⼀定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插⼊了5个数据，后⾯没有数据插⼊了，那么就浪费了95个数据空间。

思考：如何解决以上问题呢？
接下来请移步单链表，进行单链表的学习，让我们对于上述问题提供解决方案。
单链表（SList）

结语

穷且益坚，不坠青云之志。
在这个充满诱惑的年代，希望读者能够坚定本心，矢志不渝。
高中第一个我的恩施才哥跟我说过：
加油！！！