第一章 面向对象数据结构

鲍捷，2001年3月11日

1 面向对象数据结构... 1
第一节 数据结构的基本概念和术语... 2
第二节 抽象数据类型的表示与实现... 6
第三节 算法及算法设计要求... 10
第四节 类和对象的概念... 14
第五节 封装性及实现... 15
第六节 继承性及实现... 18

面向对象数据结构



对应的教材章节


第1章 概述 1．1 抽象数据类型 1．2 C++类和抽象数据类型 1．3 C++应用中的对象 1．4 对象设计 1．5 类继承的应用 1．6 面向对象程序设计 1．7 程序测试与维护 1．8 C++程序设计语言 1．9 抽象基类及多态性	1	重点
第2章 基本数据类型 2．1 整型 2．2 字符类型 2．3 实数类型 2．4 枚举类型 2．5 指针 2．6 数组类型 2．7 文本串及变量 2．8 记录 2．9 文件 2．10 数组和记录的应用	无	自习
抽象数据类型和类 3．1 对象类型类 3．2 类的举例 3．3 对象和信息传递 3．4 对象数组 3．5 多构造函数 3．6 应用举例：三角矩阵	1	一般要求
第6章 抽象操作 运算符重载 有理数 有理数类 作为成员函数的有理数运算 作为友元函数的有理数流运算符 有理数的转换 有理数的使用	无	自习
第8章 类和动态存储 指针与动态数据结构 动态申请对象 赋值与初始化 安全数组 串类 模式匹配 整型集合	4	自习
第12章 继承和抽象类 12．1 继承概述 12．2 C++中的继承 12．3 多态性和虚函数 12．4 抽象基类 12．5 迭代算子 12．6 有序表 12．7 异构表	无	自习




第一节数据结构的基本概念和术语


教学目的：了解数据结构的基本概念，理解常用术语
教学重点：基本概念：数据与数据元素
教学难点：数据元素间的四种结构关系。
授课内容：
一、数据、数据元素、数据对象、数据结构的定义
1、数据的定义
定义一（广义）：数据是客观事物的符号表示。
例子：成绩单

学号	姓名	语文	数学	C语言
6201001	张三	85	54	92
6201002	李四	92	84	64
6201003	王五	87	74	73
6201004
...


例：张三的C语言考试成绩为92分，92就是该同学的成绩数据。
定义二（狭义）：能输入到计算机中并被计算机程序处理的符号的总称。
例：图像、声音等。

2、数据元素、数据项
数据元素是数据的基本单位，它也可以再由不可分割的数据项组成。如图示：

3、数据对象
是性质相同的数据元素的集合。如上例：一个班级的成绩表可以看作一个数据对象。
4、数据结构
定义一、数据元素集合（也可称数据对象）中各元素的关系。
定义二、相互之间存在特定关系的数据元素集合。
数据结构的种类：

	特征	示例
集合	元素间为松散的关系	广场上的一群鸽子
线性结构	元素间为严格的一对一关系	如上面的成绩表中各元素 （字典、Hash表、数组、记录、文件、表、栈、队列）
树形结构	元素间为严格的一对多关系	（树、堆） 堆是节点间具有层次次序关系的完全二叉树
图状结构（或网状结构）	元素间为多对多关系


数据结构的形式定义：

数据结构名称=（D，S）
其中D为数据元素的有限集，S是D上关系的有限集
 

逻辑结构		“数据结构”定义中的“关系”指数据间的逻辑关系，故也称数据结构为逻辑结构。
存储结构	顺序存储结构	数据结构在计算机中的表示称为物理结构。又称存储结构。
	链式存储结构


存储结构详解：
计算机中存储信息的最小单位： 位，8位为一字节，两个字节为一字，字节、字或更多的二进制位可称为 位串。在逻辑描述中，把位串称为元素或 结点。
当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为 数据域(Data Field)。
例：上述成绩表数据用C语言的结构体数组classonestu[50]来存储：

