下载文档原格式
数据类型和抽象数据类型⼀.数据类型先看看为什么会有不同的数据类型呢？很简单，很多东西不能⼀概⽽论，⽽是需要更精确的划分。
计算机计算1+1并不需要多么⼤的空间，但是计算10000000000+1000000000就得需要有个⽐较⼤的空间来放。
还有有时候会计算⼩数，⼩数的位数不⼀样，需要的空间也就不⼀样。
数字1和字母a也需要区分啊，于是开发者就想出了“数据类型”这⼀招，⽤来描述不同的数据的集合。
我记得最早接触的数据类型就是int了。
当初⼀个int a;就把我看得神魂颠倒，不知所以。
像这种类型，就是⼀个基本的数据类型。
以前总以为数据类型就是⼀个描述数据到底是什么玩意⼉的东东，现在再去看，倒是有点⼉浅了。
数据类型学术点呢，是⼀个值的集合和定义在这个值集合的⼀组操作的总称。
⼀种数据类型也可以看成是⼀种已经实现了的“数据结构”。
按“值”是否可分解，将其分为两类：1.原⼦类型：其值不可分解，通常由语⾔直接提供，像C++中的int,float,double等等。
2.结构类型：其值可以分解为若⼲部分（分量），是程序员⾃定义的，⽐如结构体，类等等。
ps：对于什么是“原⼦”，经常会看到什么“原⼦操作”，“原⼦类型”，⼀般就是指不可再分的。
⼆.抽象的数据类型抽象数据类型（abstract data type,ADT）只是⼀个数学模型以及定义在模型上的⼀组操作。
通常是对数据的抽象，定义了数据的取值范围以及对数据操作的集合。
其实，数据类型和抽象数据类型可以看成⼀种概念。
⽐如，各种计算机都拥有的整数类型就是⼀个抽象数据类型，尽管实现⽅法不同，但他们的数学特性相同。
抽象数据类型的特征是实现与操作分离，从⽽实现封装。
看到有⼈举出了“超级玛丽”例⼦，觉得写得很不错，如下：就像“超级玛丽”这个经典的任天堂游戏，⾥⾯的游戏主⾓是马⾥奥，我们给他定义了基本操作，前进、后退、跳、打⼦弹等。
这就是⼀个抽象数据类型，定义了⼀个数据对象、对象中各元素之间的关系及对数据元素的操作。
二元关系与抽象数据类型笛卡尔积全序与偏序ADT <类型名>{数据：<数据描述>操作：<操作声明>};…《数据结构与算法》Previously …数据与算法数学模型•C++简单回顾•二元关系及性质•数据的逻辑与存储结构•数据类型与抽象数据类型虽然Java ，C#，Python 等高级语言也应用广泛，大量软件代码仍用C/C++编写，各类编程资源丰富；C++支持各种简单数据类型以及抽象数据类型； C++语言编译器发展成熟，程序执行效率高； C++在信息科学类教育中被广泛使用；数据与算法本质不局限于语言，本课程采用C/C++描述.&简单回顾构造函数与类同名，在对象生成时调用。
析构函数在删除对象时调用。
类的成员函数可以访问其成员变量。
private 修饰的仅能在类内部访问；protected 修饰的可被子类访问；public 修饰的大家都能访问；class intStack {public:intStack(int sz=10);~intStack();void Push(int);int Pop();protected:int* stack;int top;private:int size();};&简单回顾new int [sz]创建长度为sz 的整型数组；delete[]释放数组占用的内存;成员函数可以访问成员变量，注意一元操作符的顺序；intStack::intStack(int sz=10){stack = new int [sz];top = -1;}intStack::~intStack{delete [] stack;}void intStack::push(int k){stack[++top] = k;}int intStack::pop(){return stack[top--];}&简单回顾…{ intStack S1(1000);S1.push(10);S1.put(12);S1.push(3.1415);S1.size();} //~intStack()被调用……{ intStack* S2 = new intStack(1000);S2->push(10);S2->put(12);delete S2;//~intStack()被调用} …&简单回顾//Warning? Error?不愿意用指针？用引用(reference)!…{ intStack S1(1000);intStack& S2=S1;S2.push(10);cout<<S1.pop()<<endl; //print 10} //~intStack()被调用…void func1(intStack & S){ … }void func2(const intStack & S){ … }&简单回顾•C++简单回顾•二元关系及性质•数据的逻辑与存储结构•数据类型与抽象数据类型二元关系及性质 集合的笛卡尔积(Cartesian product)◦集合A,B:A={a1,a2},B={b1,b2}；◦A对B的笛卡尔积，记作A B，定义为：◦A B={<a,b>|a∈A且b∈B}◦则有:◦A B={<a1,b1>,<a1,b2>,<a2,b1>,<a2,b2>}◦一般的：A B B A,(A B) C A B C);◦扩展到多个集合的笛卡尔积.二元关系(binary relation)◦定义：设有集合A,B ，其笛卡尔积A B 的任意一个子集R ⊆A B ，被称为A 到B 的一个二元关系；如果A=B ，R 就被称作A 上的一个二元关系◦二元关系实际上是表述了集合A 和集合B 中元素的某种关联性；例如足球联赛中每轮的对阵情况就是足球俱乐部集合上的一个二元关系；◦如果<a,b>∈ R ，则’a 是b 关于R 的前件’，而’b 是a 关于R 的后件’.二元关系及性质二元关系基本性质◦设R 是集合A 上的二元关系：◦自反性：对于每个a ∈ A ，都有<a,a>∈ R ；◦反自反性：对于所有的a ∈ A ，都有<a,a>∉R ；◦对称性：如果有<a,b>∈ R ，则必有<b,a>∈ R ；◦反对称性：如果有<a,b>∈ R 且<b,a>∈ R ，则必有a=b ；◦传递性：如果有<a,b>∈ R 且<b,c>∈ R ，则必有<a,c>∈ R.二元关系及性质常见的二元关系◦实数集合上的=,≤，≥的关系；◦集合的=，⊆，⊂的关系；◦三角形的全等关系，相似关系等；◦拓扑空间的同胚关系(庞加莱猜想)；◦清华校友关系，用户名和密码；◦……二元关系及性质等价关系(equivalence relation)◦同时满足自反性，对称性和传递性的关系；◦如果R 是等价关系，且<a,b> ∈ R ，则称a 等价于b ，记作a~b ；◦设R 是非空集合A 上的等价关系，则A 中相互等价的元素所构成的不相交的子集成为A 的R 等价类；◦上面提到的：实数集合上的相等关系，集合的相等关系，清华校友关系，三角形全等或相似关系，以及拓扑空间的同胚关系，均是等价关系.二元关系及性质偏序关系(partial order relation)◦同时满足自反性，反对称性和传递性的关系；◦如果R 是集合A 上的偏序关系，则称<A,R>为偏序集合，也可记作<A,≤>；◦偏序集合<A,≤>中的x,y ∈A ，如果有x ≤y 或y ≤x 成立，则称x,y 是可比较的；◦实数集上的≤关系，集合的⊆关系,均是偏序关系.二元关系及性质拟序关系(quasi order relation)◦同时满足反自反性，反对称性和传递性的关系；◦也被称作严格偏序关系(strict partial order)◦实数集上的<关系，集合的⊂关系,均是偏序关系.二元关系及性质全序关系(total order relation)◦如果R 是集合A 上的偏序关系，且A 中的任意两个元素x,y 都可比较，则称R 是A 上的全序关系；◦定义了全序关系的集合称为全序集；◦实数集合上的≤关系是全序关系.二元关系及性质思考题：举例，不是全序关系的偏序关系？•C++简单回顾•二元关系及性质•数据的逻辑与存储结构•数据类型与抽象数据类型数据逻辑结构：数据(D)以及数据元素之间的关系(R)，记作B=(D,R)； 线性结构：头元素仅有一个后件，尾元素仅有一个前件，其他元素有且仅有一个前件、一个后件； 非线性结构数据的逻辑及存储结构头尾数据存储结构(物理结构)：数据元素及其关系在计算机中的表示(representation). 顺序存储：数据元素按逻辑顺序依次存放于数据的逻辑及存储结•C++简单回顾•二元关系及性质•数据的逻辑与存储结构•数据类型与抽象数据类型C++中的数据类型◦五种基本数据类型：无值型(void)，字符型(char)，整型(int)，单精度浮点型(float)，双精度浮点型(double)；◦可在基本数据类型前添加修饰符：signed,long 等;◦各种类型均有定义相关操作，如+,-,*,/,%等； 数据类型◦性质相同的元素的集合以及定义在其上的一组操作；◦’封装好’的数据结构，用户无需知道计算机内的表示和实现细节；◦高级语言中的数据类型分为原子类型和结构类型.抽象数据类型ADT:Abstract Data TypeADT 是抽象层次更高，范畴更广的数据类型；◦定义：描述数据的逻辑结构和所允许的操作；◦实现：完成功能，其方式取决于平台、语言等； ADT 的优点：◦使程序清晰易读，便于开发、调试、扩展与维护；◦增加了软件的可复用度；◦通过数据封装，分离使用和实现，增强关键数据的安全性.抽象数据类型ADT 例子：三角形ADT Triangle {数据对象：D={x1,x2,x3,y1,y2,y3| ∈ R}数据关系：R={<x1,y1>,<x2,y2>,<x3,y3>|三点坐标}基本操作：CreateTriangle(x1,x2,x3,y1,y2,y3)操作结果：给出三点坐标，构造三角形Area(Triangle t, &a)初始条件：三角形存在操作结果：计算三角形面积，以a 返回；Perimeter(Triangle t, &p)初始条件：三角形存在操作结果：计算三角形周长，以p 返回；InscribedCircle(Triangle t, &Cx, &Cy, &r)初始条件：三角形存在操作结果：计算三角形内切圆，返回圆心坐标及半径；}ADT Triangle (x1,y1)(x2,y2)(x3,y3)抽象数据类型ADT 的描述规范基本操作参数列表◦赋值参数提供输入值；◦引用参数用&修饰，用于结果返回.ADT 抽象数据类型名{数据对象：<数据对象定义>数据关系：<数据关系定义>基本操作：基本操作名（参数列表）初始条件：<初始条件描述>操作结果：<操作结果描述>… …}ADT 抽象数据类型名抽象数据类型编程范式(paradigm)◦面向过程编程(Pascal,C )◦基于对象编程(OO,but encapsulation only )◦面向对象编程(C++,Java)◦面向侧面编程(AspectJ)◦函数式编程(F#,LISP)◦…… ADT 与面向对象◦面向对象语言提供了良好的封装特性；◦继承(inheritance)与多态(polymorphism)方便模块的复用；◦ADT 出发可以很容易实现面向对象编程.抽象数据类型/* Q & A */。
浙江大学城市学院实验报告课程名称数据结构基础实验项目名称实验二抽象数据类型的表示和实现学生姓名专业班级学号实验成绩指导老师（签名）日期一.实验目的和要求1、通过抽象数据类型三元组的表示和实现，了解抽象数据类型的定义方式。
2、掌握抽象数据类型的定义方式和用C语言实现的方法。
3、熟悉如何运用主函数检验各基本操作函数的正确性的具体操作。
二.实验内容1、认真阅读以下有关抽象数据类型的知识：（1）抽象数据类型的概念抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。
抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，就不影响其外部的使用。
一个含抽象数据类型的软件模块通常应包含定义、表示和实现3个部分。
抽象数据类型通常采用以下格式定义：ADT抽象数据类型名{数据对象：<数据对象的定义>数据关系：<数据关系的定义>基本操作：<基本操作的定义>} ADT抽象数据类型名（2）三元组的抽象数据类型定义及表示我们以抽象数据类型三元组为例，说明抽象数据类型是如何定义的。
三元组实际上就是一个数据对象中有3个数据元素。
三元组中元素的数据类型，可以是整型数，也可以是字符、浮点数或者更复杂的数据类型。
以下是三元组的抽象数据类型定义：ADT Triplet{数据对象：D={e1, e2, e3 | e1, e2, e3∈ElemSet (ElemSet为某个数据对象的集合)}数据关系：R1={<e1, e2>, <e2, e3>}基本操作：InitTriplet(&T, v1, v2, v3)操作结果：构造三元组T，元素e1, e2和e3分别被赋以v1, v2, v3值DestroyTriplet(&T)操作结果：三元组T被销毁Get(T, i, &e)初始条件：三元组T已存在，1≤i≤3操作结果：用e返回T的第i元的值IsAscending(T)初始条件：三元组T已存在操作结果：如果T的三个元素按升序排列，则返回1，否则返回0 IsDecending(Triplet T);初始条件: 三元组T已存在操作结果: 如果T的三个元素按降序排列，则返回1，否则返回0 Put(&T, i, e)初始条件：三元组T已存在，1≤i≤3操作结果：改变T的第i元的值为eMax(T, &e)初始条件：三元组T已存在操作结果：用e返回T的三个元素中的最大值Min(T, &e)初始条件：三元组T已存在操作结果：用e返回T的三个元素中的最小值} ADT Triplet三元组在计算机中的具体存储方式可以采用动态分配的顺序存储结构，如图所示：Triplet ElemType动态分配的顺序存储的三元组2、在计算机中实现上述三元组抽象数据类型。
【⼆】、什么是抽象数据类型【⼆】、什么是抽象数据类型在上⼀篇【】中我详细介绍了我对数据结构的理解，其实描述数据结构，有⼀个很好的⽅法叫抽象数据类型。
下⾯我会详细介绍抽象数据类型。
抽象数据类型英⽂名叫(Abstract Data Type)，这⾥有两个关键词，⼀个叫“数据类型”，⼀个叫“抽象”，它们分别是什么意思呢？⾸先说什么是数据类型呢？数据类型，它包含了两个东西，⼀个是“数据对象集”，就是我们说的“是什么东西”，第⼆个是“数据集合相关联的操作集”，就上我在上⼀篇中说的，我们不能单纯讲怎么去处理图书，我们是要对这些图书进⾏操作的，这两件事情：图书的摆放，对图书的操作，是紧密结合在⼀起的。
这两个东西在C语⾔⾥是独⽴处理的，但是在⼀些⾯向对象的语⾔⾥边，⽐如C++、Java，你就会发现，它们很好的为数据类型专门设计了⼀种机制，就是⼀个“类”，把这个数据集跟它相关的操作集封装在⼀个类⾥⾯。
那再说什么是抽象呢？总体来说，我们只描述数据对象集和相关的操作集"是什么"，我们不关⼼“它是怎么做到的”这个问题。
可能到现在⼀些没有基础的朋友看起来还是很抽象，没关系，我再举个例⼦，可能帮助你更好的理解抽象数据类型到底是个什么东西，这个例⼦是关于“矩阵”的抽象数据类型的定义。
⾸先我们要给这个抽象数据类型⼀个名称叫“矩阵”，然后我们要描述⼀下它的数据对象集，⼀个N M的矩阵，是由N M个矩阵的元素构成的，我们把这个元素描述成⼀个三元组a,i,j，其中a是这个矩阵元素的值，同时我们还需要知道这个矩阵元素在矩阵⾥⾯所处的位置，就是它的⾏号i和列号j，就这样描述了⼀个数据的对象集，相关联的操作集有很多很多(如下图)我们来看⼀下，为什么这个就叫做“抽象”的表⽰呢？⾸先我们来看，在描述数据对象集的时候，说a是矩阵元素的值，那这个值是float？还是double？还是int？我们在这个抽象数据类型中描述是不关⼼的，相应地，当需要对它的元素值进⾏操作的时候，我们返回的也是ElementType,是⼀个通⽤的元素类型，我在实现这个矩阵相关的所有函数的时候，我在头上写⼀个define,你需要什么，我就把它define(定义)成什么样⼦，这样的话，你实现的这些函数是跟“你那个矩阵元素到底是哪种类型”是没有关系的，哪种类型都是可以运算的。
抽象数据类型1.数据类型数据类型（data type）是⼀个值的集合和定义在这个值集上的⼀组操作的总称。
原⼦类型:如语⾔的整形、字符型等标准类型及指针等简单的导出类型和空类型。
结构类型：其值是由若⼲成分按某种结构组成的，因此是可以分解的，并且它的成分可以是⾮结构的，也可以是结构的，通常是由标准类型派⽣的。
例如，C/C++中的数组、结构等类型。
2.抽象数据类型（abstract data type, ADT）抽象数据类型是指⼀个数学模型以及定义在该模型上的⼀组操作。
它通常是指对数据的某种抽象，定义了数据的取值范围及其结构形式，以及对数据的操作的集合。
“抽象”的意义在于数据类型的数学抽象特性。
3.抽象数据类型的描述⽅法（D，S，P）D是数据对象，S是D上的关系集，P是对D的基本操作集。
4.抽象数据类型⼀般可以由数据对象、数据关系及基本操作来定义。
ADT 抽象数据类型{数据对象（数据对象的定义）数据关系（数据关系的定义）基本操作（基本操作的定义）}ADT 抽象数据类型名其中，数据对象和数据关系的定义⽤集合描述，基本操作的定义格式为返回类型基本操作名（参数表）5.对于每个操作，包含下列5个基本要素：输⼊前置条件过程输出后置条件6.基本操作有两种参数：赋值参数只为操作提供输出值；引⽤参数以&开头，除可提供输出值外，还将返回操作结果。
7.⾯向对象的程序设计（OPP）⽅法。
在⾯向对象程序设计语⾔中，借助对象描述抽象数据类型，存储结构的说明和操作函数的说明被封装在⼀个整体结构中，这个整体结构称为类（class），属于某个类的具体变量称为对象（object）。
8.ADT和类的概念实际上反映了程序或软件设计的两层抽象：ADT相当于是在概念层（抽象层）上描述问题，⽽类相当于是在实现层上描述问题。
抽象数据类型与C++中类的对应关系如下：抽象数据类型——类数据对象——数据成员（属性）基本操作——成员函数（⽅法）。
抽象数据类型名词解释抽象数据类型又称原子类型，是一种能够将现实世界的对象和它们的数值之间的对应关系完全或部分抽象出来的数据类型。
记忆，即对于事物的名称、概念、属性等的识记过程。
语言信息的编码表示是以记忆为基础的。
语言信息的识别和理解要依靠人们的记忆。
人类由于在进化过程中逐渐形成了语言信息识别和储存的能力，这使得人类可以超越一般动物仅仅依赖本能来做出行动。
正是因为有了这个能力，我们才能利用大脑高度发达的思维能力去认识世界。
记忆的内容就是语言信息。
例如，我们听到和看到某一个词语，可能很快就可以在头脑中回忆起它的含义。
通过这样的认知活动，我们就已经完成了对该词语的记忆过程。
当然，在记忆过程中，所需要的识别、判断和评价也同时进行。
这些都是语言信息的识别和判断。
例如，在我们对一张地图进行识别和判断后，会发现该地图中包括了两个比较重要的信息。
其中之一是地图上那条我们认为非常重要的河流。
其二是，地图上标注的经纬线指向西北方向。
如果不告诉我们河流名字，我们可能会怀疑它是否属于内陆河。
但是，如果我们告诉我们它是印度河，则就不会怀疑它的确属于印度。
抽象数据类型也被称为原子类型，是能够保证各个类型具有互换性的数据类型。
在各个抽象数据类型中，都至少有一种构造体，它们有着相同的表示，并且可以转换为另一种构造体。
对于任意一个抽象数据类型的对象来说，只要它具备合适的类型，便能够被归入其中一个类型；对于任何一个类型来说，只要该类型能够满足相应的约束条件，便能够成为另一个类型的构造体。
在程序设计语言中，数据类型与对象类型之间的映射关系就是一种抽象的关系，通常称之为抽象数据类型与对象类型的映射规则。
例如，我们在运行程序的过程中，必须按照一定的规则给每个变量赋予一个适当的类型，而无论这个变量的实际类型是什么。
例如，假设我们在命令窗口中输入要计算机数学公式1+2+3+4+5……，而电脑的屏幕显示了该输入结果，即1+3+4+5……。
通常，该电脑会直接按照最高层次的类型转换方法将这些公式转换为1+2+3+4+5……，然后根据这些公式计算出1+2+3+4+5……，最终得出这个运算结果。
抽象数据类型
抽象数据类型（Abstract Data Type，简称ADT）是一
种数学模型，它具有一套定义的操作，这些操作可以对数据进行操作，进而实现相应的目的。
它是一种面向对象的技术，主要用于创建存储数据的数据结构和逻辑功能。
ADT具有通用性，所谓通用性，指的是数据结构、
算法、服务或者实体（如进程）可以从现有的抽象数据类型中获得足够的灵活性和复用性，而不必依赖于特定应用程序服务或具体实现。
早在上个世纪二十年代，科学家就开始使用抽象数据类型建模数据和实现程序。
真正把它作为一个研究领域的，不过是在上个世纪六十年代。
在计算机科学，抽象数据类型也可以称之为虚拟数据类型或抽象数据对象（ADO）。
抽象数据类型的发展离不开它的两个组成部分：抽象数据结构和相关算法。
ADT提供了一种强大的模型，有助
于模型化数据，并设计出促进求解问题的操作。
此外，从现有ADT获取模型成功并不容易，因为对于不同ADT，其对应的实现解决方案大多不兼容。
此外，抽象数据类型还分为非有穷和有穷类型，前者用于存储无限量的情况，而后者只能存储有限量的情况。
其中，有穷类型也是抽象数据类型的一种类型，主要应用于限制性问题求解。
总而言之，抽象数据类型（ADT）是一种重要的数据模型，它是面向对象编程技术的一个重要组成部分，用于表达和记录数据以及实现逻辑功能。
它可以通过抽象数据结构和抽象算法来模拟现实世界的各种情况，从而使计算机科学完成数据的建模和处理工作。
抽象数据类型数据结构的三个⽅⾯：数据的逻辑结构：线性结构：线性表、栈、队⾮线性结构：树形结构、图形结构数据的存储结构：顺序存储、链式存储数据的运算：插⼊、删除、修改、查找、排序什么叫数据的逻辑结构？表⽰数据元素之间的逻辑关系，即从逻辑关系上描述数据，它与数据的存储⽆关，是独⽴于计算机的。
集合结构：仅同属⼀个集合线性结构：⼀对⼀ 线性树结构：⼀对多 ⾮线性图结构：多对多 ⾮线性什么叫数据的物理结构？物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表⽰（或映像）。
它依赖于计算机。
存储结构详解：“数据元素”的映像“关系”的映像两种不同的存储结构：顺序存储结构、链式存储结构什么是数据的运算？在数据的逻辑结构上定义的操作算法。
它在数据的存储结构上实现。
最常⽤的数据运算有5种：插⼊，删除，修改，查找，排序抽象数据类型（Abstract Data Type）数据：数据是指能够输⼊到计算机当中，且能被计算机接受和处理的，字符，图形，图像，⾳频，视频等的总称。
数据类型：是⼀个值的集合和定义在该值集上的⼀组操作的总称。
int、string、float、double这些数据类型均包含两个内容：⼀是数据对象集，它确定了⼀个取值范围，就像书店⾥的每⼀本书⼀样。
另⼀个是作⽤域数据对象集上的操作集，也就是仅作⽤于相应的数据元素集合上，就像从书架上找书和向书架上插⼊新书这些操作仅对应于相应书架⼀样。
这两个内容在c语⾔中是独⽴处理的，⽽在⾯向对象程序设计语⾔中，则是将两者封装在⼀起，称为类。
抽象数据类型：由⽤户定义，⽤以表⽰应⽤问题的数据模型。
它由基本的数据类型构成，并包括⼀组相关的服务（或称操作）。
它与数据类型实质上是⼀个概念，但其特征是使⽤与实现分离，实⾏封装和信息隐蔽（独⽴于计算机）。
定义抽象数据类型“复数”ADT Complex{数据对象：D {e1,e2 e1,e2∈RealSet}数据关系：R1 {<e1,e2> | e1是复数的实数部分，|e2是复数的虚数部分}}基本操作：AssignComplex（&Z,v1，v2）操作结果：构造复数Z，其实部和虚部分别被赋以参数v1和v2的值DestroyComplex（&Z）操作结果：复数Z被销毁。
