[TOC]
枚举类型
enum 枚举类型名 {元素}
auto类型
auto:编译器通过初始值自动推断变量的类型
值传递与引用传递
引用（&）是标识符的别名
定义一个引用时，必须同时对它进行初始化，使它指向一个已经存在的对象，一旦一个引用被初始化，就不能改为指向其他对象
值传递做参数为单向传递，引用传递做参数为双向传递
内联函数
l 声明时使用关键字 inline。
l 编译时在调用处用函数体进行替换，节省了参数传递、控制转移等开销。
l 注意：
n 内联函数体内不能有循环语句和switch语句；
n 内联函数的定义必须出现在内联函数第一次被调用之前；
n 对内联函数不能进行异常接口声明。
函数重载
函数名相同，形参不同：个数不同或类型不同
面向程序设计的基本特点
- 抽象：对同一类对象的共同属性和行为进行概括，形成类
- 封装：将抽象出的数据，代码封装在一起，形成类
- 继承：在已有类的基础上，进行扩展形成新的类
- 多态：同一名称，不同的功能实现方式
类成员的访问控制
- 公有类型成员：public，任何外部函数都可以访问公有类型数据和函数
- 私有类型成员：private，只允许本类中的函数访问，而类外的任何函数都不能访问
- 保护类型成员：与private类似，其差别表现在继承与派生时对派生类的影响不同
默认构造函数
每个类中都有一个默认的构造函数，没有参数，也没有返回值
委托构造函数
使用类的其他构造函数来执行初始化，减少重复性代码
复制构造函数
复制构造函数是一种特殊的构造函数，其形参为本类的对象引用。作用是用一个已经存在的对象来初始化新的对象。
类名（形参）；//构造函数
类名（const 类名 &对象名）； //复制构造函数
const表明为常引用，不会改变引用对象的数据
默认复制构造函数实现的是浅复制，对应的数据一一复制；当类中有指针数据时，应该自定义复制构造函数，实现深复制。
复制构造函数被调用的三种情况：
- 定义一个对象时，以本类的另一个对象作为初始值，发生复制构造
- 函数的形参为类的对象，调用函数会发生复制构造
- 函数的返回值是类的对象，函数执行完成返回主调函数时，会发生复制构造。
析构函数
析构函数完成对象被删除前的一些清理工作。
在对象的生存期结束的时候系统会自动调用它，然后在释放此对象所属的空间
程序未声明析构函数，编译器将会自动产生一个默认的析构函数，其函数体为空
～类名（）；
类的组合
类中的成员是另一个类的对象。
类组合的构造函数设计：
原则：不仅要负责本类中的基本类型成员数据初始化，也要对对象成员初始化
构造组合类对象时的初始化次序
- 首先对构造函数初始化列表中列出的成员（包括基本类型成员和对象成员）进行初始化，初始化次序是成员在类体中定义的次序。
- 成员对象构造函数调用顺序：按对象成员的声明顺序，先声明者先构造。
- 初始化列表中未出现的成员对象，调用用默认构造函数（即无形参的）初始化
- 处理完初始化列表之后，再执行构造函数的函数体。
前向引用声明
如果需要在某个类的声明之前，引用该类，则应进行前向引用声明。
class B；
class A {
}
class B {
}
UML简介
三个基本部分：事物，关系，图
结构体
结构体是一种特殊的类
与类唯一的区别：类的默认访问权限是private，结构体的默认访问权限为public
结构体在C++中并不常用，主要用来与C语言保存兼容
struct 结构体名称 { |
联合体
特点
- 成员公用同一组内存单元
- 任何两个成员不会同时有效
union 联合体名称 { |
枚举类
定义：
enum class 枚举类型名：底层类型 {枚举值列表} |
优势：
- 强作用域：其作用域限制在枚举类中
- 转换限制：枚举类对象不可以与整型隐式的互相转换
- 可以指定底层类型
标识符的作用域与可见性
- 函数原型作用域
- 函数原型中的形参
- 局部作用域
- 函数的形参、在块中声明的标识符
- 类作用域
- 类的成员具有类作用域
- 文件作用域
- 命名空间作用域
程序运行到某一点，能够引用到的标识符，就是该处可见的标识符
对象的生存期
静态生存期
- 生存期与程序的运行期相同
- 在文件作用域声明的对象具有静态生存期
- 在函数内部声明静态生存期对象，要加关键字static
动态生存期
- 在作用域中声明的，没有static修饰的对象就是动态生存期的对象
类的静态成员
静态数据成员
用关键字static声明，为该类的所有对象共享，具有静态生存期，必须在类外定义和初始化，用类名::数据成员来指定
静态函数成员
主要用于处理静态数据成员，可以直接调用静态函数成员，用类名::函数名来调用
类的友元
友元是C++提供的一种破坏数据封装和数据隐藏的机制。为了确保数据的完整性，及数据封装与隐藏的原则，建议尽量不使用或少用友元
- 友元函数
- 友元函数是在类声明中由关键字friend修饰说明的非成员函数，在它的函数体中能够通过对象名访问 private 和 protected成员
- 作用：增加灵活性，使程序员可以在封装和快速性方面做合理选择。
- 访问对象中的成员必须通过对象名。
- 友元类
- 若一个类为另一个类的友元，则此类的所有成员都能访问对方类的私有成员。
- 声明语法：将友元类名在另一个类中使用friend修饰说明。
类的友元关系是单向的
如果声明B类是A类的友元，B类的成员函数就可以访问A类的私有和保护数据，但A类的成员函数却不能访问B类的私有、保护数据。
共享数据的保护
共享数据的保护
- 对于既需要共享、又需要防止改变的数据应该声明为常类型（用const进行修饰）。
- 对于不改变对象状态的成员函数应该声明为常函数。
常类型
- 常对象：必须进行初始化,不能被更新。
- const 类名 对象名
常成员
- 用const进行修饰的类成员：常数据成员和常函数成员
- 常成员函数
- 用const关键字修饰的函数
- 常成员函数不更新对象的数据成员
- 语法格式：类型说明符 函数名 （参数表）const；
- const关键字可以用于对重载函数的区别
- 常对象只能调用常成员函数
- 常数据成员
- 使用const说明的数据成员
- 常成员函数
常引用：被引用的对象不能被更新。
- 如果声明引用时用const修饰，被声明的引用就是常引用
- const 类型说明符 &引用名
常数组：数组元素不能被更新(详见第6章)。
- 类型说明符 const 数组名[大小]…*
常指针：指向常量的指针(详见第6章)。
多文件结构和预编译命令
c++程序的一般组织结构
- 一个工程可以划分为多个源文件
- 类声明文件（.h文件）
- 类实现文件（.cpp文件）
- 类的使用文件（main()所在的.cpp文件）
- 利用工程来组合各个文件
标准C++类库是一个极为灵活并可扩展的可重用软件模块的集合。标准C++类与组件在逻辑上分为6种类型：
- 输入/输出类
- 容器类与抽象数据类型
- 存储管理类
- 算法
- 错误处理
- 运行环境支持
数组的定义与使用
数组是具有一定顺序关系的若干相同类型变量的集合体，组成数组的变量称为该数组的元素
定义：类型说明符 数组名[常量表达式]
使用：必须先定义，后使用，只能逐个引用数组元素，而不能一次引用整个数组
数组的存储与初始化
数组元素在内存中顺序存放，他们的地址是连续的。元素之间物理地址相邻，逻辑次序相邻
数组名字是数组首元素的内存地址
一维数组的初始化
在定义数组时给出数组元素的初始值。
- 列出全部元素的初始值
- 例如：static int a[10]={0,1,2,3,4,5,6,7,8,9};
- 可以只给一部分元素赋初值
- 例如：static int a[10]={0,1,2,3,4};
- 在对全部数组元素赋初值时，可以不指定数组长度
- 例如：static int a[]={0,1,2,3,4,5,6,7,8,9}
二维数组的初始化
1.将所有初值写在一个{}内，按顺序初始化 |
注意：
- 如果不作任何初始化，内部auto型数组中会存在垃圾数据，static数组中的数据默认初始化为0；
- 如果只对部分元素初始化，剩下的未显式初始化的元素，将自动被初始化为零；
数组作为函数参数
- 数组元素作实参，与单个变量一样
- 数组名作参数，形、实参数都是数组名，类型要一样，传送的是数组首地址，对形参的改变会直接影响到实参数组
对象数组
- 定义对象数组
- 类名 数组名[元素个数]
- 访问对象数组元素
- 通过下标访问
- 数组名[下标].成员名
- 对象数组初始化
- 数组中每一个元素对象被创建时，系统都会调用类构造函数初始化该对象
- 通过初始化列表复制
- 如果没有为数组元素指定显式初始值，数组元素使用默认值初始化
- 数组元素所属类的构造函数
- 元素所属的类不声明构造函数，则采用默认构造函数
- 各元素对象的初值要求为相同的值时，可以声明具有默认形参值的构造函数。
- 各元素对象的初值要求为不同的值时，需要声明带形参的构造函数。
- 当数组中每一个对象被删除时，系统都要调用一次析构函数。
基于范围的for循坏
int array[3] = {1,2,3}; |
指针的概念、定义和指针运算
内存空间的访问方式
- 通过变量名访问
- 通过地址访问
指针的概念
指针：内存地址，用于间接访问内存单元
指针变量：用于存放地址的变量
int i; int* ptr = &i; <!--5-->
指针类型的常量
若声明指针常量，则指针本身的值不能被改变
Int * const p2 = &a;
int a; int * const p2 = &a; p2 = &b; //错误，p2是指针常量，值不能改变 <!--6-->
指针类型的关系运算
- 指向相同类型数据的指针之间可以进行各种关系运算。
- 指向不同数据类型的指针，以及指针与一般整数变量之间的关系运算是无意义的。
- 指针可以和零之间进行等于或不等于的关系运算。
- 例如：p==0或p!=0
用指针访问数组元素
数组是一组连续存储的同类型数据，可以通过指针的算术运算，使指针依次指向数组的各个元素，进而可以遍历数组。
赋值与定义
int a[10], *pa;
pa = &a[0];\\ pa = a;等效形式
a[i] *(pa+i) *(a+i) pa[i]
注意：不能写a++，因为a是数组首地址、是常量
指针数组
数组的元素是指针型，指针数组的元素可以用地址初始化
int line1[] = { 1, 0, 0 }; //矩阵的第一行 |
指针数组与二维数组的区别
以指针作为函数参数
为什么需要用指针作参数？
- 需要数据双向传递（引用也可以达到此效果）
- 需要传递一组数据，只传首地址运行效率比较高
- 实参是数组名时，形参可以是指针
指针类型的函数
若函数的返回值是指针，该函数就是指针类型的函数
注意
不要将非静态局部地址用作函数的返回值
错误例子：在子函数中定义局部变量将其地址返回给主函数，就是非法地址
int main(){
int* function();
int* ptr= function();
*prt=5; //危险的访问！
return 0;
}
int* function(){
int local=0; //非静态局部变量作用域和寿命都仅限于本函数体内
return &local;
}//函数运行结束时，变量local被释
返回的指针要确保在主调函数中是有效、合法的地址
主函数中定义的数组，在子函数中对该数组元素进行某种操作后，返回其中一个元素的地址，属于合法地址
using namespace std;
int main(){
int array[10]; //主函数中定义的数组
int* search(int* a, int num);
for(int i=0; i<10; i++)
cin>>array[i];
int* zeroptr= search(array, 10); //将主函数中数组的首地址传给子函数
return 0;
}
int* search(int* a, int num){ //指针a指向主函数中定义的数组
for(int i=0; i<num; i++)
if(a[i]==0)
return &a[i]; //返回的地址指向的元素是在主函数中定义的
}//函数运行结束时，a[i]的地址仍有
- 在子函数中通过动态内存分配new操作取得的内存地址返回给主函数是合法有效的，但是内存分配和释放不在同一级别，要注意不能忘记释放，避免内存泄漏
int main(){
int* newintvar();
int* intptr= newintvar();
*intptr=5; //访问的是合法有效的地址
delete intptr; //如果忘记在这里释放，会造成内存泄漏
return 0;
}
int* newintvar (){
int* p=new int();
return p; //返回的地址指向的是动态分配的空间
}//函数运行结束时，p中的地址仍有效
指向函数的指针
定义：返回类型 (*函数名)(参数表) = &func；
|
对象指针
定义
- 类名 *对象指针名
通过指针访问对象成员
- 对象指针名->对象成员
Point a(5,10);
Point *p = &a;
p->getX();//(*p).getX()this指针
- 指向当前对象自己
- 隐含于类的每一个非静态成员函数中
- 指向成员函数所操作的对象
- 当通过一个对象调用成员函数时，系统先将该对象的地址赋给this指针，然后调用成员函数，成员函数对对象的数据进行操作时，就隐含使用了this指针
动态分配与释放内存
- 动态申请内存操作符new
- new 类型名（初始化参数列表）
- 功能：在程序执行期间，申请用于存放T类型对象的内存空间，并依初值列表来赋初值
- 结果值：成功：T类型的指针，指向新分配的内存；失败：抛出异常
- 释放内存操作符delete
- delete 指针p
- 功能：释放指针p所指向的内存。p必须是new操作的返回值
申请和释放动态数组
分配：new 类型名T[数组长度]
- 数组长度可以是任何表达式，在运行时计算
释放：delete[] 数组名p
- 释放指针p所指向的数组
- p必须是用new分配得到的数组首地址
动态创建多维数组
char (*fp)[3] = new char[2][3];
int (*cp)[9][8] = new int[7][8][9]//cp是指向一个二维数组的指针将动态数组封装成类
- 更加简洁，便于管理
- 可以在访问数组元素前检查下标是否越界
为什么element函数返回对象的引用？
返回“引用”可以用来操作封装数组对象内部的数组元素。如果返回“值”则只是返回了一个“副本”，通过“副本”是无法操作原来数组中的元素的
Point& element(int index) {
assert(index >= 0 && index < size);
return points[index];
}
智能指针
- 显示管理内存有优势，但容易出错
- C++11提供智能指针的数据类型，对垃圾回收技术提供了一些支持，实现一定程度的内存管理
- unique_ptr ：不允许多个指针共享资源，可以用标准库中的move函数转移指针
- shared_ptr ：多个指针共享资源
- weak_ptr ：可复制shared_ptr，但其构造或者释放对资源不产生影响
vector对象
为什么需要vector？
- 封装任何类型的动态数组，自动创建和删除
- 数组下标越界检查
定义
vector<元素类型> 数组对象名(数组长度)
vector<int> arr(5)
使用
- 对数组元素的引用
- 对象名[下标]
- vector数组对象名不表示数组首地址
- 获得数组长度
- 对象名.size()
- 对数组元素的引用
基于范围的for循环配合auto举例
using namespace std;
int main() {
vector<int> v = {1, 2, 3};
for(auto i = v.begin(); i != v.end(); ++i) {
cout << *i << endl;
}
for(auto e : v) {
cout << e << endl;
}
return 0;
}
浅层复制与深层复制
浅层复制
实现对象间数据元素的一一对应复制
深层复制
当被复制的对象数据成员是指针类型时，不是复制该指针成员本身，而是将指针所指对象进行复制
ArrayOfPoints::ArrayOfPoints(const ArrayOfPoints& v) {
size = v.size;
points = new Point[size];
for (int i = 0; i < size; i++)
points[i] = v.points[i];
}
移动构造
- C++11标准中提供了一种新的构造方法——移动构造
- C++11之前，如果要将源对象的状态转移到目标对象只能通过复制。在某些情况下，我们没必要复制对象，只需要移动它们
- 移动构造函数
- class_name(class_name &&)
- 当有被利用的临时对象时触发
- 使用深层复制构造函数
- 返回时构造临时对象，动态分配将临时对象返回到主调函数，然后删除临时对象
- 使用移动构造函数
- 将还要返回的局部对象转移到主调函数，省去构造和删除临时对象的过程
|
C风格字符串
字符串常量
- 例：”program”
- 各字符连续、顺序存放，每个字符占一个字节，以‘\0’结尾，相当于一个隐含创建的字符常量数组
- “program”出现在表达式中，表示这一char数组的首地址
- 首地址可以赋给char常量指针：const char *STRING1 = “program”;
用字符数组存储字符串
char str[8] = { 'p', 'r', 'o', 'g', 'r', 'a', 'm', '\0' }; char str[8] = "program"; char str[] = "program"; <!--21-->
多继承
语法
class 派生类名：继承方式1 基类名1，继承方式2 基类名2，…
{
成员声明；
}
class Derived: public Base1, private Base2
{
public:
Derived ();
~Derived ();
};
派生类的构造过程
- 吸收基类成员
- 默认情况下派生类包含了全部基类中除了构造和析构函数之外的所有成员
- C++11规定可以用using语句继承基类构造函数
- 改造基类成员
- 如果派生类声明了一个和基类成员同名的新成员，派生类的新成员就隐藏或覆盖了外层同名成员
- 添加新的成员
- 派生类增加新成员使派生类在功能上有所发展
继承方式简介
不同继承方式的影响主要体现在
- 派生类成员对基类成员的访问权限
- 通过派生类对象对基类成员的访问权限
公有继承(public)
继承的访问控制
- 基类的public和protected成员：访问属性在派生类中保持不变；
- 基类的private成员：不可直接访问
访问权限
- 派生类中的成员函数：可以直接访问基类中的public和protected成员，但不能直接访问基类的private成员；
- 通过派生类的对象：只能访问public成员
class Point {
//基类Point类的定义
public:
//公有函数成员
void initPoint(float x = 0, float y = 0){
this->x = x;
this->y = y;
}
void move(float offX, float offY){
x += offX;
y += offY;
}
float getX() const { return x; }
float getY() const { return y; }
private:
//私有数据成员
float x, y;
};
class Rectangle: public Point {
//派生类定义部分
public:
//新增公有函数成员
void initRectangle(float x, float y, float w, float h) {
initPoint(x, y); //调用基类公有成员函数
this->w = w;
this->h = h;
}
float getH() const { return h; }
float getW() const { return w; }
private:
//新增私有数据成员
float w, h;
};
using namespace std;
int main() {
Rectangle rect; //定义Rectangle类的对象
//设置矩形的数据
rect.initRectangle(2, 3, 20, 10);
rect.move(3,2); //移动矩形位置
cout << "The data of rect(x,y,w,h): " << endl;
//输出矩形的特征参数
cout << rect.getX() <<", "
<< rect.getY() << ", "
<< rect.getW() << ", "
<< rect.getH() << endl;
return 0;
}
私有继承(private)
继承的访问控制
- 基类的public和proted成员：都以private身份出现在派生类中；
- 基类的private成员：不可直接访问；
访问权限
- 派生类中的成员函数：可以直接访问基类中的public和protected成员，但不能直接访问基类的private成员；
- 通过派生类的对象：不能直接访问从基类继承的任何成员；
class Point { //基类Point类的定义
public: //公有函数成员
void initPoint(float x = 0, float y = 0)
{ this->x = x; this->y = y;}
void move(float offX, float offY)
{ x += offX; y += offY; }
float getX() const { return x; }
float getY() const { return y; }
private: //私有数据成员
float x, y;
};
class Rectangle: private Point { //派生类定义部分
public: //新增公有函数成员
void initRectangle(float x, float y, float w, float h) {
initPoint(x, y); //调用基类公有成员函数
this->w = w;
this->h = h;
}
void move(float offX, float offY) { Point::move(offX, offY); }
float getX() const { return Point::getX(); }
float getY() const { return Point::getY(); }
float getH() const { return h; }
float getW() const { return w; }
private: //新增私有数据成员
float w, h;
};
using namespace std;
int main() {
Rectangle rect; //定义Rectangle类的对象
rect.initRectangle(2, 3, 20, 10); //设置矩形的数据
rect.move(3,2); //移动矩形位置
cout << "The data of rect(x,y,w,h): " << endl;
cout << rect.getX() <<", " //输出矩形的特征参数
<< rect.getY() << ", "
<< rect.getW() << ", "
<< rect.getH() << endl;
return 0;
}
保护继承(protected)
继承的访问控制
- 基类的public和protected成员：都以protected身份出现在派生类中；
- 基类的private成员：不可直接访问
访问权限
- 派生类中的成员函数：可以直接访问基类中的public和protected成员，但不能直接访问基类的private成员；
- 通过派生类的对象：不能直接访问从基类继承的任何成员；
protected成员的特点与作用
- 对建立其所在类对象的模块来说，它与private成员性质相同
- 对于其派生类来说，它与public成员的性质相同
- 既实现了数据隐藏，又方便继承，实现代码重用
- 如果派生类有多个基类，也就是多继承时，可以用不同的方式继承每个基类
class A {
protected:
int x;
};
int main() {
A a;
a.x = 5;//错误
}
class A {
protected:
int x;
};
class B: public A{
public:
void function();
};
void B:function() {
x = 5; //正确
}
基类与派生类类型转换
类型转换
公有派生对象可以被当作基类的对象使用，反之则不可
- 派生类的对象可以隐含转换为基类对象
- 派生类的对象可以初始化基类的使用
- 派生类的指针可以隐含转换为基类的指针
通过基类对象名、指针只能使用从基类继承的成员
using namespace std;
class Base1 {
public:
void display() const {
cout << "Base1:display()" << endl;
}
};
class Base2: public Base1 {
public:
void display() const {
cout << "Base2:display()" << endl;
}
};
class Derived: public Base2 {
public:
void display() const {
cout << "Derived:display()" << endl;
}
};
void fun(Base1 *ptr) {
ptr->display();
}
int main() {
Base1 base1;
Base2 base2;
Derived derived;
fun(&base1);
fun(&base2);
fun(&derived);
return 0;
}
派生类的析构函数
默认情况
- 基类的构造函数不被继承
- 派生类需要定义自己的构造函数
C++11规定
- 可用using语句继承基类构造函数
- 但是只能初始化从基类继承的成员
- 派生类新增成员可以通过类内初始值进行初始化
- 语法形式
- using B::B;
建议
- 如果派生类有自己新增的成员，且需要通过构造函数初始化，则派生类要自定义构造函数
若不继承基类的构造函数
- 派生类新增成员：派生类定义构造函数初始化
- 继承来的成员：自动调用基类构造函数进行初始化
- 派生类的构造函数需要给基类的构造函数传递参数
单继承
派生类只有一个直接基类的情况，是单继承。单继承时，派生类的构造函数只需要给一个直接基类构造函数传递参数
单继承构造函数的定义语法
派生类名::派生类名(基类所需的形参，本类成员所需的形参):
基类名(参数表), 本类成员初始化列表
{
//其他初始化；
}；
using namespace std;
class B {
public:
B();
B(int i);
~B();
void print() const;
private:
int b;
};
B::B() {
b=0;
cout << "B's default constructor called." << endl;
}
B::B(int i) {
b=i;
cout << "B's constructor called." << endl;
}
B::~B() {
cout << "B's destructor called." << endl;
}
void B::print() const {
cout << b << endl;
}
class C: public B {
public:
C();
C(int i, int j);
~C();
void print() const;
private:
int c;
};
C::C() {
c = 0;
cout << "C's default constructor called." << endl;
}
C::C(int i,int j): B(i), c(j){
cout << "C's constructor called." << endl;
}
C::~C() {
cout << "C's destructor called." << endl;
}
void C::print() const {
B::print();
cout << c << endl;
}
int main() {
C obj(5, 6);
obj.print();
return 0;
}
多继承
多继承时，有多个直接基类，如果不继承基类的构造函数，派生类构造函数需要给所有的基类构造函数传递参数
多继承构造函数的定义语法
派生类名::派生类名(参数表) :
基类名1(基类1初始化参数表),
基类名2(基类2初始化参数表),
...
基类名n(基类n初始化参数表),
本类成员初始化列表
{
//其他初始化；
}；
派生类与基类的构造函数
- 当基类有默认构造函数时
- 派生类构造函数可以不向基类构造函数传递参数。
- 构造派生类的对象时，基类的默认构造函数将被调用。
- 如需执行基类中带参数的构造函数
- 派生类构造函数应为基类构造函数提供参数
- 当基类有默认构造函数时
多继承且有对象成员时派生的构造函数定义语法
派生类名::派生类名(形参表):
基类名1(参数), 基类名2(参数), ..., 基类名n(参数),
本类成员（含对象成员）初始化列表
{
//其他初始化
}；构造函数的执行顺序
调用基类构造函数。
- 顺序按照它们被继承时声明的顺序（从左向右）。
对初始化列表中的成员进行初始化。
- 顺序按照它们在类中定义的顺序。
- 对象成员初始化时自动调用其所属类的构造函数。由初始化列表提供参数。
执行派生类的构造函数体中的内容。
using namespace std;
class Base1 {
public:
Base1() {
cout << "Base1 default constructor calling" << endl;
}
Base1(int i) {
cout << "Base1 constructor calling" << endl;
}
};
class Base2 {
public:
Base2() {
cout << "Base2 default constructor calling" << endl;
}
Base2(int i) {
cout << "Base2 constructor calling" << endl;
}
};
class Base3 {
public:
Base3() {
cout << "Base3 default constructor calling" << endl;
}
};
class Derived: public Base2, public Base1, public Base3 {
public:
Derived(int a, int b, int c, int d):Base1(a),member2(d),member1(c),Base2(d) {
cout << "Derived default constructor calling" << endl;
}
private:
Base1 member1;
Base2 member2;
Base3 member3;
};
int main() {
Derived derived(1,2,3,4);
return 0;
}
派生类复制构造函数
- 派生类未定义复制构造函数的情况
- 编译器会在需要时生成一个隐含的复制构造函数
- 先调用基类的复制构造函数
- 再为派生类新增的成员执行复制
- 派生类定义类复制构造函数的情况
- 一般都要为基类的复制构造函数传递参数
- 复制构造函数只能接受一个参数，既用来初始化派生类定义的成员，也将被传递给基类的复制构造函数
- 基类的复制构造函数形参类型是基类对象的引用，实参可以是派生类对象的引用
- 例如：C::C(const C &c1):B(c1){…}
派生类的析构函数
- 析构函数不被继承，派生类如果需要，要自行声明析构函数
- 声明方法与无继承关系时类的析构函数相同
- 不需要显示地调用基类的析构函数，系统会自动隐式调用
- 先执行派生类析构函数的函数体，在调用基类的析构函数
- 析构函数的调用顺序与构造函数的调用顺序相反
访问从基类继承的成员
- 作用域限定
- 当派生类与基类中有相同成员时：
- 若为特别限定，则通过派生类对象使用的是派生类中的同名成员
- 如要通过派生类对象访问基类中被隐藏的同名成员，应使用基类名和作用域操作符(::)来限定
- 当派生类与基类中有相同成员时：
- 二义性问题
- 如果从不同基类继承了同名成员，但是在派生类中没用定义同名成员，“派生类对象名或引用名.成员名”或“派生类指针->成员名”访问成员存在二义性
- 解决方式：用类名限定
虚基类
需要解决的问题
- 当派生类从多个基类派生，而这些基类有共同基类，则在访问此共同基类中的成员时，将产生冗余，并有可能因冗余带来不一致性
虚基类声明
- 以virtual说明基类继承方式
- 例：class B1:virtual public B
作用
- 主要用来解决多继承时可能发生的对同一基类继承多次而产生的二义性问题
- 为最远的派生类提供唯一的基类成员，而不重复产生多次复制
注意：
- 在第一级继承时就要将共同基类设计为虚基类。
虚基类及其派生类构造函数
- 建立对象时所指定的类称为最远派生类。
- 虚基类的成员是由最远派生类的构造函数通过调用虚基类的构造函数进行初始化的。
- 在整个继承结构中，直接或间接继承虚基类的所有派生类，都必须在构造函数的成员初始化表中为虚基类的构造函数列出参数。如果未列出，则表示调用该虚基类的默认构造函数。
- 在建立对象时，只有最远派生类的构造函数调用虚基类的构造函数，其他类对虚基类构造函数的调用被忽略。
运算符重载的规则
- 运算符重载是对已有的运算符赋予多重含义，使同一个运算符作用于不同类型的数据时导致不同的行为
- C++几乎可以重载全部的运算符，而且只能够重载已有的
- 不能重载的运算符：”.” “.*“ “::” “?.”
- 重载之后运算符的优先级和结合性都不会改变
- 运算符重载是针对新类型数据的实际需要，对原有运算符进行适当的改造
双目运算符重载为成员函数
重载为类成员的运算符函数定义形式
函数类型 operator 运算符 (形参) {
}双目运算符重载规则
- 如果要重载B为类成员函数，使之能够实现表达式oprd1 B oprd2，其中oprd1为A类对象，则B应为A类的成员函数，形参类型应该是oprd2所属的类型
- 经重载后，表达式oprd1 B oprd2 相当于 oprd1.operator B(oprd2)
using namespace std; class Complex { public: Complex(double r = 0.0, double i = 0.0):real(r),imag(i){} //运算符+重载成员函数 Complex operator +(const Complex &c2) const; //运算符-重载成员函数 Complex operator -(const Complex &c2) const; void display() const; private: double real;//复数实部 double imag;//复数虚部 }; Complex Complex::operator+(const Complex &c2) const { return Complex(real+c2.real,imag+c2.imag); } Complex Complex::operator-(const Complex &c2) const { return Complex(real-c2.real,imag-c2.imag); } void Complex::display() const { cout << "(" << real << ", " << imag << ")" << endl; } int main() { Complex c1(5,4), c2(2,10), c3; cout << "c1 = ";c1.display(); cout << "c2 = ";c2.display(); c3 = c1 - c2; cout << "c3 = c1 - c2 = ";c3.display(); c3 = c1 + c2; cout << "c3 = c1 + c2 = ";c3.display(); return 0; } <!--33-->
运算符重载为非成员函数
规则
函数的形参代表依自左至右次序排列的各操作数。
重载为非成员函数时
参数个数=原操作数个数（后置++、–除外）
至少应该有一个自定义类型的参数。
后置单目运算符 ++和–的重载函数，形参列表中要增加一个int，但不必写形参名。
如果在运算符的重载函数中需要操作某类对象的私有成员，可以将此函数声明为该类的友元。
双目运算符 B重载后，
- 表达式oprd1 B oprd2
- 等同于operator B(oprd1,oprd2 )
前置单目运算符 B重载后，
- 表达式 B oprd
- 等同于operator B(oprd )
后置单目运算符 ++和–重载后，
- 表达式 oprd B
- 等同于operator B(oprd,0 )
using namespace std;
class Complex {
public:
Complex(double r = 0.0, double i = 0.0):real(r),imag(i){}
friend Complex operator+(const Complex &c1, const Complex &c2);
friend Complex operator-(const Complex &c1, const Complex &c2);
friend ostream & operator<<(ostream &out, const Complex &c);
private:
double real;
double imag;
};
Complex operator+(const Complex &c1, const Complex &c2) {
return Complex(c1.real+c2.real,c1.imag+c2.imag);
}
Complex operator-(const Complex &c1, const Complex &c2) {
return Complex(c1.real-c2.real,c1.imag-c2.imag);
}
ostream & operator<<(ostream &out, const Complex &c) {
out << "(" << c.real << ", " << c.imag << ")";
return out;
}
int main() {
Complex c1(5,4), c2(2,10), c3;
cout << "c1 = " << c1 << endl;
cout << "c2 = " << c2 << endl;
c3 = c1 - c2;
cout << "c3 = c1 - c2 = " << c3 << endl;
c3 = c1 + c2;
cout << "c3 = c1 + c2 = " << c3 << endl;
return 0;
}
虚函数
初识虚函数
- 用virtual关键字说明的函数
- 虚函数是实现运行时多态性基础
- C++中的虚函数是动态绑定的函数
- 虚函数必须是非静态的成员函数，虚函数经过派生之后，就可以实现运行过程中的多态。
- 一般成员函数可以是虚函数
- 构造函数不能是虚函数
- 析构函数可以是虚函数
一般虚函数成员
虚函数的声明
virtual 函数类型 函数名（形参表）;
虚函数声明只能出现在类定义中的函数原型声明中，而不能在成员函数实现的时候。
在派生类中可以对基类中的成员函数进行覆盖。
虚函数一般不声明为内联函数，因为对虚函数的调用需要动态绑定，而对内联函数的处理是静态的
virtual关键字
- 派生类可以不显式地用virtual声明虚函数，这时系统就会用以下规则来判断派生类的一个函数成员是不是虚函数：
- 该函数是否与基类的虚函数有相同的名称、参数个数及对应参数类型；
- 该函数是否与基类的虚函数有相同的返回值或者满足类型兼容规则的指针、引用型的返回值；
- 如果从名称、参数及返回值三个方面检查之后，派生类的函数满足上述条件，就会自动确定为虚函数。这时，派生类的虚函数便覆盖了基类的虚函数。
- 派生类中的虚函数还会隐藏基类中同名函数的所有其它重载形式。
- 一般习惯于在派生类的函数中也使用virtual关键字，以增加程序的可读性。
- 派生类可以不显式地用virtual声明虚函数，这时系统就会用以下规则来判断派生类的一个函数成员是不是虚函数：
|
虚析构函数
为什么需要虚析构函数？
可能通过基类指针删除派生类对象。如果你打算允许其他人通过基类指针调用对象的析构函数，就需要让基类的析构函数成为虚函数，否则执行delete的结果是不确定的
using namespace std;
class Base {
public:
virtual ~Base();
};
Base::~Base() {
cout << "Base destructor" << endl;
}
class Derived: public Base {
public:
Derived();
virtual ~Derived();
private:
int *p;
};
Derived::Derived() {
p = new int(0);
}
Derived::~Derived() {
cout << "Derived destructor" << endl;
delete p;
}
void fun(Base *b) {
delete b;
}
int main() {
Base *b = new Derived();
fun(b);
return 0;
}
虚表与动态绑定
虚表
- 每个多态类有一个虚表(virtual table)
- 虚表中有当前类的各个虚函数的入口地址
- 每个对象有一个指向当前类的虚表的指针(虚指针vptr)
动态绑定的实现
构造函数中为对象的虚指针赋值
通过多态类型的指针或引用调用成员函数时，通过虚指针找到虚表，进而找到所调用的虚函数的入口地址
通过该入口地址调用虚函数
抽象类
纯虚函数
抽象类
带有纯虚函数的类称为抽象类
class <类名> { virtual <类型><函数名>(<参数表>)=0; … }; <!--38-->
函数模板
创建一个通用功能的 函数，支持多种不同形参，简化重载函数的函数题设计
template<typename T>
T abs(T x){
return x < 0 ? -x : x;
}函数模板定义语法
语法形式：
template <模板参数表>
函数定义
- 模板参数表的内容
- 类型参数：class（或typename） 标识符
- 常量参数：类型说明符 标识符
- 模板参数：template <参数表> class标识符
- 模板参数表的内容
注意
- 一个函数模板并非自动可以处理所有类型的数据
- 只有能够进行函数模板中运算的类型，可以作为类型实参
- 自定义的类，需要重载模板中的运算符，才能作为类型实参
using namespace std;
template <class T>//定义函数模版
void outputArray(const T *array, int count) {
for(int i = 0; i < count; i++) {
cout << array[i] << " ";//如果数组元素是类对象，需要重载<<运算符
}
cout << endl;
}
int main() {
const int A_COUNT = 8, B_COUNT = 8, C_COUNT = 20;
int a [A_COUNT] = { 1, 2, 3, 4, 5, 6, 7, 8 };
double b[B_COUNT] = { 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8 };
char c[C_COUNT] = "Welcome!";
cout << "a array contains:" << endl;
outputArray(a, A_COUNT);
cout << "b array contains:" << endl;
outputArray(b, B_COUNT);
cout << "c array contains:" << endl;
outputArray(c, C_COUNT);
return 0;
}
类模板
类模板的作用
- 使用类模板使用户可以为类声明一种模式，使得类中的某些数据成员、某些成员函数的参数、某些成员函数的返回值，能取任意类型（包括基本类型的和用户自定义类型）。
类模板的声明
- 类模板 template <模板参数表> class 类名 {类成员声明};
- 如果需要在类模板以外定义其成员函数，则要采用以下的形式： template <模板参数表> 类型名 类名<模板参数标识符列表>::函数名（参数表）
using namespace std;
struct Student {
int id;
float gpa;
};
template <class T>
class Store{
private:
T item;
bool haveValue;
public:
Store();
T& getElem();
void putElem(const T &x);
};
template <class T>
Store<T>::Store():haveValue(false) {}
template <class T>
T& Store<T>::getElem() {
if(!haveValue) {
cout << "No item present!" << endl;
exit(1);
}
return item;
}
template <class T>
void Store<T>::putElem(const T &x) {
haveValue = true;
item = x;
}
int main() {
Store<int> s1, s2;
s1.putElem(3);
s2.putElem(-7);
cout << s1.getElem() << " " << s2.getElem() << endl;
Student g = { 1000, 23 };
Store<Student> s3;
s3.putElem(g);
cout << "The student id is " << s3.getElem().id << endl;
return 0;
}
线性群体
- 群体是指由多个数据元素组成的集合体。群体可以分为两个大类：线性群体和非线性群体。
- 线性群体中的元素按位置排列有序，可以区分为第一个元素、第二个元素等。
- 非线性群体不用位置顺序来标识元素。
- 线性群体中的元素次序与其逻辑位置关系是对应的。在线性群体中，又可按照访问元素的不同方法分为直接访问、顺序访问和索引访问。
数组类模板
静态数组是具有固定元素个数的群体，其中的元素可以通过下标直接访问
- 缺点：大小在编译时就已经确定，在运行时无法修改
动态数组由一系列位置连续的，任意数量相同类型的元素组成
- 优点：其元素个数可在程序运行时改变
vector就是用类模板实现的动态数组
为什么有的函数返回引用
- 如果一个函数的返回值是一个对象的值，就是右值，不能成为左值
- 如果返回值为引用。由于引用是对象的别名，通过引用可以改变对象的值，因此是左值
template <class T> //数组类模板定义
class Array {
private:
T* list; //用于存放动态分配的数组内存首地址
int size; //数组大小（元素个数）
public:
Array(int sz = 50); //构造函数
Array(const Array<T> &a); //复制构造函数
~Array(); //析构函数
Array<T> & operator = (const Array<T> &rhs); //重载"=“
T & operator [] (int i); //重载"[]”
const T & operator [] (int i) const; //重载"[]”常函数
operator T * (); //重载到T*类型的转换
operator const T * () const;
int getSize() const; //取数组的大小
void resize(int sz); //修改数组的大小
};
template <class T> Array<T>::Array(int sz) {//构造函数
assert(sz >= 0);//sz为数组大小（元素个数），应当非负
size = sz; // 将元素个数赋值给变量size
list = new T [size]; //动态分配size个T类型的元素空间
}
template <class T> Array<T>::~Array() { //析构函数
delete [] list;
}
template <class T>
Array<T>::Array(const Array<T> &a) { //复制构造函数
size = a.size; //从对象x取得数组大小，并赋值给当前对象的成员
list = new T[size]; // 动态分配n个T类型的元素空间
for (int i = 0; i < size; i++) //从对象X复制数组元素到本对象
list[i] = a.list[i];
}
template <class T>
Array<T> &Array<T>::operator = (const Array<T>& rhs) {
if (&rhs != this) {
//如果本对象中数组大小与rhs不同，则删除数组原有内存，然后重新分配
if (size != rhs.size) {
delete [] list; //删除数组原有内存
size = rhs.size; //设置本对象的数组大小
list = new T[size]; //重新分配size个元素的内存
}
//从对象X复制数组元素到本对象
for (int i = 0; i < size; i++)
list[i] = rhs.list[i];
}
return *this; //返回当前对象的引用
}
//重载下标运算符，实现与普通数组一样通过下标访问元素，具有越界检查功能
template <class T>
T &Array<T>::operator[] (int n) {
assert(n >= 0 && n < size); //检查下标是否越界
return list[n]; //返回下标为n的数组元素
}
template <class T>
const T &Array<T>::operator[] (int n) const {
assert(n >= 0 && n < size); //检查下标是否越界
return list[n]; //返回下标为n的数组元素
//重载指针转换运算符，将Array类的对象名转换为T类型的指针
template <class T>
Array<T>::operator T * () {
return list; //返回当前对象中私有数组的首地址
}
//取当前数组的大小
template <class T>
int Array<T>::getSize() const {
return size;
}
// 将数组大小修改为sz
template <class T>
void Array<T>::resize(int sz) {
assert(sz >= 0); //检查sz是否非负
if (sz == size) //如果指定的大小与原有大小一样，什么也不做
return;
T* newList = new T [sz]; //申请新的数组内存
int n = (sz < size) ? sz : size;//将sz与size中较小的一个赋值给n
//将原有数组中前n个元素复制到新数组中
for (int i = 0; i < n; i++)
newList[i] = list[i];
delete[] list; //删除原数组
list = newList; // 使list指向新数组
size = sz; //更新size
}
链表的概念与结点类模板
链表是一种动态数据结构，可以用来表示顺序访问的线性群体
链表是由系列结点组成的，结点可以在运行时动态生成
每一个结点包括数据域和指向指针链表中下一个结点的指针(即下一个结点的地址)。如果链表每个结点中只有一个指向后继结点的指针，则该链表称为单链表
单链表的结点类模板
//Node.h
//类模板的定义
template <class T>
class Node {
private:
Node<T> *next; //指向后继结点的指针
public:
T data; //数据域
Node (const T &data, Node<T> *next = 0); //构造函数
void insertAfter(Node<T> *p); //在本结点之后插入一个同类结点p
Node<T> *deleteAfter(); //删除本结点的后继结点，并返回其地址
Node<T> *nextNode(); //获取后继结点的地址
const Node<T> *nextNode() const; //获取后继结点的地址
};
//类的实现部分
//构造函数，初始化数据和指针成员
template <class T>
Node<T>::Node(const T& data, Node<T> *next = 0 ) : data(data), next(next) { }
//返回后继结点的指针
template <class T>
Node<T> *Node<T>::nextNode() {
return next;
}
//返回后继结点的指针
template <class T>
const Node<T> *Node<T>::nextNode() const {
return next;
}
//在当前结点之后插入一个结点p
template <class T>
void Node<T>::insertAfter(Node<T> *p) {
p->next = next; //p结点指针域指向当前结点的后继结点
next = p; //当前结点的指针域指向p
}
//删除当前结点的后继结点，并返回其地址
template <class T> Node<T> *Node<T>::deleteAfter() {
Node<T> *tempPtr = next;//将欲删除的结点地址存储到tempPtr中
if (next == 0) //如果当前结点没有后继结点，则返回空指针
return 0;
next = tempPtr->next;//使当前结点的指针域指向tempPtr的后继结点
return tempPtr; //返回被删除的结点的地址
}链表的基本操作
- 生成链表
- 插入结点
- 查找结点
- 删除结点
- 遍历链表
- 清空链表
链表类模板
//LinkedList.h
template <class T>
class LinkedList {
private:
//数据成员：
Node<T> *front, *rear; //表头和表尾指针
Node<T> *prevPtr, *currPtr; //记录表当前遍历位置的指针，由插入和删除操作更新
int size; //表中的元素个数
int position; //当前元素在表中的位置序号。由函数reset使用
//函数成员：
//生成新结点，数据域为item，指针域为ptrNext
Node<T> *newNode(const T &item,Node<T> *ptrNext=NULL);
//释放结点
void freeNode(Node<T> *p);
//将链表L 拷贝到当前表（假设当前表为空）。
//被拷贝构造函数、operator = 调用
void copy(const LinkedList<T>& L);
public:
LinkedList(); //构造函数
LinkedList(const LinkedList<T> &L); //拷贝构造函数
~LinkedList(); //析构函数
LinkedList<T> & operator = (const LinkedList<T> &L); //重载赋值运算符
int getSize() const; //返回链表中元素个数
bool isEmpty() const; //链表是否为空
void reset(int pos = 0);//初始化游标的位置
void next(); //使游标移动到下一个结点
bool endOfList() const; //游标是否到了链尾
int currentPosition() const; //返回游标当前的位置
void insertFront(const T &item); //在表头插入结点
void insertRear(const T &item); //在表尾添加结点
void insertAt(const T &item); //在当前结点之前插入结点
void insertAfter(const T &item); //在当前结点之后插入结点
T deleteFront(); //删除头结点
void deleteCurrent(); //删除当前结点
T& data(); //返回对当前结点成员数据的引用
const T& data() const; //返回对当前结点成员数据的常引用
//清空链表：释放所有结点的内存空间。被析构函数、operator= 调用
void clear();
};
template <class T> //生成新结点
Node<T> *LinkedList<T>::newNode(const T& item, Node<T>* ptrNext)
{
Node<T> *p;
p = new Node<T>(item, ptrNext);
if (p == NULL)
{
cout << "Memory allocation failure!\n";
exit(1);
}
return p;
}
template <class T>
void LinkedList<T>::freeNode(Node<T> *p) //释放结点
{
delete p;
}
template <class T>
void LinkedList<T>::copy(const LinkedList<T>& L) //链表复制函数
{
Node<T> *p = L.front; //P用来遍历L
int pos;
while (p != NULL) //将L中的每一个元素插入到当前链表最后
{
insertRear(p->data);
p = p->nextNode();
}
if (position == -1) //如果链表空,返回
return;
//在新链表中重新设置prevPtr和currPtr
prevPtr = NULL;
currPtr = front;
for (pos = 0; pos != position; pos++)
{
prevPtr = currPtr;
currPtr = currPtr->nextNode();
}
}
template <class T> //构造一个新链表，将有关指针设置为空，size为0，position为-1
LinkedList<T>::LinkedList() : front(NULL), rear(NULL),
prevPtr(NULL), currPtr(NULL), size(0), position(-1)
{}
template <class T>
LinkedList<T>::LinkedList(const LinkedList<T>& L) //拷贝构造函数
{
front = rear = NULL;
prevPtr = currPtr = NULL;
size = 0;
position = -1;
copy(L);
}
template <class T>
LinkedList<T>::~LinkedList() //析构函数
{
clear();
}
template <class T>
LinkedList<T>& LinkedList<T>::operator=(const LinkedList<T>& L)//重载"="
{
if (this == &L) // 不能将链表赋值给它自身
return *this;
clear();
copy(L);
return *this;
}
template <class T>
int LinkedList<T>::getSize() const //返回链表大小的函数
{
return size;
}
template <class T>
bool LinkedList<T>::isEmpty() const //判断链表为空否
{
return size == 0;
}
template <class T>
void LinkedList<T>::reset(int pos) //将链表当前位置设置为pos
{
int startPos;
if (front == NULL) // 如果链表为空，返回
return;
if (pos < 0 || pos > size - 1) // 如果指定位置不合法，中止程序
{
std::cerr << "Reset: Invalid list position: " << pos << endl;
return;
}
// 设置与遍历链表有关的成员
if (pos == 0) // 如果pos为0，将指针重新设置到表头
{
prevPtr = NULL;
currPtr = front;
position = 0;
}
else // 重新设置 currPtr, prevPtr, 和 position
{
currPtr = front->nextNode();
prevPtr = front;
startPos = 1;
for (position = startPos; position != pos; position++)
{
prevPtr = currPtr;
currPtr = currPtr->nextNode();
}
}
}
template <class T>
void LinkedList<T>::next() //将prevPtr和currPtr向前移动一个结点
{
if (currPtr != NULL)
{
prevPtr = currPtr;
currPtr = currPtr->nextNode();
position++;
}
}
template <class T>
bool LinkedList<T>::endOfList() const // 判断是否已达表尾
{
return currPtr == NULL;
}
template <class T>
int LinkedList<T>::currentPosition() const // 返回当前结点的位置
{
return position;
}
template <class T>
void LinkedList<T>::insertFront(const T& item) // 将item插入在表头
{
if (front != NULL) // 如果链表不空则调用Reset
reset();
insertAt(item); // 在表头插入
}
template <class T>
void LinkedList<T>::insertRear(const T& item) // 在表尾插入结点
{
Node<T> *nNode;
prevPtr = rear;
nNode = newNode(item); // 创建新结点
if (rear == NULL) // 如果表空则插入在表头
front = rear = nNode;
else
{
rear->insertAfter(nNode);
rear = nNode;
}
currPtr = rear;
position = size;
size++;
}
template <class T>
void LinkedList<T>::insertAt(const T& item) // 将item插入在链表当前位置
{
Node<T> *nNode;
if (prevPtr == NULL) // 插入在链表头，包括将结点插入到空表中
{
nNode = newNode(item, front);
front = nNode;
}
else // 插入到链表之中. 将结点置于prevPtr之后
{
nNode = newNode(item);
prevPtr->insertAfter(nNode);
}
if (prevPtr == rear) //正在向空表中插入，或者是插入到非空表的表尾
{
rear = nNode; //更新rear
position = size; //更新position
}
currPtr = nNode; //更新currPtr
size++; //使size增值
}
template <class T>
void LinkedList<T>::insertAfter(const T& item) // 将item 插入到链表当前位置之后
{
Node<T> *p;
p = newNode(item);
if (front == NULL) // 向空表中插入
{
front = currPtr = rear = p;
position = 0;
}
else // 插入到最后一个结点之后
{
if (currPtr == NULL)
currPtr = prevPtr;
currPtr->insertAfter(p);
if (currPtr == rear)
{
rear = p;
position = size;
}
else
position++;
prevPtr = currPtr;
currPtr = p;
}
size++; // 使链表长度增值
}
template <class T>
T LinkedList<T>::deleteFront() // 删除表头结点
{
T item;
reset();
if (front == NULL)
{
cerr << "Invalid deletion!" << endl;
exit(1);
}
item = currPtr->data;
deleteCurrent();
return item;
}
template <class T>
void LinkedList<T>::deleteCurrent() // 删除链表当前位置的结点
{
Node<T> *p;
if (currPtr == NULL) // 如果表空或达到表尾则出错
{
cerr << "Invalid deletion!" << endl;
exit(1);
}
if (prevPtr == NULL) // 删除将发生在表头或链表之中
{
p = front; // 保存头结点地址
front = front->nextNode(); //将其从链表中分离
}
else //分离prevPtr之后的一个内部结点，保存其地址
p = prevPtr->deleteAfter();
if (p == rear) // 如果表尾结点被删除
{
rear = prevPtr; //新的表尾是prevPtr
position--; //position自减
}
currPtr = p->nextNode(); // 使currPtr越过被删除的结点
freeNode(p); // 释放结点，并
size--; //使链表长度自减
}
template <class T>
T& LinkedList<T>::data() //返回一个当前结点数值的引用
{
if (size == 0 || currPtr == NULL) // 如果链表为空或已经完成遍历则出错
{
cerr << "Data: invalid reference!" << endl;
exit(1);
}
return currPtr->data;
}
template <class T>
void LinkedList<T>::clear() //清空链表
{
Node<T> *currPosition, *nextPosition;
currPosition = front;
while (currPosition != NULL)
{
nextPosition = currPosition->nextNode(); //取得下一结点的地址
freeNode(currPosition); //删除当前结点
currPosition = nextPosition; //当前指针移动到下一结点
}
front = rear = NULL;
prevPtr = currPtr = NULL;
size = 0;
position = -1;
}
栈类模板
栈类
- 栈是只能从一端访问的线性群体，可以访问的这一端称栈顶，另一段称栈底。栈是一种后进先出的数据结构
栈的应用
表达式处理
栈的基本操作
- 初始化
- 入栈
- 出栈
- 清空栈
- 访问栈顶元素
- 检测栈的状态（满、空）
栈类模板
//Stack.h
template <class T, int SIZE = 50>
class Stack {
private:
T list[SIZE];
int top;
public:
Stack();
void push(const T &item);
T pop();
void clear();
const T &peek() const;
bool isEmpty() const;
bool isFull() const;
};
//模板的实现
template <class T, int SIZE>
Stack<T, SIZE>::Stack() : top(-1) { }
template <class T, int SIZE>
void Stack<T, SIZE>::push(const T &item) {
assert(!isFull());
list[++top] = item;
}
template <class T, int SIZE>
T Stack<T, SIZE>::pop() {
assert(!isEmpty());
return list[top--];
}
template <class T, int SIZE>
const T &Stack<T, SIZE>::peek() const {
assert(!isEmpty());
return list[top]; //返回栈顶元素
}
template <class T, int SIZE>
bool Stack<T, SIZE>::isEmpty() const {
return top == -1;
}
template <class T, int SIZE>
bool Stack<T, SIZE>::isFull() const {
return top == SIZE - 1;
}
template <class T, int SIZE>
void Stack<T, SIZE>::clear() {
top = -1;
}
队列类模板
队列是只能向一端添加元素，从另一端删除元素的线形群体
循环队列
为了避免队列假溢出，把队列形成一个环
//Queue.h |
排序
- 排序概述
- 排序是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。
- 数据元素: 数据的基本单位。在计算机中通常作为一个整体进行考虑。一个数据元素可由若干数据项组成。
- 关键字: 数据元素中某个数据项的值，用它可以标识（识别）一个数据元素。
- 在排序过程中需要完成的两种基本操作
- 比较两个数的大小
- 调整元素在序列中的位置
- 内部排序与外部排序
- 内部排序：待排序的数据元素存放在计算机内存中进行的排序过程
- 外部排序：待排序的数据元素数量很大，以至内存中一次不能容纳全部数据，在排序过程中尚需要对外存进行访问的排序过程
- 插入排序
- 基本思想：每一步将一个待排序元素按其关键字的大小插入到已排序序列的适当位置，直到待排序元素插入完为止
//直接插入排序函数模板 |
- 选择排序
- 基本思想：每次从待排序序列中选择一个关键字最小的元素，（当需要按关键字升序排列时），顺序排在已排序序列的最后，直至全部排完。
template <class T> |
交换排序
基本思想：两两比较待排序序列的元素，并交换不满足顺序要求的各对元素，直到全部满足要求为止
