上一节我们知道数据结构是学习数据存储方式的学科,那么数据存储方式有哪些呢? 本节简要总结了数据结构的学习内容。
数据结构大致包含以下几种存储结构:
行表还可以细分为顺序表、链表、堆栈和队列。
包括普通树、二叉树、线索二叉树等的树结构;
图的存储结构;
以下详细说明各种数据结构。线性表
存储在路线列表结构中的数据通常可以按顺序排列。 就像孩子牵着手一样,每个学生前面和后面只有一个孩子牵着手。 具有这种“一对一”关系的数据可以使用线性列表保存。
牵手的孩子
例如,在存储{1、3、5、7、9}这样的数据时,各要素按顺序排列,在各要素的前后,除了开头要素和末尾要素以外只有一个要素相邻,所以可以使用线性表来存储。
线性表不是具体的存储结构,而是包括顺序存储结构和链存储结构,是顺序表和链表的总称。
顺序表
简单来说,顺序表是常用的数组,只是更改了名称。 例如,使用顺序表存储{1、3、5、7、9},如图1所示。
顺序表结构
图1顺序表的构成
由于顺序表结构的下级安装利用了数组,所以对于初学者来说,可以将顺序表与数组完全等价,但事实并非如此。 数据结构是研究数据存储方法的学科,涵盖各种存储结构,但数组是各种编程语言中的基本数据类型,不属于数据结构范畴。
链表
我们知道,如果使用顺序表(低级实现依赖数组),则必须提前申请一定大小的存储空间,如图1所示。 此存储区域的物理地址是连续的。
链表完全不同。 使用链表存储数据时,由于数据是按需存储的,所以数据的存储位置是相互分离的。 换句话说,数据的存储位置是随机的。
为了在每个块中创建“按顺序排列”关系,链表会在每个块中添加指针。 每个块的指针指向下一个块,最后一块的指针指向NULL。 像小学生伸手拉下一个小学生的手一样,看起来不相关的模块会建立“按顺序排列”的关系,也会形成链表。 如图2所示:
链表结构
图2链表结构
堆栈和队列
堆栈和队列属于线性表,由于明确要求线性表内的要素出入,所以是特殊的线性表。
堆栈中的元素只能从线性列表的一端进出,另一端被阻塞,遵循“先进后出”原则。 即,先进堆栈的要素将在后面叙述。
堆栈结构图像
图3堆栈结构示意图
堆栈结构如图3所示,类似于木桶,堆栈包含a、b、c三个要素,从堆栈中的状态可以看出a最前端的堆栈,然后b进入堆栈,最后c进入堆栈。 根据“先进后出”原则,三个要素出现的顺序应该是: c先出,b后出,a最后出。
队列中的元素只能从线性表的一端进入,从另一端出来。 另外,必须遵循“先进先出”的特点。 也就是说,先进队列的要素也必须先退出队列。
队列结构映像
图4队列结构示意图
队列结构如图4所示,可以看出队列中有a、b、c三个要素,从在队列中的状态开始a前进进入队列,然后b前进,最后c前进。 根据“先进先出”原则,三个要素出列的顺序应该是a先出列,然后b,最后c。
树存储结构
树存储结构适合存储具有“一对多”关系的数据。
家谱
图5家族谱系
如图5所示,wydxhd只有一个父亲,但有两个以上的孩子。 这就是“一对多”关系,满足该关系的数据可以使用树存储结构。
地图存储结构
图中的存储结构适合存储具有“多对多”关系的数据。
图记忆结构示意图
图6是存储结构的示意图
如图6所示,能够从V1到达V2、V3、V4,同样地,也能够从V2、V3、V4到达V1 . 这就是“多对多”关系,满足该关系的数据可以使用映射存储器结构。