当前位置:网站首页>顺序表的定义和基本操作
顺序表的定义和基本操作
2022-08-09 18:58:00 【从未止步..】
顺序表:
用顺序存储的方式实现线性表顺序存储,把逻辑上相邻的元素存储在物理位置也相邻的存储单元中,元素之间的关系有存储单元的邻接关系来体现。
二者之间关系如下图所示:
顺序表的实现-----静态分配:
设置数据元素默认值的重要性:
设置的:
#include<stdio.h>
#define Maxsize 10
typedef struct
{
int data[Maxsize];
int length;
}SqList;
void InitList(SqList &L)
{
for (int i = 0; i < Maxsize; i++)
{
L.data[i] = 0;//初始化顺序表:设置数据元素的默认值
}
L.length = 0;//顺序表中最开始没有任何数据,因此长度为0
}
int main()
{
SqList L;//声明顺序表
InitList(L);//初始化顺序表
for (int i = 0; i < Maxsize; i++)
{
printf("data[%d]=%d\n", i, L.data[i]);
}
return 0;
}
输出如下:
将设置默认值的代码删去:
输出如下:
出现这些数据的原因即为我们进行初始化顺序表之后,系统为其开辟了一段空间,但由于我们对其中的值并没有设置默认值,这块空间之前存有的数据还保留在这个空间中。
但其实我们所编写的main函数也是有问题的:
//尝试“违规打印整个data数组”
for (int i = 0; i < Maxsize; i++)
{
printf("data[%d]=%d\n", i, L.data[i]);
}
违规的原因在于Maxsize是顺序表的最大长度,并不是当前长度,那有的小伙伴会说,既然用不了Maxsize,那么L.length总可以吧?其实也不可以,不信你替换成L.length你会发现程序是没有任何输出的,因为我们不应该访问大于顺序表实际长度的元素。
最好的做法就是使用我们上篇文章所讲的基本操作中的GetElem(L,I)进行访问,选用这种正确的方法,把各个数据元素的值设为默认值这一步骤就可以省略了。
但是L.length=0(将顺序表的长度初始化为0),这一步骤可不能省略哦,和上面的原因相同,内存为顺序表开辟的这一块空间,你并不知道之前存放了什么样的数据。
直接放图会比较好理解:
相信不少学过C语言的同学会有这样的疑问,那在C语言中为什么我没有设定初始值,系统就会默认给初始值为0呢?实际上做这个初始化工作的是编译器,你在VS编译器下系统会帮你进行初始化,但并不是所有的编译器都像VS那么暖心,因此我们还是自己操作吧。
静态分配的缺点:
原因:
int data[Maxsize];
上述这种用静态数组存放数据元素,这里的Maxsize一旦设置好是不能改变的,因此,如果当数组元素放满了之后,只能拜拜了,因为存储空间是静态的,无法被改变。
既然我们“怕存满”,那为什么不直接在设置长度的时候设置一个超大的呢?
这样根本就不怕,enmmm,确实是空间足够大了,但是你不觉得这样很浪费?假设你在设置长度的时候给定的长度为10000,结果你实际只用了10,这样就浪费了一大块的存储空间啊,所以还是好好继承中华传统美德“节约光荣,浪费可耻”。
由此我们可得出一个结论:静态分配具有很大的局限性,因为容量是固定不变的。
顺序表的实现-----动态分配:
C语言规定了动态空间的申请函数malloc和释放该空间的函数free,他们所包含的头文件#include<stdlib.h>
malloc函数:
功能:分配所需的连续内存空间
free函数:
free 函数没有返回值,它的功能是释放指针变量 data所指向的内存单。此时data所指向的那块内存单元将会被释放并还给操作系统,不再归它使用。
操作系统可以重新将它分配给其他变量使用,但释放并不是指清空内存空间,而是指将该内存空间标记为 “可用”状态,使操作系统在分配内存时可以将它重新分配给其他变量使用。
注:
只有动态创建的内存才能用 free 把它释放掉,静态内存是不能用free释放的。静态内存只能由系统释放。
代码实现动态内存分配:
#include<stdio.h>
#include<stdlib.h>
#define Initsize 10
//顺序表的定义
typedef struct {
int* data;
int length;
int Maxsize;
}SeqList;
//顺序表的内存分配
void InitList(SeqList& L)
{
L.data = (int*)malloc(sizeof(int*)*Initsize);
L.length = 0;
L.Maxsize = Initsize;
}
//调用顺序表
int main()
{
SeqList L;
InitList(L);
}
如果此时出现了上述静态分配中出现的问题,数组存满了,该怎么办呢?
此时我们可以使用Increasesize(SeqList &L, int len)函数。
Increasesize函数:
该函数的功能是把已有元素的数组赋值给新建的int *p。自己再从新开辟一片能够存下原来的值和新增加的长度的空间。
此时L.data是为没有元素的,下面进行循环遍历把旧的元素给赋值过来。还剩下给新的元素留下的空间地址。这样就实现了动态分配了。
用代码实现:
#include<stdio.h>
#include<stdlib.h>
#define Initsize 10
---snip---
void Inicreasesize(SeqList& L, int len)
{
int* p = L.data;//将扩充前的数据赋值给新的指针P
L.data = (int*)malloc(sizeof(int) * (L.Maxsize + len));//扩宽顺序表的长度
for (int i = 0; i < L.length; i++)//实现原数据的复制
{
L.data[i] = p[i];
}
L.Maxsize = L.Maxsize + len;//将最大长度修改为扩宽后的长度
free(p);//释放内存空间
}
int main()
{
SeqList L;
InitList(L);
Inicreasesize(L, 5);
}
分析过程如下:
顺序表的特点:
1:随机访问:可实现在O(1)【常数级】时间内找到第i个元素,这也得益于它的按顺序存储的特点。
代码实现方法:data[i-1]
2:存储密度高,每个节点只存储数据元素。
相比于链式存储模式,既存放数据元素还存放对应的指针来说,顺序存储模式只存储数据元素。
3:拓展容量不方便(静态分配直接就是不能拓展容量,虽然动态分配可以拓展,但是拓展长度的时间复杂度也比较高)
4:插入,删除操作不方便,需要移动大量元素,这个特点也是和顺序存储模式有关
边栏推荐
猜你喜欢
看完这波 Android 面试题;助你斩获心中 offer
真香|持一建证书央企可破格录取
Toronto Research Chemicals加米霉素-d4说明书
ebook download | "Business executives' IT strategy guide - why enterprises should implement DevOps"
渗透测试——CFS三层靶机内网渗透实操
【kali-密码攻击】(5.1.1)密码在线破解:Hydra(图形界面)
PCL学习之滤波Filtering
《痞子衡嵌入式半月刊》 第 60 期
Fully automated machine learning modeling!The effect hangs the primary alchemist!
基于CC2530 E18-MS1-PCB Zigbee DIY作品
随机推荐
力扣15-三数之和——HashSet&双指针法
安装多版本php(php5.6,php7.2)
[Free Column] Android Security for Peace Elite (FZ) APK Reverse Analysis
基于SSM实现手机销售商城系统
倍福CX5120实现温度控制例程详细解析
[免费专栏] Android安全之Android应用的汉化功能(修改so中的字符串内容)
Toronto Research Chemicals加米霉素-d4说明书
源码编译安装与yum和rpm软件安装详解
数学建模代码速成~赛前一个月~matlab~代码模板~吐血总结~三大模型代码(预测模型、优化模型、评价模型)
Flume (六) --------- Flume 数据流监控
工大科雅深交所上市:市值45亿 齐承英家族是大股东
漏洞复现-redis未授权getshell
pytest框架之mark标记功能详细介绍
leetcode 二叉树的公共近祖先
【NOI模拟赛】防AK题(生成函数,单位根,Pollard-Rho)
AttributeError: module 'click' has no attribute 'get_os_args'
ebook下载 | 《 企业高管IT战略指南——企业为何要落地DevOps》
面试官:MySQL 中 update 更新,数据与原数据相同时会执行吗?大部分人答不上来!
SqlServer 2016 备份和还原
渗透测试——CFS三层靶机内网渗透实操