1. 数据结构基本概念 (1)

本文部分ppt、视频截图来自：[青岛大学-王卓老师的个人空间-王卓老师个人主页-哔哩哔哩视频]

1. 数据结构基本概念

1.1 研究内容

数据结构是一门研究非数值计算的程序设计中计算机操作队形以及他们之间关系和操作的核心课程，学习的主要内容如下：

用计算机解决问题的一般步骤是：具体问题抽象为数学模型 —— 设计算法 —— 编程、调试、运行，而如何将具体化为抽象呢，一般是先分析问题，然后提取操作对象并找出操作对象之间的关系，最后用数学语言描述，也就是数据结构。

1.2 数据结构基本概念

数据(Data)： 能输入计算机且能被计算机处理的各种符号的集合，是信息的载体，是对客观事物符号化的表示，能够被计算机识别、存储和加工。数据分为两类：

• 数值型数据：整数、实数等可以进行算术运算的数据
• 非数值型数据：文字、图像、声音等

数据元素(Data element)：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据元素也可以简称为元素、记录、结点或顶点。

数据项：构成数据元素的不可分割的最小单位。

数据对象(Data Object)：性质相同的数据元素的集合，是数据的一个子集。

数据元素和数据对象关系：

数据结构(Data Structure)：数据元素不是孤立存在的，它们之间存在着某种联系，数据元素相互之间的关系称为结构。是指相互之间存在一种或多种特定关系的数据元素集合。

数据结构的两个层次：

1.3 逻辑结构种类划分

（1）划分方法一

• 线性结构：有且仅有一个开始和一个终端节点，并且所有节点都最多只有一个直接前趋和一个直接后继。（如线性表、栈、队列、串）
• 非线性结构：一个结点可能有多个直接前趋和直接后继。（如树、图）

（2）划分方法二

将逻辑结构划分为四种逻辑结构：集合、线性、树和图。

• 集合结构：结构中的数据元素间除了同属于一个集合的关系外，无任何其它关系。
  
• 线性结构：结构中的元素之间存在着一对一的线性关系。
  
• 树形结构：结构中的数据元素之间存在着一对多的层次关系。
  
• 图状结构（网状结构）：结构中的数据元素之间存在着多对多的任意关系。
  

1.4 存储结构的种类

存储结构主要有四种：顺序存储结构、链式存储结构、索引存储结构和散列存储结构。

• 顺序存储结构
  

• 用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。
• C语言中用数组来实现顺序存储结构。

• 链式存储结构
  
  

• 用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。
• C语言中用指针来实现链式存储结构。

• 索引存储结构
  

• 在存储结点信息的同时，还建立附加的索引表。
• 索引表中的每一项称为一个索引项，其一般形式是：(关键字，地址)
• 关键字是能唯一标识一个结点的那些数据项。
• 若每个结点在索引表中都有一个索引项，则该索引表称为稠密索引(Dense Index)。若一组结点在索引表中只对应一个索引项，则该索引表称之为稀疏索引(Sparse Index)。

• 散列存储结构

• 根据结点的关键字直接计算出该结点的存储地址。