（数据结构）线性表（上）：SeqList 顺序表

基本了解

线性表

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

顺序表

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

静态顺序表

优点：一次性开辟空间
缺点：不可改动，当数据量变化时，空间给大了会造成浪费，空间给小了容易导致数据丢失等问题。

typedef int SLDataType;
#define N 7
typedef struct SeqList {SLDataType arr[N];//定长数组int size;		//有效数据个数int capacity;	//空间大小
}SL;

动态顺序表

优点：灵活可改动，随时可扩容

typedef int SLDataType;
typedef struct SeqList {SLDataType* arr;//动态顺序表，定义动态数组int size;		//有效数据个数int capacity;	//空间大小
}SL;

增容的一般逻辑：

编写动态顺序表

项目结构

SeqList
├── SeqList.h	# 头文件：定义结构、声明
函数
├── SeqList.c	# 实现文件：函数具体实现└── test.c		# 测试文件：每写一个功能以后都要测试一下

基础结构

SeqLIst.h 中

typedef int SLDataType;
typedef struct SeqList {SLDataType* arr;//动态顺序表，定义动态数组int size;		//有效数据个数int capacity;	//空间大小
}SL;

初始化

这里有一个易错点提醒：函数传参时一定要思考是要传值还是传址，只有传址，函数改动的才是传过去的变量本身！
比如如果初始化函数这么写

void SLInit(SL s) {s.arr = NULL;s.size = s.capacity = 0;
}

测试

void test01() {SL sl;SLInit(sl);
}int main() {test01();return 0;
}

此时就会报这样的错误，为什么呢？
因为传值传参，函数中形参是实参的拷贝，但sl是未初始化的变量，所以这个值拷贝无法完成，自然就会报错了

所以注意此处进行传址调用

void SLInit(SL* ps) {ps->arr = NULL;ps->size = ps->capacity = 0;
}

void test01() {SL sl;SLInit(&sl); //注意这里要传地址
}int main() {test01();return 0;
}

尾插

注释中标明了易错的步骤和知识重点

void SLPushBack(SL* ps, SLDataType x) {//尾插前先判断顺序表是否仍有位置插入if (ps->size == ps->capacity) {ps->capacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//避免一开始capacity==0，做乘法以后仍为0出现问题SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) *ps->capacity*2);//用临时指针接收realloc的返回值，防止扩容失败返回NULL，导致影响顺序表的存储//注意realloc第二个参数单位是字节，扩容至原capacity的两倍时，别忘了要乘上SLDataType的字节大小//realloc扩容逻辑：能就地扩就就地扩；不能就另找一块（malloc新的内存块）、拷贝（memcpy）、释放旧块（free）if (tmp == NULL) {perror("realloc fail!");//会在输出里变成realloc fail!: Cannot allocate memoryexit(1);//直接退出程序}ps->arr = tmp;}//尾插操作，可以画图思考，发现size大小实时对应尾插的位置，不需要额外遍历//记得自增size！ps->arr[ps->size++] = x;
}

测试

