数据结构c.ppt

《数据结构c.ppt》由会员分享，可在线阅读，更多相关《数据结构c.ppt（60页珍藏版）》请在三一文库上搜索。

1、1,C+语言的概要 类、对象、构造函数与析构函数 输入/输出 函数、参数传递与函数返回值 函数名重载与操作符重载 动态存储分配 友元函数与内联函数 结构、联合与类,编程简介,C+,2,C+语言概要,C+源于C语言。 1970年，贝尔实验室的Brian Kernighan和Dennis Ritchie首创了一种新的程序设计语言，取名为C语言。 设计C语言的最初目的是编写操作系统。,3,C 语言是一个面向过程的语言。随着软件开发技术的进步, 程序员们最终发现, 把数据和施加在其上的操作结合起来，会得到更易于理解的程序，由此产生了面向对象的程序设计思想。 1980年代初，美国 AT & T 贝尔实验

2、室的Bjarne Stroustrup设计并实现了C语言的扩充、改进版本，C+语言诞生了！ C+改进了C的不足之处，增加了对面向对象的程序设计的支持，在改进的同时，保持了C的简洁性和高效性。,4,/一个简单的C+程序（标准版本） #include using namespace std; int main() cout “hello!“; return 0; /正常返回 ,5,注释,C+的块注释格式源于C语言。注释开始于“/*”，结束于“*/” 。 行注释符以“/”开头。,6,#include 语句,C+将一些标准函数和变量说明放在头文件中。 用户也可以定义自己的头文件。 #include指令

3、有两种格式： #include #include “头文件名”,7,C+源程序中还可包括各种编译命令, 这些命令被称为预处理指令, 常用的除 #include外, 还有条件预处理指令 #if、#ifndef 和#endif 等和宏替换指令 #define。,8,#define 用来定义一个常量或替换宏, 如： #define size 20 /定义一个常量size，其值永远为20 #define MAX(x, y) (x y) ? y : x) /求x, y中的最大值 经过预编译后, 程序中所有出现 size 和 MAX(x, y) 之处都会被 20 和 (x y) ? y : x) 代替，如

4、： int arraysize; int i = MAX(4, 55); 经预编译后会变为 int array20; int i = (4 55) ? 55 : 4);,9,C+的数据声明,C+的数据声明将数据名与数据类型联系起来。其主要形式有： 常数值：如25, 13.4, “value is”, 它们的内容保持不变。 常量：数据声明时在变量名前冠以保留字const，如 const int MAX = 500, 可定义 一个常量。 变量：数据类型的实例, 在程序执行时可以改变其内容。,10,C+提供两大类数据类型：基本数据类型和复合数据类型。 基本数据类型有 6 种： int 、 float

5、、char、double、bool 、void。 复合数据类型包括结构(struct)、联合(union)、位域、枚举(enum)、类(class)和用户自定义类型。 此外还有由基本数据类型和复合数据类型引申而来的数据类型，包括数组、指针、引用等。,11,枚举：是声明一个整型常数序列的方式。例如, 在程序开头做如下声明 enum Boolean FALSE, TRUE 则建立一个Boolean类型。 指针：存放对象的存储地址，例如 int i = 5; int *np; /np为一个指向整型量的指针 np = /k中存入np所指地址i的内容,12,引用：它用来给一个对象提供一个替代的名字。例如

6、 int i = 5; int,13,C+的类,C+的核心部分是类的定义。类定义体现了抽象数据类型的思想。为达到信息隐蔽的原则。规定对类的成员有三级存取： 共有(public) 私有(private) 保护(protected) 在 public 域中声明的数据成员和函数成员(成员函数)，它们构成类的界面部分。,14,在private域和protected域中声明的数据成员和成员函数构成类的私有部分，只能由该类的对象和成员函数，以及声明为友元(friend)的函数或类的对象才能访问它们。 在protected域中声明的数据成员和成员函数，还允许该类的派生类访问它们； 在private域中声明的

7、数据成员和成员函数，则不允许该类的派生类访问它们。 下面给出一个 point 类的声明。Point 类中 点的表示由两个整数变量 x, y 组成。类的用户不能直接访问它们。,15,#ifndef POINT_H #define POINT_H /In the header file point.h class Point /类定义 private: /私有域 int x; /数据成员：点坐标 int y; public: /共有域 Point ( int = 0, int = 0 ); /构造函数 Point (const Point /取y坐标,16,Point operator + ( c

