数据结构c++ppt课件

1、nC+语言的概要语言的概要n类、对象、构造函数与析构函数类、对象、构造函数与析构函数n输入输入/输出输出n函数、参数传递与函数返回值函数、参数传递与函数返回值n函数名重载与操作符重载函数名重载与操作符重载n动态存储分配动态存储分配n友元函数与内联函数友元函数与内联函数n构造、联合与类构造、联合与类nC 语言是一个面向过程的语言。随着软件语言是一个面向过程的语言。随着软件开发技术的进步开发技术的进步, 程序员们最终发现程序员们最终发现, 把把数据和施加在其上的操作结合起来，会得数据和施加在其上的操作结合起来，会得到更易于理解的程序，由此产生了面向对到更易于理解的程序，由此产生了面向对象的程序设计

2、思想。象的程序设计思想。n1980年代初，美国年代初，美国 AT & T 贝尔实验室的贝尔实验室的Bjarne Stroustrup设计并实现了设计并实现了C语言语言的扩充、改进版本，的扩充、改进版本，C+语言诞生了！语言诞生了！nC+改进了改进了C的不足之处，增加了对面向的不足之处，增加了对面向对象的程序设计的支持，在改进的同时，对象的程序设计的支持，在改进的同时，保持了保持了C的简洁性和高效性。的简洁性和高效性。/一个简单的一个简单的C+程序标准版本）程序标准版本）#include using namespace std;int main() cout hello!;return

3、0;/正常返回正常返回nC+将一些标准函数和变量说明放在头文将一些标准函数和变量说明放在头文件中。件中。n用户也可以定义自己的头文件。用户也可以定义自己的头文件。n#include指令有两种格式：指令有两种格式：n #include n #include “头文件名头文件名”nC+源程序中还可包括各种编译命令源程序中还可包括各种编译命令, 这些这些命令被称为预处理指令命令被称为预处理指令, 常用的除常用的除 #include外外, 还有条件预处理指令还有条件预处理指令 #if、#ifndef 和和#endif 等和宏替换指令等和宏替换指令 #define。n#define 用来定义一个常量或替

4、换宏用来定义一个常量或替换宏, 如：如：n #define size 20n /定义一个常量定义一个常量size，其值永远为，其值永远为20n #define MAX(x, y) (x y) ? y : x)n /求求x, y中的最大值中的最大值n经过预编译后经过预编译后, 程序中所有出现程序中所有出现 size 和和 MAX(x, y) 之处都会被之处都会被 20 和和 (x y) ? y : x) 替代，如：替代，如：n int arraysize;int i = MAX(4, 55);n经预编译后会变为经预编译后会变为n int array20;int i = (4 ( const Po

5、int &); /点比较 int operator ( istream&, Point& ); /输入友元函数 friend ostream& operator ( ostream&, const Point& ); /输出友元函数;#endif 例，对于例，对于Point类的输出友元函数的实现可以类的输出友元函数的实现可以在源程序文件中给出，形为：在源程序文件中给出，形为： ostream & operator (ostream& strm, const Point& p) return strm ( p.x , p.y

6、 ); 这个函数把点这个函数把点p的值以的值以“x, y的格式送到的格式送到strm指明的输出流中去。指明的输出流中去。C+中的对象n建立类的对象建立类的对象(亦称为实例化亦称为实例化)时采用的方式时采用的方式类似于定义类似于定义C变量的方式，可以自动地，或变量的方式，可以自动地，或静态地静态地, 或通过动态分配来建立。建立一个或通过动态分配来建立。建立一个 Point类实例的语句是：类实例的语句是：nPoint p (6, 3); 自动地自动地nPoint q; 自动地自动地nstatic Point s (3, 4); 静态地静态地nPoint *t = new Point(1, 1);

