数据结构（DS）学习笔记（二）：数据类型与抽象数据类型

参考教材：数据结构C语言版（严蔚敏，吴伟民编著）

工具：XMind、幕布、公式编译器

正在备考，结合自身空闲时间，不定时更新，会在里面加入一些真题帮助理解数据结构

1.1数据类型

1.2抽象数据类型（ADT）

1.3多形数据类型

1.4抽象数据类型的表示与实现

1.1数据类型

数据类型就是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。

数据类型=值的集合+值集合上的一组操作

C语言中基本数据类型：

整型：int 长整型：long int 短整型：short int

浮点型（单精度）：float 浮点型（双精度）：double 字符型：char 布尔型：bool

不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。

例如：bool类型的值为：true、false。可进行的操作：与、或、非...

作用：

约束变量或常量的取值范围；约束变量或常量的操作

1.2抽象数据类型（ADT）

抽象数据类型是指一个数学模型以及定义在此数学模型上的一组操作。与其在计算机内部如何表示无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。

抽象数据类型 = 数据的逻辑结构 + 抽象运算（运算的功能描述）

抽象数据类型的形式定义

用三元组表示（D，S，P）：D是数据对象，S是D上的关系集，P是对D的基本操作集。

定义抽象数据类型：

ADT抽象数据类型名{数据对象：<数据对象的定义>数据关系：<数据关系的定义>基本操作：<基本操作的定义>
}ADT抽象数据类型

数据对象和数据关系的定义用伪码（伪代码）描述。

基本操作的定义格式为：

基本操作名（参数表）初始条件：<初始条件描述>操作结果：<操作结果描述>

赋值参数只为操作提供输入值；

引用参数以&打头，除了可以提供输入值，还将返回操作结果。

三种抽象数据类型

（一）原子类型：属于原子类型的变量的值是不可以分解的。

（二）固定聚合类型：属于固定聚合类型的变量，其值由确定数目的成分按某种结构组成

（三）可变聚合类型：构成可变聚合类型“值”的成分的数目不确定。比如定义一个“有序整数序列”的抽象数据类型，其中序列的长度是可变的。

1.3多形数据类型

多形数据类型是指其值的成分不确定的数据类型。一个抽象数据类型里面的元素可以是整数或字符或字符串，甚至更复杂地由多种成分构成（只要能进行关系运算即可）

1.4抽象数据类型的表示与实现

（一）预定义常量和类型

//函数结果状态代码
#define    TURE           1
#define    FALSE          0
#define    OK             1
#define    ERROR          0
#define    INFEASIBLE     -1
#define    OVERFLOW       -2
//Status是函数的类型，其值是函数结果状态的代码
typedef  int  Status;

（二）数据结构的表示（存储结构）用类型定义（typedef）描述。数据元素类型约定为ElemType，有用户在使用该数据类型时自行定义

（三）赋值语句

简单赋值变量名 = 表达式

串联赋值变量名1 = 变量名2 = ... = 变量名k = 表达式

成组赋值 (变量名1，...，变量名k) = (表达式1，...，表达式k)；

结构名 = 结构名；

结构名 = （值1，...，值k)；

变量名[ ] = 表达式;

变量名[起始下标..终止下标] = 变量名[ 起始下标..终止下标]；

交换赋值变量名 $\leftarrow \rightarrow$ 变量名；