网站导航
> 文章列表 > 顺序表（数据结构）

顺序表（数据结构）

网友: 文章列表 2024-03-21 20:57:22

顺序表（数据结构）

1、线性表

概念：线性表是n个具有相同特性的数据元素的有限序列！

使用性：线性表是实际当中广泛使用的数据结构！

常见的线性表：顺序表、链表、栈、队列、字符串 等……

2、顺序表

概念：

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

结构：

1、静态顺序表：

使用定长数组来存储元素。也就是给数组指定的大小，来存储数组，但是有一个弊端，空间不知道给多大，给小了不够，给大了浪费，不建议写这类结构的顺序表！

2、动态顺序表：

使用动态开辟的数组来存储。就是用动态申请空间，通过一个指针来访问该空间，此时有一个好处，我们想要多大的空间就开多大的空间，空间不够还可以扩容，用多少开多少，比较静态顺序表，解决了空间不够，以及空间浪费的问题。比较推荐这类结构写顺序表！

本章将选择动态顺序表的结构形式往下写

1>顺序表创建

静态顺序表：指定数组大小

动态顺序表：动态开辟空间

定义：

我们首先定义一个结构体，让结构体里面存放一个数组（动态顺序表里存的是指向数组的指针），再存放一个整型变量，用来记录在数组种存放有效数据的个数！再通过typedef关键字，将这个结构体进行重命名操作！

代码：

//创建静态顺序表结构（不推荐这样写）//用typedef重命名一下类型，
//后续我们需要放什么类型只需要改这一处即可
typedef int SLDateType;
#define N 100
typedef struct SeqList
{SLDateType a[N];//存放数据数组int size;//有效数据的个数
}SL;//创建动态顺序表结构（推荐）//用typedef重命名一下类型，
//后续我们需要放什么类型只需要改这一处即可
typedef int SLDateType;//创建结构体，用动态增容的方式来控制空间
typedef struct SeqList
{SLDateType* a;//指向空间的指针int size;//有效数据的个数int capacity;//容量
}SL;SL sl;//定义全局结构体变量以便我们进行操作

2>初始化操作

思路：

对于动态的顺序表结构，在初始化的时候需要动态申请一部分空间，让结构中的指针指向申请的空间。在申请的时候我们采用calloc函数来申请空间，因为calloc函数在动态开辟空间的时候会将空间中每个字节的内容都自动初始化为0，也就不需要我们自己再进行空间初始化了。开辟空间完成之后，将记录有效数据元素个数的整型变量初始化为0，再将记录空间个数的变量初始化成我们所开辟的空间个数即可！

在传函数参数的时候我们传的是结构体变量的地址，便于操作！

代码：

//结构体指针可通过->操作符，访问到结构体成员
#define IN 4//初始化
void SLInit(SL* ps)
{//进行动态开辟空间，让指针指向空间ps->a = (SLDateType*)calloc(IN, sizeof(SLDateType));//判断空间是否开辟成功if (ps->a = NULL){prerror("calloc fail:");//提示失败错误return;}//初始化有效数据个数ps->size = 0;//初始化容量ps->capacity = IN;
}

3>扩容操作

思路：

当我们在往数组里装数据的时候，当我们一开始开辟的空间被装满了的情况下，我们就得对该空间进行扩容操作，扩容的时候用ralloc函数来进行扩容，每次增大多少容量呢，这是由自己掌控的，我们每次在原空间的基础上两倍两倍的来进行扩容操作。扩容完成之后让指针指向扩容后的空间，也让记录空间容量增加相同的倍数！

代码：

#define IT 2//判断是否扩容
void SLCheckCapacity(SL* ps)
{//断言指针assert(ps);//当有效数据个数等于容量的时候进行扩容if (ps->size == ps->capacity){//扩容SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * ps->capacity * IT);//判断是否开辟成功if (NULL == tmp){perror("ralloc fail:");//提示失败信息return;}//扩容成功，让指针指向该空间ps->a = tmp;//让记录容量的变量增加ps->capacity *= IT;}
}

4>尾插操作

思路：

尾插，顾名思义就是在最后插入数据。在顺序表中尾插，就是在数组的最后一个元素后面插入一个数据，我们知道结构体里面有一个记录有效数据元素个数的变量，也就是数组元素的个数，数组元素的个数恰好是数组最后一个元素的下一个位置的下标。所以尾插的时候我们直接用记录元素个数的变量做为下标放入数据即可。放入之后，让记录元素个数的变量+1即可！但是在插入的时候我们还得关心我们开辟的空间是否够用？够用的情况下我们继续插入。不够用的情况下，我们就要进行扩容了。所以在插入的时候我们得先判断一下是否需要扩容。需要扩容，我们要先扩容再插入数据，不需要就直接插入数据！

代码：

//尾插
void SLPushBank(SL* ps, SLDateType x)
{//x是要插入的数据assert(ps);//断言一下指针是否为NULL//是否要扩容SLCheckCapacity(ps);//进行尾插ps->a[ps->size] = x;//记录元素的个数增加1ps->size++;
}

5>尾删操作

思路：

尾删，顾名思义就是将数组最后一个元素删除。要删除最后一个元素，直接将记录有效数据元素个数的变量-1即可，顺便将那个位置的数据改为0！但在删除的时候我们得注意一下数组中的数据是否删完了，如果删完了我们是不能进行删除的。会导致数组越界问题！

注意：

因为我们无法正真的去将最后一个元素所占的空间去释放，动态内存管理中是不允许释放连续空间中的某一部分空间的！用realloc函数去改变空间大小也是不行的，realloc函数是不支持空间缩容的，它要缩，只是缩了我们对空间的使用权！并没有将空间释放！所以我们只能通过这种减小有效数据个数来实现删除操作！

代码：

//尾删
void SLPopBank(SL* ps)
{//断言指针assert(ps);//判断数据是否删完了if (ps->size == 0){printf("没有数据可删\\n");return;}//将要删除位置的数据改为0ps->a[ps->size - 1] = 0;//删除数据，让有效数据个数减少即可ps->size--;
}

6>头插

思路：

头插，顾名思义就是在数组的首位置插入一个元素，要在首位置插入元素，就要将数组中的每一个元素都往后移动一位，把首位置空出来，插入数据！插入数据的时候需要判断空间够不够，不够需要进行增容操作。随后让记录有效数据个数的变量+1即可！

代码：

//头插
void SLPushFont(SL* ps, SLDateType x)
{//x是要插入的数据//断言指针assert(ps);//是否要增容SLCheckCapacity(ps);//开始移动数据，让每个数据都往后移动一位int end = ps->size;while (end > 0){ps->a[end] = ps->a[end - 1];--end;}//头插数据ps->a[0] = x;//记录个数ps->size++;
}
网络标签：

相关问题