数据结构逻辑关系

数据的逻辑结构和数据的存储结构

1. 数据的逻辑结构

数据的逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的存储⽆关，是独⽴于计算机的。

数据的逻辑结构分为线性结构和⾮线性结构，线性表是典型的线性结构；集合、树和图是典型的⾮线性结构。数据的逻辑结

构分类见图1-1。

集合结构中的数据元素之间除了 “同属于⼀个集合”的关系外，别⽆其他关系。

线性结构结构中的数据元素之间只存在⼀对⼀的关系。

树形结构结构中的数据元素之间存在⼀对多的关系。图状结构或⽹状结构结构中的数据元素之间存在多对多的关系。

图1-1 数据的逻辑结构分类图

2. 数据的存储结构

存储结构是指数据结构在计算机中的表⽰（⼜称映像），也称物理结构。它包括数据元素的表⽰和关系的表⽰。数据的存储

结构是逻辑结构⽤计算机语⾔的实现，它依赖于计算机语⾔。数据的存储结构主要有：顺序存储、链式存储、索引存储和散

列存储。

1) 顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元⾥，元素之间的关系由存储单元的邻接关系来体现。

其优点是可以实现随机存取，每个元素占⽤最少的存储空间；缺点是只能使⽤相邻的⼀整块存储单元，因此可能产⽣较多的

外部碎⽚。

2) 链接存储：不要求逻辑上相邻的元素在物理位置上也相邻，借助指⽰元素存储地址的指针表⽰元素之间的逻辑关系。其优

点是不会出现碎⽚现象，充分利⽤所有存储单元；缺点是每个元素因存储指针⽽占⽤额外的存储空间，并且只能实现顺序存

取。

3) 索引存储：在存储元素信息的同时，还建⽴附加的索引表。索引表中的每⼀项称为索引项，索引项的⼀般形式是：（关键

字，地址）。其优点是检索速度快；缺点是增加了附加的索引表，会占⽤较多的存储空间。另外，在增加和删除数据时要修

改索引表，因⽽会花费较多的时间。

4) 散列存储：根据元素的关键字直接计算出该元素的存储地址，⼜称为Hash存储。其优点是检索、增加和删除结点的操作

都很快；缺点是如果散列函数不好可能出现元素存储单元的冲突，⽽解决冲突会增加时间和空间开销。

路漫漫其修远兮，吾将上下而求索 - 百度文库

11 2007 C C C 语言的特点 ， 简单的 C 程序介绍， C 程序的上机步骤。 1 、 算法的概念 2、 简单的算法举例 3、 算法的特性 4、 算法的表示（自然语言、 流程图、 N-S 图表示） 1 、 C 的数据类型、 常量与变星、 整型数据、 实型数据 、 字符型数据、 字符串常量。 2、 C 的运算符运算意义、 优先级、 结合方向。 3、 算术运算符和算术表达式， 各类数值型数据间的混合运算。 4、 赋值运算符和赋值表达式。 5、 逗号运算符和逗号表达式。 1 、 程序的三种基本结构。 2、 数据输入输出的概念及在C 语言中的实现。

字符数据的输入输出， 格式输入与输出。 1 、 关系运算符及其优先级， 关系运算和关系表达式。 2、 逻辑运算符及其优先级， 逻辑运算符和逻辑表达式。 3、 if语句。 if语句的三种形式， if语句的嵌套， 条件运算符。 4、 switch 语句. 1 、 while 语句。 2、

do/while 语句。 3、 for 语句。 4、 循环的嵌套。 5、 break 语句和 continue 语句。 1 、 一维数组的定义和引用。 2、 二维数组的定义和引用。 3、 字符数组。 4、 字符串与字符数组。 5、 字符数组的输入输出。 6、 字符串处理函数 1 、 函数的定义。 2、 函数参数和函数的值， 形式参数和实际参数。 3、 函数的返回值。 4、

函数调用的方式， 函数的声明和函数原型。 5、 函数的嵌套调用。

6、 函数的递归调用。 7、 数组作为函数参数。 8、 局部变量、 全局变量的作用域。 9、 变量的存储类别， 自动变星， 静态变量。 1 、