7、通过动态分配通过动态分配构造函数构造函数n当遇到以上的每一个语句时当遇到以上的每一个语句时, 将隐式地调用将隐式地调用一个构造一个构造(constructor)函数函数, 这个构造函这个构造函数属于一个与它同名的类。数属于一个与它同名的类。n在在Point类的定义中声明了两个构造函数类的定义中声明了两个构造函数, 构构造函数的参数用于初始化表达式的值。造函数的参数用于初始化表达式的值。n例如例如, 当使用声明当使用声明 Point p(6, 3) 建立建立 Point 类的对象类的对象 p 时时,调用了构造函数调用了构造函数 Point (int, int);通过以下函数定义通过以下函数定义,

8、 将其将其x, y分量设定分量设定为为6, 3：n Point : Point (int a,int b) x = a; y = b; n Point : Point (int a,int b) : x(a), y(b) n构造函数可以定义默认值。例如构造函数可以定义默认值。例如n Point : Point ( int a, int b ) n : x(a), y(b) n当定义实例时给定初始值当定义实例时给定初始值, 则该实例以给则该实例以给定初始值来初始化其数据成员定初始值来初始化其数据成员n Point p(6, 3);n 则有则有 x = a = 6, y = b = 3n当定义实例

9、时未给出初始值。则该实例当定义实例时未给出初始值。则该实例以默认值来初始化其数据成员以默认值来初始化其数据成员n Point q;n 则有则有 x = a = 0, y = b = 0析构函数析构函数n当要放弃对象时当要放弃对象时, 需隐式地调用另一个函数需隐式地调用另一个函数,叫做析构叫做析构(destructor)函数函数, 它属于名字相同它属于名字相同的类的类, 但在名字前面加上了一个但在名字前面加上了一个“”。例。例如如n Point。n为一个类可定义几个构造函数，但只能定义为一个类可定义几个构造函数，但只能定义 一个析构函数。当控制要退出自动变量的作一个析构函数。当控制要退出自动变量

10、的作用域时用域时, 或当通过或当通过 delete 命令释放一个动命令释放一个动态分配的变量时态分配的变量时, 就要调用析构函数。当就要调用析构函数。当main函数执行结束时，将释放静态声明的函数执行结束时，将释放静态声明的变量。变量。n一个析构函数用于在删除一个类的对象时做一个析构函数用于在删除一个类的对象时做清除工作。清除工作。C+的输入/输出n在在C+中执行输入中执行输入/输出操作输出操作, 需用需用#include预处理指令包括一个预处理指令包括一个头文件。头文件。用它可支持用它可支持C+的流的流(stream)操作。操作。n“流流是个简单的字符序列。在是个简单的字符序列。在C+中有两

11、中有两个预定义的类个预定义的类istream和和ostream，它们定，它们定义了输入流和输出流。义了输入流和输出流。n基本输入基本输入/输出方式：输出方式：n键盘屏幕输入键盘屏幕输入/输出输出n文件输入文件输入/输出输出键盘屏幕输入键盘屏幕输入/ /输出输出n在在C中有用于定向到键盘输入设备、屏幕输中有用于定向到键盘输入设备、屏幕输出设备和错误文件的命令出设备和错误文件的命令stdin、stdout和和stderr。n在在C+中用中用cin，cout和和cerr来定义键盘输入来定义键盘输入类、屏幕输出类和错误信息输出类。类、屏幕输出类和错误信息输出类。n操作符操作符 用于写出类用于写出类os

12、tream的一个对象，的一个对象，对于一系列输出对象，可用对于一系列输出对象，可用 用于读入类用于读入类istream的一个对象。的一个对象。n在下面程序中使用了流在下面程序中使用了流 cin ，相继从标准，相继从标准输入设备上输入两个整型变量输入设备上输入两个整型变量a和和b, 并将它并将它们打印到标准输出设备上。们打印到标准输出设备上。n在输出语句中最后输出的在输出语句中最后输出的endl是是C+的的I/O操操作符作符, 它的用途是输出一个换行符并清空流。它的用途是输出一个换行符并清空流。#include int main ( ) int a, b; cin a b; cout “a :