8、onst Point #endif,17,例，对于Point类的输出友元函数的实现可以在源程序文件中给出，形为： ostream 这个函数把点p的值以“x, y”的格式送到strm指明的输出流中去。,18,C+中的对象,建立类的对象(亦称为实例化)时采用的方式类似于定义C变量的方式，可以自动地，或静态地, 或通过动态分配来建立。建立一个 Point类实例的语句是： Point p (6, 3); 自动地 Point q; 自动地 static Point s (3, 4); 静态地 Point *t = new Point(1, 1); 通过动态分配,19,构造函数,当遇到以上的每一个语句时,

9、 将隐式地调用一个构造(constructor)函数, 这个构造函数属于一个与它同名的类。 在Point类的定义中声明了两个构造函数, 构造函数的参数用于初始化表达式的值。 例如, 当使用声明 Point p(6, 3) 建立 Point 类的对象 p 时,调用了构造函数 Point (int, int);通过以下函数定义, 将其x, y分量设定为6, 3： Point : Point (int a,int b) x = a; y = b; Point : Point (int a,int b) : x(a), y(b) ,20,构造函数可以定义默认值。例如 Point : Point ( i

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

11、te 命令释放一个动态分配的变量时, 就要调用析构函数。当main函数执行结束时，将释放静态声明的变量。 一个析构函数用于在删除一个类的对象时做清除工作。,22,C+的输入/输出,在C+中执行输入/输出操作, 需用#include预处理指令包括一个头文件。用它可支持C+的流(stream)操作。 “流”是个简单的字符序列。在C+中有两个预定义的类istream和ostream，它们定义了输入流和输出流。 基本输入/输出方式： 键盘屏幕输入/输出 文件输入/输出,23,键盘屏幕输入/输出,在C中有用于定向到键盘输入设备、屏幕输出设备和错误文件的命令stdin、stdout和stderr。 在C+

12、中用cin，cout和cerr来定义键盘输入类、屏幕输出类和错误信息输出类。 操作符 用于读入类istream的一个对象。,24,在下面程序中使用了流 cin ，相继从标准输入设备上输入两个整型变量a和b, 并将它们打印到标准输出设备上。 在输出语句中最后输出的endl是C+的I/O操作符, 它的用途是输出一个换行符并清空流。,#include int main ( ) int a, b; cin a b; cout “a : ” n “f : ” f endl; return 0; ,25,文件输入/输出,C+中的文件输入/输出方式如下所示。 在程序开头必须用预处理指令#include包含头

13、文件，它定义了类ifstream、ofstream和fstream。 要创建一个输入流, 必须声明它为ifstream类的实例 要创建一个输出流, 必须声明它为ofstream类的实例 执行输入和输出操作的流必须声明它为 fstream类的实例,26,#include #include #include int main ( ) ifstream inFile; / inFile为输入流对象 ofstream outFile; / outFile为输出流对象 outFile.open (“my.dat“, ios : out ); / 建立输出文件my.dat char univ = Tsin

14、ghua, name10; int course = 2401, number; outFile univ course endl; / 输出到my.dat,27,inFile.open(“my.dat“, ios:in); /打开输入文件my.dat if ( !inFile ) cerr name number; cout “name: “ name endl; cout “number: “ number endl; return 0; ,28,在文件打开的操作中，指定的文件模式有以下几种： ios:app：把所有对文件的输出添加在文件尾。它只用于输出文件。 ios:binary：文件以

15、二进制方式打开。此项缺省时文件以文本方式打开。 ios:nocreate：若文件不存在则将导致打开操作失败。 ios:out：表明该文件用于输出。此项可缺省。 ios:in：表明该文件用于输入。此项可缺省。,29,C+中的函数,在C+中有两种函数： 常规函数和成员函数 不论哪种函数, 其定义都包括 4 个部分: 函数名、形式参数表、返回类型和函数体。,30,函数返回时可以通过引用方式，参看下面程序, 此时在函数类型后面加上一 个“ ,31,C+中的参数传递,函数调用时传送给形参表的实参必须与形参在类型、个数、顺序上保持一致。 参数传递有两种方式。一种是传值，这是缺省的参数传递方式; 一种是引用

16、类型。 使用传值方式时，把实参的值传送给函数局部工作区相应的副本中，函数使用这个副本执行必要的功能。这样，函数修改的是副本的值，实参的值不变。,32,使用引用类型方式传递时, 需将形参声明为引用类型，即在参数名前加一个“,33,void swap(int /不需要加 * ,34,一种特殊的引用调用方式叫做常值引用, 其格式为 const T& a。在函数体中不能修改常值参数。 一种特殊情况是数组参数的传递。数组作为形参可按传值方式声明，传递的是数组第一个元素的地址。 此外，在参数表中一般按形如 int R 的形式声明，因此需要显式地声明数组的大小。,35,若传送的值参是一个对象 (作为类的实例

17、) 时, 在函数中就创建了该对象的一个副本。在创建这个副本时不调用该对象的构造函数，但在函数结束前要调用该副本的析构函数撤消这个副本。 若采用引用方式传递对象，在函数中不创建该对象的副本，也不存在最后撤消副本的问题。但是，通过引用传递的是对象时，函数对对象的改变将影响调用的对象。,36,成员函数的返回值,当成员函数的返回值为传值方式时, 允许改变该对象的私有数据成员。 当成员函数的返回值为常值传值方式时, 需加 const 标识, 该对象的私有成员不能改变。 当成员函数的返回值为引用方式时, 该成员函数的返回值应是一个已存在变量(或对象)的别名。当该成员函数被重新赋值时, 其对应变量(或对象)

18、的值将改变。 当成员函数的返回值为常值引用方式时, 其返回值与引用方式的成员函数返回值类同。但该成员函数不能改变该对象的私有成员。,37,当成员函数返回值为常值传值方式或常值引用方式时, const 标识符一般放在最后。 #include class Temperature private: float highTemp, lowTemp; /数据成员 public: Temperature(int hi, int lo) /构造函数 highTemp = hi; lowTemp = lo; void UpdateTemp(float temp); /传值返回 float GetHighTem

19、p( ) const; /常值返回,38,float GetLowTemp( ) const; /常值传值返回 ; void Temperature : UpdateTemp(float temp) if (temp highTemp) highTemp = temp; if (temp LowTemp) LowTemp = temp; float Temperature : GetHighTemp( ) const return highTemp; float Temperature : GetHighTemp( ) const return highTemp; ,39,C+中的函数名重载,

20、函数名重载允许C+程序中多个函数取相同的函数名, 但其形参或返回类型可以不同。 例如，C标准函数库中有3个标准函数abs( )、labs( )和fabs( ), 分别计算整型数、长整型数和双精度型数的绝对值。在C中因处理的数据类型不同, 必须取不同的函数名。在C+ 中, 可以把这 3 个函数都命名为abs ( )： int abs ( int ); long abs ( long ); double abs ( double );,40,C+的操作符重载,C+提供了一种能力, 可用同一个名字定义多个函数, 这种能力叫做操作符重载。,编译器能够比较具有同名的函数的特征, 通过识别实参的数目和每个

21、实参的类型, 来标识使用于一个特定调用的是哪一个版本的abs( )。,41,为了支持面向对象，C+ 提供了双目重载操作符 (如和)。这种操作可使得程序更可读、写得更自然。 例如, 可定义“点(Point)”的运算, 像 p1+p2: 把两个点(x1, y1)和(x2, y2)相加成一个点 (x1+x2, y1+y2)。,42,p1p2: 两个点p1和p2的“小于”关系, 表示p1比p2更靠近原点(0, 0)。 p1i: 一个点p(x, y) 除以一个整数 i 的除法 (x/i, y/i)。 可以按以下方式使用重载操作： Point operator + ( Point p ); Point o

22、perator / (int i); int operator (Point p); 使用这些新的操作的表达式如: Point midPoint = (point1+ point2) / 2; 或 if ( midPoint referencePoint ) .,43,C+的动态存储分配,在C程序中, 使用一个函数 malloc, 为程序分配它所需要的空间，一旦程序执行结束需要返回到它的调用者时，必须释放这个空间。 C+为动态存储分配提供了两个新的命令：new和delete。它们可用于取代 C 中的库函数malloc和free。 在C+中没有无用单元收集，使用new分配的存储必须显式地使用de

23、lete释放。,44,操作new要求以被建立对象的类型做为参数，并返回一个指向新分配空间的指针。 作为对比, 在C中, 函数malloc要求它的调用者提供所需存储空间的数量。 例如, 为动态分配一个整数或一个点, 可编写如下语句： int *ip = new int; 或 Point *p = new Point; 它们组成了指针变量的声明 (如 * name) 和动态存储分配 ( new 类型 )。,45,delete 命令必须能够知道 new 分配了多少存储。当要释放动态分配的数组时，必须告诉 delete 该数组中包含的元素个数。 例如，如果已建立下列有 100个点的数组： Point*

24、 p = new Point100; 则通过以下命令释放该存储: delete 100 p; 若遗漏了“100”, 则将只释放 p 所指示的第一个元素, 将“失去”其它99个点所占据空间, 以致不能再复用它们。若使用时元素下标超出100, 程序将会出错且结果不可预测。,46,友元(friend)函数,在类的声明中可使用保留字 friend 定义友元函数。 友元函数实际上并不是这个类的成员函数，它可以是一个常规函数，也可以是另一个类的成员函数。如果想通过这种函数存取类的私有成员和保护成员，则必须在类的声明中给出函数的原型，并在该函数原型前面加上一个friend。 参看Point类的声明, 有两个

25、重载操作符，它们都被声明为友元函数。,47,内联(inline)函数,在函数定义前加上一个inline前缀就成为内联函数。 直接插入代码所需要的空间比不直接插入的调用方式所需要的空间要多，这取决于函数定义的大小。 除了加上inline保留字外, 内联函数的定义 与其它任何函数定义的方式一样。 inline Point operator + (Point p);,48,结构(struct)与类,C+ 扩充了 C 中结构 (struct) 型的功用, 加进成员函数以说明一个类 (class)。在 C+ 中 struct 与 class 的区别在于: 在 struct 中, 默认的访问级别是 pub

26、lic。若在 struct 内部自始至终缺省访问级别, 则所有的成员都是共有的。 在 class 中, 缺省的访问级别是 private。 除此之外，struct 与 class 是等价的。例如，下面给出定义矩形类的三种等价的类声明。,49,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 GetWidth ( ); ,50,

27、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; ,51,联合(Union)与类,与结构一样, 用Union也可以定义类。 在C+中, Union可包含函数和变量, 还可包含构造函数和析构函数。 C+的Union保留了所有C的特性, 主要是让所有的数据成员共享相同的存储地址。 与class和st

28、ruct相比, Union可节省存储。与结构相似, Union中默认存取级别是public。,52,模板 (template),定义 适合多种数据类型的类定义或算法，在特定环境下通过简单地代换，变成针对具体某种数据类型的类定义或算法,53,用模板定义用于排序的数据表类 #include template class DataList private: T *Element; int ArraySize; void Swap (int m1, int m2); int MaxKey (int low, int high);,54,public: DataList (int size = 10)

29、: ArraySize (size), Element (new T Size) DataList ( ) delete Element; void Sort ( ); friend ostream,55,类中所有操作作为模板函数的实现 template void DataList : Swap (int m1, int m2) /交换由m1, m2为下标的数组元素的值 T temp = Element m1; Element m1 = Element m2; Element m2 = temp; ,56,template int DataList: MaxKey (int low, int

30、high) /查找数组Elementlow到Elementhigh /中的最大值，函数返回其位置 int max = low; for (int k = low+1, k = high, k+) if ( Elementmax Elementk ) max = k; return max; ,57,template ostream ,58,template istream ,59,template void DataList:Sort ( ) /按非递减顺序对ArraySize个关键码 /Element0到ElementArraySize-1排序 for ( int i = ArraySize -1; i 0; i- ) int j = MaxKey (0, i); if ( j != i ) Swap (j, i); ,60,使用模板的选择排序算法的主函数 #include “DataList.h” const int SIZE = 10; int main ( ) DataList TestList (SIZE); cin TestList; cout TestList endl; TestList.Sort ( ); cout TestList endl; return 0; ,