基本概念

数据

是能输入计算机且能被计算机处理的各种符号的集合

数据元素

是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。也简称为元素，或记录、节点或顶点。

数据项

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

数据对象

是性质相同的数据元素的结合,是数据的一个子集。
例如: 整数数据对象是集合N={0,1,-1,…}

数据结构

• 数据元素不是孤立存在的,他们之间存在着某种关系,数据元素相互之间的关机称为结构
• 是指相互之间存在一种或多种特定关系的数据元素集合

数据结构两个层次: 逻辑结构，物理结构

逻辑结构的种类1:

线性结构:

有且仅有一个开始和一个终端节点,并且所有节点都最多只有一个直接前驱和一个直接后继。

非线性结构:

一个节点可能有多个直接前驱和直接后继

逻辑结构的种类2:

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

存储结构的种类

顺序存储结构

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

链式存储结构

• 用一组任意的存储单元存储数据元素,数据元素之间的逻辑用指针来表示
• c语言中用指针来实现链式存储表示

索引存储结构

• 在存储节点信息的同时，还建立附加的索引表

散列存储结构

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

数据类型和抽象数据类型

• 在使用高级程序设计语言编写程序时,必须对程序中出现的每个变量、常量或表达式,明确说明他们所属的数据类型
  • 例如: C语言中
    • 提供int,char, float, double等基本数据类型
    • 数组、结构、共用体、枚举等构造数据类型
    • 还有指针,空(void)类型
    • 用户也可用typedef自己定义数据类型
• 一些最基本数据结构可以用数据类型来实现,如数组、字符串等
• 而另一些常用的数据结构,如栈、队列、树、图等,不能直接用数据类型来表示
• 高级语言中的数据类型明显地或隐含地规定了在程序执行期间变量和表达的所有可能的取值范围,以及 在这些数值范围上所允许进行的操作