数据结构C++（1）

抽象数据类型

 

1.抽象数据类型（ADT）:一种用户定义的数据类型，其运算符指明了用户如何操作数据。与具体应用无关，集中与数据及其操作的理想模型上。C++使用用户定义的类（class）来表示抽象数据结构。

 

2.ADT描述规范：

ADT    ADT名称     is

Data  

   描述数据的结构

Operations 

   Constructor<构造函数>

      Initial values: 用来初始化对象的数据

      Process:初始化对象

    操作1

       Input:用户输入的数值

       Preconditions:系统执行本操作前数据所必须的状态（前提）

       Process:对数据进行的动作（过程）

       Output:返回给用户的数据（输出）

       Postconditions:系统执行本操作后数据的状态（结果）

    操作2

       ...

    操作n

       ...

  end ADT  ADT名称

 

3、类class： 

private:      数据成员：  值1   值2      内部操作方法

public:      构造函数      操作方法1      操作方法2

封装信息：类通过把数据和方法包装在一起并将它们视作整体。

信息隐藏：在结构上隐藏了应用细节（私有）并严格控制对其数据和操作的外部访问（公共方法）。

消息传递：由控制各对象相互作用的主控模块指挥每个对象活动的过程。

http://s15/middle/4a93cceagb1843430b31e&690

举例：一圆形游泳池，在其周围建一圆形过道，并在其周围围上栅栏，栅栏价格每米3.5美元、过道造价每平方米0.5美元。过道宽度3米，游泳池半径由键盘输入，要求计算并输出过道和栅栏造价。

#include<iostream.h> const float PI=3.1416; const float FencePrice=3.50; const float ConcretePrice=0.50; class Circle{ private: float radius; public: Circle(float r); float Circumference(void) const; float Area(void) const; }; Circle::Circle(float r):radius(r){ } float Circle::Circumference(void) const {return 2*PI*radius;} float Circle::Area(void)const{return PI*radius*radius;} void main(){ float radius; float FenceCost,ConcreteCost; cout.setf(ios::fixed); cout.setf(ios::showpoint); cout.precision(2);//设定输出小数点保留后2位 cout<<"请输入圆池半径："; cin>>radius; Circle Pool(radius); Circle PoolRim(radius+3); FenceCost =PoolRim.Circumference()*FencePrice; ConcreteCost=(PpolRim.Area()-Pool.Area())*ConcretePrice; cout<<"栅栏造价："<<FenceCost<<endl; cout<<"过道造价："<<ConcreteCost<<endl; }

 

4、对象复合：类包含本身就是对象的数据成员。优点：可以访问组成它的对象的成员函数，实现代码复用。

从点线面看对象复合：

http://s2/middle/4a93cceagb18564bee6a1&690

5、类的继承：

继承：通过细化某个类来创建（派生）新类，并复用已开发的代码。

从Seqlist（线性表） 到OrderdList（有序表）看类的继承：

http://s3/middle/4a93cceagb18565263972&690

 

实现类OrderedList仅需我们写构造函数和Insert的代码，所有其他操作都可以从类SeqList中得到。

C++继承表示：

class OrderedList:public SeqList {

  public： OreredList(void); //初始化基类来创建一个空表

           void Insert(const dataType& item) //按保序往表中插入元素

}

 

6、面向对象程序设计：

http://s13/middle/4a93cceagb185ac0f670c&690

第一阶段:问题分析和功能定义

 程序员和用户共同分析问题，确定输入和输出数据及其格式，设计计算的算法。

第二阶段：设计

 给出所有对象的描述和对象间相互作用的控制。

 对象设计：明确每个类的定义，并设计小程序对各个类进行单元测试。

 控制设计：程序框架设计。用自顶向下方法创建主程序和子程序来控制对象间相互作用。

http://s7/middle/4a93cceag7826fac3a656&690

第三阶段：编码

 实现程序设计的主程序和子程序的编码。

第四阶段：测试

 集中于对控制模块的设计进行测试。

 

7、程序的测试和维护：

对象测试：开发小程序调用类的每个公共方法来对类进行测试。

控制模块测试：用精心选择的测试用例运行程序。还应该用不正确的输入来测试代码的“健壮性”。

 测试数据的选择：可测试程序不同算法的一系列输入数据，包括简单数据、典型数据、测试程序的特殊情况的特殊数据和检验程序响应错误输入能力的非法数据。

完整结构化测试：如果程序中还有代码没被执行到，就没有达到完全测试。要求选择数据测试程序中的不同算法：每个条件语句、每个循环结构、每个函数调用等等。

 

8、抽象基类及虚函数：

抽象基类着重描述类的最基本的性质。这些数据集实现该类的最基本的操作。

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 以及=0标识了纯粹的虚函数

     //修改表的方法

          virtual void Insert(const T& item) = 0;

          virtual void Delete(const T& item) = 0;

          virtual void ClearList(void) = 0;

};

 

9、多重继承——多态性

 允许不同类的对象响应相同的消息。接收消息的对象在运行时动态确定。C++通过动态绑定和虚函数来支持这种继承结构。动态加载到对象的操作均定义为虚成员函数。