专栏原创出处:github-源笔记文件 github-源码 ,欢迎 Star,转载请附上原文出处链接和本声明。

# 1.数据结构

相互之间存在一种或多种特定关系的数据元素的集合称为「数据结构」。按照视点的不同,数据结构可以分为「逻辑结构」和「存储结构」。

# 2.逻辑结构

数据对象中数据元素之间的相互关系称为「逻辑结构」。

# 2.1 逻辑结构的分类

  • 线性结构: 数据元素之间是一对一的关系。

  • 树形结构: 数据元素之间存在一种一对多的层次关系。

  • 图形结构: 数据元素是多对多的关系。

  • 集合结构: 数据元素除了同属于一个集合外,他们之间没有其他关系。 各数据元素之间是平等的,共同属性是“同属于一个集合”。

# 2.2 常见的数据逻辑结构层次关系图

# 3.存储结构

逻辑结构指的是数据间的关系,而存储结构是逻辑结构的存储映像。通俗的讲,可以将存储结构理解为逻辑结构用计算机语言的实现。常见的存储结构有顺序存储、链式存储、索引存储以及散列存储(哈希表)。

  • 顺序存储:将数据元素存放在地址连续的存储单元中,其数据间的逻辑关系与物理关系是一致的。常见的数组采用顺序存储结构。优点:节省空间,可以实现随机存取;缺点:插入、删除时需要移动元素,效率低。

  • 链式存储:将数据元素存放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的。常见的链表采用链式存储结构。优点:插入、删除灵活;缺点:不能随机存取,查找速度慢。

# 4.逻辑结构和存储结构的区别

这两者并不冲突,一个指的是数据之间的关系,而另一个指这种关系在计算机中的表现形式。

比如,线性表中的栈,数据元素之间的关系是一对一的,除头和尾结点之外的每个结点都有唯一的前驱和唯一的后继,这体现的是逻辑结构;
而对于栈中的结点来说,它们可以顺序存储(也就是顺序栈),取一段连续的存储空间,将栈结点按顺序存入,每个结点和其前驱和后继在物理上都是相邻的。
同时,栈结点也可以链式存储(链栈),每个结点中包括数据域和指针域,而指针域就是用来指向其后继的,在访问时就可以通过指针来找到其后继进行访问,每个结点之间物理上可以相邻也可以不相邻。

# 参考

  • 《大话数据结构》 程杰著

# 专栏更多文章笔记

最后修改时间: 2/22/2020, 4:51:12 PM