带参数的宏定义。 2、 “文件包含” 处理。 1 、 地址和指针的概念。 2、 变量的指针和指向变量的指针变量。 3、 指针变量的定义路漫漫其修远兮，吾将上下而求索 - 百度文库

少年易学老难成，一寸光阴不可轻 - 百度文库

1 数据结构中常用的逻辑结构和存储结构

一、概念

数据是指由有限的符号（比如，"0"和"1"，具有其自己的结构、操作、和相应的语义）组成的元素的集合。结构是元素之间的关系的集合。

数据结构是在整个计算机科学与技术领域上广泛被使用的术语。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。

数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系即逻辑结构，而物理上的数据结构反映成分数据在计算机内部的存储安排即存储结构。数据结构是数据存在的形式。

数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。因而研究数据结构的逻辑结构与存储结构显得十分重要。

二、结构分析

（一）逻辑结构

数据的逻辑结构是对数据之间关系的描述，有时就把逻辑结构简称为数据结构。逻辑结构形式地定义为（K，R）（或（D，S）），其中，K是数据元素的有限集，R是K上的关系的有限集。

逻辑结构元素决定输入、存储、发送、处理和信息传递的基本操作功能，常将逻辑结构元素称为逻辑模块。逻辑结构元素可以是计算机操作系统、终端模块、通信程序模块等。逻辑结构元素还可以是相关的几个逻辑模块联合起来的更复杂的实体。分析逻辑结构元素的相互作用，应考虑整个系统的操作，研究处理与信息流有关的进程（操作系统中的一个概念，表示程序的一次执行），并决定系统的逻辑资源。

逻辑结构有四种基本类型：集合结构、线性结构、树状结构和网络结构。表和树是最常用的两种高效数据结构，许多高效的算法能够用这两种数据结构来设计实现。

逻辑数据模型之层次数据模型、⽹状数据模型和关系数据模型

（转）

上⼀篇⽂章简单介绍了概念数据模型、逻辑数据模型、物理数据模型的基本概念、特性以及三者所对应的数据库的开发阶段。现在针对逻辑数据模型中所⽤到的三种数据模型---层次数据模型、⽹状数据模型以及关系数据模型做⼀个相信的介绍与对⽐分析。

⼀、层次数据模型

定义：层次数据模型是⽤树状结构来表⽰实体类型和实体间联系的数据模型。(来⾃百度百科)

其实层次数据模型就是的图形表⽰就是⼀个倒⽴⽣长的树，由基本数据结构中的树（或者⼆叉树）的定义可知，每棵树都有且仅有⼀个根节点，其余的节点都是⾮根节点。每个节点表⽰⼀个记录类型对应与实体的概念，记录类型的各个字段对应实体的各个属性。各个记录类型及其字段都必须记录。

特征:树的性质决定了树状数据模型的特征

1. 整个模型中有且仅有⼀个节点没有⽗节点，其余的节点必须有且仅有⼀个⽗节点，但是所有的节点都可以不存在⼦节点；

2. 所有的⼦节点不能脱离⽗节点⽽单独存在，也就是说如果要删除⽗节点，那么⽗节点下⾯的所有⼦节点都要同时删除，但是可以单独删除⼀些叶⼦节点；

3. 每个记录类型有且仅有⼀条从⽗节点通向⾃⾝的路径；

实例：

如图1，以学校某个系的组织结构为例，说明层次数据模型的结构。

1. 记录类型系是根节点，其属性为系编号和系名；

2. 记录类型教研室和学⽣分别构成了记录类型系的⼦节点，教研室的属性有教研室编号和教研室姓名，学⽣的属性分别是学号、姓名和成绩； 3. 记录类型教师是教研室这⼀实体的⼦节点，其属性由教师的编号，教师的姓名，教师的研究⽅向。

优点： 1. 层次数据模型的结构简单、清晰、明朗，很容易看到各个实体之间的联系；

2. 操作层次数据类型的数据库语句⽐较简单，只需要⼏条语句就可以完成数据库的操作；（百度百科）

3. 查询效率较⾼，在层次数据模型中，节点的有向边表⽰了节点之间的联系，在DBMS中如果有向边借助指针实现，那么依据路径很容易找到待查的记录；