13、” n “f : ” f endl; return 0;文件输入文件输入/ /输出输出nC+中的文件输入中的文件输入/输出方式如下所示。输出方式如下所示。n在程序开头必须用预处理指令在程序开头必须用预处理指令#include包包含头文件含头文件，它定义了类，它定义了类ifstream、ofstream和和fstream。n要创建一个输入流要创建一个输入流, 必须声明它为必须声明它为ifstream类的实例类的实例n要创建一个输出流要创建一个输出流, 必须声明它为必须声明它为ofstream类的实例类的实例n执行输入和输出操作的流必须声明它为执行输入和输出操作的流必须声明它为 fstream类的

14、实例类的实例#include #include #include int main ( ) ifstream inFile; / inFile为输入流对象为输入流对象 ofstream outFile; / outFile为输出流对象为输出流对象 outFile.open (my.dat, ios : out ); / 建立输出文件建立输出文件my.dat char univ = Tsinghua, name10; int course = 2401, number; outFile univ course endl; / 输出到输出到my.dat inFile.open(my.dat, io

15、s:in); /打开输入文件my.dat if ( !inFile ) cerr “不能打开my.dat” name number; cout name: name endl; cout number: number endl; return 0;n在文件打开的操作中，指定的文件模式有在文件打开的操作中，指定的文件模式有以下几种：以下几种：nios:app：把所有对文件的输出添加在文：把所有对文件的输出添加在文件尾。它只用于输出文件。件尾。它只用于输出文件。nios:binary：文件以二进制方式打开。此：文件以二进制方式打开。此项缺省时文件以文本方式打开。项缺省时文件以文本方式打开。nios

16、:nocreate：若文件不存在则将导致打：若文件不存在则将导致打开操作失败。开操作失败。nios:out：表明该文件用于输出。此项可缺：表明该文件用于输出。此项可缺省。省。nios:in：表明该文件用于输入。此项可缺：表明该文件用于输入。此项可缺省。省。C+中的函数 n在在C+中有两种函数：中有两种函数：n 常规函数和成员函数常规函数和成员函数n不论哪种函数不论哪种函数, 其定义都包括其定义都包括 4 个部分个部分: 函函数名、形式参数表、返回类型和函数体。数名、形式参数表、返回类型和函数体。n函数返回时可以通过引用方式，参看下面函数返回时可以通过引用方式，参看下面程序程序, 此时在函数类型

17、后面加上一此时在函数类型后面加上一 个个“&”。n #include nchar& replace(int m);nchar s80 = “Hello There”;nmain ( ) n replace(5) = x; cout s; n/用用x代替代替Hello后面的空格后面的空格nnchar& replace ( int m ) n return sm; nC+中的参数传递n函数调用时传送给形参表的实参必须与形函数调用时传送给形参表的实参必须与形参在类型、个数、顺序上保持一致。参在类型、个数、顺序上保持一致。n参数传递有两种方式。一种是传值，这是参数传递有两种方式

18、。一种是传值，这是缺省的参数传递方式缺省的参数传递方式; 一种是引用类型。一种是引用类型。n使用传值方式时，把实参的值传送给函数使用传值方式时，把实参的值传送给函数局部工作区相应的副本中，函数使用这个局部工作区相应的副本中，函数使用这个副本执行必要的功能。这样，函数修改的副本执行必要的功能。这样，函数修改的是副本的值，实参的值不变。是副本的值，实参的值不变。n使用引用类型方式传递时使用引用类型方式传递时, 需将形参声明为需将形参声明为引用类型，即在参数名前加一个引用类型，即在参数名前加一个“&”。n当一个实参与一个引用型形参结合时，被当一个实参与一个引用型形参结合时，被传递的不是实参的