//测试尾插
void test02() {SL sl;SLInit(&sl);SLPushBack(&sl,1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPushBack(&sl, 5);
}
int main() {test02();return 0;
}

时间复杂度为O(n)

头插

判满——将数据向右挪动（从右往左依次挪！）——把新数据放到头部

判满操作是在多个功能中都需要使用到的，所以这里我们把它单独分出来

//判满扩容操作
void SLCheckCapacity(SL* ps) {if (ps->size == ps->capacity) {ps->capacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//避免一开始capacity==0，做乘法以后仍为0出现问题SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * ps->capacity * 2);//用临时指针接收realloc的返回值，防止扩容失败返回NULL，导致影响顺序表的存储//注意realloc第二个参数单位是字节，扩容至原capacity的两倍时，别忘了要乘上SLDataType的字节大小//realloc扩容逻辑：能就地扩就就地扩；不能就另找一块（malloc新的内存块）、拷贝（memcpy）、释放旧块（free）if (tmp == NULL) {perror("realloc fail!");//会在输出里变成realloc fail!: Cannot allocate memoryexit(1);//直接退出程序}ps->arr = tmp;}
}

void SLPushHead(SL* ps, SLDataType x) {//检查一下ps，如果传入了空指针会导致程序直接报错////比较温和的方法//if (ps == NULL)//	return;//比较粗暴的方法：使用断言语句assert(ps);//等价于assert(ps!=NULL)SLCheckCapacity(ps);for (int i = ps->size - 1;i >= 0;i--) {ps->arr[i + 1] = ps->arr[i];}ps->arr[0] = x;
}

时间复杂度为O(n)

尾删

特殊条件：顺序表不能为空
操作：有效数据个数size–，原来的数据不做处理也没有关系

void SLPopBack(SL* ps) {assert(ps && ps->size);ps->size--;
}

时间复杂度O(1)

头删

特殊条件：顺序表不能为空
操作：

1. 让数组从左到右往左移一位（覆盖）
2. 有效数据个数size–，原来的数据不做处理也没有关系

void SLPopHead(SL* ps) {assert(ps && ps->size);for (int i = 1;i < ps->size;i++) {ps->arr[i - 1] = ps->arr[i];}ps->size--;
}

时间复杂度O(n)

查找

设定找到了返回下标，未找到返回-1

int SLFind(SL ps, SLDataType x) {for (int i = 0;i < ps.size;i++) {if (ps.arr[i] == x)return i;//找到了就返回位置}//会运行到这一定是没有找到return -1;
}

指定位置pos之前插入数据

在指定位置pos之前插入数据，实际上新数据就放在pos位置
特殊条件:插入都要判断空间够不够，删除都要判空
且pos有限制范围pos>=0&&pos<=size
核心操作：pos之后的数据向右挪动一位（从右往左挪）

//指定位置前插入
void SLInsert(SL* ps, int pos, SLDataType x) {assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);//插入都要判断一下！for (int i = ps->size;i > pos;i--) {ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}

删除指定位置pos的数据

特殊条件：删除都要判空，且pos有限制范围pos>=0&&pos<=size
核心操作：pos之后的数据向左挪动一位（从左往右往左挪）

//指定位置删除数据
void SLErase(SL* ps, int pos) {assert(ps&&ps->size);assert(pos >= 0 && pos <= ps->size);for (int i = pos;i < ps->size-1;i++) {ps->arr[i] = ps->arr[i + 1];}ps->size--;
}

销毁

//销毁
void SLDesTroy(SL* ps) {if (ps->arr) {//即arr非空free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}

完整代码

SeqLIst.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataType;
typedef struct SeqList {SLDataType* arr;//动态顺序表，定义动态数组int size;		//有效数据个数int capacity;	//空间大小
}SL;//初始化
void SLInit(SL* ps);//尾插
void SLPushBack(SL* ps, SLDataType x);//头插
void SLPushHead(SL* ps, SLDataType x);//尾删
void SLPopBack(SL* ps);//头删
void SLPopHead(SL* ps);//查找
int SLFind(SL ps, SLDataType x);//指定位置前插入
void SLInsert(SL* ps, int pos, SLDataType x);//指定位置删除
void SLErase(SL* ps, int pos);//销毁
void SLDesTroy(SL* ps);

SeqLIst.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"//初始化
void SLInit(SL* ps) {ps->arr = NULL;ps->size = ps->capacity = 0;
}//判满扩容操作
void SLCheckCapacity(SL* ps) {if (ps->size == ps->capacity) {ps->capacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//避免一开始capacity==0，做乘法以后仍为0出现问题SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * ps->capacity * 2);//用临时指针接收realloc的返回值，防止扩容失败返回NULL，导致影响顺序表的存储//注意realloc第二个参数单位是字节，扩容至原capacity的两倍时，别忘了要乘上SLDataType的字节大小//realloc扩容逻辑：能就地扩就就地扩；不能就另找一块（malloc新的内存块）、拷贝（memcpy）、释放旧块（free）if (tmp == NULL) {perror("realloc fail!");//会在输出里变成realloc fail!: Cannot allocate memoryexit(1);//直接退出程序}ps->arr = tmp;}
}
//尾插
void SLPushBack(SL* ps, SLDataType x) {SLCheckCapacity(ps);//尾插操作，可以画图思考，发现size大小实时对应尾插的位置，不需要额外遍历//记得自增size！ps->arr[ps->size++] = x;
}//头插
void SLPushHead(SL* ps, SLDataType x) {//检查一下ps，如果传入了空指针会导致程序直接报错////比较温和的方法//if (ps == NULL)//	return;//比较粗暴的方法：使用断言语句assert(ps);//等价于assert(ps!=NULL)SLCheckCapacity(ps);for (int i = ps->size - 1;i >= 0;i--) {ps->arr[i + 1] = ps->arr[i];}ps->arr[0] = x;//记得自增size！ps->size++;
}//尾删
void SLPopBack(SL* ps) {assert(ps && ps->size);ps->size--;
}//头删
void SLPopHead(SL* ps) {assert(ps && ps->size);for (int i = 1;i < ps->size;i++) {ps->arr[i - 1] = ps->arr[i];}ps->size--;
}//查找
int SLFind(SL ps, SLDataType x) {for (int i = 0;i < ps.size;i++) {if (ps.arr[i] == x)return i;//找到了就返回位置}//会运行到这一定是没有找到return -1;
}//指定位置前插入
void SLInsert(SL* ps, int pos, SLDataType x) {assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);//插入都要判断一下！for (int i = ps->size;i > pos;i--) {ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}//指定位置删除数据
void SLErase(SL* ps, int pos) {assert(ps&&ps->size);assert(pos >= 0 && pos <= ps->size);for (int i = pos;i < ps->size-1;i++) {ps->arr[i] = ps->arr[i + 1];}ps->size--;
}//销毁
void SLDesTroy(SL* ps) {if (ps->arr) {//即arr非空free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"//测试初始化
void test01() {SL sl;SLInit(&sl);
}void test02() {SL sl;SLInit(&sl);//SLPushBack(&sl, 1);//SLPushBack(&sl, 2);//SLPushBack(&sl, 3);//SLPushBack(&sl, 4);//SLPushBack(&sl, 5);SLPushHead(&sl, 1);SLPushHead(&sl, 2);SLPushHead(&sl, 3);SLPushHead(&sl, 4);SLPushHead(&sl, 5);/*for (int i = 0;i < sl.size;i++) {printf("%d ", sl.arr[i]);}printf("\n");SLPopHead(&sl);for (int i = 0;i < sl.size;i++) {printf("%d ", sl.arr[i]);}printf("\n");SLPopBack(&sl);for (int i = 0;i < sl.size;i++) {printf("%d ", sl.arr[i]);}printf("\n");*///测试findSLErase(&sl, 2);for (int i = 0;i < sl.size;i++) {printf("%d ", sl.arr[i]);}printf("\n");SLInsert(&sl, 2, 7);for (int i = 0;i < sl.size;i++) {printf("%d ", sl.arr[i]);}printf("\n");
}int main() {test02();return 0;
}

算法题

移除元素

本题首先要审题，弄明白评测需要什么

1. 返回非val的值的个数
2. 修改nums，使它的前k个数必须是非val的值（顺序不变），后面的数不管。
   
   新数组法：创建一个与nums长度相同的新数组，只选取不等于val的值存储进去，同时进行计数。再将新数组遍历赋回给nums。（之前也说过，这个方法是以空间换时间的方法）
   双“指针”法
   简述思路：记录两个下标，一个负责探路，一个负责存储和计数，一次遍历中两个下标同时发挥其作用。
   

int removeElement(int* nums, int numsSize, int val) {int src=0,dst=0;while(src<numsSize){if(nums[src]!=val){nums[dst]=nums[src];dst++;}src++;}return dst;
}

删除有序数组中的重复项

https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/

注意题目强调有序数组，这意味着重复项都在一起，要利用好这个特性。
新数组法
创建一个与nums长度相同的新数组，只选取符合条件的数字进去，再将新数组遍历赋回给nums。
双"指针"法
画图思考让思路更清晰！
依然是src负责读取数据，dst负责录入数据和返回数据数量
想象src在数组上面走，dst在数组下面走。

int removeDuplicates(int* nums, int numsSize) {int src=1,dst=0;//因为第一个元素一定算数，所以src可以从1开始走while(src<numsSize){if(nums[src]!=nums[dst]){nums[++dst]=nums[src];}src++;}return dst+1;
}

这个代码还可以做进一步优化，减少没必要的赋值操作：
当nums[src]!=nums[dst]时，如果src只比dst小1， nums[++dst]=nums[src];就相当于这个值自己给自己赋了，所以我们可以据此对代码进一步优化。

int removeDuplicates(int* nums, int numsSize) {int src=1,dst=0;//因为第一个元素一定算数，所以src可以从1开始走while(src<numsSize){if(nums[src]!=nums[dst]&&++dst!=src){nums[dst]=nums[src];}src++;}return dst+1;
}