【数据结构与算法】万字顺序表与OJ题
文章目
线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串… 本篇博客介绍的就是顺序表 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的（比如链表），线性表在物理上存储时，通常以数组和链式结构的形式存储 ：
顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
对于顺序表：我们可以分为静态顺序表和动态顺序表。
对于静态顺序表，我们该如何去定义呢?
#define N 10
typedef int SLDataType;
struct SeqList
{
SLDataType a[N];
int size;//存储数据的个数
};
我们可以看到，对于静态顺序表而言，里面的数组元素个数是固定的，不够灵活
对于动态顺序表：
//动态顺序表
typedef int SLDataType;
typedef struct SeqLIst
{
SLDataType* a;
int size;//存储数据的个数
int capacity;//存储空间的大小
}SL;
这里有一个问题
- 对于应该扩容多少究竟扩多少倍这个问题❓
我们这里的代码实现默认的是扩容2倍（实际上空间满之后，不一定是扩容2倍）：因为2倍比较合适，并不是必须一定是2倍，2倍2不会导致扩容过大或过小，如果扩容一次扩多了，将会存在空间浪费，扩少了，会导致频繁扩容，会导致效率损失。这并不是我们想要的
同时，还有另外一个问题，需要我们进行探讨一下：
- 在进行删除相关操作（如下面会说到的头删操作时）后面剩余的空间要不要进行缩容❓
对于删除顺序表没有缩容的概念，虽然可以缩容，都是我们不会去缩容，缩容要付出极大的代价。对于realloc我们知道扩容有2种情况(取决于后面的空间够不够)：一种是原地扩容，返回原来的地址，另一种是异地扩容，返回的不是同一个地址。
如果我们扩容扩的比原来还小呢？会不会进行缩容❓可能会原地缩容或者异地缩容
- 对于删除数据后面剩余的空间有点多，我们确实可以用realloc进行缩容，但是付出的代价有点多：可能会在新空间开一个空间，将其里面的数据进行拷贝，将旧空间释放掉。这就是要付出的代价，这是性能的代价。
- 有没有想过，缩容之后，如果又要插入数据，这时候我们又得扩容，扩容又得申请新的空间，在释放旧空间，在插入数据。这不就是在反复横跳。况且现在计算机的空间也没那么少
我们可以认为缩容是一种以时间换空间的方案。不缩容是在以空间换时间，而不缩容后面插入数据我们可能都不需要进行扩容，这就是不缩容的优势。虽然缩容是可以的，但是没有系统会去做。
接口实现
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，下面我们实现动态顺序表
我们将会实现的功能是：
初始化顺序表、销毁顺序表、尾插数据、头插数据、尾删数据、头删数据、查找数据、在某个位置插入数据、在某个位置删除数据、修改数据。以及中间实现过程中会涉及到的打印数据、扩容操作等。
很显然，在实现某个位置插入数据的功能的时候，我们就能用这个函数取代尾插和头插操作
在实现某个位置删除数据的功能，我们就能用这个函数取代尾删和头删操作
面对这么多的操作，我们采用模块化设计，分为3个板块，同时，我们应该在边实现功能函数的过程中边进行调试操作，不要让自己的代码出现过多的错误。我们可以在主函数的部分通过设计void TestSeqList()里面存放一些功能函数来看看自己的代码是否能够达到预期的效果，这点能够大大提高我们代码的准确性。
SeqList.h
防止头文件的重复包含。这一部分包括了头文件的统一包含，顺序表结构体的定义，以及上述各个功能函数的声明。
下面，我们来一起看一看总体将会设计到的源代码：
#pragma once
//#ifndef __SEQLIST_H__
//#define __SEQLIST_H__
//#endif
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
静态顺序表
//#define N 10
//typedef int SLDataType;
//struct SeqList
//{
// SLDataType a[N];
// int size;
//};
//动态顺序表
typedef int SLDataType;
typedef struct SeqLIst
{
SLDataType* a;
int size; //存储数据的个数
int capacity;//存储空间的大小
}SL;
//初始化
void SLInit(SL* psl);
//销毁
void SLDestory(SL* psl);
//打印
void SLPrint(const SL* psl);
//尾插头插 尾删头删
//尾插
void SLPushBack(SL* psl, SLDataType x);
//头插
void SLPushFront(SL* psl, SLDataType x);
//尾删
void SLPopBack(SL* psl);
//头删
void SLPopFront(SL* psl);
//查找
int SLFind(SL* psl, SLDataType x);
//插入
void SLInsert(SL* psl, size_t pos, SLDataType x);
//删除
void SLErase(SL* psl, size_t pos);
//修改
void SLModify(SL* psl, size_t pos, SLDataType x);
SeqList.c
这一部分就是对SeqList.h里面声明的函数进行实现的部分，是最为重要的部分，对于这一部分的函数，千万不要把SeList.h里面的函数全部实现完再去测试，那样子会大大提高工作量，出现错误很不好找，最好的办法就是写完一个函数去测试一个函数，调试看看有没有bug。这点至关重要。
下面，我们一起来看一看我们的源码(注意：代码里面的注释是精髓)：
#include "SeqList.h"
void SLPrint(const SL* psl)
{
assert(psl);
for (int i = 0; i < psl->size; i++)
{
printf("%d ", psl->a[i]);
}
//注意换行
printf("\n");
}
void SLInit(SL* psl)
{
assert(psl);
psl->a = NULL;
psl->capacity = psl->size = 0;
}
void SLDestory(SL* psl)
{
assert(psl);
if (psl->a)
{
free(psl->a);
psl->a = NULL;
psl->capacity = psl->size = 0;
}
}
//扩容,后面会用到扩容这个操作，我们干脆将其封装成一个函数即可
void SLCheckCapacity(SL* psl)
{
assert(psl);
//检查容量
if (psl->size == psl->capacity)
{
//如果是0那就容量初始化为4，否则就增加2倍
int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
//注意是sizeof(SLDataType)*newCapacity
SLDataType* tmp = (SLDataType*)realloc(psl->a, sizeof(SLDataType) * newCapacity);
//注意realloc会出现的情况
if (NULL == tmp)
{
perror("realloc fail");
return;
//exit(-1);
}
psl->a = tmp;
psl->capacity = newCapacity;
}
}
//尾插
void SLPushBack(SL* psl, SLDataType x)
{
assert(psl);
SLCheckCapacity(psl);
psl->a[psl->size] = x;
psl->size++;
//SLInsert(psl, psl->size, x);//直接调用SLInsetrt函数也可以实现尾插
}
//头插
void SLPushFront(SL* psl, SLDataType x)
{
assert(psl);
SLCheckCapacity(psl);
int end = psl->size-1;
while (end>=0)
{
psl->a[end+1] = psl->a[end];
--end;
}
psl->a[0] = x;
psl->size++;
//SLInsert(psl, 0, x);//直接调用SLInsert也可以实现头插
}
//尾删
void SLPopBack(SL* psl)
{
assert(psl);
//温柔的检查——元素的合理性
/*if (psl->size == 0)
{
return;
}*/
//暴力的检查，直接报错——元素的合理性
assert(psl->size > 0);
psl->size--;
//SLErase(psl, psl->size - 1);//直接调用SLErase也可以实现尾删
}
//头删
void SLPopFront(SL* psl)
{
assert(psl);
assert(psl->size > 0);
int begin = 0;
while (begin < psl->size - 1)
{
psl->a[begin] = psl->a[begin + 1];
++begin;
}
psl->size--;
//SLErase(psl, 0);//直接调用SLErase也可以实现头删
}
//查找
int SLFind(SL* psl, SLDataType x)
{
assert(psl);
for (int i = 0; i < psl->size; i++)
{
if (psl->a[i] == x)
{
return i;
}
}
return -1;
}
//插入
void SLInsert(SL* psl, size_t pos, SLDataType x)
{
assert(psl);
assert(pos <=psl->size);
SLCheckCapacity(psl);
int end = psl->size - 1;
//强转为int，这点很重要，因为pos为size_t类型，不强转会发生算术转化，永远跳不出循环
while (end >=(int)pos)
{
psl->a[end + 1] = psl->a[end];
--end;
}
psl->a[pos] = x;
psl->size++;
}
//删除
void SLErase(SL* psl, size_t pos)
{
assert(psl);
assert(pos < psl ->size);
size_t begin = pos;
while (begin < psl->size - 1)
{
psl->a[begin] = psl->a[begin + 1];
++begin;
}
psl->size--;
}
//修改
void SLModify(SL* psl, size_t pos, SLDataType x)
{
assert(psl);
assert(pos < psl->size);
psl->a[pos] = x;
}
test.c
温馨提示：一定要通过调用每个TestSeqList()函数确认里面涉及到的功能函数没有bug我们在去进行菜单的实现，同时，一旦里面的函数多了，我们极有可能忘记这个是测试什么功能函数的，所以我的建议是：写好注释，方便自己的理解复习，同时也让别人能够看得懂。不要本末倒置了。导致出现问题而不知道错在哪里，这样子得不偿失。
（对于菜单，博主这里并没有全部完善，但是整个框架已经搭起来了，而且可以正确运行起来。如果有需要，直接进行补充即可,可以参考之前博主类似的菜单内容。）
//测试尾插、打印、头插
void TestSeqList1()
{
SL s;
SLInit(&s);
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPushBack(&s, 5);
SLPushBack(&s, 6);
SLPrint(&s);
SLPushFront(&s, 10);
SLPushFront(&s, 20);
SLPushFront(&s, 30);
SLPrint(&s);
SLDestory(&s);
}
//测试尾删
void TestSeqList2()
{
SL s;
SLInit(&s);
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPrint(&s);
SLPopBack(&s);
SLPopBack(&s);
SLPrint(&s);
SLPopBack(&s);
SLPopBack(&s);
SLPrint(&s);
SLPopBack(&s);
SLPrint(&s);
SLPushBack(&s, 10);
SLPushBack(&s, 20);
SLPushBack(&s, 30);
SLPushBack(&s, 40);
SLPrint(&s);
SLDestory(&s);
}
//测试头删
void TestSeqList3()
{
SL s;
SLInit(&s);
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPrint(&s);
SLPopFront(&s);
SLPopFront(&s);
SLPrint(&s);
SLDestory(&s);
}
//测试插入
void TestSeqList4()
{
SL s;
SLInit(&s);
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPrint(&s);
SLInsert(&s, 2, 30);
SLPrint(&s);
SLInsert(&s, 0, 30);
SLPrint(&s);
/*int x = 0;
scanf("%d", &x);
int pos = SLFind(&s, x);
if (pos != -1)
{
SLInsert(&s, pos, x * 100);
}*/
SLPrint(&s);
}
//测试删除
void TestSeqList5()
{
SL s;
SLInit(&s);
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPushBack(&s, 5);
SLPrint(&s);
SLErase(&s, 0);
SLPrint(&s);
int x = 0;
scanf("%d", &x);
int pos = SLFind(&s, x);
if (pos != -1)
{
SLErase(&s, pos);
}
SLPrint(&s);
}
void menu()
{
printf("**********************\n");
printf("1.尾插数据 2.头插数据\n");
printf("3.尾删数据 4.头删数据\n");
printf("5.查找数据 6.插入数据\n");
printf("7.删除数据 8.修改数据\n");
printf("9.打印数据 -1.退出\n");
printf("**********************\n");
}
int main()
{
SL s;
SLInit(&s);
int option = 0;
int x = 0;
do
{
menu();
printf("请输入你的操作：>");
scanf("%d", &option);
switch (option)
{
case 1:
printf("请连续输入要插入的数据，-1为结束\n");
scanf("%d", &x);
while (x != -1)
{
SLPushBack(&s, x);
scanf("%d", &x);
}
break;
case 2:
//后面内容自己进行补充说明
break;
case 3:
break;
case 4:
break;
case 5:
break;
case 6:
break;
case 7:
break;
case 8:
break;
case 9:
SLPrint(&s);
default:
return;
}
} while (option);
SLDestory(&s);
return 0;
}
最后，附上我们的代码运行图：
OJ题
移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 示例 1： 输入：nums = [3,2,2,3], val = 3 输出：2, nums = [2,2] 解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。 示例 2： 输入：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。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。 来源：力扣
思路1：开辟一个数组，遍历如果不等于val就放到数组里面，最后将数组的元素赋值给原来的数组即可，但是时间复杂度不符合O（1）：
int removeElement(int* nums, int numsSize, int val){
int j = 0;
int*tmp = (int*)malloc(sizeof(int)*numsSize);
for(int i = 0;i<numsSize;i++)
{
if(nums[i] != val)
{
tmp[j++] = nums[i];
}
}
for(int i = 0;i<j;i++)
{
nums[i] = tmp[i];
}
return j;
}
思路2：不开辟额外数组，在原有的数组上进行操作，把上面开辟的数组看成原来的数组，定义两个变量src和dst，当nums[val] != val的时候，我们直接让src继续走下去，dst继续走下去。出现等于val的时候，我们让src继续走下去，直接跳过即可：
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];
dst++;
src++;
}
else
{
src++;
}
}
return dst;
}
删除有序数组中的重复项
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。 由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。 将最终结果插入 nums 的前 k 个位置后返回 k 。 不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 示例 1： 输入：nums = [1,1,2] 输出：2, nums = [1,2,_] 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。 示例 2： 输入：nums = [0,0,1,1,1,2,2,3,3,4] 输出：5, nums = [0,1,2,3,4] 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。 来源：力扣
解题思路：
int removeDuplicates(int* nums, int numsSize){
int src = 0;
int dst = 0;
while(src<numsSize)
{
if(nums[src] == nums[dst])
{
++src;
}
else
{
++dst;
nums[dst] = nums[src];
++src;
}
}
return dst+1;
}
合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。 示例 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 中的元素。 示例 2： 输入：nums1 = [1], m = 1, nums2 = [], n = 0 输出：[1] 解释：需要合并 [1] 和 [] 。 合并结果是 [1] 。 示例 3： 输入：nums1 = [0], m = 0, nums2 = [1], n = 1 输出：[1] 解释：需要合并的数组是 [] 和 [1] 。 合并结果是 [1] 。 注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。 **进阶：**你可以设计实现一个时间复杂度为
O(m + n)的算法解决此问题吗？ 来源：力扣
思路1：开辟一个新的数组，遇到小的数就存放进去，当其中一个数组放完之后，另一个数组的元素在存放进去，最后在把新数组的元素拷贝到num1中，但是这中做法的时间复杂度是O(m+n),空间复杂度也是O(m+n)：
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
int*tmp = malloc(sizeof(int)*(m+n));
int i1 =0,i2=0;
int i = 0;
while(i1<m&&i2<n)
{
if(nums1[i1]<nums2[i2])
{
tmp[i] = nums1[i1];
++i;
++i1;
}
else
{
tmp[i] = nums2[i2];
++i;
++i2;
}
}
while(i1<m)
{
tmp[i] = nums1[i1];
++i;
++i1;
}
while(i2<n)
{
tmp[i] = nums2[i2];
++i;
++i2;
}
memcpy(nums1,tmp,sizeof(int)*(m+n));
}
思路2：不开辟新的空间，倒着进行数的大小进行比较，取大放在num1后面的位置中，在往前走。当数组num2结束了，那就结束了。当num1先结束，另外在进行处理。
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
int end1 = m-1;
int end2 = n-1;
int i = m+n-1;
while(end1>=0&&end2>=0)
{
if(nums1[end1]>nums2[end2])
{
nums1[i] = nums1[end1];
i--;
--end1;
}
else
{
nums1[i] = nums2[end2];
i--;
end2--;
}
}
//end2结束，num2的数据都拷贝过去了，不用处理
//end1结束，num1的数据都拷贝过去了，处理num2剩下的数据
while(end2 >=0 )
{
nums1[i] = nums2[end2];
--i;
--end2;
}
}
结语
回顾一下，我们说了顺序表的概念以及相关接口的实现，理清楚之前的逻辑关系。以及最后3到OJ题目的练习。在数据结构与算法这一块，我们还是要着重多做题目的，提高自己的做题能力。本次就先到这里结束了。
腾讯云开发者