19、值，而是实参的地址，传递的不是实参的值，而是实参的地址，函数通过地址存取被引用的实参。函数执函数通过地址存取被引用的实参。函数执行后实参的值将发生改变。行后实参的值将发生改变。n当一个函数的返回值多于一个时当一个函数的返回值多于一个时, 其中一个其中一个可由可由return语句返回语句返回, 其它返回值可使用其它返回值可使用引用型参数返回。引用型参数返回。n#include nvoid swap (int& i, int& j);void swap(int &, int &);int main ( ) int a = 1, b =2; cout a and b:

20、 a b n; swap ( a, b ); /调用时实际参数不需要加& cout a and b: a b n; return 0;void swap (int& i, int& j) /对换 i 与 j 的内容 int t = j; j = i; i = t; /不需要加 *n一种特殊的引用调用方式叫做常值引用一种特殊的引用调用方式叫做常值引用, 其其格式为格式为 const T& a。在函数体中不能修改。在函数体中不能修改常值参数。常值参数。n一种特殊情况是数组参数的传递。数组作一种特殊情况是数组参数的传递。数组作为形参可按传值方式声明，传递的是数组为形参

21、可按传值方式声明，传递的是数组第一个元素的地址。第一个元素的地址。n此外，在参数表中一般按形如此外，在参数表中一般按形如 int R 的的形式声明，因此需要显式地声明数组的大形式声明，因此需要显式地声明数组的大小。小。n若传送的值参是一个对象若传送的值参是一个对象 (作为类的实例作为类的实例) 时时, 在函数中就创建了该对象的一个副本。在函数中就创建了该对象的一个副本。在创建这个副本时不调用该对象的构造函在创建这个副本时不调用该对象的构造函数，但在函数结束前要调用该副本的析构数，但在函数结束前要调用该副本的析构函数撤消这个副本。函数撤消这个副本。n若采用引用方式传递对象，在函数中不创若采用引用

22、方式传递对象，在函数中不创建该对象的副本，也不存在最后撤消副本建该对象的副本，也不存在最后撤消副本的问题。但是，通过引用传递的是对象时，的问题。但是，通过引用传递的是对象时，函数对对象的改变将影响调用的对象。函数对对象的改变将影响调用的对象。 成员函数的返回值n当成员函数的返回值为传值方式时当成员函数的返回值为传值方式时, 允许改变该允许改变该对象的私有数据成员。对象的私有数据成员。n当成员函数的返回值为常值传值方式时当成员函数的返回值为常值传值方式时, 需加需加 const 标识标识, 该对象的私有成员不能改变。该对象的私有成员不能改变。n当成员函数的返回值为引用方式时当成员函数的返回值为引

23、用方式时, 该成员函数的该成员函数的返回值应是一个已存在变量返回值应是一个已存在变量(或对象或对象)的别名。当该的别名。当该成员函数被重新赋值时成员函数被重新赋值时, 其对应变量其对应变量(或对象或对象)的值的值将改变。将改变。n当成员函数的返回值为常值引用方式时当成员函数的返回值为常值引用方式时, 其返回值其返回值与引用方式的成员函数返回值类同。但该成员函与引用方式的成员函数返回值类同。但该成员函数不能改变该对象的私有成员。数不能改变该对象的私有成员。n当成员函数返回值为常值传值方式或常值引用方当成员函数返回值为常值传值方式或常值引用方式时式时, const 标识符一般放在最后。标识符一般放

24、在最后。n #includen class Temperature n private:n float highTemp, lowTemp; /数据成员数据成员n public:n Temperature(int hi, int lo) /构造函数构造函数n highTemp = hi; lowTemp = lo; n void UpdateTemp(float temp); /传值返回传值返回n float GetHighTemp( ) const; /常值返回常值返回 float GetLowTemp( ) const; /常值传值返回常值传值返回;void Temperature : U

