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

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

数据结构是计算机存储、组织数据的方式。在工作中，我们通常会直接使用已经封装好的集合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中主要是测试功能，检查顺序表是否能正常使用。

输出结果如下：