2第二章抽象数据类型.

数据结构计算机科学系施化吉E-mail:[e-mail]第二章抽象数据类型和C++类•抽象数据类型(AbstractDataType,ADT)是用户在基本数据类型基础上定义和实现的数据类型。•一种抽象数据类型就是定义了一种新的数据元素集合和该数据元素集合上所允许的操作集合。•抽象数据类型在更高一级的抽象程度上实现了信息的隐藏和封装。•C++中类的定义体现了抽象数据类型的思想。C++中对于面向对象程序设计的支持,核心部分就是类的定义。2.1抽象数据类型2.1.1从数据类型到抽象数据类型•数据类型定义:一组性质相同的值的集合,以及定义于这个值的集合上的一组操作的总称.•C语言中的基本数据类型有charintfloatdoublevoid字符型整型浮点型双精度型无值•数据类型规定了其值的集合中元素的取值范围和对这些元素所能采用的操作。例如:整型定义了其数据集合中的元素的:可取的值是机器所能表示的最小负整数和最大正整数之间的任何一个整数。可用的操作有单目运算符+、-,双目运算符+、-、*、/、%,关系运算符、=、、=、==、!=和赋值运算符=等。而抽象数据类型：•抽象数据类型定义:是用户自己定义和实现的数据类型。是指一个数学模型以及定义在该模型上的一组操作。是用以表示应用问题的数据模型,由基本的数据类型组成,并包括一组相关的服务（或称操作）。抽象数据类型类似于在计算机机器语言的“位、字节和字”的基础上引入“字符、整数、浮点数和双精度数”等数据类型这样一种方法。这里,“字符、整数、浮点数和双精度数”等数据类型是对“位、字节和字”的抽象。因为计算机是使用二进制定点数和浮点数来实现数据的存储和运算的。从计算机硬件系统的角度看,计算机能处理的数据类型只包括位、字节和字。高级程序设计语言中引入了字符、整数、浮点数、双精度数后,程序中就可以直接使用“A”,“57”,“1.3E10”等数据表示,而不必使用它们的二进制表示。编译程序会将这些数据值转换成二进制码。这些数据表示就是二进制数据的抽象。一个抽象数据类型定义了一种新的数据元素集合和数据元素集合上所允许的操作集合。在高级程序设计语言中,由基本数据类型可以定义出更高一级的抽象数据类型,如各种表、队列、图甚至窗口、管理器等。下面以“队列”为例,解释抽象数据类型。一个队列是由若干个元素组成的一个序列以及这个序列上的相关操作所构成。其操作遵循的是“先到先服务”的原则。当新的元素进队列:加入在队列的尾部。当元素出队列:总是取出队列头的元素。队列中的元素可以是各种不同类型的对象。它们可以是整数,也可以是字符,也可以是字符串,甚至可以是关于一个学生的记录。不管是由什么对象组成队列,都不影响我们对“队列”本质的理解。“队列”本质就是“先进先出”。所以,可把队列看成是一个抽象数据类型。注意:对于一个其数据成员完全相同的数据类型,如果对它作不同的“限制”,即定义不同功能的一组操作,就可以形成不同的抽象数据类型。如栈和队列,可能都是相同的顺序表结构,但“限制”不同,则具有不同的服务,因此是不同的抽象数据类型。抽象数据类型与具体应用无关,这样我们在编程序的时候就可以把注意力集中在数据及其操作的理想模型上。如何描述抽象数据类型？2.1.2抽象数据类型描述抽象数据类型的特征是把使用和实现分离开来,实行封装和信息隐藏。每种抽象数据类型的描述应包括:•抽象数据类型的名(称)•数据集合的定义•每种操作的名称，该操作的输入、前置条件、功能、输出和后置条件等定义。一个抽象数据类型的描述在形式上可繁可简,描述形式举例如下:ADT抽象数据类型名isData数据元素集合和数据元素间的关系Operation构造函数数据值的初始化操作1输入:用户输入的数据值前置条件:执行此操作前数据所必需的状态动作:对数据进行的处理输出:操作后的返回值描述后置条件:系统执行操作后数据的状态操作2……操作3……endADT抽象数据类型名例2-1要设计一个掷骰子（zhìtóuzi）的程序,骰子可设计成一个抽象数据类型Dice.其数据类型包括：被掷骰子个数N,掷出骰子的总点数,每个骰子的点数；其操作包括:掷骰子,返回该次投掷的骰子总点数,打印所掷每个骰子的点数。ADTDiceisData//数据集合该次投掷骰子的个数。这是一个大于或等于1的整数。该次掷出的总点数。这是一个大于等于N且小于等于6N的整数。该次掷出的每个骰子的点数。这是一个表,表中的数值均为1到6的整数。Operation//操作Constructor构造函数确定被投掷骰子的个数Toss//掷骰子输入:无前置条件:无动作:掷骰子并计算总点数输出:无后置条件:投掷的总点数及每个骰子的点数Total//总点数输入:无前置条件:无动作:检索该次投掷的总点数数据项输出:返回该次投掷的总点数后置条件:无DisplayToss//各骰子的点数输入:无前置条件:无动作:打印该次投掷的各骰子的点数输出:无后置条件:无endADTDice•本章的其他内容,同学们在上学期已经学过,这里就不再重复。但请同学们注意复习,特别是有关模板的内容。结束2.2类与对象的基本概念2.2.1类与对象人类是一个类(class)。张三是人,李四是人,都是人类的实例(instance),或称对象(object)。一个类描述一类事物以及该类事物所应具有的属性,如人有身长、体重、文化程度、性别、年龄等。一个对象是类的一个实例,它具有确定的属性值,如张三身高1.80米,体重70公斤,大学本科,男,21岁。人类只有一个,人类的实例可以有无数个。对象是具体的,对象可以被创建和销毁。类是抽象的,类是无所不在的。例如桌子是一个类,人们不断打造各种尺寸和各种风格（属性）的桌子（桌子的实例）,打造桌子,又不断毁坏桌子。年复一年,旧的去了,新的又来,但桌子的概念没变。它是一个抽象的概念。应该称它为桌子类,以区别于打造的具体桌子。在计算机领域中,对象是指在应用问题中出现的各种实体、事件、规格说明等。它是由一组属性值和在这组值上的一组服务（或称操作）构成的。其中,属性值确定了对象的状态。例如,一个显示在计算机屏幕上的圆,作为一个几何对象,它是由圆心坐标、半径长度、边线颜色和内部颜色等属性值来确定位置、大小、颜色等状态。可以通过对象的服务来改变该对象的属性值。例如,服务move(x,y),将一个圆移动到由实数x,y所指定的圆心的新位置上。服务setRadius(r)、改变圆形的半径。服务setEdgeColor(c),改变圆形的边的颜色和其内部颜色。在面向对象的方法中,类是具有相同操作（服务）与相同数据格式（属性）的对象的集合。类中的每一个对象称为该类的一个实例（instance）。有一个计算机电子邮件系统,其主要工作涉及到发信人写信、收信人看信,还有电子邮件系统中信的收（receive）、发（send）及存储（store）等方面。例如,你在计算机上写一封信给你的同事John,那么这封信本身是一个对象。它具有一般信所有的共性。例如,有信的内容和允许你处理的一些方法或动作（读信、写信、发信等）。信的内容在计算机中称为数据,而需要处理的一些方法和动作,在计算机里则统称为“操作”,将这些信的共性汇集起来就有了对象这一概念。用计算机软件的术语可描述为公式对象=数据+动作所有的信的集合就构成了类,信中的内容不同（即对象的属性值不同）。类中的“信”都具有相同的服务:发信。发送英文信和发送日文信的方式是一样的。处理英文信和处理日文信有相同的方式,还有一些各自独有的方式。那么,如果建立两套平行的信件处理机制,显然是不经济的。可以由“信”这个类来定义两个类:“英文信”和“日文信”,它们保留了“信”类的服务,并添加上各自独立的服务。这种“保留”称为“继承”。“信”类称为基类,基类又可称为父类、超类或泛化类。它具有一般信件的公共操作,读、写、发送信。“英文信”、“日文信”称为派生类,又可称为子类或特化类。它们继承了其超类“信”和读、写、发送等操作,但同时又加上它们自己的“英文”和“日文”特定操作。类、派生类和实例的关系如图2-1所示。继承和重用是相辅相成的两个概念。要制造新的电冰箱,可以有两种选择:一种是从草图开始；另一种是对现有的电冰箱的型号加以改进。也许现有的型号已经令人比较满意,但如果再增加两个功能,会更加完美。在原有的型号基础上增加两组电路,很快就制造出来新的电冰箱了,被赋予一种新的型号。这就是继承和重用。继承是一种联结类的层次模型,并且允许和鼓励类的重用。层次结构的上层（或祖先类）最具有通用性。下层部分,即后代具有特殊性。类可以从它的祖先那里继承方法和实例变量（即对象中可访问的数据）,也可以修改或增加新的方法使之更符合特殊的需要。2.2.2消息与合作一个对象内具有过程和数据。外部的用户或对象对对象提出的请求,可以称为对该对象发送消息。在电子邮件系统的例中,对象“信”具有读信、写信或发信等操作,是由系统设计者开发并由对象“信”提供给用户的,用户可以发送一个消息（或称为请求）来请求所需的服务。在面向对象的方法中,另一个经常用的概念就是“合作”。合作是指两个对象之间共同承担职责来达到某一目标。当你告诉对象“信”,你想把它发送给John时,你此时的作用就是一个客户。对象“信”在这里相当于一个服务器。它提供给你一个服务。你还可以要求别的服务,如读、写信等。很多人用客户/服务器模型来描述面向对象模型。在这个模型中,各个对象具有完成不同任务的职责,客户对象可以通过服务器对象来完成一些任务。这里把两个对象共同承担职责称为“合作”。2.2.3多态性多态性机制是指允许不同类的对象对同一消息作出响应。以前面提到的电子邮件系统为例,现有局域网类对象LAN和宽域网类对象WAN,这两类对象均可对来自对象“信”的同一消息“发送给John”作出响应。即对同一个“发送给John”操作,可以有不同的实现方法。可以通过TCP-IP协议来找到John,也可通过X.25协议来找到John,这是在系统运行时由系统决定的。这种动态决定实现方法的机制称为动态联编（dynamicbinding）。一个多态性的例子:学生类应该有一个计算成绩的操作。大学生继承了中学生。对于中学生,计算成绩的操作是对语文、数学、英语等课程的计算,而对于后继的大学生,计算成绩的操作是对高等数学、计算机、普通物理等课程的计算。多态性引用静态类型和动态类型。多态引用的动态类型可以在程序执行期间在实例之间进行变化。在强类型面向对象环境中,运行时系统保持所有多态引用自动地和它们的动态类型相联结。静态类型是在程序上下文中由实体说明决定的。在编译时,系统知道并且决定对象在运行时可接受的有效类型。这一决定是通过分析继承图实现的。2.3面向对象的程序设计方法传统的程序设计技术采用的是算法分解。算法分解就是功能分解,该方法将软件看成一个处理过程,将该过程分解成若干个步骤的模块。一般都是在项目被分解成了功能模块后,再来考虑数据结构。面向对象的程序设计技术建立在对象分解的基础上,以类设计为核心。面向对象分解将软件看成有良好定义的对象组成的集合。这些对象是应用领域中实体的模型化体现。这些对象以及对象之间的相互作用构成了一个软件系统。当系统已被分解成为若干个对象之后,再去考虑功能的分解。面向对象分解最主要的优点在于它增进了软件的可重用性。面向对象分解同面向算法分解相比较更直观。程序设计阶段应给出所有对象的描述,这是构成程序的主要部分。同时,设计阶段也描述对象间相互作用的控制。对象设计阶段明确所有在程序中将要用到的对象,并给出每个类的定义,再设计出一些程序模块对类进行测试。类可以独立于系统之外测试,这是面向对象程序设计的一大特色。处理控制设计阶段完成程序的框架设计,它使用自顶向下方法创建主程序和子程序来控制对象间的相互作用。2.4C++类与对象•C++对于面向对象程序设计的支持,核心就是类的定义。•类由多个存放数据值的成员和加工数据的运算组成。这些运算称为成员函数,又称为方法。•成员函数用来响应发送给对象的消息。消息就是对成员函数的调用。