数据结构2（陈慧南）基础知识课件.ppt

《数据结构2（陈慧南）基础知识课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2讲DATASTRUCTURE第1章基础知识算法与数据结构1什么是数据结构2数据抽象和抽象数据类型3描述数据结构和算法4算法分析的基本方法5算法与数据结构1什么是数据结构2数据抽象和抽象数据类型3§1.3.1抽象、数据抽象和过程抽象抽象：其实质是抽取共同的和本质的内容，忽略非本质的细节。§1.3.1抽象、数据抽象和过程抽象数据抽象：使程序设计者可以将数据元素间的逻辑关系和数据在计算机内的具体表示分别考虑。链表结构a1a2a4a3a5Λ数据类型charintfloatdouble§1.3.1抽象、数据抽象和过程抽象过程抽象：使程序设计者将一个运算的定义与实现运算的具体方法分开考虑。抽象

2、的好处主要在于降低了问题求解的难度。运算123456784运算符及函数+-*/%<=>===Sin()Cos()……§1.3.2封装与信息隐蔽封装：是指把数据和操纵数据的运算组合在一起的机制。使用者只能通过一组允许的运算访问其中的数据。信息隐蔽：对使用者隐藏了数据结构或程序的实现细节。通常将数据和操纵数据的运算组成模块。每个模块有一个明确定义的界面，模块内部信息只能经过这一界面被外部访问。Employee#name:char[20]#individualEmpNo:int#grade:int#accumPay:float#employeeNo:int=1000+employee()+~

3、employee()+pay():void+promotion(:int):void+SetName(:char*):void+GetName():char*+GetindividualEmpNo():int+Getgrade():int+GetaccumPay():float§1.3.2封装与信息隐蔽protectedpublic§1.3.3数据类型和抽象数据类型数据类型是程序设计语言中的概念，它是数据抽象的一种方式。一个数据类型定义了一个值的集合以及作用于该值集的运算集合。C++数据类型charintfloatdoubleVC++数据类型BYTESHORTLONGDOUBLESQL

4、数据类型bitintdecimalmoneydatetime§1.3.3数据类型和抽象数据类型程序设计语言中，一个数据类型不仅规定了该类型的变量（或常量）的取值范围，还定义了该类型允许的运算。short值的集合：-32768~32767运算的集合：+-*/%<><=>===!==短整型数的表示：16bits运算的实现：算术、逻辑和赋值运算的实现§1.3.3数据类型和抽象数据类型抽象数据类型（abstractdatatypeADT）是一个数据类型，其主要特征是该类型的对象及其运算的规范，与该类型对象的表示和运算的实现分离，实行封装和信息隐蔽，即所谓使用和实现分离。抽象的数据类型ADT

5、lassName>isData:Operations:end§1.3.4数据结构与抽象数据类型逻辑结构和运算的定义组成了数据结构的规范（specification）。数据的存储表示和运算算法的描述构成数据结构的实现（implementation）。从规范和实现两方面来讨论数据结构的方式是抽象数据类型的观点。一种数据结构被视为一个抽象数据类型。第1章基础知识算法与数据结构1什么是数据结构2数据抽象和抽象数据类型3描述数据结构和算法4算法分析的基本方法5算法与数据结构1什么是数据结

6、构2数据抽象和抽象数据类型3描述数据结构和算法4§1.4.1数据结构的规范数据结构被看成是一个类属抽象数据类型(ADT)，用格式化的自然语言来描述。ADTStack{Data：0个或多个元素的线性序列（a0,a1,...,an-1）,其最大允许长度为MaxStackSize。Operations:Create()：建立一个空栈Destroy()：撤消一个栈Push(x)：值为x的新元素进栈，成为栈顶元素Pop()：从栈中删除栈顶元素Top(x)：在x中返回栈顶元素}§1.4.1数据结构的规范数据结构可以形式地用一个C++的抽象模板类描述。templateclassSta

7、ck{//栈类Stack是一个模板抽象类，//其成员函数为纯虚函数，未定义数据成员。public:virtualboolPush(Tx)=0;virtualboolPop()=0;virtualboolTop(T&x)const=0;……};§1.4.2实现数据结构templateclassSeqStack:publicStack{public:……private:inttop;//top记录最后入栈的元素在s的下标int