数据结构入门篇 之 【顺序表】的实现讲解(附完整实现代码)
阿里!阿里巴巴!我要进阿里巴巴研发5G!
一.顺序表
1.顺序表的作用
2.顺序表和数组的区别
3.顺序表的分类
4.动态顺序表的实现
1).分装文件
2).定动态顺序表
3).初始化变量函数SLInit
4).数据管理函数头插和尾插和扩容函数
5).头删SLPopBack和尾删SLPopFront函数
6).指定位置 插入/删除 函数 SLInsert/SLErase
7).查找函数SLFind
8).销毁函数SLDestory
二.完整实现代码
三.完结撒❀
前言
在开始讲解之前先问大家几个问题:
1、什么是数据结构? | |
---|---|
2、我们为什么要学习数据结构? | |
3、学习数据结构我们需要掌握哪些知识? |
–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–
1.什么是数据结构?
其实数组就是一个数据结构。
数据结构是由“数据”和“结构”两词组织而来的。
什么是数据?
常见的数值有1、2、3、4…、教务系统里保存的用户信息(姓名、性别、年龄、学历等等)、网页里肉眼可以看到的信息(文字、图片、视频等等),这些都是数据。
什么是结构?
当我们想要大量使用同一类型数据时,通过手动定义大量的独立变量对于程序来说,可读性非常差,我们可以借助数组这样的数据结构将大量的数据组织在一起,结构也可以理解为组织数据的方式。
举个例子:
假如在草原上的羊群里:
你想找到名叫“咩咩”的羊很难,但是在羊圈里的话:
要找到编号为1的羊就很简单,羊圈这种结构有效的将羊群组织了起来。
数据结构的概念:
数据结构是计算机存储,组织数据的方式。数据结构是指互相之间存在一种或多种特定关系的数据元素的合集。数据结构反映数据的内部构成,即数据由那部分构成,以什么方式构成,以及数据元素之间呈现的结构。
总结:
1)能够存储数据(如顺序表、链表等结构)
2)存储的数据能够方便查找
2.我们为什么要学习数据结构?
这里再给大家举个例子:
就比如我们在买饭的时候,如果不借助排队来管理客户,那么会导致客户就餐体验差,餐厅营业混乱等恶略情况。同理,如果程序中的数据不能进行有效的管理,可能会导致数据丢失,操作数据困难、野指针等情况。
而通过数据结构,我们就可以很好的将数据进行管理。按照我们的方式任意对数据进行增删改查等操作。
最基础的数据结构是:数组。
假设有一个10个空间的数组,已经使用了5个,向数组中插入数据步骤:
求数组的长度,数组的有效数据个数,向下标为有效数据的数据位置插入数据(这里还要判断数组是否满了,满了的话还能继续插入吗?)
所以最基础的数据结构能够提供的操作已经不能完全满足复杂算法的实现。
3.学习数据结构我们需要掌握那些知识?
我们至少需要掌握结构体,指针(一级指针、二级指针、指针传参)、结构体指针、动态内存管理,这些知识才能学习数据结构。
下面就进入顺序表的讲解。
一.顺序表
1.顺序表的作用
我们之所以实现顺序表,作用就是想要按照我们定义的方式,任意的去对数据进行增删改查的操作,目的在于可以更好的管理所存储的数据,比如我们手机上都有的通讯录,其就可以用顺序表来进行实现。(在下一篇博客中我会为大家讲解通讯录的实现)
2.顺序表和数组的区别
顺序表的底层结构是数组,对数组的封装,实现了常用的增删改查等接口。 |
---|
3.顺序表的分类
顺序表分为:静态顺序表和动态顺序表
静态顺序表:
所谓静态顺序表就是使用的是给定长度的数组用来存储数据。下面代码就是静态顺序表(这里以储存管理int类型为例):
#define N 7
typedef int SLDataList;
typedef struct SeqList
{
SLDataList arr[N];//定长数组
int size;//有效数据个数
}SL;
代码讲解:
可以看到使用上面静态顺序表来管理数据的话,其基于数组arr来实现,并且长度为固定的7个整形,size表示arr数组里所存储的有效数据个数(真是存放数据的个数),这里可能有人会问,第二行为什么要把int 变成 SLDataList来进行使用呢?因为我们在完成所有代码的编写之后,在以后的使用中,我们进行管路的可能并不是ing类型,而在这里将int转换成SLDataList的话,如果在以后要管理比如char类型,直接在typedef后面将int该成char即可,所以第二行代码的使用增强了整体代码的健壮性。
**静态顺序表的缺陷:**空间给少了不够用,给多了会造成空间浪费。
如果我们给定的空间不足以存放我们的数据,这可能导致数据丢失,这在工作中是非常严重的技术,所以我们一般不推荐使用静态顺序表,而是使用动态顺序表。
动态顺序表:
特点:按需申请。
//动态顺序表
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* arr;//储存数据的底层结构
int capacity;//记录顺序表的空间大小
int size;//记录顺序表当前有效的数据个数
}SL;
上面就是动态顺序表,与静态顺序表一样,都是在结构体内包含所需要的变量。
代码讲解:
这里与静态顺序表相比用来存储数据的底层结构是一个整形指针arr(学习过我讲的“柔性数组”那一片博客的同学可能已经知道使用的方法了),并且还多出来一个变量capacity,因为静态顺序表的空间大小是固定的,而动态顺序表的空间大小是可以增容扩大的,所以在动态顺序表里面也必然需要一个变量来表示空间的总大小。
**动态顺序表的优点:**按需申请空间,使用灵活。
4.动态顺序表的实现
我们讲解动态顺序表的实现(静态顺序表相较于动态顺序表简单,并且实现是一个逻辑)
1).分装文件
对于动态顺序表的实现我们采用分装文件的方法给大家进行讲解。
在VS中创建一个新项目,打开视图,新建一个头文件SeqList.h里面完成定义顺序表的结构,顺序表要实现的接口/方法,再建两个源文件SeqList.c和test.c分别是实现文件和测试文件,在实现文件中是具体实现顺序表的方法,在测试文件中进行测试顺序表,检查是否存在BUG。
2).定动态顺序表
这一步就是在头文件SeqList.h中将动态顺序表定义出来,并将一般过程中会使用的头文件写入SeqList.h中去,在测试文件和实现文件中引入头文件SeqList.h。
SeqList.h:
#include <stdio.h>
#include <stdlib.h>
//动态顺序表
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* arr;//储存数据的底层结构
int capacity;//记录顺序表的空间大小
int size;//记录顺序表当前有效的数据个数
}SL;
3).初始化变量函数SLInit
定义了动态顺序表之后我们要创建相应的结构体变量的话需要先对其进行初始化操作,所以我们在头文件中声明初始化函数,在实现文件中进行实现,代码如下:
SeqList.h:
#include <stdio.h>
#include <stdlib.h>
//动态顺序表
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* arr;//储存数据的底层结构
int capacity;//记录顺序表的空间大小
int size;//记录顺序表当前有效的数据个数
}SL;
//初始化变量
void SLInit(SL* ps);
SeqList.c:
#include "SeqList.h"
void SLInit(SL* ps)
{
ps->arr = NULL;
ps->capacity = ps->size = 0;
}
我才有人会问:为什么要用结构体指针当作形参?,下面我们可以创建一个结构体变量进行存储,给大家讲解。
我们在测试文件中主函数里创建测试函数1,进行创建结构体变量初始化测试,代码如下:
test.c:
#include "SeqList.h"
void slTest01()
{
SL sl;
SLInit(&sl);
}
int main()
{
slTest01();
return 0;
}
我们在之前的学习中学到,形参是实参的一份临时拷贝,这里我们如果直接把变量sl当作实参传递,那么在初始化函数中进行初始化的不是sl变量本身,而是接收sl变量的形参被初始化了,变量sl的值并不会发生改变,假如我们直接把变量sl的地址传过去,那么在初始化函数中使用指针进行接收,再对其解引用就可以找到实参sl,再初始化就可以改变变量sl的值。所以我们想要通过函数来改变实参的话,就需要传地址过去进行实现。
4).数据管理函数头插和尾插和扩容函数
我们创建好了结构体变量sl当然要往结构体里面存储数据,而结构体中的SLDataType* arr便是让我们来开辟空间使用的,这里我们先实现从头部存入数据(头插SLPushFront)和从尾部存入数据(尾插SLPushBack)的函数。
我们还要考虑一点,在实现插入数据的时候是分两种情况:
1、内存空间足够使用
2、内存空间不够使用
假如内存空间足够使用,那么我们直接进行插入操作就可以,但是如果内存空间不够使用我们就需要对内存空间进行扩容操作。
那么什么时候内存才不够了呢?
假如我们有一个int arr[6]的数组,画图如下所示:
可以看到,给数组已经存满了元素,其有效的数据个数为6,所以size = 6,而整个数组的空间大小也是6,所以capacity = 6,那么大家就可以看出来了,当size = capacity的时候,内存空间是被沾满了的,空间便不够使用,所以我们在扩容函数SLCheckCapacipy中也要以此为条件进行判断。
那么我们已经找到需要增容的条件了,还有一个问题:我们在增容时要增多大的空间。这也肯定时有讲究的,因为如果每次空间开辟较小,那么在整个数据管理的过程中可能就涉及到多次的空间开辟,而多次的空间开辟会造成运行效率降低,并且在内存池中出现多处内存碎片,而空间开辟较大可能会导致空间浪费的情况,那么在这里可以告诉大家,一般在开辟空间的时候都是以每次1.5倍,或者2倍的增长进行开辟扩大的,这样可以保证开辟次数不会过多,空间浪费也会在最小范围。要解释原理的话大家可以在网上进行搜索学习,这里就不进行赘述了(数学原理我也不太清楚)。
代码实现:
SeqList.h:
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//动态顺序表
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* arr;//储存数据的底层结构
int capacity;//记录顺序表的空间大小
int size;//记录顺序表当前有效的数据个数
}SL;
//初始化变量
void SLInit(SL* ps);
//内存管理
void SLPushBack(SL* ps, SLDataType x);//尾插
//1、空间足够,直接在arr[size]插入 2、空间不够,需要增容
void SLPushFront(SL* ps, SLDataType x);//头插
SeqList.c:
#include "SeqList.h"
void SLInit(SL* ps)
{
ps->arr = NULL;
ps->capacity = ps->size = 0;
}
//扩容函数
void SLCheckCapacipy(SL* ps)
{
if (ps->capacity == ps->size)
{
ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* ptr = (SLDataType*)realloc(ps->arr, ps->capacity* sizeof(SLDataType));
if (ptr == NULL)
{
perror("realloc:");
exit(1);
}
else
{
ps->arr = ptr;
//ps->capacity = NewCapacity;
}
}
}
void SLPushBack(SL* ps, SLDataType x)
{
assert(ps);
//2、空间不够,需要扩容
SLCheckCapacipy(ps);
//1、空间足够
ps->arr[ps->size++] = x;
//ps->size++;
}
//头插实现
void SLPushFront(SL* ps, SLDataType x)
{
//断言空指针
assert(ps);
//扩容
SLCheckCapacipy(ps);
//现在空间足够,把每位数都向后移动一位
for (int i = ps->size; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
//插入首位置
ps->arr[0] = x;
ps->size++;
}
下面我们就可以在测试函数里面调用测试,看看是否存在BUG,我们先测试尾插函数SLPushBack
test.c:
#include "SeqList.h"
void slTest01()
{
SL sl;
SLInit(&sl);
测试尾插
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4);
SLPrint(&sl);
}
int main()
{
slTest01();
return 0;
}
这里还顺带实现了一个打印函数SLPrint,代码如下
SLPrint:
void SLPrint(SL* ps)
{
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}
打印函数的形参使用的也是指针,这是为了保持接口(形参)一致性所以才也用指针来当形参,打印函数直接放在实现文件里调用使用就可以。
打印结果如下:
再测试头插函数SLPushFront
test.c:
#include "SeqList.h"
void slTest01()
{
SL sl;
SLInit(&sl);
测试尾插
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4);
SLPrint(&sl);
//测试头插
SLPushFront(&sl, 5);
SLPushFront(&sl, 6);
SLPushFront(&sl, 7);
SLPrint(&sl);
}
int main()
{
slTest01();
return 0;
}
打印结果如下:
5).头删SLPopBack和尾删SLPopFront函数
头删函数尾删函数,顾名思义就是进行头部数据或者尾部数据的删除操作。
调用这两个函数进行数据修改的时候也要考虑两种情况:
1、内存空间内有数据
2、内存空间内没有数据
只有当内存空间存有数据的时候我们才能执行删除操作,所以这就涉及到了结构体中的有效数据个数size不能为0,assert直接进行断言,那么就只剩下了空间中有数据的情况。
对于头删操作,我们直接把后面的数据向前移动一位,同时有效数据个数size减一,就实现了头删的效果。
对于尾删,我们直接将有效数据个数size减一,就实现了尾删的效果。
代码实现:
SeqList.h:
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//动态顺序表
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* arr;//储存数据的底层结构
int capacity;//记录顺序表的空间大小
int size;//记录顺序表当前有效的数据个数
}SL;
//初始化变量
void SLInit(SL* ps);
//内存管理
void SLPushBack(SL* ps, SLDataType x);//尾插
//1、空间足够,直接在arr[size]插入 2、空间不够,需要增容
void SLPushFront(SL* ps, SLDataType x);//头插
//删除
void SLPopBack(SL* ps);//头删
void SLPopFront(SL* ps);//尾删
SeqList.c:
#include "SeqList.h"
void SLInit(SL* ps)
{
ps->arr = NULL;
ps->capacity = ps->size = 0;
}
//扩容函数
void SLCheckCapacipy(SL* ps)
{
if (ps->capacity == ps->size)
{
ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* ptr = (SLDataType*)realloc(ps->arr, ps->capacity* sizeof(SLDataType));
if (ptr == NULL)
{
perror("realloc:");
exit(1);
}
else
{
ps->arr = ptr;
//ps->capacity = NewCapacity;
}
}
}
void SLPushBack(SL* ps, SLDataType x)
{
assert(ps);
//2、空间不够,需要扩容
SLCheckCapacipy(ps);
//1、空间足够
ps->arr[ps->size++] = x;
//ps->size++;
}
void SLPrint(SL* ps)
{
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}
//头插实现
void SLPushFront(SL* ps, SLDataType x)
{
//断言空指针
assert(ps);
//扩容
SLCheckCapacipy(ps);
//现在空间足够,把每位数都向后移动一位
for (int i = ps->size; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
//插入首位置
ps->arr[0] = x;
ps->size++;
}
//尾删
void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->size);//有效数据为0不能删除
//顺序表不为空
ps->size--;
}
//头删
void SLPopFront(SL* ps)
{
assert(ps);
assert(ps->size);
//顺序表不为空
for (int i = 1; i < ps->size; i++)
{
ps->arr[i - 1] = ps->arr[i];
}
ps->size--;
}
下面我们就可以进入测试函数进行测试
test.c:
#include "SeqList.h"
void slTest01()
{
SL sl;
SLInit(&sl);
测试尾插
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4);
SLPrint(&sl);
//测试头插
SLPushFront(&sl, 5);
SLPushFront(&sl, 6);
SLPushFront(&sl, 7);
SLPrint(&sl);
测试尾删
SLPopBack(&sl);
SLPopBack(&sl);
SLPrint(&sl);
测试头删
SLPopFront(&sl);
SLPopFront(&sl);
SLPrint(&sl);
}
int main()
{
slTest01();
return 0;
}
执行结果如下:
6).指定位置 插入/删除 函数 SLInsert/SLErase
在指定位置进行插入删除操作,那么其函数的形参一定要多一个插入位置的参数。
对于指定位置插入,我们看下图:
假如要在pos的位置进行插入数据(对应下标为2),那么就需要下标为2往后的数据进行集体后移一位,这里我们也可以使用memmove函数进行实现,如果忘记了的同学我们也可以像之前那样进行赋值后移都可以。
这里我们还必须要考虑一个问题,如果进行后移空间是否足够,如果空间不够,那么我们是需要进行扩容操作的。
对于指定位置删除,与之前类似,我们只需要将指定位置后面的数据集体向前移一位,那么就实现了指定位置的删除,删除之后记得也必须要将有效数据个数size减一,这一部非常重要不能忘记。
代码实现:
SeqList.h:
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//动态顺序表
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* arr;//储存数据的底层结构
int capacity;//记录顺序表的空间大小
int size;//记录顺序表当前有效的数据个数
}SL;
//初始化变量
void SLInit(SL* ps);
//内存管理
void SLPushBack(SL* ps, SLDataType x);//尾插
//1、空间足够,直接在arr[size]插入 2、空间不够,需要增容
void SLPushFront(SL* ps, SLDataType x);//头插
//删除
void SLPopBack(SL* ps);//头删
void SLPopFront(SL* ps);//尾删
//指定位置插入增加
void SLInsert(SL* ps, int pos, SLDataType x);
//指定位置删除
void SLErase(SL* ps, int pos);
SeqList.c:
#include "SeqList.h"
void SLInit(SL* ps)
{
ps->arr = NULL;
ps->capacity = ps->size = 0;
}
//扩容函数
void SLCheckCapacipy(SL* ps)
{
if (ps->capacity == ps->size)
{
ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* ptr = (SLDataType*)realloc(ps->arr, ps->capacity* sizeof(SLDataType));
if (ptr == NULL)
{
perror("realloc:");
exit(1);
}
else
{
ps->arr = ptr;
//ps->capacity = NewCapacity;
}
}
}
void SLPushBack(SL* ps, SLDataType x)
{
assert(ps);
//2、空间不够,需要扩容
SLCheckCapacipy(ps);
//1、空间足够
ps->arr[ps->size++] = x;
//ps->size++;
}
void SLPrint(SL* ps)
{
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}
//头插实现
void SLPushFront(SL* ps, SLDataType x)
{
//断言空指针
assert(ps);
//扩容
SLCheckCapacipy(ps);
//现在空间足够,把每位数都向后移动一位
for (int i = ps->size; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
//插入首位置
ps->arr[0] = x;
ps->size++;
}
//尾删
void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->size);//有效数据为0不能删除
//顺序表不为空
ps->size--;
}
//头删
void SLPopFront(SL* ps)
{
assert(ps);
assert(ps->size);
//顺序表不为空
for (int i = 1; i < ps->size; i++)
{
ps->arr[i - 1] = ps->arr[i];
}
ps->size--;
}
//任意位置增加
void SLInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
//保证在数据范围内
assert(pos > 0 && pos <= ps->size+1);
if (pos == ps->size+1)
{
SLCheckCapacipy(ps);
SLPushBack(ps, x);
}
else
{
SLCheckCapacipy(ps);
for (int i = ps->size; i >= pos; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[pos - 1] = x;
ps->size++;//数据丢失!!!
}
}
//任意位置删除
void SLErase(SL* ps, int pos)
{
assert(ps);
//保证在数据范围内
assert(pos > 0 && pos <= ps->size);
for (int i = pos; i < ps->size; i++)
{
ps->arr[i - 1] = ps->arr[i];
}
ps->size--;
}
下面就进入测试环节:
test.c:
#include "SeqList.h"
void slTest01()
{
SL sl;
SLInit(&sl);
测试尾插
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4);
SLPrint(&sl);
//测试头插
SLPushFront(&sl, 5);
SLPushFront(&sl, 6);
SLPushFront(&sl, 7);
SLPrint(&sl);
测试尾删
SLPopBack(&sl);
SLPopBack(&sl);
SLPrint(&sl);
测试头删
SLPopFront(&sl);
SLPopFront(&sl);
SLPrint(&sl);
测试指定位置增加
SLInsert(&sl, 2, 3);
SLInsert(&sl, 4, 3);
SLPrint(&sl);
//指定位置删除
SLErase(&sl, 3);
SLPrint(&sl);
}
int main()
{
slTest01();
return 0;
}
打印结果如下:
7).查找函数SLFind
查找函数是实现对所存数据进行查找,如果有对应的数值那么就返回其所对应的位置,如果没有也要返回提示。
这就又要考虑两种情况了
1、空间没有存储数据
2、空间存储有数据
对于空间如果没有存储数据,那么就不用进行查找操作了,直接给予提示。
对于空间存储有数据,那么就要进行查找操作,如果有那么就返回对应所在位置,如果没有就给予提示。
这里既然要返回位置,那么函数的返回类型应该是int。
对于如何进行查找操作,其实很简单,对存储的数据进行遍历一边即可。
代码实现:
SeqList.h:
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//动态顺序表
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* arr;//储存数据的底层结构
int capacity;//记录顺序表的空间大小
int size;//记录顺序表当前有效的数据个数
}SL;
//初始化变量
void SLInit(SL* ps);
//内存管理
void SLPushBack(SL* ps, SLDataType x);//尾插
//1、空间足够,直接在arr[size]插入 2、空间不够,需要增容
void SLPushFront(SL* ps, SLDataType x);//头插
//删除
void SLPopBack(SL* ps);//头删
void SLPopFront(SL* ps);//尾删
//指定位置插入增加
void SLInsert(SL* ps, int pos, SLDataType x);
//指定位置删除
void SLErase(SL* ps, int pos);
//查找对应数在第几个
int SLFind(SL* ps, SLDataType x);
SeqList.c:
#include "SeqList.h"
void SLInit(SL* ps)
{
ps->arr = NULL;
ps->capacity = ps->size = 0;
}
//扩容函数
void SLCheckCapacipy(SL* ps)
{
if (ps->capacity == ps->size)
{
ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* ptr = (SLDataType*)realloc(ps->arr, ps->capacity* sizeof(SLDataType));
if (ptr == NULL)
{
perror("realloc:");
exit(1);
}
else
{
ps->arr = ptr;
//ps->capacity = NewCapacity;
}
}
}
void SLPushBack(SL* ps, SLDataType x)
{
assert(ps);
//2、空间不够,需要扩容
SLCheckCapacipy(ps);
//1、空间足够
ps->arr[ps->size++] = x;
//ps->size++;
}
void SLPrint(SL* ps)
{
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}
//头插实现
void SLPushFront(SL* ps, SLDataType x)
{
//断言空指针
assert(ps);
//扩容
SLCheckCapacipy(ps);
//现在空间足够,把每位数都向后移动一位
for (int i = ps->size; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
//插入首位置
ps->arr[0] = x;
ps->size++;
}
//尾删
void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->size);//有效数据为0不能删除
//顺序表不为空
ps->size--;
}
//头删
void SLPopFront(SL* ps)
{
assert(ps);
assert(ps->size);
//顺序表不为空
for (int i = 1; i < ps->size; i++)
{
ps->arr[i - 1] = ps->arr[i];
}
ps->size--;
}
//任意位置增加
void SLInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
//保证在数据范围内
assert(pos > 0 && pos <= ps->size+1);
if (pos == ps->size+1)
{
SLCheckCapacipy(ps);
SLPushBack(ps, x);
}
else
{
SLCheckCapacipy(ps);
for (int i = ps->size; i >= pos; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[pos - 1] = x;
ps->size++;//数据丢失!!!
}
}
//任意位置删除
void SLErase(SL* ps, int pos)
{
assert(ps);
//保证在数据范围内
assert(pos > 0 && pos <= ps->size);
for (int i = pos; i < ps->size; i++)
{
ps->arr[i - 1] = ps->arr[i];
}
ps->size--;
}
//查找
int SLFind(SL* ps, SLDataType x)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return i + 1;
}
}
return -1;
}
接下来进入测试环节:
test.c:
#include "SeqList.h"
void slTest01()
{
SL sl;
SLInit(&sl);
测试尾插
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4);
SLPrint(&sl);
//测试头插
SLPushFront(&sl, 5);
SLPushFront(&sl, 6);
SLPushFront(&sl, 7);
SLPrint(&sl);
测试尾删
SLPopBack(&sl);
SLPopBack(&sl);
SLPrint(&sl);
测试头删
SLPopFront(&sl);
SLPopFront(&sl);
SLPrint(&sl);
测试指定位置增加
SLInsert(&sl, 2, 3);
SLInsert(&sl, 4, 3);
SLPrint(&sl);
//指定位置删除
SLErase(&sl, 3);
SLPrint(&sl);
//测试查找
int ret = SLFind(&sl, 3);
if (ret == -1)
{
printf("没有你要找的数\n");
}
else
{
printf("你要找的数在第%d位\n", ret);
}
}
int main()
{
slTest01();
return 0;
}
打印结构如下:
8).销毁函数SLDestory
之前既然进行了动态空间的开辟,在程序执行结束后也必须要将空间进行销毁。
销毁函数实现代码如下:
void SLDestory(SL* ps)
{
assert(ps);
if (ps->arr)//if可有可无
{
free(ps->arr);
}
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
这里的if可以有也可以没有,因为进行销毁的话要保证ps->arr里是开辟的有动态空间的,只有有开辟空间,那么才能进行销毁,而其实就算给free函数传了个空指针过去,free函数也什么都不会做,所以if可有可无。
二.完整实现代码
这样一来对于动态顺序表的实现就完成了,具体如何使用,那就要今后继续进行学习。
完整代码如下:
SeqList.h:
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//动态顺序表
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* arr;//储存数据的底层结构
int capacity;//记录顺序表的空间大小
int size;//记录顺序表当前有效的数据个数
}SL;
//初始化变量
void SLInit(SL* ps);
//内存管理
void SLPushBack(SL* ps, SLDataType x);//尾插
//1、空间足够,直接在arr[size]插入 2、空间不够,需要增容
void SLPushFront(SL* ps, SLDataType x);//头插
//删除
void SLPopBack(SL* ps);//头删
void SLPopFront(SL* ps);//尾删
//指定位置插入增加
void SLInsert(SL* ps, int pos, SLDataType x);
//指定位置删除
void SLErase(SL* ps, int pos);
//查找对应数在第几个
int SLFind(SL* ps, SLDataType x);
//销毁
void SLDestory(SL* ps);
SeqList.c:
#include "SeqList.h"
void SLInit(SL* ps)
{
ps->arr = NULL;
ps->capacity = ps->size = 0;
}
//扩容函数
void SLCheckCapacipy(SL* ps)
{
if (ps->capacity == ps->size)
{
ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* ptr = (SLDataType*)realloc(ps->arr, ps->capacity* sizeof(SLDataType));
if (ptr == NULL)
{
perror("realloc:");
exit(1);
}
else
{
ps->arr = ptr;
//ps->capacity = NewCapacity;
}
}
}
void SLPushBack(SL* ps, SLDataType x)
{
assert(ps);
//2、空间不够,需要扩容
SLCheckCapacipy(ps);
//1、空间足够
ps->arr[ps->size++] = x;
//ps->size++;
}
//销毁
void SLDestory(SL* ps)
{
assert(ps);
if (ps->arr)//if可有可无
{
free(ps->arr);
}
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
void SLPrint(SL* ps)
{
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}
//头插实现
void SLPushFront(SL* ps, SLDataType x)
{
//断言空指针
assert(ps);
//扩容
SLCheckCapacipy(ps);
//现在空间足够,把每位数都向后移动一位
for (int i = ps->size; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
//插入首位置
ps->arr[0] = x;
ps->size++;
}
//尾删
void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->size);//有效数据为0不能删除
//顺序表不为空
ps->size--;
}
//头删
void SLPopFront(SL* ps)
{
assert(ps);
assert(ps->size);
//顺序表不为空
for (int i = 1; i < ps->size; i++)
{
ps->arr[i - 1] = ps->arr[i];
}
ps->size--;
}
//任意位置增加
void SLInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
//保证在数据范围内
assert(pos > 0 && pos <= ps->size+1);
if (pos == ps->size+1)
{
SLCheckCapacipy(ps);
SLPushBack(ps, x);
}
else
{
SLCheckCapacipy(ps);
for (int i = ps->size; i >= pos; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[pos - 1] = x;
ps->size++;//数据丢失!!!
}
}
//任意位置删除
void SLErase(SL* ps, int pos)
{
assert(ps);
//保证在数据范围内
assert(pos > 0 && pos <= ps->size);
for (int i = pos; i < ps->size; i++)
{
ps->arr[i - 1] = ps->arr[i];
}
ps->size--;
}
//查找
int SLFind(SL* ps, SLDataType x)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return i + 1;
}
}
return -1;
}
test.c:
#include "SeqList.h"
void slTest01()
{
SL sl;
SLInit(&sl);
测试尾插
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4);
SLPrint(&sl);
//测试头插
SLPushFront(&sl, 5);
SLPushFront(&sl, 6);
SLPushFront(&sl, 7);
SLPrint(&sl);
测试尾删
SLPopBack(&sl);
SLPopBack(&sl);
SLPrint(&sl);
测试头删
SLPopFront(&sl);
SLPopFront(&sl);
SLPrint(&sl);
测试指定位置增加
SLInsert(&sl, 2, 3);
SLInsert(&sl, 4, 3);
SLPrint(&sl);
//指定位置删除
SLErase(&sl, 3);
SLPrint(&sl);
//测试查找
int ret = SLFind(&sl, 3);
if (ret == -1)
{
printf("没有你要找的数\n");
}
else
{
printf("你要找的数在第%d位\n", ret);
}
//销毁
SLDestory(&sl);
}
int main()
{
slTest01();
return 0;
}
3.完结撒❀
如果以上内容对你有帮助不妨点赞支持一下,以后还会分享更多编程知识,我们一起进步。
最后我想讲的是,据说点赞的都能找到漂亮女朋友