C++语言程序设计教案.doc

教 案课程名称： C+语言程序设计 教员姓名： 潘俊杰 授课对象：层次 晋升中高级职称专业技术人员 队别 审 查 人：姓名 时间 2007年4月 主要内容：一、教案题目：C+语言程序设计（时间40学时）二、教学目的：C+语言程序设计是为总装部队科研试验技术干部晋升专业技术职务进行职前培训而开设的一门选修课。通过该课程的学习，使参加学习的各级专业技术干部掌握面向对象程序设计的基本思想和C+程序设计知识，提高程序设计能力。 三、教学内容、重点 教学内容：C+语言程序设计包括C+基础知识，函数，类与对象，C+程序结构，数组、指针与字符串，继承与多态，群体类，标准模板库，异常处理。教学重点：C+基础知识，函数，类与对象，C+程序结构，数组、指针与字符串，继承与多态。四、教学方法 采用课堂讲授与模拟练习相结合。基本概念和理论、基本操作方法及应用的课堂讲授占总学时的70，个人动手实验操作、模拟练习占总学时的30。五、教学手段多媒体课件、板书。六、教学保障 多媒体教学系统。 教学过程教学内容第一章C+基础1 C+语言概述 C+语言的产生l C+是从C语言发展演变而来的，首先是一个更好的Cl 引入了类的机制，最初的C+被称为“带类的C”l 1983年正式取名为C+l 从1989年开始C+语言的标准化工作l 于1994年制定了ANSI C+标准草案l 于1998年11月被国际标准化组织（ISO）批准为国际标准，成为目前的C+C+的特点l 全面兼容C 它保持了C的简洁、高效和接近汇编语言等特点 对C的类型系统进行了改革和扩充 C+也支持面向过程的程序设计，不是一个纯正的面向对象的语言l 支持面向对象的方法2基本数据类型和表达式数据类型 整型数据及取值范围类型说明符 位数数值范围短整short16-3276832767基本 int32 -231(231-1)长整long32-231(231-1)无符号unsigned short16065535 unsigned int320(232-1)unsigned long320(232-1) 数据类型 字符型数据（一）l 字符常量 单引号括起来的一个字符，如：a, D, ?, $l 字符变量 用来存放字符常量 例：char c1,c2; c1=a; c2=A;l 字符数据在内存中的存储形式 以ASCII 码存储，占1 字节，用7 个二进制位 数据类型 字符型数据（二）l 字符数据的使用方法 字符数据和整型数据之间可以运算。 字符数据与整型数据可以互相赋值。l 字符串常量 例:CHINA a a 所以：char c; c=a; 数据类型 布尔型数据l 布尔型变量的说明：例：bool flag;l 布尔型数据的取值：只有 false 和 true 两个值3数据的输入与输出简单的输入、输出l 向标准输出设备（显示器）输出例：int x; cout“x=“x; 4算法的基本控制结构 顺序结构 分支结构 循环结构5自定义数据类型枚举类型enuml 只要将需要的变量值一一列举出来，便构成了一个枚举类型。l 枚举类型的声明形式如下：enum 枚举类型名 变量值列表;结构体结构的声明l 结构的概念 结构是由不同数据类型的数据组成的集合体。l 声明结构类型 struct 结构名 数据类型 成员名 1 ； 数据类型 成员名 2 ； ： 数据类型 成员名 n ； ;联合体l 声明形式：union 联合名 数据类型 成员名 1 ； 数据类型 成员名 2 ； ： 数据类型 成员名 n ； ;l 联合体类型变量说明的语法形式 联合名 联合变量名； l 引用形式： 联合名. 成员名 第二章 函数1函数的声明和调用函数的声明l 函数是面向对象程序设计中，对功能的抽象l 函数声明的语法形式类型标识符 函数名（形式参数表） 语句序列函数的声明l 形式参数表 name1, name2, ., namenl 函数的返回值 由 return 语句 给出，例如： return 0 无返回值的函数（void类型），不必写return语句。 函数的调用l 调用前先声明函数原型： 在调用函数中，或程序文件中所有函数之外，按如下形式说明： 类型标识符 被调用函数名 （含类型说明的形参表）;l 调用形式 函数名（实参列表）l 嵌套调用 函数可以嵌套调用，但不允许嵌套定义。 l 递归调用 函数直接或间接调用自身。 2内联函数内联函数声明与使用l 声明时使用关键字 inline。l 编译时在调用处用函数体进行替换,节省了参数传递、控制转移等开销。l 注意： 内联函数体内不能有循环语句 和switch 语句。 内联函数的声明必须出现在内联函数第一次被调用之前。 对内联函数不能进行异常接口声明。 3内联函数声明与使用l 声明时使用关键字 inline。l 编译时在调用处用函数体进行替换,节省了参数传递、控制转移等开销。l 注意： 内联函数体内不能有循环语句 和switch 语句。 内联函数的声明必须出现在内联函数第一次被调用之前。 对内联函数不能进行异常接口声明。 4 重载函数的声明l C+允许功能相近的函数在相同的作用域内以相同函数名声明，从而形成重载。方便使用，便于记忆。l 注意事项l 重载函数的形参必须不同: 个数不同或类型不同。l 编译程序将根据实参和形参的类型及个数的最佳匹配来选择调用哪一个函数。5 C+系统函数l C+的系统库中提供了几百个函数可供程序员使用。例如：求平方根函数（sprt）、求绝对值函数（abs）等。l 使用系统函数时要包含相应的头文件。 例如：math.h 或 cmath第三章类与对象本章主要内容l 面向对象的思想l OOP的基本特点l 类概念和声明l 对象l 构造函数l 析构函数l 内联成员函数l 拷贝构造函数ll 一 类概念和声明类的声明形式 类是一种用户自定义类型，声明形式：class 类名称 public: 公有成员 （外部接口） private: 私有成员 protected: 保护型成员 l 二 对象对象l 类的对象是该类的某一特定实体，即类类型的变量。l 声明形式： 类名 对象名；l 例： Clock myClock;类中成员的访问方式l 类中成员互访 直接使用成员名l 类外访问 使用 “对象名.成员名 ” 方式访问 public 属性的成员 三 构造函数构造函数l 构造函数的作用是在对象被创建时使用特定的值构造对象，或者说将对象初始化为一个特定的状态。l 在对象创建时由系统自动调用。l 如果程序中未声明，则系统自动产生出一个默认形式的构造函数l 允许为内联函数、重载函数、带默认形参值的函数四 析构函数析构函数l 完成对象被删除前的一些清理工作。l 在对象的生存期结束的时刻系统自动调用它，然后再释放此对象所属的空间。l 如果程序中未声明析构函数，编译器将自动产生一个默认的析构函数。五 内联成员函数内联成员函数l 为了提高运行时的效率，对于较简单的函数可以声明为内联形式。l 内联函数体中不要有复杂结构（如循环语句和switch语句）。l 在类中声明内联成员函数的方式： 将函数体放在类的声明中。 使用inline 关键字。 六 拷贝构造函数拷贝构造函数拷贝构造函数是一种特殊的构造函数，其形参为本类的对象引用。class 类名 public : 类名（形参）；/ 构造函数 类名（类名 & 对象名）；/拷贝构造函数 . ； 类名: 类名（类名 & 对象名）/拷贝构造函数的实现 函数体 第四章程序结构主要内容本章主要内容l 作用域与可见性l 对象的生存期l 数据与函数l 静态成员l 共享数据的保护l 友元l 编译预处理命令l 多文件结构和工程一 作用域与可见性函数原形的作用域l 函数原型中的参数，其作用域始于(，结束于)。l 例如，设有下列原型声明：double Area(double radius);块作用域l 在块中声明的标识符，其作用域自声明处起，限于块中，例如：void fun(int a) int b(a); cinb; if (b0) int c; . 类作用域l 类作用域作用于特定的成员名。l 类X的成员M具有类作用域，对M的访问方式如下： 如果在X的成员函数中没有声明同名的局部作用域标识符，那么在该函数内可以访问成员M。 通过表达式x.M或者X:M访问。 通过表达式prt-M文件作用域l 不在前述各个作用域中出现的声明，具有文件作用域，这样声明的标识符的作用域开始于声明点，结束于文件尾。可见性l 可见性是从对标识符的引用的角度来谈的概念l 可见性表示从内层作用域向外层作用域 “看 ”时能看见什么。l 如果标识在某处可见，则就可以在该处引用此标识符。l 标识符应声明在先，引用在后。l 如果某个标识符在外层中声明，且在内层中没有同一标识符的声明，则该标识符在内层可见。l 对于两个嵌套的作用域，如果在内层作用域内声明了与外层作用域中同名的标识符，则外层作用域的标识符在内层不可见。同一作用域中的同名标识符l 在同一作用域内的对象名、函数名、枚举常量名会隐藏同名的类名或枚举类型名。l 重载的函数可以有相同的函数名。二 对象的生存期对象的生存期对象从产生到结束的这段时间就是它的生存期。在对象生存期内，对象将保持它的值，直到被更新为止。静态生存期l 这种生存期与程序的运行期相同。l 在文件作用域中声明的对象具有这种生存期。l 在函数内部声明静态生存期对象，要冠以关键字static 。动态生存期l 块作用域中声明的，没有用static修是的对象是动态生存期的对象（习惯称局部生存期对象）。l 开始于程序执行到声明点时，结束于命名该标识符的作用域结束处。三 数据与函数数据与函数l 数据存储在局部对象中，通过参数传递实现共享函数间的参数传递。l 数据存储在全局对象中。l 将数据和使用数据的函数封装在类中。四 静态成员静态成员l 静态数据成员 用关键字static声明 该类的所有对象维护该成员的同一个拷贝 必须在类外定义和初始化，用(:)来指明所属的类。l 静态成员函数 类外代码可以使用类名和作用域操作符来调用静态成员函数。 静态成员函数只能引用属于该类的静态数据成员或静态成员函数。 五 共享数据的保护常类型 常类型的对象必须进行初始化，而且不能被更新。l 常引用：被引用的对象不能被更新。const 类型说明符 &引用名l 常对象：必须进行初始化,不能被更新。类名 const 对象名l 常数组：数组元素不能被更新(下一章介绍)。类型说明符 const 数组名大小.l 常指针：指向常量的指针(下一章介绍)。六 友元友元l 友元是C+提供的一种破坏数据封装和数据隐藏的机制。l 通过将一个模块声明为另一个模块的友元，一个模块能够引用到另一个模块中本是被隐藏的信息。l 可以使用友元函数和友元类。l 为了确保数据的完整性，及数据封装与隐藏的原则，建议尽量不使用或少使用友元。友元函数l 友元函数是在类声明中由关键字friend修饰说明的非成员函数，在它的函数体中能够通过对象名访问 private 和 protected成员l 作用：增加灵活性，使程序员可以在封装和快速性方面做合理选择。l 访问对象中的成员必须通过对象名。七 编译预处理命令编译预处理命令l #include 包含指令 将一个源文件嵌入到当前源文件中该点处。 #include l 按标准方式搜索，文件位于C+ 系统目录的include 子目录下 #include 文件名l 首先在当前目录中搜索，若没有，再按标准方式搜索。 l #define 宏定义指令 定义符号常量，很多情况下已被const 定义语句取代。 定义带参数宏，已被内联函数取代。 l #undef 删除由#define 定义的宏，使之不再起作用。 条件编译指令 #if 和 #endif#if 常量表达式 /当“ 常量表达式”非零时编译 程序正文 #endif. 八 多文件结构和工程多文件结构（例5-10）l 一个源程序可以划分为多个源文件： 类声明文件（.h文件） 类实现文件（.cpp文件） 类的使用文件（main()所在的.cpp文件）l 利用工程来组合各个文件。第五章 数组 指针与字符串本章主要内容l 数组l 指针l 动态存储分配l 指针与数组l 指针与函数l 字符串一 数组数组的概念数组是具有一定顺序关系的若干相同类型变量的集合体，组成数组的变量称为该数组的元素。数组属于构造类型。一维数组的声明与引用l 一维数组的声明类型说明符 数组名 常量表达式 ； 例如： int a10; 表示 a 为整型数组，有10个元素：a0.a9二 指针指针变量的赋值运算指针名=地址l “地址”中存放的数据类型与指针类型必须相符。l 向指针变量赋的值必须是地址常量或变量，不能是普通整数。但可以赋值为整数0，表示空指针。l 指针的类型是它所指向变量的类型，而不是指针本身数据值的类型，任何一个指针本身的数据值都是unsigned long int型。l 允许声明指向 void 类型的指针。该指针可以被赋予任何类型对象的地址。例： void *general; 三 动态存储分配动态申请内存操作符 newnew 类型名T（初值列表）功能：在程序执行期间，申请用于存放T类型对象的内存空间，并依初值列表赋以初值。结果值：成功：T类型的指针，指向新分配的内存。失败：0（NULL）释放内存操作符deletedelete 指针P功能：释放指针P所指向的内存。P必须是new操作的返回值。动态存储分配函数l void *malloc( size );参数size：欲分配的字节数返回值： 成功，则返回void型指针。 失败，则返回空指针。头文件： 和 动态内存释放函数l void free( void *memblock );参数memblock： 指针，指向需释放的 内存。返回值：无头文件： 和 四 指针与数组指向数组元素的指针l 声明与赋值例： int a10, *pa; pa=&a0; 或 pa=a;l 通过指针引用数组元素 经过上述声明及赋值后： *pa 就是a0 ，*(pa+1) 就是a1 ，. ，*(pa+i) 就是ai. ai, *(pa+i), *(a+i), pai 都是等效的。 不能写 a+ ， 因为a 是数组首地址是常量。 五 指针与函数以指针作为函数参数l 以地址方式传递数据，可以用来返回函数处理结果。l 实参是数组名时形参可以是指针。六 字符串用字符数组存储和处理字符串字符串的输入/输出l 方法 逐个字符输入输出 将整个字符串一次输入或输出例：char c=China; coutc;l 注意 输出字符不包括 0 输出字符串时，输出项是字符数组名，输出时遇到0 结束。 输入多个字符串时，以空格分隔；输入单个字符串时其中 不能有空格。 第六章 继承与派生本章主要内容l 类的继承与派生l 类成员的访问控制l 单继承与多继承l 派生类的构造、析构函数l 类成员的标识与访问一 类的继承与派生l 保持已有类的特性而构造新类的过程称为继承。l 在已有类的基础上新增自己的特性而产生新类的过程称为派生。l 被继承的已有类称为基类（或父类）。l 派生出的新类称为派生类。派生类的声明class 派生类名：继承方式 基类名 成员声明；继承方式l 不同继承方式的影响主要体现在： 派生类成员对基类成员的访问权限 通过派生类对象对基类成员的访问权限l 三种继承方式 公有继承 私有继承 保护继承 公有继承(public)l 基类的public和protected成员的访问属性在派生类中保持不变，但基类的private成员不可直接访问。l 派生类中的成员函数可以直接访问基类中的public和protected成员，但不能直接访问基类的private成员。l 通过派生类的对象只能访问基类的public成员。私有继承(private)l 基类的public和protected成员都以private身份出现在派生类中，但基类的private成员不可直接访问。l 派生类中的成员函数可以直接访问基类中的public和protected成员，但不能直接访问基类的private成员。l 通过派生类的对象不能直接访问基类中的任何成员。保护继承(protected)l 基类的public和protected成员都以protected身份出现在派生类中，但基类的private成员不可直接访问。l 派生类中的成员函数可以直接访问基类中的public和protected成员，但不能直接访问基类的private成员。l 通过派生类的对象不能直接访问基类中的任何成员protected 成员的特点与作用l 对建立其所在类对象的模块来说，它与 private 成员的性质相同。l 对于其派生类来说，它与 public 成员的性质相同。l 既实现了数据隐藏，又方便继承，实现代码重用。l 类成员的访问控制l 单继承与多继承l 基类与派生类的对应关系l 单继承l 派生类只从一个基类派生。l 多继承 l 派生类从多个基类派生。 l 多重派生 l 由一个基类派生出多个不同的派生类。 l 多层派生 l 派生类又作为基类，继续派生新的类。 l 多继承时派生类的声明l class 派生类名：继承方式1 基类名1，继承方式2 基类名2，.l l 成员声明；l l 注意：每一个 “继承方式 ”，只用于限制对紧随其后之基类的继承。二 派生类的构造、析构函数l 继承时的构造函数l 基类的构造函数不被继承，派生类中需要声明自己的构造函数。l 声明构造函数时，只需要对本类中新增成员进行初始化，对继承来的基类成员的初始化，自动调用基类构造函数完成。l 派生类的构造函数需要给基类的构造函数传递参数l 单一继承时的构造函数l 派生类名:派生类名(基类所需的形参，本类成员所需的形参):基类名(参数表)l l 本类成员初始化赋值语句；l ；l 多继承时的构造函数l 派生类名:派生类名(基类1形参，基类2形参，.基类n形参，本类形参):基类名1(参数), 基类名2(参数), .基类名n(参数)l l 本类成员初始化赋值语句；l ；l 派生类与基类的构造函数l 当基类中声明有默认形式的构造函数或未声明构造函数时，派生类构造函数可以不向基类构造函数传递参数。l 若基类中未声明构造函数，派生类中也可以不声明，全采用缺省形式构造函数。l 当基类声明有带形参的构造函数时，派生类也应声明带形参的构造函数，并将参数传递给基类构造函数。l 多继承且有内嵌对象时的构造函数l 派生类名:派生类名(基类1形参，基类2形参，.基类n形参，本类形参):基类名1(参数), 基类名2(参数), .基类名n(参数)，对象数据成员的初始化l l 本类成员初始化赋值语句；l ；l 构造函数的调用次序l 1 调用基类构造函数，调用顺序按照它们被继承时声明的顺序（从左向右）。l 2 调用成员对象的构造函数，调用顺序按照它们在类中声明的顺序。l 3 派生类的构造函数体中的内容。l 类成员的标识与访问同名隐藏规则当派生类与基类中有相同成员时：l 若未强行指名，则通过派生类对象使用的是派生类中的同名成员。l 如要通过派生类对象访问基类中被覆盖的同名成员，应使用基类名限定。二义性问题l 在多继承时，基类与派生类之间，或基类之间出现同名成员时，将出现访问时的二义性（不确定性）采用虚函数（第8章）或同名隐藏规则来解决。l 当派生类从多个基类派生，而这些基类又从同一个基类派生，则在访问此共同基类中的成员时，将产生二义性采用虚基类来解决。二义性的解决方法l 解决方法一：用类名来限定c1.A:f() 或 c1.B:f()l 解决方法二：同名覆盖在C 中声明一个同名成员函数f()，f()再根据需要调用 A:f() 或 B:f()虚基类l 虚基类的引入 用于有共同基类的场合l 声明 以virtual 修饰说明基类 例：class B1:virtual public Bl 作用 主要用来解决多继承时可能发生的对同一基类继承多次而产生的二义性问题. 为最远的派生类提供唯一的基类成员，而不重复产生多次拷贝 l 注意： 在第一级继承时就要将共同基类设计为虚基类。 虚基类及其派生类构造函数l 建立对象时所指定的类称为最（远）派生类。l 虚基类的成员是由最派生类的构造函数通过调用虚基类的构造函数进行初始化的。l 在整个继承结构中，直接或间接继承虚基类的所有派生类，都必须在构造函数的成员初始化表中给出对虚基类的构造函数的调用。如果未列出，则表示调用该虚基类的缺省构造函数。l 在建立对象时，只有最派生类的构造函数调用虚基类的构造函数，该派生类的其它基类对虚基类构造函数的调用被忽略。第七章 多态性本章主要内容l 多态性l 运算符重载l 虚函数l 纯虚函数l 抽象类一 多态性的概念l 多态性是面向对象程序设计的重要特征之一。l 多态性是指发出同样的消息被不同类型的对象接收时有可能导致完全不同的行为。l 多态的实现： 函数重载 运算符重载 虚函数 二 运算符重载的实质l 运算符重载是对已有的运算符赋予多重含义l 必要性 C+中预定义的运算符其运算对象只能是基本数据类型，而不适用于用户自定义类型（如类）l 实现机制 将指定的运算表达式转化为对运算符函数的调用，运算对象转化为运算符函数的实参。 编译系统对重载运算符的选择，遵循函数重载的选择原则。两种形式l 重载为类成员函数。l 重载为友元函数。运算符函数l 声明形式函数类型 operator 运算符（形参） .l 重载为类成员函数时 参数个数=原操作数个数-1（后置+、-除外）l 重载为友元函数时 参数个数=原操作数个数，且至少应该有一个自定义类型的形参。运算符成员函数的设计l 双目运算符 B 如果要重载 B 为类成员函数，使之能够实现表达式 oprd1 B oprd2 ， 其中 oprd1 为A 类对象，则 B 应被重载为 A 类的成员函数，形参类型应该是 oprd2 所属的类型。 经重载后，表达式 oprd1 B oprd2 相当于 oprd1.operator B(oprd2)三 静态绑定与动态绑定l 绑定 程序自身彼此关联的过程，确定程序中的操作调用与执行该操作的代码间的关系。l 静态绑定（静态联编） 联编工作出现在编译阶段，用对象名或者类名来限定要调用的函数。 l 动态绑定 联编工作在程序运行时执行，在程序运行时才确定将要调用的函数。 虚函数l 虚函数是动态绑定的基础。l 是非静态的成员函数。l 在类的声明中，在函数原型之前写virtual。l virtual 只用来说明类声明中的原型，不能用在函数实现时。l 具有继承性，基类中声明了虚函数，派生类中无论是否说明，同原型函数都自动为虚函数。l 本质：不是重载声明而是覆盖。l 调用方式：通过基类指针或引用，执行时会根据指针指向的对象的类，决定调用哪个函数。虚析构函数何时需要虚析构函数？l 当你可能通过基类指针删除派生类对象时l 如果你打算允许其他人通过基类指针调用对象的析构函数（通过delete这样做是正常的），并且被析构的对象是有重要的析构函数的派生类的对象，就需要让基类的析构函数成为虚拟的。四 抽象类带有纯虚函数的类称为抽象类:class 类名 virtual 类型 函数名(参数表)=0; /纯虚函数 .抽象类l 作用 抽象类为抽象和设计的目的而声明，将有关的数据和行为组织在一个继承层次结构中，保证派生类具有要求的行为。 对于暂时无法实现的函数，可以声明为纯虚函数，留给派生类去实现。l 注意 抽象类只能作为基类来使用。 不能声明抽象类的对象。 构造函数不能是虚函数，析构函数可以是虚函数。例 8.5#include using namespace std;class B0 /抽象基类B0声明 public: /外部接口virtual void display( )=0; /纯虚函数成员;class B1: public B0 /公有派生 public:void display()coutB1:display()endl; /虚成员函数;class D1: public B1 /公有派生 public:void display()coutD1:display()display(); void main()/主函数B0 *p;/声明抽象基类指针B1 b1;/声明派生类对象D1 d1;/声明派生类对象p=&b1;fun(p);/调用派生类B1函数成员p=&d1;fun(p);/调用派生类D1函数成员第八章 群体类和群体数据的组织本章主要内容l 模板l 群体类l 群体数据的组织第一部分模板l 函数模板l 类模板函数模板l 函数模板可以用来创建一个通用功能的函数，以支持多种不同形参，进一步简化重载函数的函数体设计。l 声明方法：template 函数声明 类模板的作用使用类模板使用户可以为类声明一种模式，使得类中的某些数据成员、某些成员函数的参数、某些成员函数的返回值，能取任意类型（包括基本类型的和用户自定义类型）。类模板的声明l 类模板：template class 类名类成员声明l 如果需要在类模板以外定义其成员函数，则要采用以下的形式： template 类型名 类名: 函数名（参数表） 第二部分群体数据l 线性群体 线性群体的概念 直接访问群体-数组类 顺序访问群体-链表类 栈类 队列类群体的概念群体是指由多个数据元素组成的集合体。群体可以分为两个大类：线性群体和非线性群体。线性群体中的元素按位置排列有序，可以区分为第一个元素、第二个元素等。非线性群体不用位置顺序来标识元素。线性群体的概念线性群体中的元素次序与其位置关系是对应的。在线性群体中，又可按照访问元素的不同方法分为直接访问、顺序访问和索引访问。在本章我们只介绍直接访问和顺序访问。数组l 静态数组是具有固定元素个数的群体，其中的元素可以通过下标直接访问。 缺点：大小在编译时就已经确定，在运行时无法修改。l 动态数组由一系列位置连续的，任意数量相同类型的元素组成。 优点：其元素个数可在程序运行时改变。 l 动态数组类模板：数组类模板的构造函数/ 构造函数template Array:Array(int sz) if (sz = 0) /sz为数组大小（元素个数），若小于0，则输出错误信息 Error(invalidArraySize); size = sz; / 将元素个数赋值给变量size alist = new Tsize; /动态分配size个T类型的元素空间 if (alist = NULL) /如果分配内存不成功，输出错误信息 Error(memoryAllocationError);数组类的拷贝构造函数template Array:Array(const Array& X) int n = X.size; size = n; alist = new Tn; if (alist = NULL) Error(memoryAllocationError); T* srcptr = X.alist; / X.alist是对象X的数组首地址 T* destptr = alist; / alist是本对象中的数组首地址 while (n-) / 逐个复制数组元素 *destptr+ = *srcptr+;链表l 链表是一种动态数据结构，可以用来表示顺序访问的线性群体。l 链表是由系列结点组成的，结点可以在运行时动态生成。l 每一个结点包括数据域和指向链表中下一个结点的指针（即下一个结点的地址）。如果链表每个结点中只有一个指向后继结点的指针，则该链表称为单链表。单链表单链表的结点类模板template class Node private: Node *next; public: T data; Node(const T& item,Node* ptrnext = NULL); void InsertAfter(Node *p); Node *DeleteAfter(void); Node *NextNode(void) const; 链表的基本操作l 生成结点l 插入结点l 查找结点l 删除结点l 遍历链表l 清空链表特殊的线性群体栈栈是只能从一端访问的线性群体，可以访问的这一端称栈顶，另一端称栈底。栈的基本状态l 栈空 栈中没有元素l 栈满 栈中元素个数达到上限 l 一般状态 栈中有元素，但未达到栈满状态 栈的基本操作l 初始化l 入栈l 出栈l 清空栈l 访问栈顶元素l 检测栈的状态（满、空）特殊的线性群体队列队列是只能向一端添加元素，从另一端删除元素的线性群体队列的基本状态l 队空 队列中没有元素l 队满 队列中元素个数达到上限 l 一般状态 队列中有元素，但未达到队满状态 第三部分群体数据的组织l 插入排序l 选择排序l 交换排序l 顺序查找l 折半查找排序（sorting）l 排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。 数据元素：数据的基本单位。在计算机中通常作为一个整体进行考虑。一个数据元素可由若干数据项组成。 关键字：数据元素中某个数据项的值，用它可以标识（识别）一个数据元素。l 在排序过程中需要完成两种基本操作： 比较两个数的大小 调整元素在序列中的位置内部排序与外部排序l 内部排序：待排序的数据元素存放在计算机内存中进行的排序过程。l 外部排序：待排序的数据元素数量很大，以致内存存中一次不能容纳全部数据，在排序过程中尚需对外存进行访问的排序过程。选择排序的基本思想每次从待排序序列中选择一个关键字最小的元素，（当需要按关键字升序排列时），顺序排在已排序序列的最后，直至全部排完。最简单的交换排序方法 起泡排序对具有n个元素的序列按升序进行起泡排序的步骤： 首先将第一个元素与第二个元素进行比较，若为逆序，则将两元素交换。然后比较第二、第三个元素，依次类推，直到第n-1和第n个元素进行了比较和交换。此过程称为第一趟起泡排序。经过第一趟，最大的元素便被交换到第n个位置。 对前n-1个元素进行第二趟起泡排序，将其中最大元素交换到第n-1个位置。 如此继续，直到某一趟排序未发生任何交换时，排序完毕。对n个元素的序列，起泡排序最多需要进行n-1趟。第九章 C+标准模板库主要内容l 泛型程序设计l 与标准模板库有关的概念和术语l C+标准模板库中的容器l 迭代器l 标准C+库中的算法l 函数对象 一 泛型程序设计l 将程序写得尽可能通用 l 将算法从特定的数据结构中抽象出来，成为通用的l C+的模板为泛型程序设计奠定了关键的基础 l STL是泛型程序设计的一个范例 容器(container) 迭代器(iterator) 算法（algorithms） 函数对象（function object）二 容器l 容器类是容纳、包含一组元素或元素集合的对象。l 异类容器类与同类容器类l 顺序容器与关联容器l 七种基本容器： 向量（vector ）、 双端队列（deque ）、 列表（list ）、 集合（set ）、 多重集合（multiset ）、 映射（map ） 和多重映射（multimap ） 容器的接口l 通用容器运算符 =，!=，=，=，=l 方法（函数） 迭代方法l begin()，end()，rbegin()，rend() 访问方法l size()，max_size()，swap()，empty()三 适配器l 适配器是一种接口类 为已有的类提供新的接口。 目的是简化、约束、使之安全、隐藏或者改变被修改类提供的服务集合。l 三种类型的适配器： 容器适配器 l 用来扩展7 种基本容器，它们和顺序容器相结合构成栈、队列和优先队列容器 迭代器适配器 函数对象适配器。 迭代器迭代器是面向对象版本的指针，它们提供了访问容器、序列中每个元素的方法。什么是迭代器l 迭代器是面向对象版本的指针 指针可以指向内存中的一个地址 迭代器可以指向容器中的一个位置l STL的每一个容器类模版中，都定义了一组对应的迭代器类。使用迭代器，算法函数可以访问容器中指定位置的元素，而无需关心元素的具体类型。迭代器的类型l 输入迭代器 可以用来从序列中读取数据l 输出迭代器 允许向序列中写入数据l 前向迭代器 既是输入迭代器又是输出迭代器，并且可以对序列进行单向的遍历l 双向迭代器 与前向迭代器相似，但是在两个方向上都可以对数据遍历l 随机访问迭代器 也是双向迭代器，但能够在序列中的任意两个位置之间进行跳转。四 算法l C+标准模板库中包括70多个算法 其中包括查找算法，排序算法，消除算法，记数算法，比较算法，变换算法，置换算法和容器管理等等。l 这些算法的一个最重要的特性就是它们的统一性，并且可以广泛用于不同的对象和内置的数据类型。标准C+库中的算法l 算法本身是一种函数模板l 不可变序列算法（Non-mutating algorithms） 不直接修改所操作的容器内容的算法l 可变序列算法（Mutating alg