数据结构概念.ppt

四边形类及其对象 属性 aPoint1 aPoint2 aPoint3 aPoint4 服务 Draw( ) move(?x, ?y) contains(aPoint) 属性值 属性值 quadrilateral1 quadrilateral2 (35, 10) (50, 10) (35, 25) (50, 25) (45, 65) (50, 45) (65, 66) (60, 70) Draw( ) move(?x, ?y) contains(aPoint) Draw( ) move(?x, ?y) contains(aPoint) 服务 服务 quadrilateral 第二十九页，共七十二页，2022年，8月28日 继承 派生类（子类）：四边形，三角形，… 基类（父类）：多边形 派生类 继承的特性 + 特有的特性 基类 多边形 四边形 三角形 六边形 第三十页，共七十二页，2022年，8月28日 通信 消息传递 C++中消息传递的方式： 定义：Point p; void move(int Δx, intΔy); 使用：p.move(x, y); C中则不同，需使用函数调用方式： 定义：Point p; void move(Point q, int Δx, intΔy); 使用：move(p, x, y); 第三十一页，共七十二页，2022年，8月28日 Draw( ) move(?x, ?y) contains(aPoint) Polygon referencePoint Vertices Polygon 类 referencePoint Vertices Draw( ) move(?x, ?y) contains(aPoint) Polygon的子类 Quadrilateral类 Quadrilateral 第三十二页，共七十二页，2022年，8月28日 算法定义 定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列 特性： 输入 有0个或多个输入 输出 有一个或多个输出(处理结果) 确定性 每步定义都是确切无歧义的 有穷性 算法应在执行有穷步后结束 有效性 每一条运算应足够基本 第三十三页，共七十二页，2022年，8月28日 事例学习：选择排序问题 明确问题：递增排序 解决方案：逐个选择最小数据 算法框架： for (int i = 0; i n-1; i++) { //n-1趟 从a[i]检查到a[n-1]; 若最小整数在a[k], 交换a[i]与a[k]; } 细化程序：程序 SelectSort 算法设计 自顶向下，逐步求精 第三十四页，共七十二页，2022年，8月28日 void selectSort ( int a[ ], const int n ) { //对n个整数a[0],a[1],…,a[n-1]按递增顺序排序 for (int i = 0; i n-1; i++) { int k = i; //从a[i]查到a[n-1], 找最小整数, 在a[k] for (int j = i+1; j n; j++) if (a[j] a[k]) k = j; int temp = a[i]; a[i] = a[k]; a[k] = temp; } } 第三十五页，共七十二页，2022年，8月28日 模板 (template) 定义 适合多种数据类型的类定义或算法，在特定环境下通过简单地代换，变成针对具体某种数据类型的类定义或算法。 第三十六页，共七十二页，2022年，8月28日 用模板定义用于排序的数据表类 #ifndef DATALIST_H #define DATALIST_H #include iostream.h //K是表项关键码类型 template class K, class E / /E是表项类型 class dataList { private: E *element; int listSize; void swap (int m1, int m2); int minKey (int low, int high); 第三十七页，共七十二页，2022年，8月28日 public: dataList (int size = 10) : listSize (size), element (new E[size]) { }