【数据结构】：顺序表专题

前言：今天我们开始介绍数据结构有关内容，那么数据结构是什么呢？

数据结构是计算机存储、组织数据的方式。在工作中，我们通常会直接使用已经封装好的集合API(应用程序编程接口)，这样可以更高效地完成任务。但是作为一名程序员，掌握数据结构是非常重要的，因为它可以帮助我们更好地理解和设计算法，从而提高程序的效率和可靠性。

一.🐶常见数据结构分类：

二.顺序表概述：

（一）：何为顺序表？

本篇将介绍线性数据结构中的顺序表专题（Sequence List），其本质就是数组。

一句话总结顺序表：顺序表就是经过封装后提供了许多现成方法的一种数据结构，其底层是数组。

那已经有了数组，为什么还需要顺序表呢？

当我们需要对数组中的某些数据进行处理（包括增删查改等），此时我们需要找到数组中有元素个数，再通过循环或其他方式插入，删除数据。这样以来就十分麻烦，而顺序表就方便解决了这些问题。

此外，顺序表是线性表的一种。

顺序表的特性：物理结构是连续的，逻辑结构一定是连续的。

（物理结构：数据在内存上是连续存储的，是硬件层面上的；逻辑结构：数据按某种逻辑排序，有迹可循，是抽象意义上的）

（二）顺序表的分类：

试想我们如何写一个顺序表，我们知道顺序表本质是数组，那么对于数组我们有定长数组和动态内存开辟数组：

int arr[10]={0}:定长的数组

int* arr:动态内存开辟的数组，确定大小之后再去动态申请

那么对于顺序表也应该分为两种情况，分为静态顺序表和动态顺序表：

//静态顺序表定义：
struct Seqlist
{
	int arr[100];//定长的数组
	int size;//顺序表当前有效的数据个数
};

//动态顺序表：
struct SeqList
{
	int* arr;
	int size;//有效数据个数
	int capacity;//空间大小
};

那么哪一种方式更好呢？不难理解当然是动态顺序表更胜一筹，对于静态顺序表，其中的数组是定长的，数组大小给小了，空间不够用；数组给大了，空间又浪费了。极不方便，而动态顺序表由于可以动态增容，因而我们选择这种实现方式。

三.顺序表的实现

接下来我们将就如何实现一个顺序表具体讲解，作为一个项目而言，代码量是庞大的，所以我们要创建多个文件，方便我们流畅地实现一个结构清晰的代码，我们需要创建三个文件：

test.c：主文件，也是测试文件；

Seqlist.c:顺序表主体，具体功能实现；

Seqlist.h:顺序表头文件，声明顺序表的结构，方法等。

1.Seqlist.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//我们选择动态顺序表

//存储的数据我们不能仅仅是int，还需要其他类型
typedef int SLDataType;
//当对应数据类型改变时，我们只需改变int，换成所需数据类型即可
//typedef struct Seqlist SL;

typedef struct Seqlist
{
	SLDataType* arr;
	int size;//有效数据个数
	int capacity;//空间大小
}SL;

//顺序表的初始化
void SLInit(SL* ps);

//容量检查
void SLCheckCapacity(SL* ps);

//头部插入删除/尾部插入删除
//尾插/头插
void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);

//尾删/头删
void SLPopBack(SL* ps);
void SLPopFront(SL* ps);

//顺序表的销毁
void SLDestroy(SL* ps);

//打印调试
void SLPrint(SL s);

在Seqlist.h中包含着顺序表的结构以及顺序表中需要实现的函数的声明。

在实现顺序表的声明中我们的思路如下：1.选择合适的顺序表结构——动态顺序表；2.使用typedef拓展数据变量以及简化顺序表名称；3.依次声明实现不同功能的各部分函数。

2.Seqlist.c

#include"Seqlist.h"
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

void SLCheckCapacity(SL* ps)
{
	//插入之前先看空间够不够
	if (ps->capacity == ps->size)
	{
		//申请空间
		//malloc calloc realloc  int arr[100] --->增容：realloc
		//第一个问题：要申请多大的空间/一次增容多大？ 答案：一般两倍增容
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(int));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);//直接退出，程序不再继续执行
		}
		//空间申请成功
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
}

void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	/*ps->arr[ps->size] = x;
	++ps->size;*/
	ps->arr[ps->size++] = x;
}

void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	for (int i = ps->size;i > 0;i--)
	{
		ps->arr[i] = ps->arr[i - 1];//arr[1]=arr[0]
	}
	ps->arr[0] = x;
	ps->size++;
}

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

void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);
	for (int i = 0;i <ps->size-1 ;i++)
	{
		ps->arr[i] = ps->arr[i + 1];//arr[size-2]=arr[size-1]
	}
	--ps->size;
}

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

void SLPrint(SL s)
{
	for (int i = 0;i <s.size;i++)
	{
		printf("%d ", s.arr[i]);
	}
	printf("\n");
}

在Seqlist.c 中主要是具体实现Seqlist.h中声明的各函数，顺序最好按声明的顺序来，方便查找。

切记还要包含头文件"Seqlist,h”。

3.test.c

#include"Seqlist.h"

void SLTest01()
{
	SL sl;
	//SLInit(sl);
	//形参是实参的一份临时拷贝，都没有初始化，拷贝不过去
	SLInit(&sl);//传址
	//增删查找
	//尾插
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPrint(sl);
    //头插
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPrint(sl);
	SLPushFront(&sl, 5);
	SLPushFront(&sl, 6);
	SLPrint(sl);
    //头删
	SLPopFront(&sl);
	SLPopFront(&sl);
	SLPrint(sl);
    //尾删
	SLPopBack(&sl);
	SLPopBack(&sl);
	SLPrint(sl);
	SLDestroy(&sl);//销毁
}

int main()
{
	SLTest01();
	return 0;
}

在test.c中主要是测试功能，检查顺序表是否能正常使用。

输出结果如下：