struct stu { int stuno;/*数据项，也称stu位串中的一个子位串，或叫做数据域*/ char name[20]; int maths; int language; int c_language; } classonestu[50];

二、数据类型
1、定义：数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
例：C语言中的整型，其内涵为一定范围的自然数集合，及定义在该集合上的加减乘除及取模、比较大小操作。而实型则无取模操作。当然整型也不需四舍五入。
2、数据类型的种类：

	特征	例
原子类型	值在逻辑上不可分解	int float
结构类型	值由若干成分按某种结构组成	struct stu


数据类型封装了数据存储与操作的具体细节。
三、总结
数据->数据元素
具有特定关系的数据元素集合->数据结构
数据结构的逻辑表示与物理存储->逻辑结构与存储结构
人们不仅关心数据的逻辑结构、存储结构，还关心数据的处理方法（算法）与处理结果->数据类型
数据类型->分类


第二节抽象数据类型的表示与实现


本课主题： 抽象数据类型的表示与实现
教学目的： 了解抽象数据类型的定义、表示和实现方法
教学重点： 抽象数据类型表示法、类C语言语法
教学难点： 抽象数据类型表示法
授课内容：
一、抽象数据类型定义（ADT）
ADT是定义了数据的取值范围和表现法则以及数据的操作集
作用：抽象数据类型可以使我们更容易描述现实世界。例：用线性表描述学生成绩表，用树或图描述遗传关系。
定义：一个数学模型以及定义在该模型上的一组操作。
关键：使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。
例：线性表这样的抽象数据类型，其数学模型是：数据元素的集合，该集合内的元素有这样的关系：除第一个和最后一个外，每个元素有唯一的前趋和唯一的后继。可以有这样一些操作：插入一个元素、删除一个元素等。

抽象数据类型分类
原子类型	值不可分解，如int
固定聚合类型	值由确定数目的成分按某种结构组成，如复数
可变聚合类型	值的成分数目不确定如学生基本情况


抽象数据类型表示法：
一、

三元组表示：（D，S，P）

其中D是数据对象，S是D上的关系集，P是对D的基本操作集。

二、书中的定义格式：
ADT 抽象数据类型名{
Data:
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
Operations:
基本操作：<基本操作的定义>
}ADT 抽象数据类型名
每一种操作的基本内容：
Input 用户输入的数值
Proconditions 执行本操作前数据必需的状态
Process 对数据进行的动作
Output 返回用户的数据
Postconditions 系统执行操作后数据的状态
例：线性表的表示

