typedef int SLDataType;	//使用typedef重新定义一个数据类型，方便后期修改顺序表中的元素
#define N 7			//使用宏定义数组大小，方便后期修改
typedef struct SeqList
{
	SLDataType a[N];//定长数组
	int size;		//顺序表中目前的有效数据个数
}SL;				//给这个数据结构起一个别名，方便我们使用
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;
	int size;		//顺序表的容量
	int capacity;	//顺序表中有效数据数据个数
}SeqList;
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

void SeqListInit(SeqList* ps)
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

void SeqListInit(SeqList* ps)
{
	assert(ps);		//assert包含在头文件中，如果断言内容为假就会报错
	ps->a = NULL;
	ps->capacity = 0;
	ps->size = 0;
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

void SeqListDestroy(SeqList* ps)
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

• 1

销毁和创建的思路其实是一样的，都是要把顺序表中的数据置为0，只不过多了一步释放空间。

void SeqListDestroy(SeqList* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->size = 0;
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
1
2
3
4
5
6
7
8

我们先来测试一下：

void test2()
{
	SeqList SL;	//注意顺序表的初始化有很多种方法，不同的方法需要在初始化之前在 main 函数做什么也是不同的
	SeqListInit(&SL);
	//操作
	SeqListDestroy(&SL);
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
1
2
3
4
5
6
7

这样就是一个基础的创建与销毁的框架了，其他所有的代码都应该在这中间进行。

3. 2. 2 打印

为了方便我们后续对代码是否成功运行进行观察，我们先来实现打印函数，声明如下：

void SeqListPrint(SeqList* ps);		//实际上这里根本不需要传指针，但是为了使用时方便，
									//能够使用同一个变量，所以这里也使用指针
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
1
2

我们知道顺序表的底层是一个数组，而且这个数组中存储的元素个数也在顺序表内部存储着，所以只需要按照正常的打印数组的思路，使用循环遍历就可以了。

void SeqListPrint(SeqList* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
		printf("%d ", ps->a[i]);
		
	printf("\n");		//记得换行
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
1
2
3
4
5
6
7
8

3. 2. 3 尾插

void SeqListPushBack(SeqList* ps, SLDateType x);
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
1

尾插的思路如下：

1. 检查空间是否足够
2. 将数据插入
3. size++

顺序表除了尾插之外，还有头插，头插也会涉及第一步，那我们不如将第一步单独封装成一个函数，方便我们调用。那么这个函数后面再讲，我们先看第二步：
尾插要将数据插入是非常简单的，我们知道 size 是元素的个数，那么 ps->a[size]就是应该插入数据的位置了，所以：

void SeqListPushBack(SeqList* ps, SLDateType x)
{
	SeqListCheck(ps);		//这个函数的实现在后面
	ps->a[ps->size++] = x;	//将第二三步结合起来
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
1
2
3
4
5

3. 2. 3 检查空间是否足够

void SeqListCheck(SeqList* ps)
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
1

这个函数用于检查空间是否足够，如果不够就动态申请内存。
我们来分析这个函数需要做什么：

1. 检查空间是否足够，如果足够不再执行
2. 扩容

我们先来看第一步，怎么检查空间是否足够？
在顺序表的结构体中，除了数据之外还有两个参数，这两个参数就可以用来检查：

ps->size == ps->capacity
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
1

如果这个代码为真就说明空间已经满了。

那么看第二步，怎么扩容？
需要先确定要扩容多大的空间，这里也有两种情况：

1. capacity == 0
2. capacity != 0

所以要进行分类讨论，先看第一种，我们给它分配初始空间四个元素大小（可以根据实际情况调整，但是不宜过大）：

if (ps->a == NULL)
{
	SeqList* new = realloc(ps->a, 4 * sizeof(SLDateType));
	if (!new)	//等价于 new==NULL
	{
		perror("realloc");	//动态开辟内存记得检查是否开辟成功
		exit(-1);			
	}
	ps->a = new;
	ps->capacity = 4;
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
1
2
3
4
5
6
7
8
9
10
11

再看第二种情况，我们将它的空间扩大至原来的二倍。
为什么是二倍？
因为 realloc 函数扩增是有损耗的（详情请看：C语言的动态内存管理），所以我们应该尽量地减少扩增次数，但是也不能太大，否则会浪费太多空间，那么扩大至原来的二倍比较合适了。

else
{
	if (ps->size != ps->capacity)
		return;
	SeqList* new = realloc(ps->a, 2 * ps->capacity * sizeof(SLDateType));
	if (!new)
	{
		perror("realloc");
		exit(-1);			//动态开辟内存记得检查是否开辟成功
	}
	ps->a = new;
	ps->capacity *= 2;
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
1
2
3
4
5
6
7
8
9
10
11
12
13

只需要将两个代码片结合起来，再在最前面加上 assert 断言一下空指针，这个函数就大功告成了。

测试：
目前我们已经完成了头插和检查空间大小，我们不妨来测试一下，如果发现了问题，就及时解决，避免在后面代码太多，出现问题难以定位。

void test2()
{
	SeqList SL;
	SeqListInit(&SL);

	SeqListPushBack(&SL, 1);
	SeqListPushBack(&SL, 2);
	SeqListPushBack(&SL, 3);
	SeqListPushBack(&SL, 4);
	SeqListPushBack(&SL, 5);	//这里插入的数据个数应该多余初始大小，以保证测试全面

	SeqListPrint(&SL);

	SeqListDestroy(&SL);
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

运行结果如图，如果你的运行结果出现了错误，不妨调试一下定位问题。

3. 2. 4 头插

void SeqListPushFront(SeqList* ps, SLDateType x)
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
1

头插相对尾插要复杂一些：

1. 检查空间是否足够
2. 将所有的数据向后挪动一个位置
3. 将数据放在第一个位置，size++

我们来看第二步，顺序表的底层是数组，所以向后挪动一个单位也很简单，只需要从后往前遍历数组并调整就是可以了（想一下，为什么不能从前往后遍历？）。

void SeqListPushFront(SeqList* ps, SLDateType x)
{
	SeqListCheck(ps);	//在空间检查中有关于空指针的断言，就不需要额外添加了
	for (int i = ps->size; i > 0; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[0] = x;
	ps->size++;
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
1
2
3
4
5
6
7
8
9
10

头插完成后，不妨再进行测试，这是一种良好的编程习惯。

3. 2. 5 尾删和头删

我们先来看尾删，这个其实特别简单，因为顺序表中的 size 表示顺序表中元素个数，那么只需要将 size-- ，这样，这个空间就可以被覆盖，也不会被打印，就相当于被删除了。（想一想，有没有必要将最后一个元素置为0再size--？）

void SeqListPopBack(SeqList* ps)
{
	assert(ps);
	assert(ps->size);	//删除是需要检查 size 是否为 0，如果为 0 还删除，结果无法预知
	ps->size--;
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
1
2
3
4
5
6

尾删结束我们来看头删，模仿头插的思路想一想，如果逆着进行一次头插的过程——将从第二个元素开始的所有元素向前挪动一位，不就实现了头删了吗？

void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	assert(ps->size);
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
1
2
3
4
5
6
7
8
9
10

3. 2. 6 查找

int SeqListFind(SeqList* ps, SLDateType x);
//找到顺序表中存储数据 x 的位置的下标，如果没有，就返回 -1
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
1
2

这个其实再简单不过了，只需要遍历一遍就可以了，这个函数是为接下来的两个函数作准备用的。

int SeqListFind(SeqList* ps, SLDateType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
			return i;
	}
	return -1;
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
1
2
3
4
5
6
7
8
9
10

3. 2. 7 插入与删除

这两个函数是在上一个函数的基础上进行的，功能是在给定的下标处插入或删除数据。
先看插入：

void SeqListInsert(SeqList* ps, int pos, SLDateType x)
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
1

首先，这个下标是上一个函数给的，如果没找到，上一个函数会返回-1，而-1显然不是一个有效的下标，因此要进行断言判断，同时要插入数据就必须检查空间！
在下标出插入数据，可以将 pos 位置看成一个顺序表的起始位置，然后头插，这样思路就简单了：

void SeqListInsert(SeqList* ps, int pos, SLDateType x)
{
	SeqListCheck(ps);
	assert(pos >= 0 && pos < ps->size);	//保证 pos 是一个合法的下标
	for (int i = ps->size; i > pos; i--)
	{
		ps->a[i] = ps->a[i - 1];		//将后面所有数据向后挪动，将下标位置空出来
	}
	ps->a[pos] = x;						//插入
	ps->size++;	
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
1
2
3
4
5
6
7
8
9
10
11

再看删除：
删除也可以将下标位置看作顺序表的起始位置，然后头删：

void SeqListErase(SeqList* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	assert(ps->size);
	for (int i = pos; i < ps->size; i++)
	{
		ps->a[i] = ps->a[i + 1];	//将后面的所有数据向前挪动
	}
	ps->size--;
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
1
2
3
4
5
6
7
8
9
10
11

3. 2. 8 注意事项总结

1. 所有的函数都要检查空指针，但是没必要检查两遍。
2. 插入时必须检查空间是否足够
3. 删除时必须判断 size 是否为 0
4. 按下标进行操作时要判断下标是否有效

3. 2. 9 最终测试

除了每一步的小测试，我们不妨在全部完成后进行一个全方位的测试，这个测试应该使用到所有的函数，并且要在每一步的后面加上SeqListPrint函数检查结果是否符合预期。

本文代码可以在 gitee 上获取。

4. 双指针法

顾名思义，就是需要用两个指针变量，在简单的顺序表（数组）的题目中，这两个指针变量一般是在同一个数组中遍历，然后进行各种操作。
我们通过具体例子进行分析。

4. 1 移除元素

链接点这里

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。 返回 k。

int removeElement(int* nums, int numsSize, int val)
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
1

由于这道题要求原地进行，所以不能创建新的数组，这时候我们就可以使用双指针法。

首先我们定义cur 和 real 两个指针，都指向nums也就是数组第一个元素。
接下来开始遍历，让 cur 往后走，如果说 cur 指向的元素数据不等于 val ，就把这个值复制给 real 指向的地方，real再往后走，如果cur指向的元素等于val，就不做处理，继续遍历，那么最终real之前的数据就是实际要返回的数据了。

参考代码：

int removeElement(int* nums, int numsSize, int val) {
    int cur = 0;
    int real = 0;
    for (; cur < numsSize; cur++) {	//这个for循环没有初始条件
        if (nums[cur] != val)
            nums[real++] = nums[cur];
    }
    return real;
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
1
2
3
4
5
6
7
8
9

看了这个答案，你是否会有疑惑：不是双指针吗，怎么是两个 int 数据？
事实上，双指针法只是一种思想，不规定实际代码的书写，将 cur 和 real 换成指针一样能写，只是每次都要多一步解引用，其他的和这个完全一样。

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

链接点这里

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的
相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与nums 的大小不重要。
返回 k 。

int removeDuplicates(int* nums, int numsSize)
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
1

这道题的思路和上道题一样，只是判断值是否有效的依据从 val变成了上一个数字，为什么是上一个数字？
我们来看一个用例：

0,0,1,1,1,2,2,3,3,4
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
1

我们按照上面的思路分析：如果一个数字与上一个不同，那么就说明它是一个新的数字，就可以写入到 real 中，如果它和上一个数字相同，那很显然它就是一个重复项，需要跳过。

int removeDuplicates(int* nums, int numsSize) {
    int cur = 1;
    int real = 1;
    for (; cur < numsSize; cur++) {
        if (nums[cur] != nums[cur - 1])
            nums[real++] = nums[cur];
    }
    return real;
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
1
2
3
4
5
6
7
8
9

为什么这里的 cur 和 real 都是从 1 开始的？因为无论如何，第一个数字肯定是一个新的数字没有和前面的数字重合·，并且下面的代码中涉及到了 nums[cur-1]，如果cur=0，这里就会发生越界访问了。

4. 3 合并两个有序数组

链接点这里

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 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) {
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
1

这道题和上面两道就有些不一样了，这道题涉及到了两个数组，也就是说我们的双指针肯定不会指向同一个数组了。
这里我们需要三个指针，一个 end1 指向nums1的有效数据，一个end2指向nums2的有效数据，还有一个end指向最终数据，那么问题来了，这三个指针要怎么分布呢？都指向数组头吗？我们来尝试一下：

nums1 = [1,2,3,0,0,0];
nums2 = [2,5,6];
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
1
2

如果是从前往后， 那么第一次比较，end++,end1++；
第二次比较 end++,end1++；
第三次，nums1[end++]=nums2[end2++]；

此时nums1就变成了：

nums1 = [1,2,2,0,0,0];
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
1

这就出现问题了，3没了，那么结果就很显然是错的了，所以从前往后遍历是不可取的，所以我们应该从后往前遍历：end1,end2分别指向nums1,nums2有效数据的末尾，end指向nums1的末尾，从后往前排成一个递减数组，就可以顺利地完成任务了。

参考代码：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int end1 = m - 1, end2 = n - 1, end = nums1Size - 1;//注意这里应该-1，因为我们使用的时候是当做下标使用的
    while (end1 >= 0 && end2 >= 0) {
        if (nums1[end1] > nums2[end2])
            nums1[end--] = nums1[end1--];
        else
            nums1[end--] = nums2[end2--];
    }
    //上面的循环结束后，有两种情况：
    //1. nums1走到了头，nums2还没有，这时候就需要将nums2中剩下的数据拷贝到nums1中
    //2. nums2走到了头，nums1还没有，这时候就可以直接结束了，因为这些数据本来就在nums1上，且排成升序
    //所以说，只需要处理第一种情况就可以了
    while (end2 >= 0)
        nums1[end--] = nums2[end2--];
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}"> class="hide-preCode-box">
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

谢谢你的阅读，喜欢的话来个点赞收藏评论关注吧！
我会持续更新更多优质文章

发表评论

登录后才能发表评论和回复 注册

/ 登录

提交评论

评论记录：

未查询到任何数据！

回复评论：

×

关闭 提交评论