根据视点的不同,我们把数据结构分为逻辑结构和物理结构.
🌳逻辑结构
逻辑结构:是指数据对象中数据元素之间的相互关系.
逻辑结构分为以下四种:
1.集合结构
集合结构:集合结构中的数据元素除了同属于一个集合外,它们之间没有其他关系.
也即,各个数据元素是"平等"的,它们的共同属性是"同属于一个集合".
集合结构图示
集合结构画风如下:
2.线性结构
线性结构:线性结构中的数据元素之间存在一个对一个的关系.
线性结构图示
线性结构画风如下:
3.树形结构
树形结构:树形结构中的数据元素之间存在一种一对多的层次关系.
树形结构图示
树形结构画风如下:
4.图形结构或网状结构
图形结构:图形结构的数据元素是多对多的关系.
图形结构示意图
图形结构画风如下:
我们在用示意图表示数据结构时,要注意两点:
- 将每一个数据元素看作一个结点,用圆圈表示.
- 元素之间的逻辑关系用结点之间的连线表示,如果这个关系是有方向的,那么用带箭头的连线表示.
逻辑结构是针对具体问题的,是为了解决某个问题,在对问题理解的基础上,选择一个合适的数据结构表示数据元素之间的逻辑关系.
🌳物理结构
物理结构:又称存储结构,是指数据的逻辑结构在计算机中的存储形式,它包含数据元素的表示和关系的表示.
数据是数据元素的集合,根据物理结构的定义,实际上就是如何把数据元素存储到计算机的存储器中.存储器主要是针对内存而言的,像硬盘,软盘,光盘等外部存储器的数据组织通常用文件结构来描述.
计算机存储器的分类
数据的存储结构应正确反映数据元素之间的逻辑关系,这是最为关键的.
如何存储数据元素之间的逻辑关系,是实现物理结构的重点和难点.
数据元素的存储结构形式有两种:顺序存储和链式存储.
1.顺序存储结构
顺序存储结构:是把数据元素存放在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的.
如:
可以看到,字符型变量a,b,c,d,e,f在内存中就是按顺序存储的.
顺序存储的特点就是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系.
再比如,我们假设可以使用2个字节的空间表示一个实数,则可以用地址相邻的4个字节的空间表示一个复数.
如下图为表示复数 z1=3.0-2.3i 和 z2=-0.7+4.8i 的顺序存储结构:
复数顺序存储结构示意图
顺序结构其实非常简单,就是大家都按顺序排好,每个人站一小段空间.
我们之前学习C语言时,数组就是这样的顺序存储结构.
2.链式存储结构
虽然顺序存储结构非常简单和有规律,但我们在前期学习C语言的时候一定遇到过这样的问题:
就是以删除数组元素为基础的题目,这时候因为数组是顺序结构,我们没法直接将找到的某个元素删除掉.
因为顺序结构的内存空间是固定的,我们只能采用将指定元素后面的所有元素向前移动一个位置的方法来实现"删除"某个元素的效果.
图示如下:
当数组元素少或者要删除的元素在数组中的位置较为靠后时,似乎只需要移动几个元素就可以达到我们想要的效果,
但是当数组元素非常多且删除元素在数组中的位置较为靠前的时候,这样的删除元素的效率就非常低了.
因此,面对这样时常要变化的结构,顺序存储是不科学的.于是我们就引入了链式存储结构:
链式存储结构:是把元素存放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的.
链式存储结构示意图
如图,因为数据元素的存储关系并不能反映其逻辑关系,因此需要用一个指针存放数据元素的地址,这样通过地址就可以找到相关联数据元素的位置.
链式存储结构的特点是借助指示元素存储地址的指针(pointer)表示数据元素之间的逻辑关系.
显然,链式存储就灵活的多,数据存在哪里不重要,只要有一个指针存放了相应的地址就能找到它了.
我们再拿上面顺序结构中提到过的复数来举例:
如下图为表示复数 z1=3.0-2.3i 的链式存储结构,其中实部和虚部之间的关系用值为"0x12ff0415"的指针来表示(0x12ff0415是虚部的存储地址):
综上,逻辑结构是面向问题的,而物理结构就是面向计算机的,其基本的目标就是将数据及其逻辑关系存储到计算机的内存中.
结语
本节我们一起学习了数据结构中的逻辑结构与物理结构,在数据结构绪论章中,我们还将一起探讨其他三节的内容,分别是:什么是数据结构,数据结构的基本概念和术语以及抽象数据类型,有兴趣的朋友可以直接点击下方链接跳转至相应博客:
相关文章推荐
......
数据结构绪论篇思维导图:
