数据结构与算法分析-PPT.ppt

《数据结构与算法分析-PPT.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法分析-PPT.ppt（81页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1主讲：朱立华副教授南邮计算机学院E_mail: 2教材：1、数据结构部分：数据结构用C+语言描述，陈慧南主编，南大学出版社2、算法分析与设计部分：计算机算法设计与分析，王晓东编著，电子工业出版社课时安排：第一次面授：数据结构第一章到第五章第二次面授：数据结构第六章到第十章第三次面授：算法分析第二章到第七章（部分）考试时间及方式：第三次面授最后半天，复习加考试，开卷。3 第一章第一章 绪论绪论1.1 1.1 什么是数据结构什么是数据结构1.2 1.2 数据抽象和抽象数据抽象和抽象 数据类型数据类型 1.3 1.3 面向对象程序设计面向对象程序设计1.4 C+1.4 C+程序设计程序设计1.5

2、1.5 数据结构的描述数据结构的描述1.6 1.6 算法及其性能分析算法及其性能分析内容提要：内容提要：内容提要：内容提要：1 1给出数据结构的概念2 2介绍抽象数据类型和面向对 象的基本概念3 3回顾C+语言的基本特征4 4说明数据结构的描述方法5 5介绍算法和算法分析的基本 方法第一章第一章 绪论绪论 4 第一章第一章 绪论绪论 1.1 1.1 什么是数据结构什么是数据结构 1.2 1.2 数据抽象和抽象数据抽象和抽象 数据类型数据类型 1.3 1.3 面向对象程序设计面向对象程序设计 1.4 C+1.4 C+程序设计程序设计 1.5 1.5 数据结构的描述数据结构的描述 1.6 1.6

3、算法及其性能分析算法及其性能分析1.1 1.1 什么是数据结构什么是数据结构 在程序设计时就已经遇到过。在程序设计时就已经遇到过。一维数组是一个数据结构一维数组是一个数据结构 例如：一维数组例如：一维数组A=A=（a a1 1,a,a2 2,a,a3 3,a,a4 4）int a4;int a4;/定义并创建一维整型 /数组(a0,a1,a2,a3)x=a2;x=a2;/读数组元素a2的值 a2=x;a2=x;/置a2的值为x 数据结构由数据元素依某种逻辑关数据结构由数据元素依某种逻辑关系组织起来，在数据结构上需要定义系组织起来，在数据结构上需要定义一组操作（运算）。一组操作（运算）。1、数据

4、结构学科的定义：主要是为研究和解决如何使用计算机处理非数值问题而产生的理论、技术和方法。5 1.1.数据：数据：数据：数据：是信息的载体是信息的载体,是是计算机加工处理的对象.2.2.数值数据和非数值数据数值数据和非数值数据数值数据和非数值数据数值数据和非数值数据(1)数值数据：包括整数、实数或复数。主要用于工程计算、科学计算。(2)非数值数据：包括字符、文字、图形、图象、语音等。用于情报检索、企业管理、图形图象、人工智能、远程教育、远程医疗、电子商务、电子图书馆和办公自动化等诸多领域。3.3.数据元素：数据元素：数据元素：数据元素：组成数据的基本单位。第一章第一章 绪论绪论 1.1 1.1

5、什么是数据结构什么是数据结构 一、数据和数据元素一、数据和数据元素 二、什么是数据结构二、什么是数据结构一、数据和数据元素一、数据和数据元素 6例如：一维数组例如：一维数组A=A=（a a1 1,a,a2 2,a,a3 3,a,a4 4）(1)(1)数据元素间的逻辑关系：数据元素间的逻辑关系：B=B=（D D，R R）其中，D是数据元素的有限集合，R是D上关系的有限集合。本书中一般只考虑R包含一个关系的情况，即R=r。D=a1,a2,a3,a4 r=,R=r 第一章第一章 绪论绪论 1.1 1.1 什么是数据结构什么是数据结构 一、数据和数据元素一、数据和数据元素 二、什么是数据结构二、什么是

6、数据结构 1.1.数据结构举例数据结构举例（1 1）数据元素之间的）数据元素之间的 逻辑关系逻辑关系二、什么是数据结构二、什么是数据结构 1.1.数据结构举例数据结构举例 7 1.1 1.1 什么是数据结构什么是数据结构 一、数据和数据元素一、数据和数据元素 二、什么是数据结构二、什么是数据结构 1.1.数据结构举例数据结构举例（1 1）数据元素之间的）数据元素之间的 逻辑关系逻辑关系（2 2）数据在计算机内）数据在计算机内 的表示的表示(2)(2)数据在计算机内的表示数据在计算机内的表示例如：一维数组例如：一维数组A=A=（a a1 1,a,a2 2,a,a3 3,a,a4 4）8Creat

7、e():建立一个数组。Retrieve(i):返回下标为i的元素值。Store(i,x):将下标为i的数据元素 的值置为x。1.1 1.1 什么是数据结构什么是数据结构 一、数据和数据元素一、数据和数据元素 二、什么是数据结构二、什么是数据结构 1.1.数据结构举例数据结构举例（1 1）数据元素之间的）数据元素之间的 逻辑关系逻辑关系（2 2）数据在计算机内）数据在计算机内 的表示的表示（3 3）运算的定义和算法）运算的定义和算法(3)(3)运算的定义和算法运算的定义和算法例如：int a4;/定义一个一维整型数组 /(a0,a1,a2,a3)x=a2;/读数组元素a2的值 a2=x;/置a2

8、的值为x92.42.4种基本的逻辑结构种基本的逻辑结构 集合结构：集合结构：集合结构：集合结构：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其它关系；线性结构：线性结构：线性结构：线性结构：结构中的数据元素之间存在一对一的关系；树形结构：树形结构：树形结构：树形结构：结构中的数据元素之间存在一对多的关系；图结构：图结构：图结构：图结构：结构中的数据元素之间存在多对多的关系。1.1 1.1 什么是数据结构什么是数据结构 一、数据和数据元素一、数据和数据元素 二、什么是数据结构二、什么是数据结构 1.1.数据结构举例数据结构举例 2.42.4种基本的结构关系种基本的结构关系 3.3.什

9、么是数据结构什么是数据结构10 1.1 1.1 什么是数据结构什么是数据结构 一、数据和数据元素一、数据和数据元素 二、什么是数据结构二、什么是数据结构 1.1.数据结构举例数据结构举例 2.4 2.4 种基本的结构关系种基本的结构关系 3.3.什么是数据结构什么是数据结构2.42.4种基本的逻辑结构种基本的逻辑结构11 第一章第一章 绪论绪论1.1 1.1 什么是数据结构什么是数据结构 一、数据和数据元素一、数据和数据元素 二、什么是数据结构二、什么是数据结构 1.1.数据结构举例数据结构举例 2.42.4种基本的结构关系种基本的结构关系 3.3.什么是数据结构什么是数据结构数据结构包括以下

10、四个方面：数据结构包括以下四个方面：(1)数据元素及特性 是数据结构中的最基本信息单元。(2)数据的逻辑结构 对数据元素间的逻辑关系的描述。(3)数据的存储表示（存储结构）数据在计算机内的组织方式。(4)运算的定义和算法 数据结构上执行的运算和实现。3.3.什么是数据结构什么是数据结构12第一章第一章 绪论绪论1.1 1.1 什么是数据结构什么是数据结构1.2 1.2 数据抽象和抽象数据抽象和抽象 数据类型数据类型 1.3 1.3 面向对象程序设计面向对象程序设计1.4 C+1.4 C+程序设计程序设计1.5 1.5 数据结构的描述数据结构的描述1.6 1.6 算法及其性能分析算法及其性能分析

11、1.2 1.2 数据抽象和抽象数据类型数据抽象和抽象数据类型 抽抽 象象 抽取事物的共同的和实质的东西，忽略其非本质的细节。例如，“学生学生”这一概念是对学生群体的抽象，它 抽取了学生这一群体的共性，忽略 了每个学生的特殊性。13 第一章第一章 绪论绪论 1.2 1.2 数据抽象和数据抽象和 抽象数据类型抽象数据类型 一、数据类型一、数据类型 1.C 1.C 语言的数据类型语言的数据类型 二、数据抽象二、数据抽象 三、抽象数据类型三、抽象数据类型一、数据类型一、数据类型 1.C C 语言的数据类型语言的数据类型(1)(1)基本类型：基本类型：字符、整数、枚举、实数、双精度数(2)(2)构造类型

12、：构造类型：数组、结构和联合(3)(3)指针类型：指针指针类型：指针例如，二维整型数组int a35;int a35;定义了一个包含15个整数的二维数组。14 第一章第一章 绪论绪论 1.2 1.2 数据抽象和数据抽象和 抽象数据类型抽象数据类型 一、数据类型一、数据类型 1.C 1.C 语言的数据类型语言的数据类型 二、为什么要研究数二、为什么要研究数 据结构据结构 三、什么是数据结构三、什么是数据结构 又如，结构类型 struct Studentstruct Studentchar*name;char*name;int student_id;int student_id;char grad

13、e;char grade;定义了结构类型Student,包括以下三个域：name,student_id和grade。15 第一章第一章 绪论绪论 1.2 1.2 数据抽象和数据抽象和 抽象数据类型抽象数据类型 一、数据类型一、数据类型 1.C 1.C 语言的数据类型语言的数据类型 2.2.数据类型数据类型 二、数据抽象二、数据抽象 三、抽象数据类型三、抽象数据类型2.数据类型数据类型 一个数据类型定义了一个值的集合以及作用于该值集的操作的集合。例如，int a;int a;变量a a a a 的取值范围是：-3276832767对变量a a a a执行的操作有：算术运算 +、-、*、/、%关系

14、运算 、=、=、!=赋值运算 =16 第一章第一章 绪论绪论 1.2 1.2 数据抽象和数据抽象和 抽象数据类型抽象数据类型 一、数据类型一、数据类型 二、数据抽象二、数据抽象 三、抽象数据类型三、抽象数据类型二、数据抽象二、数据抽象 数据类型数据类型 是具有相同值集和操作集的数据对象（变量和常量）的抽象。相同的数据类型的变量具有相 同的取值范围，允许执行相同的操作；对变量执行允许的操作，可以不必考虑变量在计算机内的存储细节和这些操作是如何执行的。17 第一章第一章 绪论绪论 1.2 1.2 数据抽象和数据抽象和 抽象数据类型抽象数据类型 一、数据类型一、数据类型 二、数据抽象二、数据抽象 三

15、、抽象数据类型三、抽象数据类型三、抽象数据类型三、抽象数据类型 抽抽 象象 数数 据据 类类 型型（abstract data structure ADT）是一个数据类型，其主要特征是该类型的对象及其操作的规范,与该对象的表示和操作的实现分离，即使用和实现分离，并实行封装和信息隐蔽。18 第一章第一章 绪论绪论 1.2 1.2 数据抽象和数据抽象和 抽象数据类型抽象数据类型 一、数据类型一、数据类型 二、数据抽象二、数据抽象 三、抽象数据类型三、抽象数据类型 例如，int a;int a;整型int int 的规范规范包括变量 a a a a 的取值范围是：-3276832767对变量 a a

16、 a a 执行的操作有：算术运算 +、-、*、/、%关系运算 、=、=、!=赋值运算 =整型int int 的实现实现是指变量 a a 在计算机内存储表示方法。操作的实现实现是指整型上定义的操作的具体实现方法。19 第一章第一章 绪论绪论 1.2 1.2 数据抽象和数据抽象和 抽象数据类型抽象数据类型 一、数据类型一、数据类型 二、数据抽象二、数据抽象 三、抽象数据类型三、抽象数据类型 使使用用和和实实现现分分离离：使用者通过规范使用该类型的数据，而不必考虑其实现细节；改变实现将不影响使用。封封装装和和信信息息隐隐蔽蔽：将数据和代码组合在一起；数据类型的细节对外部是隐蔽的。例如，int a;i

17、nt a;其实现是隐蔽的，使用者只能通过整型上定义的一组运算对变量 a a 执行操作。20 第一章第一章 绪论绪论 1.2 1.2 数据抽象和数据抽象和 抽象数据类型抽象数据类型 一、数据类型一、数据类型 二、数据抽象二、数据抽象 三、抽象数据类型三、抽象数据类型 四、数据结构的规范四、数据结构的规范 和实现和实现数据结构可分成以下两部分：(1)(1)数据结构的规范：数据结构的规范：逻辑结构和运算的定义(2)(2)数据结构的实现：数据结构的实现：存储结构和运算算法实现规范是实现的准则和依据。规范指明“做什么”，实现解决“怎样做”。21第一章第一章 绪论绪论1.1 1.1 什么是数据结构什么是数

18、据结构1.2 1.2 数据抽象和抽象数据抽象和抽象 数据类型数据类型 1.3 1.3 面向对象方法面向对象方法1.4 C+1.4 C+程序设计程序设计1.5 1.5 数据结构的描述数据结构的描述1.6 1.6 算法及其性能分析算法及其性能分析1.3 1.3 面向对象方法面向对象方法 例子，问题的陈述：开发一个非常简单的字处理程序。该系统允许用户产生文档产生文档；所产生的文档存储存储在一个用户目录目录中；用户可以打印打印和显示显示文档；文档可以改变改变，也可以被删除删除。对象对象 服务服务 文档 产生、存储、打印 显示、改变、删除 目录 存储、删除22第一章第一章 绪论绪论1.1 1.1 什么是

19、数据结构什么是数据结构1.2 1.2 数据抽象和抽象数据抽象和抽象 数据类型数据类型 1.3 1.3 面向对象方法面向对象方法1.4 C+1.4 C+程序设计程序设计1.5 1.5 数据结构的描述数据结构的描述1.6 1.6 算法及其性能分析算法及其性能分析1.3 1.3 面向对象方法面向对象方法 对象对象 应用领域内的实体和概念，它们通常是问题陈述中的名词。属性属性 刻划对象的特征。服务或运算服务或运算 施于对象属性的操作，它们通常是问题陈述中的动词。同类对象具有相同的属性和服务。同一个类（class)中的每个对象称为该类的一个实例。23第一章第一章 绪论绪论1.1 1.1 什么是数据结构什

20、么是数据结构1.2 1.2 数据抽象和抽象数据抽象和抽象 数据类型数据类型 1.3 1.3 面向对象方法面向对象方法1.4 C+1.4 C+程序设计程序设计1.5 1.5 数据结构的描述数据结构的描述1.6 1.6 算法及其性能分析算法及其性能分析继承继承 是指派生类（子类）可自动共享基类（父类）的公有的和保护的属性和服务的机制。它是面向对象方法最重要的共享机制，从而减少数据和代码的重复。这也是面向对象方法最有特色的方面。24第一章第一章 绪论绪论1.1 1.1 什么是数据结构什么是数据结构1.2 1.2 数据抽象和抽象数据抽象和抽象 数据类型数据类型 1.3 1.3 面向对象程序设计面向对象

21、程序设计1.4 C+1.4 C+程序设计程序设计1.5 1.5 数据结构的描述数据结构的描述1.6 1.6 算法及其性能分析算法及其性能分析1.4 C+1.4 C+程序设计程序设计 回顾回顾C+C+语言的基本特征语言的基本特征内容提要：内容提要：内容提要：内容提要：1.4.1 函数与参数传递1.4.2 动态存储分配1.4.3 C+类1.4.4 继承和派生类1.4.5 多态性、虚函数和动态联编1.4.6 纯虚函数和抽象类1.4.7 模板25 第一章第一章 绪论绪论1.4 C+1.4 C+程序设计程序设计1.4.1 1.4.1 函数与参数传递函数与参数传递 1.1.传值参数和引用参数传值参数和引用

22、参数 2.2.函数的返回值函数的返回值 3.3.函数原型函数原型1.4.11.4.1函数与参数传递函数与参数传递#include#includeint Abc(int a,int&b)int Abc(int a,int&b)a+;a+;b+;b+;return a+b;return a+b;void main()void main()int int x=3,y=3;x=3,y=3;int z=Abc(x,y);int z=Abc(x,y);rintf rintf(z=%d,y=%dn,z,y);(z=%d,y=%dn,z,y);1.1.传值参数与引用参数传值参数与引用参数（见（见dsapg4.

