C++超详细分析顺序表

本次我们解剖顺序表将从以下三个结构：

1、静态顺序表和动态顺序表

2、顺序表实现增删查改等常见接口

3、顺序表相关OJ题练习

什么是顺序表

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

兄弟们兄弟们，记得抠字眼啊，顺序表一定是连续的存储单元，并且是依次存储数据的！！！！

顺序表一般可以分为：

? 静态顺序表      ? 动态顺序表

静态顺序表：使用定长数组存储，简单来说大小是固定的，数据个数也是固定的！

动态顺序表：使用动态开辟的数组存储，简单来说，装满了会自动扩大容量！

静态顺序表的实现我们就不讲了，冬天到了春天还会远吗？会了动态你还不会静态吗？所以我们今天主要讲动态顺序表！静态顺序表搭建代码如下：

// 顺序表的静态存储
#define N 100
typedef int SLDataType;
typedef struct SeqList
{
    SLDataType array[N]; // 定长数组
    size_t size;     // 有效数据的个数 
}SeqList;

动态顺序表

? 来到今天的重点！动态顺序表！

首先先来搭建顺序表的结构。

? 上面就是我给大家画的基本一个结构图了，下面我们来实现顺序表的基本接口：

? 首先我们顺序表需要初始化：

 ? 既然我们没有在初始化给定大小，我们现在要判断需不需要给动态表顺序表增容：

 ? 我们来实现动态顺序表头部插入数据：

 ? 接着来实现尾部插入数据：

 ? 我们要开始实现头部删除数据了：

? 下面实现尾部删除数据：

 ? 接着我们来实现在pos下标位置插入数据：

 ? 我们再来实现删除pos下标位置的数据：

? 查找顺序表中的元素x：

 ? 修改指定pos下标的数据

在实际中在我上面写的函数有些都可以复用哦！这个就等着你们去发现吧，我们接着往下走：

其实还有一些顺序表的打印，清空，求元素个数，这些相信你们看完上面的内容对于你们来说非常容易！我就不一一举例了，下面进入我们的习题时间！(●'?'●)

题目1：给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1：

输入：nums = [0,1,2,2,3,0,4,2], val = 2

输出：5, nums = [0,1,4,0,3]

解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

题目来源：27. 移除元素 - 力扣（LeetCode） (leetcode-cn.com)

思路1：遍历数组，发现元素为val就把后面的往前挪覆盖掉val，但是这样的时间复杂度为O(N?)，这样当数组全是val，效率就会特别低！

思路2：以空间换时间，开辟一个新数组，把不是val的数放到新数组，再把新数组的值拷贝回来！但是这样的话空间复杂度O(N)不符合题意！

思路3：使用双指针，空间复杂度O(1),时间复杂度O(n),代码如下：

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++];
		}
		else
		{
			++src;
		}
	}
	return dst;
}

题目2：给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。请你 合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3

输出：[1,2,2,3,5,6]

解释：需要合并 [1,2,3] 和 [2,5,6] 。

合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

题目来源：88. 合并两个有序数组 - 力扣（LeetCode） (leetcode-cn.com)

 那这道题的思路就留给小伙伴们自己去思考了，我就直接给你们上代码！

void merge(int* nums1, int m, int* nums2, 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];
			--end;
			--end1;
		}
		else
		{
			nums1[end] = nums2[end2];
			--end;
			--end2;
		}
	}
	//如果是end2结束，不需要处理因为就是在nums1里面
	while (end2 >= 0)
	{
		nums1[end] = nums2[end2];
		--end;
		--end2;
	}
}

好了，通过这篇文章的学习，相信你会把顺序表理解的更透彻，还是那句话，我们一起快乐编程不头秃！加油奥里给！???

??????完结撒花！??????

gitee(码云)：Mercury. (zzwlwp) - Gitee.com