数据结构的基本概念

基本概念和术语

• 数据
  • 描述客观事物的符号是计算机中可以操作的对象是能被计算机识别并输入给计算机处理的符号集合。

    数值类型、字符、声音、图像、视频
    数据具有两个基本前提：
    可以输入到计算机中、能够被计算机程序处理

• 数据元素
  • 数据元素是组成数据的，有一定意义的基本单位，在计算机种通常作为整体处理。也被称为记录。
• 数据项（数据项是数据的最小单位）
  • 数据项是指一个数据元素可以由若干个数据项组成。
• 数据对象（在不产生混淆的情况下，通常简称为数据）
  • 性质相同的数据元素的集合，指数据元素具有相同数量和类型的数据项。

    字母字符数据对象是集合
    {‘A’ ‘B’ ‘C’ … ‘Y’ ‘Z’}

数据结构

数据结构是相互之间存在的一种或多种特定关系的数据元素的集合。
数据结构就是关系。
数据结构的两大结构：

• 逻辑结构
  • 数据对象中数据元素之间的相互关系。
• 物理结构（数据元素的存储结构形式）
  • 数据的逻辑结构在计算机中的存储形式。

    物理结构实际上研究的就是如何把数据元素存储到计算机的存储器中。
    存储器主要是针对内存。光盘等外部存储器的数据组织通常用文件结构来描述。一般我们说的存储器是指内存。

四大逻辑结构

• 集合结构
  • 集合结构中的数据元素除了同属于一个集合以外，没有其他的关系。
• 线性结构
  • 数据元素是一对一的关系。
• 树形结构
  • 数据元素中存在一对多的关系。
• 图形结构
  • 数据元素之间是多对多的关系。

示意图注意事项：
将每个数据元素看作一个节点，用圆圈表示。元素之间的逻辑关系用节点之间的连线表示，如果这个关系是由方向的，那么用带箭头的连线表示。

数据元素的存储结构形式

• 顺序存储
  • 顺序存储结构：把数据元素存放地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。
• 链式存储
  • 链式存储结构：把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。

    很显然，这样说的话链式存储结构的数据元素并不能反映其逻辑关系，因此需要用一个指针存放数据元素的地址，这样子通过地址就可以找到相关联数据元素的位置。

    |data|next|

    其中，data 是元素，next 是指针。用一个存储空间来存放数据，一个存储空间来存放指针。指针指向的就是下一个元素的地址。

本作品采用《CC 协议》，转载必须注明作者和本文链接