当前位置:网站首页>冰冰学习笔记:一步一步带你实现顺序表
冰冰学习笔记:一步一步带你实现顺序表
2022-04-23 14:42:00 【bingbing~bang】
系列文章目录
冰冰学习笔记:一步一步带你实现《通讯录》
文章目录
前言
线性表是N个具有相同特性的数据元素的有限序列,线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的, 线性表在物理上存储时,通常以数组和链式结构的形式存储。
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。接下来我们一步一步实现顺序表。
注意:顺序表中,数组必须从第一个位置存储,并且是连续存放的。
一、确定顺序表实现的大体逻辑
既然顺序表是一种数据结构,那么顺序表就是用来存储数据的。我们之前实现过通讯录,通讯录也是存放信息的工具,那么这个工具应该具备最基础的功能:增删查改。
顺序表的数据增加有三种情况,从开头增加,从尾部增加,从任意位置增加。同理,删除也有三种情况,头部删除,尾部删除,任意位置删除。
除了增加和删除,我们还应该加入查找函数,方便我们从顺序表中查找存储的数据,当我们不知道一个数据是否被保存到顺序表中时,我们就可以使用该函数进行查找。
修改功能也是需要的,当我们发现原先存储的数据出错时,我们可以对其进行更改,然后在存储数据。
最后我们还需要一个功能,那就是将存储的数据打印出来,方便我们直观的观察。
二、顺序表的具体实现
有了上面的大体分析,我们现在就开始一步一步的实现顺序表的搭建。
2.1 结构创建与初始化
与通讯录的搭建类似,分为三个文件进行搭建,SeqList.c用来具体实现各功能函数,SeqList.h用来包含头文件,函数声明,结构创建,test.c用来对顺序表进行功能调用测试。
2.1.1顺序表结构
顺序表存储什么样的数据类型呢,整型?字符?都有可能,因此我们的顺序表应该具有通用性,不能将存储数据类型写死,应该给使用者选择空间。那如何实现呢?
答案就是对存储类型进行重命名,当存储类型更换时,只需要将重命名的类型进行更改就可以。
由于静态顺序表只能存储一定数据的空间,并且空间大小无法改变,我们直接实现动态的版本。
顺序表的结构《通讯录》类似,里面包含接收数据存储数组的指针,数组元素大小size,数组容量capacity。(19条消息) 冰冰学习笔记:一步一步带你实现《通讯录》_bingbing~bang的博客-CSDN博客
2.1.2初始化函数构建
初始化函数是比不可少的,我们使用SeqList类型的结构体创建变量SL,里面都是系统分配的随机值,我们需要自己对其进行初始化,将指针指向存储的空间,将容量与数组元素个数设定为初始状态。
初始化代码如图所示:
在初始化时,我们并没有为数组开辟初始空间,而是将其置为空指针,容量和数组元素个数设置为0 。我们将数组空间的开辟统一写到了增容函数中,如果想预先开辟空间,可以写成下面这样。
下面代码在初始化时为数组预先开辟了10个SLDATAType类型的空间,并将容量设为10。
void SLInit(SeqList* ps)
{
assert(ps != NULL);
SLDATAType* tmp = (SLDATAType*)malloc(10*sizeof(SLDATAType));
if ( tmp == NULL )
{
perror("malloc::SLInit");
exit(-1);
}
ps->a = tmp;
ps->capacity =10;
ps->size = 0;
}
2.2数据的尾部增加和删除
顺序表的存储空间已经创建完毕,现在我们要对数据从数组末尾进行增删操作。
2.2.1数据尾增
数据尾增,顾名思义就是从数组末尾存放元素。
我们知道size代表的就是数据元素的个数,我们只需要将数据x放入到数组下标为size的地方即可。
存储完数据后,size自增1,指向下次存放的位置。
所以数据尾增函数应该包含两个参数,一个参数为指向数据存储位置的结构体指针,一个是需要存储的数据。
因此我们实现代码如下:
但是,正确吗?答案 是否定的,我们没有考虑容量是否够用,如果容量够用,如此存放当然没问题,但是如果数组没有容量了,size的大小已经不在容量内了,数组就越界访问了。
所以,在存储数据之前,我们应该先对容量进行检查。由于头增,任意增都需要检查容量的大小,因此我们直接封装成一个函数,方便我们调用。
2.2.2扩容函数
扩容函数首先要对容量进行检查,确认此时容量是否已满,如果容量没满,则直接返回,如果容量满了就需要对其进行扩容。
我们定义,每次扩容扩容为原先存储空间的2倍。扩容采用realloc函数进行扩容,但是我们要注意,由于我们初始化时没有开辟空间,如果直接写成下面的扩容形式,空间将会开辟失败。
因为我们没有开辟容量,capacity初始值仍然为0,因此newcapacity也为0,增容到0字节?肯定不行。
所以我们使用三目操作符进行操作,当capacity为0是,开辟4个存储空间,如果不是,扩容到2倍。然后对开辟的临时指针进行判定是否成功,成功开辟再复制给存储数据的指针。扩容完毕后,将容量进行更新。
注意:当realloc函数接收的指针为空指针时,realloc函数的功能形同malloc函数。
扩容代码如下所示:
void SLCheckCapacity(SeqList* ps)
{
assert(ps != NULL);
if ( ps->capacity == ps->size )
{
int newcapacity = (ps->capacity == 0 ? 4 : ps->capacity * 2);
SLDATAType* tmp = (SLDATAType*)realloc(ps->a, newcapacity * sizeof(SLDATAType));
if ( tmp == NULL )
{
perror("realloc::SLCheckCapacity");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
/*printf("扩容成功\n");*/
}
}
扩容函数写完,我们就可以对尾增进行更改,更改完毕后如下所示:
2.2.3数据尾删
数据尾删最容易实现,我们只需要将数组的元素个数size减一即可,数据根本不需要改变,由于size减少了,数组访问的元素也会减少。
然后我们进行尾增尾删测试:
输入1,2,3,4, 5,然后在调用尾删进行删除。
然后我们继续增加三个数字6,7,8,继续打印出来观察。
我们发现输入的明明是6,7,8,结果打印出来是7,8
通过调试我们会发现,我们在写入数字6时,写入的是ps->a[-1]的位置,也就是说size变成-1了。
这什么情况?检查测试代码会发现,我们输入了5个数据,却对其删除了6次,导致size减到了-1。
数据6保存到了下标为-1的地方,数组越界访问了。
这时候又有疑惑了,我都越界访问了,怎么没提示我呀?这里我们放到后文介绍,我们先解决size递减到-1的问题。
我们进行尾删,当数组中没有元素时,我们就应该停止删除,如果调用,直接终止程序,所以我们应该增加一个断言,来预防size<0的情况。
因此,尾删代码如下所示。
void SLPopBack(SeqList* ps)
{
assert(ps != NULL);
assert(ps->size > 0);
ps->size--;
}
2.3数据的头部增加和删除
只有尾增尾删还不行,我们还要处理数据从开头进行插入和删除的情况。
2.3.1数据头增
数据的头增比起数据的尾增就复杂了,我们无法将元素存储到下标为-1,-2的位置,我们能做的只能是将现有的数据进行整体移动,然后在将新数据放到下标为0的地方,最后size自增1。
数据应该如何移动呢?
我们应该从后往前移动,这样才不会覆盖数据,如果从前往后移动,后面需要移动的数据将会被覆盖。
所以我们需要创建一个变量end,起始时为size-1,然后逐步将数据向后挪动。
上面的情况是我们自己构建变量来进行数据后移,我们也可以调动此前学过的库函数memmove进行移动,然后在赋值。
代码:
void SLPushFront(SeqList* ps, SLDATAType x)
{
assert(ps != NULL);
SLCheckCapacity(ps);
调用库函数,memmove
memmove(ps->a+1, ps->a, (ps->size) * sizeof(SLDATAType));
ps->a[0] = x;
ps->size++;
}
2.3.2数据头删
数据头删就是将数组开头的位置保存的数据删除,毫无疑问,我们也需要先将数据移动。
既然是删除,我们只需要将下标为2的数据到下标为size-1的数据整体向前移动一步,将头上的数据直接覆盖即可。
这里的挪动方式也可以直接调用库函数memmove进行实现,就不再赘述,我们介绍一下用下标逐步移动的方法,此处移动时应该从前往后移动,先移动数据1到数据0的位置,将其覆盖,在移动数据2到数据1的位置,直到移动完毕。
所以我们定义变量begin指向下标为0的位置,由于我们要把下标为begin+1位置处的数据移动到begin位置处,所以要确保begin+1不会越界访问,因此限定条件begin应该小于size-1。当然我们也可以让begin起始时为1,将begin指向的数据移动到begin-1指向的数据。
代码如下:
void SLPopFront(SeqList* ps)
{
assert(ps != NULL);
assert(ps->size > 0);
int begin = 1;
while ( begin < ps->size )
{
ps->a[begin - 1] = ps->a[begin];
begin++;
}
ps->size--;
}
2.4数据任意位置的增删
任意位置的插入与删除能够让数据存储变得更加灵活,下面我们来实现具体函数构建。
2.4.1任意插入
既然是任意插入,那我就得需要得知插入的位置,所以函数应该能够接收用户输入的下标,作为插入数据的位置。
任意插入函数含有三个参数,结构体指针,指向数据存储位置;pos下标,表明插入的位置;数据x,代表插入的具体数据。
此时就有人说了,简单啊,直接将数组pos位置及其后面的元素整体后移,然后将数据x放入pos下标位置即可。
没错,是这样,但是有一点需要注意,pos下标是否合法。如果pos的值为-1呢?大于size呢?
所以我们要先对其进行检查,pos下标完全合法后才能进行存储操作。
注意:别忘了检查容量。
插入过程如下图所示:
任意插入pos的数值范围为0到size,当我们调用SLInsert(&SL,0,x)时,实际上执行的是头插操作。 而调用SLInsert(&SL,ps->size,x)实际上是尾插操作,所以我们的头插和尾插也可以直接复用该代码。
2.4.2任意删除
任意位置的删除函数也需要获取删除坐标,然后将坐标指向位置的数据及其后面的数据整体向前移动一步,将需要删除的数据直接覆盖。我们也需要检查pos是否在合适的范围,切记此时的pos不能等于size,因为size下标指向的位置是下次需要存储数据的位置,此时并没有数据保存,因此无法删除。
代码:
void SLErase(SeqList* ps, int pos)
{
assert(ps != NULL);
assert(pos >= 0 && pos < ps->size);
int begin = pos;
while ( begin < ps->size - 1 )
{
ps->a[begin] = ps->a[begin + 1];
begin++;
}
ps->size--;
}
同样的道理头删尾删也可以进行复用。SLErase(ps, 0),SLErase(ps, ps->size - 1)。
2.5查找与修改
查找和修改也是必不可少的功能,尤其是查找,但我们想删除某个数据的时候直接进行查找,返回该数据的下标,然后输入下标进行删除,就不用自己一个一个的数下标位置了。
2.5.1数据查找
数据查找代码比较简单,就是遍历数组找数据是否与x相同,相同返回下标,没有就返回-1。
代码:
int SLFind(SeqList* ps, SLDATAType x)
{
assert(ps != NULL);
int i = 0;
for ( i = 0; i < ps->size; i++ )
{
if ( ps->a[i] == x )
{
return i;
}
}
return -1;
}
2.5.2数据修改
数据修改就是将输入的pos下标位置的数据更改为输入的x即可,注意,pos同样具有范围限制,pos应该在0到size之间,包含0但不包含size。
代码:
void SLModify(SeqList* ps, int pos, SLDATAType x)
{
assert(ps != NULL);
assert(pos < ps->size && pos >= 0);
ps->a[pos] = x;
}
2.6数据打印与内存释放
打印函数是为了让我们更加直观的看到存储的数据,内存释放函数则会将我们申请的空间进行释放,还给操作系统,一般只有在退出程序的时候调用。
2.6.1数据打印函数
遍历数组,将数据打印。
代码:
void SLPrint(SeqList* ps)
{
assert(ps != NULL);
int i = 0;
for ( i = 0; i < ps->size; i++ )
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
2.6.2内存释放函数与越界访问的检查
前面有一个问题,就是我们在删除时,如果多删除数据,在进行存储便会照成越界访问,访问下标为-1的位置并存储数据,但是操作系统并没有给我们警告报错,这是为什么呢?
因为数据的越界访问检查往往会在内存释放的时候进行检查,并且不是一定会报错,而是设岗抽查。如果没检查到,就不会报错,存在隐患。抽到后才会报错。
内存释放函数:
void SLDestory(SeqList* ps)
{
assert(ps != NULL);
if ( ps->a != NULL )
{
free(ps->a);
ps->a = NULL;
ps->size = ps->capacity = 0;
}
}
三、后期完善与菜单建立
3.1主逻辑函数构建
通过前面的介绍,我们已经将顺序表搭建完毕,但是我们进行的调用都是测试各功能时的测试代码,并没有一个整体的运行逻辑,我们需要创建一个菜单,用菜单来控制各个功能。
具体的实现逻辑与《通讯录》基本一致,无非是套用do,while和switch将个功能联系起来使用,下面附上代码,读者可自行分析。
更改部分代码 · b148ab6 · 冰冰棒/数据结构仓库 - Gitee.com
总结
顺序表是一种比较简单的数据结构,使用顺序表时我们尽量使用尾插和尾删进行数据的增加和删除,因为其时间复杂度为O(1),但是调用头插头删和任意位置插入删除时间复杂度都是O(N)。存储数据需要增容并拷贝,使用起来比较麻烦。相比于链表,顺序表有很多缺点,往往使用的频率并不高。
版权声明
本文为[bingbing~bang]所创,转载请带上原文链接,感谢
https://blog.csdn.net/bingbing_bang/article/details/124354123
边栏推荐
- 8.3 语言模型与数据集
- Advanced application of I / O multiplexing: Processing TCP and UDP services at the same time
- 51 MCU flowers, farmland automatic irrigation system development, proteus simulation, schematic diagram and C code
- 如何打开Win10启动文件夹?
- Proteus simulation design of four storey and eight storey elevator control system, 51 single chip microcomputer, with simulation and keil c code
- 面试官:说一下类加载的过程以及类加载的机制(双亲委派机制)
- 1N5408-ASEMI整流二极管1N5408
- 金九银十,入职字节跳动那一天,我哭了(蘑菇街被裁,奋战7个月拿下offer)
- 1-初识Go语言
- L'externalisation a duré quatre ans.
猜你喜欢
A blog allows you to learn how to write markdown on vscode
Eight way responder system 51 Single Chip Microcomputer Design [with Proteus simulation, C program, schematic diagram, PCB files, component list and papers, etc.]
Using MATLAB programming to realize the steepest descent method to solve unconstrained optimization problems
想要成为架构师?夯实基础最重要
Matlab Simulink modeling and design of single-phase AC-AC frequency converter, with MATLAB simulation, PPT and papers
51单片机的直流电机PWM调速控制系统(附Proteus仿真+C程序等全套资料)
【Servlet】Servlet 详解(使用+原理)
I thought I could lie down and enter Huawei, but I was confused when I received JD / didi / iqiyi offers one after another
3、 Gradient descent solution θ
Svn detailed use tutorial
随机推荐
Parameter stack pressing problem of C language in structure parameter transmission
Epolloneshot event of epoll -- instance program
Eight way responder system 51 Single Chip Microcomputer Design [with Proteus simulation, C program, schematic diagram, PCB files, component list and papers, etc.]
Electronic scale weighing system design, hx711 pressure sensor, 51 single chip microcomputer (proteus simulation, C program, schematic diagram, thesis and other complete data)
DVWA之暴力破解(Brute Force)Low-->high
交通灯系统51单片机设计(附Proteus仿真、C程序、原理图及PCB、论文等全套资料)
Interviewer: let's talk about the process of class loading and the mechanism of class loading (parental delegation mechanism)
Design of single chip microcomputer Proteus for temperature and humidity monitoring and alarm system of SHT11 sensor (with simulation + paper + program, etc.)
外包干了四年,废了...
QT Detailed explanation of pro file
Solve the problem of SSH configuration file optimization and slow connection
I/O复用的高级应用:同时处理 TCP 和 UDP 服务
Branch statement of process control
Matlab Simulink modeling and design of single-phase AC-AC frequency converter, with MATLAB simulation, PPT and papers
Outsourcing for four years, abandoned
查找水仙花数-for循环实践
详解TCP的三次握手
Swift:Entry of program、Swift调用OC、@_silgen_name 、 OC 调用Swift、dynamic、String、Substring
UML项目实例——抖音的UML图描述
Raised exception class eaccexviolation with 'access violation at address 45efd5 in module error