赞
踩
我们把每种数据结构均视为抽象数据类型,它不但定义了数据的组织方式,还给出了处理数据的运算。C++语言中,用类来表示抽象数据类型,在具体应用中用对象来存储和处理数据。
C++类的创建是我们学习数据结构的基础,继承性和多态性扩充了面向对象程序设计的能力,使其可以用于开发基于类库的大型软件系统。
第一章主要是熟悉概念
公司维护的进货信息程序
数据:
货号 | 当前库存 | 单价 | 进货级别 |
---|---|---|---|
- | 在售出货物时,修改库存量 | 调价格时修改价格 | 在库存小于应进货级别时,给出进货信息 |
操作:
UpdateStockLevel() //修改库存
AdjustUnitPrice() //调整单价
ReorderItem() //需订货信息
掷骰子的游戏程序
ADT:其数据包括被掷骰子数目,掷出骰子的总点数和每个骰子的点数;
操作包括:掷骰子、返回该次投掷的骰子的总点数以及打印所掷每个骰子的点数。
数据:
操作
Toss() // 掷骰子
Total() // 求骰子总点数
DisplayToss() // 打印点数
由ADT名称组成的头,对数据类型的描述以及操作列表组成。
操作列表:
操作 | 描述 |
---|---|
input(输入) | 指定用户给定的输入值 |
precondition(前提) | 表示该操作可执行前必须具有的数据 |
process(加功) | 表示由该操作完成的动作 |
output(输出) | 表示执行操作后,返回给用户的值 |
poslcondition(结果) | 表示在数据内部所作的任何改变 |
initialize(初始化) | 大多数ADT都由初始化操作,对数据赋初始值 |
Constructor(构造函数) | C++语言环境下,初始化操作称为构造函数 |
综上所述的ADT规范描述为:
ADT ADT 名称 is Data 描述数据的结构 Operations 构造函数 Initial values: 用来初始化对象的数据 Process: 初始化对象 操作1 Input: 用户输入的数值 Preconditions: 系统执行本操作前数据所必需的状态 Process: 对数据进行的动作 Output: 返回给用户的数据 Postconditions: 系统执行操作后数据的状态 操作2 ...... 操作n ...... end ADT ADT名称
抽象数据类型 Dice
的数据包括:每次所掷骰子数 N
,所掷出的总点数和一个有 N
项的存放每个骰子被掷出点数的表。
ADT Dice is Data 该次投掷骰子的个数,它是一个大于或者等于1的整数。 该次掷出的总点数,它是一个整数,如果掷 N 个骰子,则该值在 N 与 6N 之间。 该次投掷所掷出的每个骰子的点数表,该表的每个数值均为从1到6的整数。 Operations Constructor Initial values: 被掷骰子个数 Process: 初始化数据,给定每次投掷骰子的个数 Toss Input: 无 Preconditions: 无 Process: 掷骰子并计算总点数 Output: 无 Postconditions: 所掷骰子总点数及每个骰子的点数 Total Input: 无 Preconditions: 无 Process: 检索该次投掷的总点数数据项 Output: 返回该次投掷总点数 Postconditions: 无 DisplayToss Input: 无 Preconditions: 无 Process: 打印该次掷出的各骰子的点数 Output: 无 Postconditions: 无 end ADT Dice
圆的抽象数据类型:半径(计量只需要半径)。操作包括:面积、求周长
ADT Circle is Data 非负实数,给出圆的半径 Operations Constructor Initial valus: 圆的半径 Process: 给圆的半径赋初始值 Area Input: 无 Preconditions: 无 Process: 计算圆的面积 Output: 返回圆的面积 Postconditions: 无 Circumference Input: 无 Preconditions: 无 Process: 计算圆的周长 Output: 返回圆的周长 Postconditions: 无 end ADT Circle
C++语言使用用户定义的类(Class)类型来表示抽象数据结构,类由多个存放数据值的成员和“方法”组成,方法定义了存取数据的方法,类型为类的变量成为对象。
类可以分为两个部分:公有部分,用户不需要了解对象的内部细节就可以使用对象;私有部分,由帮助实现数据抽象的数据和内部操作组成。例如: ADT 圆的类中包含一个私有数据成员——半径,其公共成员包括构造函数和计算面积和周长的方法。
类:
private:
数据成员: 值1 值2
内部操作
public:
构造函数
操作1
操作2
Circle
类
private:
radius(半径)
public:
Constructor(构造函数)
Area(求面积)
Circumference(求周长)
声明C++类时,不定义成员函数时叫做类声明,是ADT的一种具体表示,方法的具体实现在独立于声明之外的类实现中。
通过完整的 Circle
类说明C++类的实现和对象的应用,用该程序来计算一个圆形水池的池壁造价。
需求:
实现程序:
#include<iostream> using namespace std; const float PI = 3.14152; const float FencePrice = 3.5; const float ConcretePrice = 0.5; class Circle; class Circle { private: float radius; public: // 构造函数 Circle(float r); // 计算圆的周长和面积的函数 float Circumference(void) const; float Area(void) const; }; //类的实现 //构造函数用类初始化数据成员 radius Circle::Circle(float r):radius(r){} // 计算圆的周长 float Circle::Circumference(void) const { return 2 * PI * radius; } // 计算圆的面积 float Circle::Area(void) const { return radius * radius * PI; } int main() { float radius; float FenceCost, ConcreteCost; // 设定浮点数输出时只显示小数点后两位 cout.setf(ios::fixed); cout.setf(ios::showpoint); cout.precision(2); // 提示用户输入半径 radius cout << "Enter the radius of the pool:"; cin >> radius; // 定义Circle对象 Circle pool(radius) ; Circle poolRim(radius + 3); // 计算栅栏造价并输出 FenceCost = poolRim.Circumference() * FencePrice; cout << "Fencing Cost is $" << FenceCost << endl; // 计算过道造价并输出 ConcreteCost = (poolRim.Area() - pool.Area()) * ConcretePrice; cout << "Concrete Cost is $" << ConcreteCost << endl; }
运行结果:
Const 限定符:限定的函数成员不改变数据成员的值,在函数的声明和定义中都要用到
几何图形由线和长方形等点集组成,可以把点定义为一个原始的对象,去描述线和长方形,并用这个案例说明对象及复合。
1. 点是平面位置,所以我们用坐标(x, y)表示点这个对象,x 和 y 分别表示点到原点水平和垂直距离。
2. 两点确定一条直线,所以 P1 和 P2 点可定义一条线段
3. 矩形是临边正交的四边形,左上点和右下点决定一个矩形。
综上所述,得到点(Ponit),线(Line),矩形(Rectangle)的类:
// Point 类 class Point { private: float x, y; // 点的水平及垂直位置 public: Point (float h, float v); // 将 h 赋值给 x,v 赋值给 y float GetX(void) const; // 返回 x 坐标(水平位置) float GetY(void) const; // 返回 y 坐标(垂直位置) void Draw(void) const; // 在(x, y)处画一个点 }; // Line 类 class Line { private: Point p1, p2; // 线段的两个端点 public: Line(Point a, Point b); // 将 a 赋值给 P1 , b 赋值给 P2 void Draw(void) const; };
继承是一个直观的概念,比如说我们每个人继承了父母身上的人种,肤色,眼睛颜色等特征
动物学的继承:
在种族链中,子类继承父类的所有属性,比如狗具有所有哺乳动物的属性,也具有狗和猫、大象等区分开的属性,动物学的继承关系图可以解释为:
苏格兰牧羊长毛狗 “是” 狗
狗 “是” 哺乳动物
在链中,“哺乳动物”是狗的积累,“狗”被称为派生类,子类可从父类和祖父类中继承属性。
比如:有序表(OrderedList)和继承
有序表是一种特殊表,其元素按升序排序
作为抽象数据类型,有序表(OrderedList)保存了 正常序列表(SeqList)除了插入之外的绝大部分操作,有序表的插入操作必须维持表的升序排序。
类 OrderedList 是从类 SeqList 派生来的,它继承了积累的许多操作,只是将 Insert 操作改写称按有序的次序插入元素。
ADT:
ADT OrderedList is Data <同 ADT SeqList> Operations Constructor <执行基类的 Constructor> ListSize <同 ADT SeqList> ListEmpty <同 ADT SeqList> ClearList <同 ADT SeqList> Find <同 ADT SeqList> Delete <同 ADT SeqList> DeleteFront <同 ADT SeqList> GetData <同 ADT SeqList> Insert Preconditions: 无 Input: 要插入表中的元素 Process: 在表中可保持元素有序的位置插入该元素 Output: 无 Postconditions: 表增加一个新元素且其大小加1 end ADT OrderedList
OrderedList 类继承 SeqList 类
SeqList 类 class SeqList { private: // 存放表的数组及表中当前元素的个数 DataType listitem[ARRAYSIZE]; int size; public: // 构造函数 SeqList(void); // 访问表的方法 int ListSize(void) const; int ListEmpty(void) const; int Find(DataType & item) const; DataType GetData(int pos) const; //修改表的方法 void Insert(const DataType& item); void Delete(const DataType& item); DataType DeleteFront(void); void ClearList(void); };
在函数
ListSize
,ListEmpty
,Find
和GetData
的定义后面都有单词const
,这些函数称为 常量函数
函数Insert
,Delete
在参数表中出现单词const
,C++用这种方式来表示:虽然传递的是参数地址,但不允许修改参数的值
C++声明派生类的语法:在头部,类名的后面用冒号(:)表示基类
OrderedList 类
class OrderedList:public SeqList // 从类 SeqList 中继承
{
public:
OrderedList(void); // 初始化基类来创建一个空表
void Insert(const dataType& item); // 按顺序往表里插入元素
};
函数
Insert
覆盖了基类中的同名函数,它遍历从基类中继承的表,将元素插入到可保持其升序排列位置。
图形上的应用集中在诸如:窗口、菜单、对话框等对象上,最基本的窗口是一具有适用于所有类型窗口的数据和操作的数据结构
这些操作包括:打开窗口、创建或修改窗口标题,建立滚动条和拖动区等
其它窗口如:对话框、菜单、文本窗口等可继承这些基本结构
如下图的类 Dialog
和 TextEdit
即是从类 Window
中派生出来的
Editor
和 View
为基类的派生类。程序开发从用户需要解决问题开始,这些问题需要程序员与用户共同分析问题,确定输入和输出数据及其格式,设计计算的算法。
(其实就是确认需求—>需求分析)
完成主程序和子程序的代码
测试贯穿在整个软件系统的开发过程中
写测试代码调用类里面的函数进行测试
需要设计测试用例测试程序是否正确:
设计文档
程序框图
控制模块结构图
用户手册
C++语言发展史:
时间 | 事件 |
---|---|
1983年8月 | 第一个C++实现投入使用(1983年C++开了天界) |
1983年12月 | Rick Mascitti建议命名为CPlusPlus,即C++ |
1985年2月 | 第一个C++ Release E发布 |
10月 | CFront的第一个商业发布,CFront Release 1.0 |
10月 | Bjarne博士完成了经典巨著The C++ Programming Language第一版 |
10月 | 1986年11月,C++第一个商业移植CFront 1.1,Glockenspiel |
1987年2月 | CFront Release 1.2发布 |
11月 | 第一个USENIX C++会议在新墨西哥州举行 |
1988年10月 | 第一次USENIX C++实现者工作会议在科罗拉多州举行 |
1989年12月 | ANSI X3J16在华盛顿组织会议 |
1990年3月 | 第一次ANSI X3J16技术会议在新泽西州召开 |
5月 | C++的又一个传世经典ARM诞生 |
7月 | 模板被加入 |
11月 | 异常被加入 |
1991年6月 | The C++ Programming Language第二版完成 |
6月 | 第一次ISO WG21会议在瑞典召开 |
10月 | CFront Release 3.0发布 |
1993年3月 | 运行时类型识别在俄勒冈州被加入 |
7月 | 名字空间在德国慕尼黑被加入 |
1994年8月 | ANSI/ISO委员会草案登记 |
1997年7月 | The C++ Programming Language第三版完成 |
10月 | ISO标准通过表决被接受 |
1998年11月 | ISO标准被批准 |
参考:C++ 诞生历史
Virtual
及将操作赋值为 0 表示了纯粹的虚函数template<class T> class List { protected: // 表中元素个数,由派生类修改 int size; public: // 构造函数 List(void); // 访问表的方法 virtual int ListSize(void) const; virtual int ListEmpty(void) const; virtual int Find(T& item) = 0; // 修改表的方法 virtual void Insert(const T& item) = 0; virtual void Delete(const T& item) = 0; virtual void ClearList(void) = 0; }
C++继承可以通过多种方式实现:
多态性案例:
多态性是面向对象程序设计的基础,专业人员长说成是“实时多态下的继承”,C++通过 动态绑定 和 虚函数 来支持这种结构。
假定对象 BigWoody
是 WoodFrame
类型,我们可以通过显式调用它的 Paint
操作来直接完成对木结构房子的油漆,我们称这种方式为静态绑定:
BigWoody.Paint(); // 静态绑定
如果当前给出的消息没有跟具体的House
联系起来,只给出来这些House
的地址,那么需要通过地址找到House
再根据House
类型选择正确的 Paint
操作,这种方式叫做 动态绑定,如下图所示:
DoPaint (House house)
{
house.Print()
}
(位于地址414的房子).Paint();
进程根据给定地址的 House
来调用相应的 Paint
操作,如果在地址414的房子是木结构,则执行类WoodFrame
的操作 Paint()
。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。