23、cppdsapg4.cpp）运行结果:z=8,x=3,y=4原因：x 3 a 3 a+a 4y 3 y 4 b b+b26 第一章第一章 绪论绪论1.4 C+1.4 C+程序设计程序设计1.4.1 1.4.1 函数与参数传递函数与参数传递 1.1.传值参数和引用参数传值参数和引用参数 2.2.函数的返回值函数的返回值 3.3.函数原型函数原型常量引用参数：常量引用参数：const int&cconst int&c（见（见dsapg4.cppdsapg4.cpp）#include#includeint Abc(int a,const int&c)int Abc(int a,const int&c

24、)/c+;/c+;若加上，则编译错若加上，则编译错 return a+c;return a+c;void main()void main()int y=3;int y=3;int z=Abc(3,y);int z=Abc(3,y);printf(z=%dn,z);printf(z=%dn,z);运行结果：运行结果：z=6z=627 第一章第一章 绪论绪论1.4 C+1.4 C+程序设计程序设计1.4.1 1.4.1 函数与参数传递函数与参数传递 1.1.传值参数和引用参数传值参数和引用参数 2.2.函数的返回值函数的返回值 3.3.函数原型函数原型函数执行时，函数执行时，(1)(1)传值参数传

25、值参数 实在参数的值赋给了形式参数，形式参数得到了实在参数的一个副本。函数执行后，实在参数的值不会改变。(2)(2)引用参数引用参数 实在参数的地址传给了形式参数。函数执行后，实在参数的值将可能改变。常量引用参数常量引用参数 函数不得修改该引用参数，否则将导致编译出错。28 第一章第一章 绪论绪论1.4 C+1.4 C+程序设计程序设计1.4.1 1.4.1 函数与参数传递函数与参数传递 1.1.传值参数和引用参数传值参数和引用参数 2.2.函数返回值函数返回值 3.3.函数原型函数原型(1)(1)函数返回一个值函数返回一个值int Abc(int a,int&c)int Abc(int a,

26、int&c)return a+c;return a+c;(2)(2)函数返回一个引用参数函数返回一个引用参数int&Abc(int a,int&c)int&Abc(int a,int&c)c=a+3;c=a+3;return c;return c;Abc Abc(2,x)/=2;(2,x)/=2;2.2.函数返回值函数返回值（见（见dsapg5.cppdsapg5.cpp）29 第一章第一章 绪论绪论1.4 C+1.4 C+程序设计程序设计1.4.1 1.4.1 函数与参数传递函数与参数传递 1.1.传值参数和引用参数传值参数和引用参数 2.2.函数的返回值函数的返回值 3.3.函数原型函数原

27、型3.3.函数原型函数原型函数原型函数原型包括 函数名、返回类型和参数表例如例如，下面的程序由三个文件组成：greet.hgreet.h，greet.cppgreet.cpp，main.cppmain.cpp。（见（见greetgreet文件夹）文件夹）/*/*存放在头文件存放在头文件greet.h*/greet.h*/void Greet();/void Greet();/函数原型30 第一章第一章 绪论绪论1.4 C+1.4 C+程序设计程序设计1.4.1 1.4.1 函数与参数传递函数与参数传递 1.1.传值参数和引用参数传值参数和引用参数 2.2.函数的返回值函数的返回值 3.3.函数

28、原型函数原型/*/*存放在源代码文件存放在源代码文件greet.cppgreet.cpp中中*/*/#include include#include“greet.h”#include“greet.h”/预处理指令void Greet()/void Greet()/函数 char Name16;char Name16;coutenter your name:;coutenter your name:;cin.get(Name,sizeof(Name);cin.get(Name,sizeof(Name);coutngreetings,Name coutngreetings,Name n;n;/*/