名称	线性表
数据对象	D={ai| ai(-ElemSet,i=1,2,...,n,n>=0)	任意数据元素的集合
数据关系	R1={<ai-1,ai>| ai-1,ai(- D,i=2,...,n)	除第一个和最后一个外，每个元素有唯一的直接前趋和唯一的直接后继
基本操作	ListInsert(&L,i,e)	L为线性表，i为位置，e为数据元素。
	ListDelete(&L,i,e)
	...


ADT SeqList is
Data:
        数组 或 链表
Operations:
        Constructor
        ListSize
        ListEmpty
        ClearList
        Find
        Insert
        Delete
        DeleteFront
End ADT SeqList

二、类C语言语法

类C语言语法示例
1、预定义常量和类型	#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef in Status; //Status是函数的类型，其值是函数结果状态代码。
2、数据结构的存储结构	typedef ElemType first;
3、基本操作的算法	函数类型 函数名（函数参数表）{ //算法说明 语句序列 }//函数名
4、赋值语句	简单赋值：	变量名=表达式；
	串联赋值：	变量名1=变量名2=...=变量名k=表达式；
	成组赋值:	（变量名1，...,变量名k）=（表达式1，...,表达式k); 结构名=结构名； 结构名=（值1，...，值k); 变量名[]=表达式； 变量名[起始下标..终止下标]=变量名[起始下标..终止下标]；
	交换赋值：	变量名<-->变量名；
	条件赋值：	变量名=条件表达式？表达式？表达式T：表达式F
5、选择语句	1、if（表达式） 语句； 2、if（表达式） 语句； else 语句； 3、switch(表达式）{ case 值1：语句序列1；break; ... case 值n：语句序列n；break; default:语句序列n+1；break; } 4、switch{ case 条件1：语句序列1；break; ... case 条件n：语句序列n；break; default:语句序列n+1；break; }
6、循环语句	for（赋初值表达式；条件；修改表达式序列）语句； while（条件）语句； do{ 语句序列}while（条件）；
7、结束语句	return [表达式]； return; //函数结束语句 break; //case结束语句 exit(异常代码); //异常结束语句
8、输入和输出语句	scanf（[格式串]，变量1，...,变量n）；
9、注释	//文字序列
10、基本函数	max（表达式1，...，表达式n） min,abs,floor,ceil,eof,eoln
11、逻辑运算	&&与运算；||或运算


例：线性表的实现： ADT List{
数据对象: D={ai| ai(-ElemSet,i=1,2,...,n,n>=0}
数据关系: R1={<ai-1,ai>| ai-1,ai(- D,i=2,...,n}
基本操作：
InitList(&L) DestroyList(&L) ListInsert(&L,i,e) ListDelete(&L,i,&e)
}ADT List
ListInsert(List &L,int i,ElemType e)
{if(i<1||i>L.length+) return ERROR;
q=&(L.elem[i-1]);
for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p;
*q=e;
++L.length;
return OK;
}
下面是C语言编译通过的示例： (略)


E:\鲍捷\学术\教学\数据结构\datastru\class02>listdemo name stuno age score zmofun 100001 80 1000 List length now is 1. name stuno age score bobjin 100002 80 1000 zmofun 100001 80 1000 List length now is 2.



三、总结
抽象数据类型定义；
抽象数据类型实现方法：一、类C语言实现 二、C语言实现

第三节算法及算法设计要求

教学目的： 掌握算法的定义及特性，算法设计的要求
教学重点： 算法的特性，算法设计要求
教学难点： 算法设计的要求
授课内容：
一、算法的定义及特性
1、定义：
BOOL IsPrime(int x)
{
int lim = sqrt(x);
for ( int i = 2 ; i < lim ; i++ )
{
if( (x % i) == 0)
return FALSE;
}
return TRUE;
}/*这是一个判断一个数是否是质数的程序*/
算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作；此外，一个算法还具有下列五个重要特性：
2、算法的五个特性：

有穷性	一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成；
确定性	算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。有任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。
可行性	一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
输入	一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。
输出	一个算法有一个或多个的输出。这些输出是同输入有着某些特定关系的量。


例：

有穷性	haha() {/*only a joke,do nothing.*/ } main() {printf("请稍等...您将知道世界的未日..."); while(1) haha(); }
确定性	float average(int *a,int num) {int i;long sum=0; for(i=0;i<num;i++) sum+=*(a++); return sum/num; } main() {int score[10]={1,2,3,4,5,6,7,8,9,0}; printf("%f",average(score,10); ) （问题：缺少对num==0的处理）
可行性
输入
输出	getsum(int num) { int i,sum=0; for(i=1;i<=num;i++) sum+=i; } /*无输出的算法没有任何意义，


二、算法设计的要求
1、正确性

算法正确性的四个层次
程序不含语法错误。	max(int a,int b,int c) { if (a>b) {if(a>c) return c; else return a; } }
程序对于几组输入数据能够得出满足规格说明要求的结果。	max(int a,int b,int c) { if (a>b) {if(a>c) return a; else return c; } } /* 8,6,7 */ /* 9,3,2 */
程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果。	max(int a,int b,int c) { if (a>b) {if(a>c) return a; else return c; } else {if(b>c) return b; else return c; } }
程序对于一切合法的输入数据都能产生满足规格说明要求的结果。


2、可读性
3、鲁棒性
4、效率与低存储量需求
效率指的是算法执行时间。对于解决同一问题的多个算法，执行时间短的算法效率高。
存储量需求指算法执行过程中所需要的最大存储空间。
两者都与问题的规模有关。

	算法一	算法二
在三个整数中求最大者	max(int a,int b,int c) {if (a>b) {if(a>c) return a; else return c; } else {if(b>c) return b; else return c; }/*无需额外存储空间，只需两次比较*/	max(int a[3]) {int c,int i; c=a[0]; for(i=1;i<3;i++) if (a[i]>c) c=a[i]; return c; } /*需要两个额外的存储空间，两次比较，至少一次赋值*/ /*共需5个整型数空间*/
求100个整数中最大者	同上的算法难写，难读	max(int a[100]) {int c,int i; c=a[0]; for(i=1;i<100;i++) if (a[i]>c) c=a[i]; return c; } /*共需102个整型数空间*/


三、总结
1、算法的特性
2、算法设计要求：正确性、可读性、健壮性、效率与低存储量需求。


第四节类和对象的概念

1 对象（Object）
面向对象技术的核心
•对象是人们要进行研究的任何事物；
•对象实现了数据和操作的结合；
•对象应具有唯一的识别功能；
•对象必须参与一个或一个以上的对象类，从而成为类的实例

2 消息(Messages)和方法(Methods)


消息是用来请求对象执行某一处理或回答某些信息的要求。
方法是描述对象对消息的响应。

消息应当包含：
1) 选择器 实质上是方法名；
2) 一个或多个变量

面向对象的程序运行:
面向对象的程序运行
1) 根据需要创建对象；
2) 一个对象传递消息到另一个对象（或从用户到对象）；
3) 不在需要该对象时，删除并回收它所占用的资源。
例：
对象：CWnd
消息：窗口重绘消息 WM_PAINT
操作：CWnd::OnPaint()


3 类(Class)和类层次(Class Hierarchy)


对象类(类)：具有相同结构、操作，并遵守相同约束规则的对象的聚合。
类说明：类的外部特性或外部接口。
类实现：类的内部表示及类说明的具体实现方法
类层次：一个类的上层可以有超类，下层可以有子类，类的层次结构的一个重要特点就是继承性。

每个子类只有一个超类——类层次结构；
一个子类有一个以上的超类—— 类格结构。







第五节封装性及实现

1 封装性(Encapsulation)
软件模块：
信息隐藏，使软件模块可以象芯片一样被使用。使用者不必知道其实现细节。

封装性定义为：
1）一个清楚的界面，所有的对象的内部软件的范畴被限定在这个边界内；
2）一个接口，这个接口描述这个对象和其他的对象之间的相互作用；
3）受保护的内部实现，这个实现给出了由软件对象提供的功能的细节，实现细节不能在定义这个对象的类的外面访问。

封装的目的：将对象的使用者和对象的设计者分开，使用者不必知道对象实现的细节，只须用设计者提供的消息来访问对象。


封装使得软件模块化、构件化。

2 类的说明
事物：属性和行为。
类：数据成员与成员函数（即方法）。
类与类型：抽象数据类型
抽象数据类型：信息隐藏，隐藏实现细节和不允许外部访问的部分。
类成员（数据成员及成员函数）：公有的(public)和私有的(private)两类。
类的说明形式：

class 类名标识符 {
    private：
    私有成员说明
    protected：
    保护成员说明
    public：
    公有成员说明
}


例1 计数器类说明
//File counter.h
class counter
{
private:
unsigned int value; // 私有数据成员
public:
counter(void);
void increment(void);
void decrement(void);
unsigned int getvalue(void);
};

数据成员：描述对象的内部数据结构；
成员函数：用于操作对象的数据成员。
类的实现：成员函数的实现。
成员函数定义形式：
返回类型 类名：：成员函数名（形式参数说明）
{ 函数体
}

例2 文件counter.cpp给出了类counter中的各成员函数的实现。
//cuunter.cpp
#include "counter.h"

counter::counter(void) {value=0;} // 构造函数(Constructor)

void counter::increment(void) { if (value<9999) value++;}
void counter::decrement(void) { if (value>0) value--;}
unsigned int counter::getvalue(void) { return value;}

//counter.hpp
class counter
{
private:
unsigned int value; public:
counter(void) {value=0;}
void increment(void) { if (value<9999) value++;}
void decrement(void) { if (value>0) value--;}
unsigned int getvalue(void) { return value;}
};

类的说明：头文件.h；
类的实现：.cpp。
类说明和类实现：.hpp
创建对象（类的实例化）：
counter c1,c2;
引用对象的成员：
c1.increment();
c1.getvalue();
例3 计数器类的简单应用
#include <iostream.h>
#include "counter.h"
void main()
{ counter c1,c2;
for(int i=1; i<5; i++)
{ c1.increment();
cout<<"c1="<<c1.getvalue()<<"\n";
c2.increment();
}
c2.decrement();
cout<<"The final value of c1="<<c1.getvalue()<<"\n";
cout<<"The final value of c2="<<c2.getvalue()<<"\n";
}

 

第六节继承性及实现

1 继承性(Inheritance)


继承性：是自动地共享类、子类和对象中的方法和数据的机制，它是面向对象技术所独有的。
继承的传递性：如果C1继承C2，C2继承C3，则C1（间接）继承C3。



多重继承：一个子类具有多个超类时，它可以继承它们的结构和方法。
解决继承“冲突”的方法：
1）子类在发生“冲突”时，立即请求重新定义有冲突的实例变量名或方法名；
2）采用“线性化”继承层次的方法，实质上就是将多重继承暂作“单继承”处理。

派生类（子类）：从任何已存在的类派生的新类。
基类（父类）：用于派生新类的类。
单继承：从一个基类派生的继承。
多重继承（多继承）：从多个基类派生类的继承

在C++类中的成员：public、private和protected。
派生类中不能直接访问基类的private成员。
protected成员可被派生类直接访问，但在基类和派生类之外都是不可见的。

定义派生类的形式：
class 派生类名：访问控制 基类名
{
…
}；



访问控制为public时，基类中所有的public和protected成员被派生类成员继承为自己的protected成员；

访问控制为private时，基类中所有的public和protected成员被派生类成员继承为自己的private成员。

派生类对象可当作基类的对象一样使用
派生类是基类的一个超集

class Base
{
//各种成员
}
class Derived: public Base
{
//各种成员
}
void main()
{
Derived d;
Base b;
b=d; //类对象转换
}


例1 类counter的派生类,上限为max_value的计数器类。
//File counter3.hpp
class counter
{ private:
unsigned int value;
public:
counter(void) {value=0;}
void increment(void){ if (value<9999) value++;}
void decrement(void){ if (value>0) value--;}
unsigned int getvalue(void) { return value;}
};

class limited_counter: public counter
{ private:
int max_value;
public:
limited_counter(int max) { max_value=max; }
void increment(void)
{ if (counter::getvalue()<max_value) counter::increment();}
};


补充： 多态性(Polymorphism)
多态性:允许把同一消息发送给超类及其子类不同对象的能力。
多态性作用：允许超类及各子类的对象各自以不同的方法响应同一消息，即所谓的“同一接口，多种方法”。
编译时的多态性—— 静态连编：编译时就将对象和方法的代码连接起来，其优点是执行速度快，所需内存小，缺点是灵活性差；
运行时的多态性—— 动态连编：运行时才按照具体的数据类型和参量数来确定将哪个方法同对象连接起来，其优点是具有相当大的灵活性，有利于建立类库，便于重用和扩充。

多态性与继承层次相结合，使软件具有更广泛的重用性和可扩充性

例子：鼠标绘图程序
CAnnotation
Virtual BOOL Draw(CDC *pDC)=0;
CAnnLine
CAnnEllipse

CAnnImageView::AnnDraw(CDC *pDC)
{ CAnnotation *pAnn;
……

pAnn->Draw(pDC);
……
}

作业：3.15（书p107）(三角矩阵减法)

本章部分基于王浩的《面向对象程序设计》，并不用于任何商业用途。