数据结构【顺序表】

1.线性表

线性表是n个具有相同特性数据元素的有限序列，线性表是一种在实际中广泛使用的数据结构，常见的线性表有：顺序表，链表，栈，队列，字符串……
线性表在逻辑结构上是线性的，但在物理结构上不一定是连续的，线性表在物理结构上存储时，通常以数组和链式结构的形式存储。

2.顺序表

2.1定义与结构

定义：顺序表是一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。

顺序表和数组的区别：
顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接口。

2.2分类

2.2.1静态顺序表

定义：使用定长数组存储数据

//静态顺序表
typedef int SLDataType;
#define N 7
typedef struct SeqList
{
	SLDataType a[N];    //定长数组
	int size;          //有效数据个数
}SL;

静态顺序表缺陷：空间给少了不够用，给多了造成空间浪费。

2.2.2动态顺序表

typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* a;
	int size;          //有效数据个数
	int capacity;     //空间容量
};

动态顺序表可增容，malloc,realloc,calloc。
详细见https://blog.csdn.net/2401_84320036/article/details/146455486?spm=1001.2014.3001.5502

2.3动态顺序表的实现

#define INIT_CAPACITY 4
typedef int SLDataType;
// 动态顺序表 -- 按需申请
typedef struct SeqList
{
	SLDataType* a;
	int size; // 有效数据个数
	int capacity; // 空间容量
}SL;
//初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);
//扩容
void SLCheckCapacity(SL* ps);
//头部插⼊删除 / 尾部插⼊删除
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);
//指定位置之前插⼊/删除数据
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
int SLFind(SL* ps, SLDataType x);

附：轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

• 思路一：

void rorate(int *nums,int numsSize,int k)
{
	while (k--)
	{
		int end = nums[numsSize - 1];
		for (int i = numsSize - 1; i > 0; i--)
		{
			nums[i] = nums[i - 1];
		}
		end = nums[0];
	}
}

时间复杂度O(n²)
空间复杂度O(1)

• 思路二：

void rorate(int* nums, int numsSize, int k)
{
	
	int newArr[numsize];
	for (int i = 0; i < numsSize - 1; i++)
	{
		newArr[(i + k) % numsSize] =nums[i];
	}
	for (int i = 0; i < numsSize - 1; i++)
	{
		nums[i] = newArr[i];
	}
}

时间复杂度O(n)
空间复杂度O(n)

• 思路三：

三次逆置

void reverse(int *nums,int begin,int end)
{
	while (begin < end)
	{
		int tmp = nums[begin];
		nums[begin] =nums[end];
		nums[end] = tmp;
		begin++;
		end--;
	}
}
void rorate(int* nums, int numsSize, int k)
{
	reverse(nums,numsSize-k,numsSize-1);
	reverse(nums, 0, numsSize - k - 1);
	reverse(nums, nums, 0, numsSize - 1);
}

时间复杂度O(n)
空间复杂度O(1)
总结：第三个算法效率最高。