29、*存放在源代码文件存放在源代码文件main.cppmain.cpp中中*/*/#include greet.h include greet.h/预处理指令void main()/void main()/主程序 Greet();Greet();31 第一章第一章 绪论绪论1.4 C+1.4 C+程序设计程序设计1.4.1 1.4.1 函数与参数传递函数与参数传递1.4.2 1.4.2 动态存储分配动态存储分配 1.4.21.4.2动态存储分配动态存储分配 C C语言的动态分配和释放函数语言的动态分配和释放函数 malloc()malloc()和和free()free()int*x;int*x;x

30、=(int*)malloc(sizeof(int);x=(int*)malloc(sizeof(int);*x=10;*x=10;printf(x=%dn,*x);printf(x=%dn,*x);free(x);free(x);int a100;int a100;32 第一章第一章 绪论绪论1.4 C+1.4 C+程序设计程序设计1.4.1 1.4.1 函数与参数传递函数与参数传递1.4.2 1.4.2 动态存储分配动态存储分配 例如：例如：int*y;int*y;y=new int;y=new int;*y=10;*y=10;三步合并为：三步合并为：int*y=new int(10);in

31、t*y=new int(10);C+C+的动态分配和释放函数的动态分配和释放函数 new()new()和和delete()delete()33 第一章第一章 绪论绪论1.4 C+1.4 C+程序设计程序设计1.4.1 1.4.1 函数与参数传递函数与参数传递1.4.2 1.4.2 动态存储分配动态存储分配 例如：例如：分配包括分配包括1010个整数的数组个整数的数组 int*a=new int 10;int*a=new int 10;a2=5;*(a+3)=7;/a3=7;a2=5;*(a+3)=7;/a3=7;printfprintf(”a2=%d n”,a2);(”a2=%d n”,a2)

32、;printf(”a3=%d printf(”a3=%d n”,*(a+3);n”,*(a+3);释放数组空间释放数组空间 deletea;deletea;（例见（例见dsapg6.cppdsapg6.cpp）C+C+的数组动态分配和释放的数组动态分配和释放 new()new()和和delete()delete()341.C+1.C+类类 数据和操作组合成类。数据和操作组合成类。C+C+类体现了抽象数据类型的思想，类体现了抽象数据类型的思想，支持面向对象程序设计，实现封装支持面向对象程序设计，实现封装和信息隐蔽的原则。和信息隐蔽的原则。第一章第一章 绪论绪论1.4 C+1.4 C+程序设计程序

33、设计1.4.11.4.1函数与参数传递函数与参数传递1.4.21.4.2动态存储分配动态存储分配1.4.31.4.3C+C+类类1.1.C+C+类类1.4.3 1.4.3 C+C+类类 三种存取级别：三种存取级别：publicpublic、privateprivate、protectedprotected35 第一章第一章 绪论绪论1.4 C+1.4 C+程序设计程序设计1.4.11.4.1函数与参数传递函数与参数传递1.4.21.4.2动态存储分配动态存储分配1.4.31.4.3C+C+类类1.1.C+C+类类publicpublic域域 共有成员，可被程共有成员，可被程 序的其它部分访问。

34、序的其它部分访问。privateprivate域域 私有成员，只能私有成员，只能 由该类的成员函数以及被声明由该类的成员函数以及被声明 为友元的函数或类的对象访问。为友元的函数或类的对象访问。protectedprotected域域 保护成员，除保护成员，除 了具有了具有privateprivate访问权限外，还访问权限外，还 允许该类的子类访问它们。允许该类的子类访问它们。privateprivate域用来保护对象内部的数据，域用来保护对象内部的数据，实现信息隐蔽。实现信息隐蔽。private private 是缺省的是缺省的存取级别。存取级别。36（完整程序见（完整程序见dsapg7.cp

35、pdsapg7.cpp）class Facultyclass Faculty/C+/C+类举例类举例 protected:protected:char*name;char*name;int age;int age;public:public:Faculty(char*name,int age);Faculty(char*name,int age);Faculty();Faculty();void Change(char*name,int age);void Change(char*name,int age);/建立类的对象（实例化）建立类的对象（实例化）Faulty emp;Faulty em

36、p;Faulty*emp1=new Faulty;Faulty*emp1=new Faulty;delete emp1;delete emp1;/释放对象存储空间释放对象存储空间 第一章第一章 绪论绪论1.4 C+1.4 C+程序设计程序设计1.4.11.4.1函数与参数传递函数与参数传递1.4.21.4.2动态存储分配动态存储分配1.4.31.4.3C+C+类类1.1.C+C+类类37 第一章第一章 绪论绪论1.4 C+1.4 C+程序设计程序设计1.4.11.4.1函数与参数传递函数与参数传递1.4.21.4.2动态存储分配动态存储分配1.4.31.4.3C+C+类类1.1.C+C+类类2

37、.2.操作符重载操作符重载Complex Complex:operator+Complex Complex:operator+(const Complex&c)(const Complex&c)return Complex(real+c.real,return Complex(real+c.real,image+c.image);image+c.image);其中，其中，realreal和和imageimage是当前复数类是当前复数类ComplexComplex对象的两个私有数据成员。对象的两个私有数据成员。/定义定义3 3个复数对象个复数对象Complex com1(3.2,6.8);Com

38、plex com1(3.2,6.8);Complex com2(4.3,2.1);Complex com2(4.3,2.1);Complex com3;Complex com3;com3=com1+com2com3=com1+com2;/;/复数相加复数相加38C+C+编译器将编译器将com1+com2com1+com2解释为解释为 com1.operator+(com2)com1.operator+(com2)；表达式表达式com1+100com1+100是错误的是错误的 因因为为100100不不是是ComplexComplex类类的的一一个个对对象。象。#The End#The End#第

39、一章第一章 绪论绪论1.4 C+1.4 C+程序设计程序设计1.4.11.4.1函数与参数传递函数与参数传递1.4.21.4.2动态存储分配动态存储分配1.4.31.4.3C+C+类类1.1.C+C+类类2.2.操作符重载操作符重载393.3.友元函数和友元类友元函数和友元类 第一章第一章 绪论绪论1.4 C+1.4 C+程序设计程序设计1.4.11.4.1函数与参数传递函数与参数传递1.4.21.4.2动态存储分配动态存储分配1.4.31.4.3C+C+类类1.1.C+C+类类2.2.操作符重载操作符重载3.3.友元函数和友元类友元函数和友元类友元函数友元函数 在类的声明中使用了保留字在类的

40、声明中使用了保留字friendfriend,给出一个普通函数的原型，给出一个普通函数的原型，将此函数定义为该类的友元函数。将此函数定义为该类的友元函数。友元类友元类 在类的声明中使用了保留字在类的声明中使用了保留字friendfriend,将另一个类的所有函数定义将另一个类的所有函数定义为该类的友元函数。为该类的友元函数。40 第一章第一章 绪论绪论1.4 C+1.4 C+程序设计程序设计1.4.11.4.1函数与参数传递函数与参数传递1.4.21.4.2动态存储分配动态存储分配1.4.31.4.3C+C+类类1.1.C+C+类类2.2.操作符重载操作符重载3.3.友元函数和友元类友元函数和友

41、元类友元类举例友元类举例 class Y;class Y;class Xclass X friend Y;friend Y;class Y class Y 友元函数友元函数 可以存取类的私有成员和保护成员。可以存取类的私有成员和保护成员。41（程序见（程序见dsapg8.cppdsapg8.cpp）class Complexclass Complex private:private:double real,image;double real,image;public:public:/构造函数构造函数 Complex()real=0.0;image=0.0;Complex()real=0.0;i

42、mage=0.0;Complex(double r,double i=0.0)Complex(double r,double i=0.0)real=r;image=i;real=r;image=i;Complex(Complex&com)Complex(Complex&com)real=com.real;image=com.image;real=com.real;image=com.image;friend Complex operator+(Complex&c1,Complex&c2);friend Complex operator+(Complex&c1,Complex&c2);frien

43、d ostream&operator(ostream&,Complex&);friend ostream&operator(ostream&,Complex&);42重载加法操作符重载加法操作符+实现两个复数相加实现两个复数相加Complex operator+(Complex&c1,Complex&c2)Complex operator+(Complex&c1,Complex&c2)return Complex(c1.real+c2.real,c1.image+c2.image);return Complex(c1.real+c2.real,c1.image+c2.image);重载输出操作

44、符重载输出操作符 向输出流中输出复数向输出流中输出复数ostream&operator(ostream&s,Complex&c)ostream&operator(ostream&s,Complex&c)sc.real+c.imageiendl;sc.real+c.imageiendl;return s;return s;43第一章第一章 绪论绪论1.4 C+1.4 C+程序设计程序设计1.4.11.4.1函数与参数传递函数与参数传递1.4.21.4.2动态存储分配动态存储分配1.4.31.4.3C+C+类类1.1.C+C+类类2.2.操作符重载操作符重载3.3.友元函数和友元类友元函数和友元类

45、void main()void main()Complex c1(2.3),c2(5,6),c3;Complex c1(2.3),c2(5,6),c3;c3=c1+c2;c3=c1+c2;coutc1c2c3;coutc1c2c3;运行结果运行结果2.3+0i2.3+0i5+6i5+6i7.3+6i7.3+6i定义定义3 3个复数对象：个复数对象：c1=2.3c1=2.3，c2=5+6ic2=5+6i，c3c3计算：计算：c3=c1+c2c3=c1+c244第一章第一章 绪论绪论1.4 C+1.4 C+程序设计程序设计1.4.11.4.1函数与参数传递函数与参数传递1.4.21.4.2动态存储

46、分配动态存储分配1.4.31.4.3C+C+类类1.4.4 1.4.4 继承性和派生类继承性和派生类1.4.4 1.4.4 继承性和派生类继承性和派生类 继承性继承性 派生类继承基类所定义的数据派生类继承基类所定义的数据和方法。和方法。public public 继承性（派生）继承性（派生）基类所有的公有成员成为派生类基类所有的公有成员成为派生类的公有成员，基类所有的保护成员的公有成员，基类所有的保护成员成为派生类的保护成员。成为派生类的保护成员。45class Facultyclass Faculty protected:protected:char*name;char*name;int i

47、nt age;age;public:public:Faculty(char*name,Faculty(char*name,int age);int age);Faculty();Faculty();void Change(char*void Change(char*name,int age);name,int age);class Professor:public Facultyclass Professor:public Faculty public:public:void ChangeLevel(int n);void ChangeLevel(int n);Professor(char*n

48、ame,int Professor(char*name,int age,int level);age,int level);Professor();Professor();private:private:int int level;level;C+C+类类FacultyFacultyProfessorProfessor继承了继承了FacultyFaculty所定义的数据和方法。本例所定义的数据和方法。本例称为称为publicpublic继承继承(派生）。派生）。从类从类FacultyFaculty派生类派生类ProfessorProfessor 46第一章第一章 绪论绪论1.4 C+1.4 C

49、+程序设计程序设计1.4.11.4.1函数与参数传递函数与参数传递1.4.21.4.2动态存储分配动态存储分配1.4.31.4.3C+C+类类1.4.4 1.4.4 继承性和派生类继承性和派生类1.4.5 1.4.5 多态性、虚函数多态性、虚函数 与动态联编与动态联编1.4.5 1.4.5 多态性、虚函数与动态联编多态性、虚函数与动态联编 多态性多态性 允许同一个函数（或操作符）有允许同一个函数（或操作符）有多个版本，对不同的对象执行不同的多个版本，对不同的对象执行不同的版本。版本。(1)(1)函数或操作符重载函数或操作符重载(2)(2)虚函数虚函数1.1.多态性多态性47一个虚函数的例子：一

50、个虚函数的例子：（见（见dsapg10.cppdsapg10.cpp）#include#includeclass Baseclass Base public:public:virtual void who()virtual void who()coutBasen;coutBasen;第一章第一章 绪论绪论1.4 C+1.4 C+程序设计程序设计1.4.11.4.1函数与参数传递函数与参数传递1.4.21.4.2动态存储分配动态存储分配1.4.31.4.3C+C+类类1.4.4 1.4.4 继承性和派生类继承性和派生类1.4.5 1.4.5 多态性、虚函数多态性、虚函数 与动态联编与动态联编虚函