1.2基本概念和术语 抽象数据类型:一个数学模型以及定义在该模型上的一组操 作。抽象数据类型的定义仅取决于它的一组逻辑特性,而与 其在计算机内部如何表示和实现无关,即不论其内部结构如 何变化,只要它的数学特性不变,都不影响其外部的使用。 ●抽象数据类型实际上就是对该数据结构的定义。因为它定义 了一个数据的逻辑结构以及在此结构上的一组算法。 和数据结构的形式定义相对应,抽象数据类型可用三元组描 述如下:(D,S,P ●D是数据对象,S是D上的关系集,P是对D的基本操作集。 北京邮电大学自动化学院 31
北京邮电大学自动化学院 31 ⚫ 抽象数据类型：一个数学模型以及定义在该模型上的一组操 作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与 其在计算机内部如何表示和实现无关，即不论其内部结构如 何变化，只要它的数学特性不变，都不影响其外部的使用。 ⚫ 抽象数据类型实际上就是对该数据结构的定义。因为它定义 了一个数据的逻辑结构以及在此结构上的一组算法。 ⚫ 和数据结构的形式定义相对应，抽象数据类型可用三元组描 述如下： （Ｄ，Ｓ，Ｐ） ⚫ D是数据对象，S是D上的关系集，P是对D的基本操作集。 1.2 基本概念和术语
1.2基本概念和术语 ●本书采用以下格式定义抽象数据类型 抽象数据类型的定义: ADT抽象数据类型名{ 数据对象:<数据对象的定义> 数据关系:<数据逻辑关系的定义> 基本操作:<基本操作的定义> }ADT抽象数据类型名 ●基本操作的定义格式为: 基本操作名(参数表) 初始条件:<初始条件描述> ●操作结果:<操作结果描述> 北京邮电大学自动化学院
北京邮电大学自动化学院 32 ⚫ 本书采用以下格式定义抽象数据类型 ⚫ 抽象数据类型的定义： ADT抽象数据类型名{ 数据对象：<数据对象的定义> 数据关系：<数据逻辑关系的定义> 基本操作：<基本操作的定义> ⚫ }ADT抽象数据类型名 ⚫ 基本操作的定义格式为： 基本操作名（参数表） 初始条件：<初始条件描述> ⚫ 操作结果：<操作结果描述> 1.2 基本概念和术语
1.2基本概念和术语 ●抽象数据类型三元组的定义: ADT Triplett 数据对象:D={e1,e2,e3|e1,e2,e3∈E| emSet} 数据关系:R1={e1,e2>,e2,e3>} 基本操作: InitTriplet(&T, v1, v2, v3) ●操作结果:构造了三元组T,元素e1,e2和e3分别赋以参数 v1,v2和v3的值 ●} ADT Triplet 北京邮电大学自动化学院
北京邮电大学自动化学院 33 ⚫ 抽象数据类型三元组的定义： ⚫ ADT Triplet{ ⚫ 数据对象：D={e1,e2,e3|e1,e2,e3ElemSet} ⚫ 数据关系：R1={<e1,e2>,<e2,e3>} ⚫ 基本操作： ⚫ InitTriplet(&T,v1,v2,v3) ⚫ 操作结果：构造了三元组T，元素e1,e2和e3分别赋以参数 v1,v2和v3的值。 ⚫ } ADT Triplet 1.2 基本概念和术语
1.2基本概念和术语 · ADT Triplet 数据对象:D={e1,e2,e3e1e2,e3∈E| em Set ·数据关系:R1={e1,e2>,e2e3>} 基本操作: Get(T,i, &e) 初始条件:三元组T已存在,1≤≤3 ●操作结果:用e返回T的第i元的值。 ·} ADT Triplet 北京邮电大学自动化学院
北京邮电大学自动化学院 34 ⚫ ADT Triplet{ ⚫ 数据对象：D={e1,e2,e3|e1,e2,e3ElemSet} ⚫ 数据关系：R1={<e1,e2>,<e2,e3>} ⚫ 基本操作： ⚫ Get(T，i，&e) ⚫ 初始条件：三元组T已存在，1i3 ⚫ 操作结果：用e返回T的第i元的值。 ⚫ } ADT Triplet 1.2 基本概念和术语
1.3抽象数据类型的表示和实现 ●抽象数据类型可通过固有数据类型来表示和实现,即利 用处理器中已存在的数据类型来说明新的结构,用已经 实现的操作来组合新的操作。 ●由于本书在高级程序设计语言的虚拟层次上讨论抽象数 据类型的表示和实现,并且讨论的数据结构及其算法主 要是面向读者,故采用介于伪码和C语言之间的类C语 言作为描述工具,有时也用伪码描述一些只含抽象操作 的抽象算法。 ●这使得数据结构和算法的描述和讨论简明清晰,不拘泥 于C语言的细节,又能容易转换成C或者C++程序。 北京邮电大学自动化学院
北京邮电大学自动化学院 35 ⚫ 抽象数据类型可通过固有数据类型来表示和实现，即利 用处理器中已存在的数据类型来说明新的结构，用已经 实现的操作来组合新的操作。 ⚫ 由于本书在高级程序设计语言的虚拟层次上讨论抽象数 据类型的表示和实现，并且讨论的数据结构及其算法主 要是面向读者，故采用介于伪码和C语言之间的类C语 言作为描述工具，有时也用伪码描述一些只含抽象操作 的抽象算法。 ⚫ 这使得数据结构和算法的描述和讨论简明清晰，不拘泥 于C语言的细节，又能容易转换成C或者C＋＋程序。 1.3 抽象数据类型的表示和实现