【数据结构】抽象数据类型

🦄个人主页:修修修也

🎏所属专栏:数据结构

⚙️操作环境:Visual Studio 2022

🎏数据类型

🎏抽象数据类型

结语

🎏数据类型

数据类型:是指一组性质相同的值的集合及定义在此集合上的一些操作的总称.

数据类型(data type)是和数据结构密切相关的一个概念,它最早出现在高级程序语言中,用以刻画(程序)操作对象的特性.

数据类型产生的原因是:

在计算机中,内存不是无限大的,如果我们要计算一个像:1+1=2,3+5=8这样的整型数字的加减乘除运算,显然不需要开辟很大的适合小数甚至字符运算的内存空间.于是计算机的研究者们就考虑,要对数据进行分类,分出来多种数据类型.

在用高级程序语言编写的程序中,每个变量,常量或表达式都有一个它所属的确定的数据类型.

类型明显或隐含地规定了在程序执行期间变量或表达式所有可能取值的范围,以及在这些值上允许进行的操作.

因此,数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

例如,C语言中的整型变量,其值集为某个区间上的整数(区间大小依赖于不同的机器),定义在其上的操作为加,减,乘,除和取模等算术运算.

比如,在C语言中变量声明:
int a,b;
这就意味着,在给变量a和b赋值时不能超出int的取值范围,变量a和b之间的运算只能是int类型所允许的运算.

C语言数据类型概览:

标准整数类型的存储大小和值范围的细节
类型	存储大小	值范围
char	1byte	-128 到 127 或 0 到 255
unsigned char	1byte	0 到 255
signed char	1byte	-128 到 127
int	2或4byte	-32,768 到 32,767 或 -2,147,483,648 到 2,147,483,647
unsigned int	2或4byte	0 到 65,535 或 0 到 4,294,967,295
short	2byte	-32,768 到 32,767
unsigned short	2byte	0 到 65,535
long	4byte	-2,147,483,648 到 2,147,483,647
unsigned long	4byte	0 到 4,294,967,295

注意,各种类型的存储大小与系统位数有关,但目前通用的以64位系统为主.

下面列出了32位系统与64位系统的存储大小的差别(windows相同):

标准浮点类型的存储大小,值范围和精度的细节
类型	存储大小	值范围	精度
float	4byte	1.2E-38到3.4E+38	6位有效位
double	8byte	2.3E-308到1.7E+308	15位有效位
long double	16byte	3.4E-4932到1.1E+4932	19位有效位

在C语言中,按照取值的不同,数据类型可以分为两类:

原子类型:是不可以再分解的基本类型,包括C语言中的基本类型(整型,字符型,实型,枚举类型),指针类型和空类型.
结构类型:由若干个类型组合而成,是可以再分解的.并且它的成分可以是非结构的,也可以是结构的.(如:整型数组是由若干个整形数据组成的).

引入"数据类型"的目的,从硬件的角度看,是作为解释计算机内存中信息含义的一种手段,而对使用数据类型的用户来说,实现了信息的隐蔽,即,将一切用户不必了解的细节都封装在类型中.

例如:用户在使用"整数"类型时,既不需要了解"整数"在计算机内部是如何表示的,也不需要知道其操作是如何实现的.如"两整数求和",程序设计者注重的仅仅是其"数学上求和"的抽象特性,而不是其硬件的"位"操作如何进行.

🎏抽象数据类型

抽象是指抽取出事物具有的普遍性的本质.

它是抽出问题的特征而忽略非本质的细节,是对具体事物的一个概括.

抽象是一种思考问题的方式,它隐藏了繁杂的细节,只保留实现目标所必需的信息.

举个例子,相信大家对这张图一定很熟悉吧:

而这张图经过抽象后:

由具体的人物动作抽象成了规则的色块,甚至最后色块的形状也已经不重要了,这样的抽出事物的特征忽略其非本质的细节,只保留实现目标所必须的信息,我们称之为抽象.

而当我们对已有的数据类型进行抽象,就有了抽象数据类型.

抽象数据类型(Abstract Data Type,ADT):是指一个数学模型及定义在该模型上的一组操作.抽象数据类型的定义仅取决于它的一组逻辑特性,而与其在计算机内部如何表示和实现无关.

比如我们上文提到的"整型"的例子:各个计算机,不管是大型机,小型机,PC,平板电脑,PDA,包括我们日常使用的手机都拥有"整数"类型,也需要整数间的运算,那么整型其实就是一个抽象数据类型,尽管它在上面提到的这些在不同计算机中实现方法上可能不一样,但由于其定义的数学特性相同,在计算机编程者看来,它们都是相同的.因此,"抽象"的意义在于数据类型的数学抽象特性.

并且,抽象数据类型不仅仅指那些已经定义并实现的数据类型,还可以是计算机编程者在设计软件程序时自己定义的数据类型.

比如我们编写关于计算机绘图或者地图类的软件系统,经常都会用到坐标.也就是说,总是有成对出现的x和y,在3D系统中还有z出现,既然这三个整型数字是始终在一起出现,我们就定义一个叫point的抽象数据类型,他有x,y,z三个整型变量,这样我们很方便地操作一个point数据变量就能知道这一点的坐标了.

我们用C语言实现一下这个叫point的抽象数据类型:

typedef struct {int x;int y;int z;
} point;int main() {//创建类型为point的两个变量p1,p2point p1;point p2;//给变量p1赋值p1.x = 1;p1.y = 2;p1.z = 3;//给变量p2赋值p2.x = 4;p2.y = 5;p2.z = 6;return 0;
}

根据抽象数据类型的定义,它还包括定义在该模型上的一组操作.还拿上面的point举例,我们不光定义了它的原子类型组成(int x;int y;int z),抽象数据类型同样也包含了坐标间可以进行的操作,如坐标间求距离啊,坐标间求中点啊,坐标间求直线方程等一系列操作都被包含在point这一抽象数据类型的定义中.

再比如"超级玛丽"的游戏主角"马里奥",我们给他定义了几种基本操作,走(前进,后退,上,下),跳,发射子弹等.

一个抽象数据类型定义了:一个数据对象,数据对象中各数据元素之间的关系及对数据元素的操作.

至于,一个抽象数据类型到底需要哪些操作,这就只能由设计者根据实际需要来定.像马里奥,可能开始只有两种操作,走和跳,后来发现应该要增加一种发射子弹的操作,再后来发现有些玩家希望它可以走得快一点,就有了按住发射子弹键后前进就会"跑"的操作.这都是根据实际情况来设计的.

事实上,抽象数据类型体现了程序设计中问题分解,抽象和信息隐藏的特性.

抽象数据类型把实际生活中的问题分解为多个规模小且容易处理的问题,然后建立一个计算机能处理的数据模型,并把每个功能模块的实现细节作为一个独立的单元,从而使具体实现过程隐藏起来.

为了便于在后面对抽象数据类型进行规范的描述,我们给出了描述抽象数据类型的标准格式:

ADT 抽象数据类型名
Data数据元素之间逻辑关系的定义
Operation操作1初始条件操作结果描述操作2......操作n......
endADT

结语

在学习了数据结构中抽象数据类型后,我们数据结构的绪论篇的四小节就正式完结了,接下来我们将进入又一个新的篇章:算法.在新的章节中,我们将一起学习并体会到一些大佬编写的"惊为天人"的算法,它们又是如何在其他同样能解决问题的算法中脱颖而出的,其中涉及到的算法设计,算法分析,算法时间复杂度,算法空间复杂度等知识将会对我们后续的学习提供非常大的帮助,希望大家能有所收获,一起学习,一起进步!