- 1System.InvalidCastException:“无法将类型为“Microsoft.Office.Interop.Excel.ApplicationClass”的 COM 对象强制转换为接口类
- 2HTC vive pro & unity开发者软件/SDK版本注意事项_htc vive unity配置
- 3php毕业设计 基于php+mysql的在线购物商城毕业设计开题报告功能参考_php mysql navicat hbuilder购买系统开题报告
- 4UE蓝图 函数调用(CallFunction)节点和源码
- 5【毕业设计】基于微信小程序体育场地预约系统（源码+LW+部署+讲解）_基于微信小程序体育馆预约系统
- 6mysql 安装问题：由于找不到MSVCP120.dll,无法继续执行代码.重新安装程序可能会解决此问题。_mysql找不到msvcp120
- 7sdkmanager工具安装
- 8redis持久化失败问题（MISCONF Redis is configured to save RDB snapshots, but ......）问题解决
- 9计算机系统：EEPROM详解
- 10虚拟机Ubuntu18.04为Jetson AGX Xavier使用jetpack4.4刷机_agx orin装jetpack4。4
【数据结构】顺序表的增删查改 (C语言实现)_顺序表的增删改查c语言
赞
踩
一、线性表
是什么线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列； 线性表是一种在实际中广泛使 用的数据结构，常见的线性表有：顺序表、链表、栈、队列、字符串…
线性表的结构
线性表在逻辑上是线性结构，也就说是连续的一条直线；但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。
二、顺序表
1、什么是顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成数据的增删查改。
简单来说，顺序表就是数组，只是要求数组里面的元素必须连续存储而已。
2、顺序表的分类
顺序一般分为两类：静态顺序表和动态顺序表。
静态顺序表：采用定长数组来存储元素。
#define MAX 1000 //数组的最大长度
typedef int SLDtataType; //重命名数据类型
typedef struct SeqList
{
SLDtataType data[MAX]; //使用定长数组来存储数据
size_t size; //有效数据的个数
}SL;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
动态顺序表：使用动态开辟的数据来存储元素。
typedef int SLDataType; //将数据类型重命名为SLDataType
typedef struct SeqList
{
SLDataType* data; //对应数据类型的指针，用来指向动态开辟的空间
size_t size; //记录当前有效数据的个数
size_t capacity; //记录当前容量，不够就增容
}SL;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
两种顺序表的对比：相较于动态顺序表，静态顺序表存在很大的缺陷，那就是空间问题：当我们数据量很大时给定的空间可能不够用，但我们数据量比较小时，给定的空间又可能过大，造成空间浪费，即静态顺序表只适用于确定知道需要存多少数据的场景；所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，而静态顺序表很少使用。下面我们用C语言来模拟实现一个动态的顺序表。
三、动态顺序表的实现
1、结构的定义
#define DEF_SIZE 5 //初始容量
#define CRE_SIZE 2 //一次扩容的倍数
typedef int SLDataType; //将数据类型重命名为SLDataType
typedef struct SeqList
{
SLDataType* data; //对应数据类型的指针，用来指向动态开辟的空间
size_t size; //记录当前有效数据的个数
size_t capacity; //记录当前容量，不够就增容
}SL;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
如上：我们将要管理的数据类型重命名为SLDateType，这样以后当我们要用此顺序表管理其他数据类型时，我们就只需要改动这一个地方。
其次，相较于静态顺序表，我们的结构体多了一个参数 – capacity，我们用它来记录顺序表当前的容量，当当前的有效数据个数size与它相等时，我们就进行扩容；由于数据个数和顺序表的容量都不可能小于0，所以我们将其定义为size_t的。
最后就是关于初始容量和每次扩增倍数的问题，这里把初始容量设定为5，然后把扩增倍数设定为2，即我们的顺序表每次扩容两倍。
2、顺序表的初始化
在初始化函数中，我们把size和capacity都置为相应大小，并且为data指针动态开辟一块空间，用于存储数据。
//初始化顺序表
void SeqListInit(SL* psl)
{
assert(psl); //断言：防止psl为空
psl->data = (SLDataType*)calloc(DEF_SIZE, sizeof(SLDataType)); //开辟默认大小的空间并初始化
if (psl == NULL) //判空
{
perror("calloc fail"); //打印错误信息
return;
}
psl->size = 0;
psl->capacity = DEF_SIZE;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
3、检查容量
在检查容量的函数中，当我们结构体中的size和capacity相等时，我们就扩容，在扩容时我们要注意不要直接用data指针来接收realloc函数的返回值，避免扩容失败导致data指针找不到之前管理的空间，从而造成内存泄漏。
//检查容量（增容） void CheckCapacity(SL* psl) { assert(psl); //断言：防止psl为空 if (psl->size == psl->capacity) //当数据个数和容量相等时扩容 { //将realloc的返回值交由一个临时变量保存，防止扩容失败丢失原来空间的地址 SLDataType* ptr = (SLDataType*)realloc(psl->data, psl->capacity * CRE_SIZE * sizeof(SLDataType)); if (ptr == NULL) //判空 { perror("realloc fail"); return; } psl->data = ptr; psl->capacity *= CRE_SIZE; //增加容量 } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
4、在头部插入数据
在头部插入数据时，我们需要先将顺序表中的数据整体向后挪动一位，然后在顺序表的开头插入；在插入完成后记得要让size++。
//在头部插入数据
void SeqListPushFront(SL* psl, SLDataType x)
{
assert(psl); //判空
CheckCapacity(psl); //检查容量
int i = 0;
for (i = psl->size - 1; i >= 0; i--)
{
psl->data[i + 1] = psl->data[i]; //将数据整体向后移
}
psl->data[0] = x; //插入数据
psl->size++;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
5、在尾部插入数据
在尾部插入数据很简单，直接插入就行。
//在尾部插入数据
void SeqListPushBack(SL* psl, SLDataType x)
{
assert(psl); //判空
CheckCapacity(psl); //检查容量
psl->data[psl->size] = x; //插入数据
psl->size++;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
6、在指定位置插入数据
在此函数中，我们需要先将pos及其之后的元素整体向后挪动一位，然后再在pos处插入数据。
//在任意位置插入数据
void SeqListInsert(SL* psl, size_t pos, SLDataType x)
{
assert(psl);
assert(pos <= psl->size); //断言 因为可能会在尾部插入数据，所以pos可以等于size
CheckCapacity(psl); //检查容量
size_t end = psl->size;
while (end > pos) //把pos及以后的数据向后挪动一位
{
psl->data[end] = psl->data[end - 1];
--end;
}
psl->data[pos] = x; //插入数据
++psl->size;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
由于尾插和头插也可以通过调用 SeqListInsret 函数实现，所以我们可以对头插和尾插函数进行改造，以此来简化代码：
在头部插入数据
//在头部插入数据
void SeqListPushFront(SL* psl, SLDataType x)
{
assert(psl);
SeqListInsert(psl, 0, x); //相当于在0位置处插入数据
}
- 1
- 2
- 3
- 4
- 5
- 6
在尾部插入数据
//在尾部删除数据
void SeqListPopBack(SL* psl)
{
assert(psl);
SeqListErase(psl, psl->size - 1); //相当于在size-1处插入数据（数组下标从0开始）
}
- 1
- 2
- 3
- 4
- 5
- 6
7、在尾部删除数据
删除尾部的数据很简单，我们只需要将size–即可，并不需要对其进行改动，因为我们下一次插入数据时会直接将原来空间中的数据覆盖掉。
//在尾部删除数据
void SeqListPopBack(SL* psl)
{
assert(psl);
assert(psl->size);
psl->size--; //如果尾部有数据，直接让size--即可
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
8、在头部删除数据
在头部删除数据，我们只需要将顺序表中的数据整体向前挪动一位，然后将size–即可。
//在头部删除数据
void SeqListPopFront(SL* psl)
{
assert(psl);
assert(psl->size);
size_t i = 0;
for (i = 0; i < psl->size - 1; i++)
{
psl->data[i] = psl->data[i + 1]; //让表中的数据依次往前移
}
psl->size--;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
9、删除指定位置的数据
删除指定位置数据，我们需要将pos后面的数据整体向前挪动一位，然后让size–。
//删除指定位置的数据
void SeqListErase(SL* psl, size_t pos)
{
assert(psl);
assert(pos < psl->size);
size_t i = 0;
for (i = pos; i < psl->size - 1; i++)
{
psl->data[i] = psl->data[i + 1];
}
psl->size--;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
和上面的插入数据一样，我们也可以通过调用 SeqListErase 函数来实现数据的头删和尾删。
在头部删除数据
//在头部删除数据
void SeqListPopFront(SL* psl)
{
assert(psl);
SeqListErase(psl, 0); //相当于删除0下标处的数据
}
- 1
- 2
- 3
- 4
- 5
- 6
在尾部删除数据
//在尾部删除数据
void SeqListPopBack(SL* psl)
{
assert(psl);
SeqListErase(psl, psl->size - 1); //相当于删除size-1下标处的数据
}
- 1
- 2
- 3
- 4
- 5
- 6
面试题：删除数据是否要缩容？
我们知道，插入数据空间不够时我们要增容，那么删除数据达到一定的数量后我们是否要缩容呢？答案是不用缩容。原因如下：
第一：我们缩容之后插入数据又需要重新增容，而增容是有代价的，会降低程序的效率。我们知道 realloc 函数扩容分为两种情况，一种是原地扩，即当原来的空间后面有足够的空闲空间时，操作系统会直接将那一块空间交由我们使用，这种情况对效率影响不大；另一种是异地扩，即当原来空间后面没有足够的的空间开辟时，操作系统会在另外空间足够的地方为我们开辟一块新的空间，这时操作系统需要先将我们原来空间中的数据拷贝到新空间中，再将原来的空间释放掉，这种情况对效率的影响就比较大了。
第二：缩容也是有代价的。其实缩容和扩容的过程是一样的，都分为原地和异地，会对程序效率造成影响。
第三：顺序表申请的是一块连续的空间，而free函数数并不能释放连续空间的一部分，只能全部一起释放，所以这里即使想释放也是做不到的。
所以综合前面三个因素考虑，顺序表删除数据不会缩容；这是我们典型的以空间换时间的做法。
10、查找数据
当我们找到该元素时，我们返回元素的下标；当该元素不存在时，我们返回一个无意义的值。（如-1）
//查找数据
int SeqListFind(const SL* psl, SLDataType x)
{
assert(psl);
int i = 0;
for (i = 0; i < (int)psl->size; i++)
{
if (psl->data[i] == x)
return i; //找到元素所在返回下标
}
return -1; //找不到返回-1（一个无效下标）
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
11、修改指定位置的数据
//修改指定位置的数据
void SeqListModify(SL* psl, size_t pos, SLDataType x)
{
assert(psl);
assert(pos < psl->size); //断言
psl->data[pos] = x; //修改数据
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
12、打印顺序表中的数据
//打印顺序表中的数据
void SeqListPrint(const SL* psl)
{
assert(psl); //判空
size_t i = 0;
for (i = 0; i < psl->size; i++)
{
printf("%d ", psl->data[i]);
}
printf("\n");
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
13、顺序表的销毁
在销毁顺序表的时候我们一定要记得将前面动态开辟的空间释放掉，防止内存泄漏。
//销毁顺序表
void SeqListDestory(SL* psl)
{
assert(psl); //断言：防止psl为空
free(psl->data); //释放（避免内存泄漏）
psl->data = NULL; //置空（避免野指针）
psl->size = 0;
psl->capacity = 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
四、完整代码
1、SeqLIst.h
#pragma once //防止头文件重复包含 //头文件的包含 #include <stdio.h> #include <stdlib.h> #include <assert.h> //符号与结构的定义 #define DEF_SIZE 5 //初始容量 #define CRE_SIZE 2 //一次扩容的倍数 typedef int SLDataType; //将数据类型重命名为SLDataType typedef struct SeqList { SLDataType* data; //对应数据类型的指针，用来指向动态开辟的空间 size_t size; //记录当前有效数据的个数 size_t capacity; //记录当前容量，不够就增容 }SL; //函数的声明 //初始化顺序表 void SeqListInit(SL* psl); //在尾部插入数据 void SeqListPushBack(SL* psl, SLDataType x); //在头部插入数据 void SeqListPushFront(SL* psl, SLDataType x); //在尾部删除数据 void SeqListPopBack(SL* psl); //在头部删除数据 void SeqListPopFront(SL* psl); //在指定下标处插入数据 void SeqListInsert(SL* psl, size_t pos, SLDataType x); //在指定下标处删除数据 void SeqListErase(SL* psl, size_t pos); //查找数据 int SeqListFind(const SL* psl, SLDataType x); //修改指定位置数据 void SeqListModify(SL* psl, size_t pos, SLDataType x); //打印顺序表中的数据 void SeqListPrint(const SL* psl); //检查容量(增容) void CheckCapacity(SL* psl); //销毁顺序表 void SeqListDestory(SL* psl);
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
2、SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "SeqList.h" //初始化顺序表 void SeqListInit(SL* psl) { assert(psl); //断言：防止psl为空 psl->data = (SLDataType*)calloc(DEF_SIZE, sizeof(SLDataType)); //开辟默认大小的空间并初始化 if (psl == NULL) //判空 { perror("calloc fail"); //打印错误信息 return; } psl->size = 0; psl->capacity = DEF_SIZE; } //销毁顺序表 void SeqListDestory(SL* psl) { assert(psl); //断言：防止psl为空 free(psl->data); //释放（避免内存泄漏） psl->data = NULL; //置空（避免野指针） psl->size = 0; psl->capacity = 0; } //检查容量（增容） void CheckCapacity(SL* psl) { assert(psl); //断言：防止psl为空 if (psl->size == psl->capacity) //当数据个数和容量相等时扩容 { //将realloc的返回值交由一个临时变量保存，防止扩容失败丢失原来空间的地址 SLDataType* ptr = (SLDataType*)realloc(psl->data, psl->capacity * CRE_SIZE * sizeof(SLDataType)); if (ptr == NULL) //判空 { perror("realloc fail"); return; } psl->data = ptr; psl->capacity *= CRE_SIZE; //增加容量 } } //在尾部插入数据 void SeqListPushBack(SL* psl, SLDataType x) { assert(psl); SeqListInsert(psl, psl->size, x); //直接调用insert函数 //assert(psl); //判空 //CheckCapacity(psl); //检查容量 //psl->data[psl->size] = x; //插入数据 //psl->size++; } //在头部插入数据 void SeqListPushFront(SL* psl, SLDataType x) { assert(psl); SeqListInsert(psl, 0, x); //直接调用insert函数 //assert(psl); //判空 //CheckCapacity(psl); //检查容量 //int i = 0; //for (i = psl->size - 1; i >= 0; i--) //{ // psl->data[i + 1] = psl->data[i]; //将数据整体向后移 //} //psl->data[0] = x; //插入数据 //psl->size++; } //打印顺序表中的数据 void SeqListPrint(const SL* psl) { assert(psl); //判空 size_t i = 0; for (i = 0; i < psl->size; i++) { printf("%d ", psl->data[i]); } printf("\n"); } //在尾部删除数据 void SeqListPopBack(SL* psl) { assert(psl); SeqListErase(psl, psl->size - 1); //直接调用Erase函数 //assert(psl); //assert(psl->size); //psl->size--; //如果尾部有数据，直接让size--即可 } //在头部删除数据 void SeqListPopFront(SL* psl) { assert(psl); SeqListErase(psl, 0); //直接调用Erase函数 //assert(psl); //assert(psl->size); //size_t i = 0; //for (i = 0; i < psl->size - 1; i++) //{ // psl->data[i] = psl->data[i + 1]; //让表中的数据依次往前移 //} //psl->size--; } //查找数据 int SeqListFind(const SL* psl, SLDataType x) { assert(psl); int i = 0; for (i = 0; i < (int)psl->size; i++) { if (psl->data[i] == x) return i; //找到元素所在返回下标 } return -1; //找不到返回-1（一个无效下标） } //修改指定位置的数据 void SeqListModify(SL* psl, size_t pos, SLDataType x) { assert(psl); assert(pos < psl->size); //断言 psl->data[pos] = x; //修改数据 } //在指定下标处插入数据 void SeqListInsert(SL* psl, size_t pos, SLDataType x) { assert(psl); assert(pos <= psl->size); //断言 因为可能会在尾部插入数据，所以pos可以等于size CheckCapacity(psl); //检查容量 size_t end = psl->size; while (end > pos) //把pos及以后的数据向后挪动一位 { psl->data[end] = psl->data[end - 1]; --end; } psl->data[pos] = x; //插入数据 ++psl->size; } //在指定下标处删除数据 void SeqListErase(SL* psl, size_t pos) { assert(psl); assert(pos < psl->size); size_t i = 0; for (i = pos; i < psl->size - 1; i++) { psl->data[i] = psl->data[i + 1]; } psl->size--; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
3、test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "SeqList.h" void test1() //测试插入 { //初始化 SL sl; SeqListInit(&sl); //尾插 SeqListPushBack(&sl, 1); SeqListPushBack(&sl, 2); SeqListPushBack(&sl, 3); SeqListPushBack(&sl, 4); SeqListPrint(&sl); //头插 SeqListPushFront(&sl, 8); SeqListPushFront(&sl, 9); SeqListPushFront(&sl, 10); SeqListPrint(&sl); //在指定位置插入 SeqListInsert(&sl, 3, 6); SeqListInsert(&sl, 0, 6); SeqListInsert(&sl, 9, 6); SeqListPrint(&sl); //销毁 SeqListDestory(&sl); } void test2() //测试删除 { //初始化 SL sl; SeqListInit(&sl); //尾插 SeqListPushBack(&sl, 1); SeqListPushBack(&sl, 2); SeqListPushBack(&sl, 3); SeqListPushBack(&sl, 4); SeqListPrint(&sl); 尾删 //SeqListPopBack(&sl); //SeqListPopBack(&sl); //SeqListPopBack(&sl); //SeqListPrint(&sl); 头删 //SeqListPopFront(&sl); //SeqListPopFront(&sl); //SeqListPopFront(&sl); //SeqListPrint(&sl); //删除指定位置元素 SeqListErase(&sl, 3); SeqListPrint(&sl); SeqListErase(&sl, 1); SeqListPrint(&sl); SeqListErase(&sl, 0); SeqListPrint(&sl); //销毁 SeqListDestory(&sl); } void test3() //测试查和改 { //初始化 SL sl; SeqListInit(&sl); //尾插 SeqListPushBack(&sl, 1); SeqListPushBack(&sl, 2); SeqListPushBack(&sl, 3); SeqListPushBack(&sl, 4); SeqListPrint(&sl); //查找并修改 int find = 0; int modify = 0; do { scanf("%d", &find); //要查找的元素 scanf("%d", &modify); //要修改的值 int pos = SeqListFind(&sl, find); //查找该元素是否存在 if (pos != -1) { SeqListModify(&sl, pos, modify); //存在就修改 } SeqListPrint(&sl); } while (find != EOF); //销毁 SeqListDestory(&sl); } //测试函数 int main() { //test1(); //测试插入 //test2(); //测试删除 test3(); //测试查和改 return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
大家也可以去我的 Gitee 仓库中获取完整代码：SeqList/SeqList · 野猪佩奇/日常学习 - 码云 - 开源中国 (gitee.com)
五、顺序表的缺陷
顺序表存在如下缺陷：
- 在头部/中间的插入与删除需要挪动数据，时间复杂度为O(N)，效率低；
- 增容需要申请新空间，可能会拷贝数据，释放旧空间，会有不小的消耗；
- 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到 200，如果我们再继续插入了5个数据，后面没有数据插入了，那么会浪费95个数据空间；
针对顺序表存在的这些缺陷，我们设计出了链表。
六、顺序表力扣OJ题
1、移除元素
题目链接
题目描述
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
思路分析
思路1 – 循环遍历，挪动覆盖数据：遍历这个数组，每当遇见等于val的元素时，就将数组后面的元素整体向前挪动一位。
时间复杂度：O(N^2) 空间复杂度：O(1)。
思路2 – 遍历数组，挪动元素到新空间：开辟一个新的数组，然后遍历原来的数组，将不等于val的元素放入新开辟的数组中，将等于val的元素丢弃；最后让新开辟的数组覆盖掉原数组。
时间复杂度：O(N) 空间复杂度：O(N)。
思路3 -- 遍历数组，挪动覆盖数据（双指针解法）：定义两个指针src 和 dst，最开始都指向数组第一个元素，然后开始遍历数组；如果arr[src] != val，那么让arr[dst] = arr[src]，然后 src++，dst++；如果 arr[src]==val，则 src++，dst不动；这样一直往后遍历，知道把数组所有元素都遍历完。思路三代码实现
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; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
2、删除有序数组中的重复项
题目链接
26. 删除有序数组中的重复项 - 力扣（LeetCode）
题目描述
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
思路分析
这道题的解题思路和上面的移除元素十分相似，都是使用双指针；让 src 和 dst 都指向数组第一个元素，然后判断 arr[src] 和 arr[dst] 是否相等，如果相等，说明是重复元素，则让 src++，dst 不动；如果不相等，就让dst++，然后将 arr[src] 赋给 arr[dst]，再让 src++；然后一直往后遍历数组，直到将数组遍历完。
时间复杂度：O(N) 空间复杂度：O(1)
代码实现
int removeDuplicates(int* nums, int numsSize){ int src = 0; int dst = 0; while(src < numsSize) { if(nums[src] != nums[dst]) { nums[++dst] = nums[src++]; //注意：dst是前置++ } else { src++; } } return dst+1; //由于dst是前置++，所以返回值需要+1 （数组下标从0开始） }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
3、合并两个有序数组
题目链接
题目描述
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
思路分析
思路1：开辟新数组，并排序：我们可以将两个数组中的元素存放到一个新数组中，然后对数组中的元素进行排序，最后用新数组的数据覆盖掉原数组的数据。
时间复杂度：O((M+N)*log(M+N)) (使用qsort进行排序) 空间复杂度：O(1)。
思路2：开辟新数组，把数据有序的放入数组中（双指针法）：因为两个原数组都是有序的，所以我们可以用两个指针 src1 和 src2 分别指向两个数组，如果src1 指向的元素小于 src2，就把src1的数据放入新数组中然后通过比较大小的方式把数据依次放入新数组中，最后新数组的数据覆盖掉原数组的数据。
思路1代码实现
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){ int src1 = 0; int src2 = 0; int dst = 0; int* ret = (int*)calloc(m+n, sizeof(int)); while(src1<m && src2<n) //当达到其中一个数组末尾时停下 { if(nums1[src1] > nums2[src2]) //如果数组1中的元素大 { ret[dst++] = nums2[src2++]; //将2中的元素赋给新数组 } else { ret[dst++] = nums1[src1++]; //否则，将1中的元素赋给新数组 } } if(src1 < m) //如果1中的元素有剩余 { while(src1 < m) { ret[dst++] = nums1[src1++]; } } if(src2 < n) //如果2中的元素有剩余 { while(src2 < n) { ret[dst++] = nums2[src2++]; } } memcpy(nums1, ret, (m+n)*sizeof(int)); //将1数组中的数据覆盖 free(ret); ret = NULL; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
思路2代码实现
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){ int end1 = m - 1; //指向数组1最后一个有效数据 int end2 = n - 1; //指向数组2末尾 int end = m+n-1; //指向数组1末尾 while(end1 >=0 && end2 >= 0) //当其中一个数组遍历完成后循环结束 { if(nums1[end1] < nums2[end2]) //从后往前，需要找大的 { nums1[end--] = nums2[end2--]; } else { nums1[end--] = nums1[end1--]; } } //如果数组1中还有元素则不用管，因为它本来就是有序的； if(end2 >= 0) //如果数组2还有元素 { while(end2 >= 0) { nums1[end--] = nums2[end2--]; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