25、pdateTemp(float temp) if (temp highTemp) highTemp = temp; if (temp LowTemp) LowTemp = temp;float Temperature : GetHighTemp( ) const return highTemp;float Temperature : GetHighTemp( ) const return highTemp;C+中的函数名重载n函数名重载允许函数名重载允许C+程序中多个函数取相同程序中多个函数取相同的函数名的函数名, 但其形参或返回类型可以不同。但其形参或返回类型可以不同。n例如，例如，C标准函

26、数库中有标准函数库中有3个标准函数个标准函数abs( )、labs( )和和fabs( ), 分别计算整型数、长整型分别计算整型数、长整型数和双精度型数的绝对值。在数和双精度型数的绝对值。在C中因处理的中因处理的数据类型不同数据类型不同, 必须取不同的函数名。在必须取不同的函数名。在C+ 中中, 可以把这可以把这 3 个函数都命名为个函数都命名为abs ( )：n int abs ( int );n long abs ( long );n double abs ( double );C+的操作符重载 nC+提供了一种能力提供了一种能力, 可用同一个名字定义可用同一个名字定义多个函数多个函数,

27、这种能力叫做操作符重载。这种能力叫做操作符重载。n编译器能够比较具有同名的函数的特征编译器能够比较具有同名的函数的特征, 通通过识别实参的数目和每个实参的类型过识别实参的数目和每个实参的类型, 来标来标识使用于一个特定调用的是哪一个版本的识使用于一个特定调用的是哪一个版本的abs( )。n为了支持面向对象，为了支持面向对象，C+ 提供了双目重载提供了双目重载操作符操作符 (如如和和)。这种操作可。这种操作可使得程序更可读、写得更自然。使得程序更可读、写得更自然。n例如例如, 可定义可定义“点点(Point)”的运算的运算, 像像np1+p2: 把两个点把两个点(x1, y1)和和(x2, y2

28、)相加成相加成一个点一个点 (x1+x2, y1+y2)。up1p2: 两个点两个点p1和和p2的的“小于小于关系关系, 表示表示p1比比p2更靠近原点更靠近原点(0, 0)。up1i: 一个点一个点p(x, y) 除以一个整数除以一个整数 i 的除法的除法 (x/i, y/i)。u可以按以下方式使用重载操作：可以按以下方式使用重载操作：u Point operator + ( Point p );u Point operator / (int i); int operator (Point p);u使用这些新的操作的表达式如使用这些新的操作的表达式如:u Point midPoint = (

29、point1+ point2) / 2;或或 if ( midPoint referencePoint ) .C+的动态存储分配n在在C程序中程序中, 使用一个函数使用一个函数 malloc, 为程序为程序分配它所需要的空间，一旦程序执行结束分配它所需要的空间，一旦程序执行结束需要返回到它的调用者时，必须释放这个需要返回到它的调用者时，必须释放这个空间。空间。nC+为动态存储分配提供了两个新的命令：为动态存储分配提供了两个新的命令：new和和delete。它们可用于取代。它们可用于取代 C 中的库中的库函数函数malloc和和free。n在在C+中没有无用单元收集，使用中没有无用单元收集，使用

30、new分分配的存储必须显式地使用配的存储必须显式地使用delete释放。释放。n操作操作new要求以被建立对象的类型做为参要求以被建立对象的类型做为参数，并返回一个指向新分配空间的指针。数，并返回一个指向新分配空间的指针。n作为对比作为对比, 在在C中中, 函数函数malloc要求它的调要求它的调用者提供所需存储空间的数量。用者提供所需存储空间的数量。n例如例如, 为动态分配一个整数或一个点为动态分配一个整数或一个点, 可编可编写如下语句：写如下语句：n int *ip = new int;或或 Point *p = new Point;n它们组成了指针变量的声明它们组成了指针变量的声明 (如

31、如 * name) 和动态存储分配和动态存储分配 ( new 类型类型 )。ndelete 命令必须能够知道命令必须能够知道 new 分配了多少分配了多少存储。当要释放动态分配的数组时，必须告存储。当要释放动态分配的数组时，必须告诉诉 delete 该数组中包含的元素个数。该数组中包含的元素个数。n例如，如果已建立下列有例如，如果已建立下列有 100个点的数组：个点的数组：n Point* p = new Point100;n则通过以下命令释放该存储则通过以下命令释放该存储:n delete 100 p;n若遗漏了若遗漏了“100”, 则将只释放则将只释放 p 所指示的第所指示的第一个元素一个

