C语言数据结构深入探索顺序表-C/C++开发

顺序表，全名顺序存储结构，是线性表的一种，线性表用于存储逻辑关系为“一对一”的数据，顺序表自然也不例外，不仅如此，顺序表对数据的物理存储结构也有要求，跟随下文来具体了解吧

2.2.1初始化
2.2.2 检查容量
2.2.3 顺序表打印
2.2.4 顺序表尾插
2.2.5 顺序表尾删
2.2.6 顺序表头插
2.2.7 顺序表头删
2.2.8 顺序表在pos位置插入x
2.2.9 顺序表删除pos位置的值
2.2.10 尾插、尾删、头插、头删的改进
2.2.11 顺序表查找
2.2.12 顺序表销毁

2.3 数组相关面试题

2.4 顺序表的问题及思考

1.线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储

IiBzcmM9

2.顺序表

2.1概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表一般可以分为：

静态顺序表：使用定长数组存储元素。

IiBzcmM9

动态顺序表：使用动态开辟的数组存储

IiBzcmM9

2.2 接口实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

#pragma once
#include<stdio.h>
#include<assert.h>
typedef int SLDataType;
typedef struct SeqList
{
	int* a;
	int size;	 //存储数据个数
	int capacity;//存储空间大小
}SeqList;

void SeqListInit(SeqList* psl);//初始化
void SeqListDestroy(SeqList* psl);//销毁

void SeqListPrint(SeqList* psl);//打印

void SeqListCheckCapacity(SeqList* psl);//检查容量

int SeqListFind(SeqList* psl, SLDataType x);//查找

//时间复杂度是O（1）
void SeqListPushBack(SeqList* psl, SLDataType x);//尾插
void SeqListPopBack(SeqList* psl);//尾删

//时间复杂度是O（N）
void SeqListPushFront(SeqList* psl, SLDataType x);//头插
void SeqListPopFront(SeqList* psl);//头删

//时间复杂度是O（N）
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);//在pos位置插入
void SeqListErase(SeqList* psl, size_t pos);//在pos位置删除

2.2.1初始化

就是将元素分别初始化。

//初始化
void SeqListInit(SeqList* psl)
{
	assert(psl);
	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;
}

2.2.2 检查容量

初始化时容量为0，想要放数据得增加容量，每次插入数据也得保证容量充足，为了方便，我们先写一个用于检查容量并增容的函数。

//检查容量
void SeqListCheckCapacity(SeqList* psl)
{
	assert(psl);

	//如果满了，就要扩容
	if (psl->size == psl->capacity)
	{
		size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;//防止一开始capacity=0无法*2增容
		SLDataType* tmp = realloc(psl->a, sizeof(SLDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			psl->a = tmp;
			psl->capacity = newCapacity;
		}
	}
}

2.2.3 顺序表打印

就是遍历一次把所有元素打印出来，这样可以检查函数写的是否正确，及时订正。

//打印
void SeqListPrint(SeqList* psl)
{
	assert(psl);

	for (int i = 0; i < psl->size; i++)
	{
		printf("%d ", psl->a[i]);
	}
	printf("\n");

}

2.2.4 顺序表尾插

//尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
	assert(psl);

	//如果满了，就要扩容
	SeqListCheckCapacity(psl);

	psl->a[psl->size] = x;
	psl->size++;
}

2.2.5 顺序表尾删

只需要把size-1这样的话下一个数据就会把尾部数据覆盖掉，达到删除的效果。

//尾删
void SeqListPopBack(SeqList* psl)
{
	assert(psl);

	if (psl->size > 0)
	{
		psl->size--;
	}
}

2.2.6 顺序表头插

IiBzcmM9

//头插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
	assert(psl);

	//如果满了，就要扩容
	SeqListCheckCapacity(psl);

	//挪动数据,腾出头部位置
	int end = psl->size - 1;
	while (end >= 0)
	{
		psl->a[end + 1] = psl->a[end];
		end--;
	}
	psl->a[0] = x;
	psl->size++;

}

2.2.7 顺序表头删

将第一个位置覆盖掉，然后用尾删的思路将最后一个数据删除。

IiBzcmM9


//头删
void SeqListPopFront(SeqList* psl)
{
	assert(psl);

	//挪动数据覆盖第一个
	if(psl->size>0)
	{
		int begin = 1;
		while (begin < psl->size)
		{
			psl->a[begin - 1] = psl->a[begin];
			begin++;
		}
	}
	psl->size--;
}

2.2.8 顺序表在pos位置插入x

思路跟头插很像,但内含陷阱！

//在pos位置插入
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);

	//如果满了，就要扩容
	SeqListCheckCapacity(psl);

	温和检测
	//if (pos > psl->size)
	//{
	//	printf("pos越界：%d\n", pos);
	//	return;
	/