32、元素, 将将“失去失去其它其它99个点所占据空个点所占据空间间, 以致不能再复用它们。若使用时元素下以致不能再复用它们。若使用时元素下标超出标超出100, 程序将会出错且结果不可预测。程序将会出错且结果不可预测。友元友元(friend)函数函数 在类的声明中可使用保留字在类的声明中可使用保留字 friend 定义友定义友元函数。元函数。 友元函数实际上并不是这个类的成员函数，友元函数实际上并不是这个类的成员函数，它可以是一个常规函数，也可以是另一个它可以是一个常规函数，也可以是另一个类的成员函数。如果想通过这种函数存取类的成员函数。如果想通过这种函数存取类的私有成员和保护成员，则必须在类的类的

33、私有成员和保护成员，则必须在类的声明中给出函数的原型，并在该函数原型声明中给出函数的原型，并在该函数原型前面加上一个前面加上一个friend。 参看参看Point类的声明类的声明, 有两个重载操作符有两个重载操作符，它们都被声明为友元函数。，它们都被声明为友元函数。内联内联(inline)函数函数n在函数定义前加上一个在函数定义前加上一个inline前缀就成为内前缀就成为内联函数。联函数。n直接插入代码所需要的空间比不直接插入直接插入代码所需要的空间比不直接插入的调用方式所需要的空间要多，这取决于的调用方式所需要的空间要多，这取决于函数定义的大小。函数定义的大小。n除了加上除了加上inline

34、保留字外保留字外, 内联函数的定义内联函数的定义 与其它任何函数定义的方式一样。与其它任何函数定义的方式一样。 inline Point operator + (Point p);构造构造(struct)与类与类nC+ 扩充了扩充了 C 中结构中结构 (struct) 型的功用型的功用, 加进加进成员函数以说明一个类成员函数以说明一个类 (class)。在。在 C+ 中中 struct 与与 class 的区别在于的区别在于:n在在 struct 中中, 默认的访问级别是默认的访问级别是 public。若在。若在 struct 内部自始至终缺省访问级别内部自始至终缺省访问级别, 则所有的则所有

35、的成员都是共有的。成员都是共有的。n在在 class 中中, 缺省的访问级别是缺省的访问级别是 private。n除此之外，除此之外，struct 与与 class 是等价的。例如，是等价的。例如，下面给出定义矩形类的三种等价的类声明。下面给出定义矩形类的三种等价的类声明。class Rectangle int x1, y1, h, w;public: Rectangle ( ); Rectangle ( ); int GetX ( ); int GetY ( ); void SetX (int x); void SetY (int y); int GetHeight ( ); int Get

36、Width ( ); struct Rectangle Rectangle ( ); Rectangle ( ); int GetX ( ); int GetY ( ); void SetX (int x); void SetY (int y); int GetHeight ( ); int GetWidth ( ); private: int x1, y1, h, w;结合结合(Union)与类与类n与结构一样与结构一样, 用用Union也可以定义类。也可以定义类。n在在C+中中, Union可包含函数和变量可包含函数和变量, 还可包还可包含构造函数和析构函数。含构造函数和析构函数。nC+的的Union保留了所有保留了所有C的特性的特性, 主要是让主要是让所有的数据成员共享相同的存储地址。所有的数据成员共享相同的存储地址。n与与cl