高级的数据表示

1、张张 华华2012年02月 张华 武汉大学2第三讲第三讲 高级的数据表示高级的数据表示在一个较高的层次上讨论程序设计的问题在一个较高的层次上讨论程序设计的问题如何设计和创建一个良好的软件工程？如何设计和创建一个良好的软件工程？切入点：研究程序中数据的表示方式。切入点：研究程序中数据的表示方式。动态数组动态数组链表链表抽象数据类型的设计、实现和应用抽象数据类型的设计、实现和应用为学习面向对象程序设计做好思想上的准备。为学习面向对象程序设计做好思想上的准备。常用的抽象数据类型：常用的抽象数据类型：列表列表队列队列栈栈C+C+语言程序设计语言程序设计2012年02月 张华 武汉大学3数据表示数据表示

2、数据表示数据表示程序设计的关键部分是程序表示数据的方式。程序设计的关键部分是程序表示数据的方式。正确地表示数据能够使程序中其他部分的编写变得简单。正确地表示数据能够使程序中其他部分的编写变得简单。例如，职工工资管理程序例如，职工工资管理程序 工资可以用工资可以用C语言固有的数据类型：单精度浮点数来表示。语言固有的数据类型：单精度浮点数来表示。 一组工资可以用数组来表示。一组工资可以用数组来表示。 职工工资表该如何表示呢？职工工资表该如何表示呢？必要的时候需要设计新的数据类型。必要的时候需要设计新的数据类型。例如，职工工资管理程序例如，职工工资管理程序 定义表示职工工资记录的数据类型（自定义的结

3、构体类型）。定义表示职工工资记录的数据类型（自定义的结构体类型）。 用职工工资记录数组来表示职工工资表。用职工工资记录数组来表示职工工资表。高级的数据表示高级的数据表示2012年02月 张华 武汉大学4案例分析：程序的演进案例分析：程序的演进问题：个人观影记录程序问题：个人观影记录程序写一个程序来管理个人一年中看过的所有电影的列表。写一个程序来管理个人一年中看过的所有电影的列表。分析和设计分析和设计每一部电影有多项数据：每一部电影有多项数据：片名、发行年份、导演、主演、片长片名、发行年份、导演、主演、片长个人评价个人评价那么，可以定义一个结构体类型来表示包含上述数据的电那么，可以定义一个结构体

4、类型来表示包含上述数据的电影记录类型。影记录类型。然后，可以用一个电影类型的结构体变量来保存一部电影然后，可以用一个电影类型的结构体变量来保存一部电影的信息，用一个结构体数组保存电影列表。的信息，用一个结构体数组保存电影列表。为了简化，我们只保存片名和个人评价（为了简化，我们只保存片名和个人评价（09级）级）高级的数据表示高级的数据表示2012年02月 张华 武汉大学5案例分析：程序的演进案例分析：程序的演进实现一实现一用结构体数组保存列表用结构体数组保存列表（FilmList1.cpp）#include #include const int TITLESIZE=51; /片名的最大长度片名的

5、最大长度const int LISTSIZE=5; /最大的影片数最大的影片数/表示电影信息，即电影列表中的一个项目表示电影信息，即电影列表中的一个项目struct MyFilm char titleTITLESIZE; int rating;高级的数据表示高级的数据表示2012年02月 张华 武汉大学6案例分析：程序的演进案例分析：程序的演进实现一实现一void main() MyFilm filmListLISTSIZE; /电影列表电影列表 int i=0; cout“请输入第一部电影的片名：请输入第一部电影的片名：endl; cin.getline(filmListi.title, T

6、ITLESIZE); while (iLISTSIZE & filmListi.title0!=0) cout请输入你的评价等级（请输入你的评价等级（09）：）：filmListi.rating; cin.get(); i+; cout“请输入第请输入第”(i+1)“部电影的片名：部电影的片名：endl; cin.getline(filmListi.title, TITLESIZE); 高级的数据表示高级的数据表示2012年02月 张华 武汉大学7案例分析：程序的演进案例分析：程序的演进实现一实现一 /输出提示信息输出提示信息 if (i=0) cout你没有输入有效的数据！你没有输入有效的数

7、据！endl; else cout下面是你输入的电影列表：下面是你输入的电影列表：endl; /输出列表中的电影信息输出列表中的电影信息 for (int j=0; ji; j+) coutsetw(TITLESIZE+1)setiosflags(ios:left) filmListj.titlefilmListj.ratingendl; coutnBye!endl;高级的数据表示高级的数据表示2012年02月 张华 武汉大学8案例分析：程序的演进案例分析：程序的演进实现一实现一运行结果运行结果请输入第一部电影的片名：请输入第一部电影的片名：星球大战星球大战请输入你的评价等级（请输入你的评价等

8、级（09）：）：7请输入第请输入第2部电影的片名：部电影的片名：江山美人江山美人请输入你的评价等级（请输入你的评价等级（09）：）：7请输入第请输入第3部电影的片名：部电影的片名：集结号集结号请输入你的评价等级（请输入你的评价等级（09）：）：8请输入第请输入第4部电影的片名：部电影的片名：下面是你输入的电影列表：下面是你输入的电影列表：星球大战星球大战 7江山美人江山美人 7集结号集结号 8Bye!高级的数据表示高级的数据表示2012年02月 张华 武汉大学9案例分析：程序的演进案例分析：程序的演进存在的问题存在的问题程序可能浪费大量内存空间。程序可能浪费大量内存空间。保存电影列表的数组的长

9、度必须在编译时确定。保存电影列表的数组的长度必须在编译时确定。当这个值设的太大时，可能某些人一年内没看几部电影。当这个值设的太大时，可能某些人一年内没看几部电影。列表容量有限。列表容量有限。修改数据的表示方式修改数据的表示方式采用动态数组来保存列表。采用动态数组来保存列表。高级的数据表示高级的数据表示2012年02月 张华 武汉大学10案例分析：程序的演进案例分析：程序的演进实现二实现二用动态结构体数组保存列表用动态结构体数组保存列表（FilmList2.cpp）const int TITLESIZE=51; /片名的最大长度片名的最大长度/表示电影信息，即电影列表中的一个项目表示电影信息，即

10、电影列表中的一个项目struct MyFilm char titleTITLESIZE; int rating;void main() MyFilm *filmList; /指向电影列表的指针指向电影列表的指针 int LISTSIZE; /比较接近实际需求的最大影片数量比较接近实际需求的最大影片数量 int i=0;高级的数据表示高级的数据表示2012年02月 张华 武汉大学11案例分析：程序的演进案例分析：程序的演进实现二实现二实现二分析实现二分析只是推迟了确定数组长度的时间，存储的问题依然存在。只是推迟了确定数组长度的时间，存储的问题依然存在。 coutLISTSIZE; cin.get

11、(); filmList = new MyFilmLISTSIZE; /动态创建保存列表的数组动态创建保存列表的数组 delete filmList; coutnBye!endl;高级的数据表示高级的数据表示2012年02月 张华 武汉大学12案例分析：程序的演进案例分析：程序的演进实现三实现三用链表来保存列表用链表来保存列表（FilmList3.cpp）struct MyFilm char titleTITLESIZE; int rating; MyFilm *next; /指向下一个结构体，为指向下一个结构体，为NULL时表示后面没有结构体了时表示后面没有结构体了;Star Wars8Ti

12、tanic7头指针头指针高级的数据表示高级的数据表示头节点头节点节点节点链链2012年02月 张华 武汉大学13案例分析：程序的演进案例分析：程序的演进实现三实现三#include #include #include const int TITLESIZE=51; /片名的片名的最大长度最大长度struct MyFilm char titleTITLESIZE; int rating; MyFilm *next; /指向下一个结构体，为指向下一个结构体，为NULL时表示后面没有结构体了时表示后面没有结构体了;void main() MyFilm *filmList; /链表的头指针，链表的头指

13、针，指向第一个结构体指向第一个结构体 MyFilm *cur, *pre; char titleTITLESIZE;高级的数据表示高级的数据表示2012年02月 张华 武汉大学14案例分析：程序的演进案例分析：程序的演进实现三实现三 filmList = NULL; /头指针为头指针为NULL，表示列表是空的，表示列表是空的 /读取数据，创建列表读取数据，创建列表 cout请输入第一个电影的片名：请输入第一个电影的片名：next = cur;高级的数据表示高级的数据表示2012年02月 张华 武汉大学15案例分析：程序的演进案例分析：程序的演进实现三实现三 cur-next=NULL; str

14、cpy(cur-title, title); cout请输入你的评价等级（请输入你的评价等级（09）：）：cur-rating; cin.get(); pre = cur; /更新更新pre指针指针 cout请输入下一个电影的片名：请输入下一个电影的片名：endl; cin.getline(title, TITLESIZE); 高级的数据表示高级的数据表示2012年02月 张华 武汉大学16案例分析：程序的演进案例分析：程序的演进实现三实现三 /输出列表输出列表 if (filmList=NULL) cout你没有输入有效的数据！你没有输入有效的数据！endl; else cout下面是你输入

15、的电影列表：下面是你输入的电影列表：endl; cur = filmList; while (cur!=NULL) coutsetw(TITLESIZE+1)setiosflags(ios:left) titleratingnext; 高级的数据表示高级的数据表示2012年02月 张华 武汉大学17案例分析：程序的演进案例分析：程序的演进实现三实现三 /释放内存释放内存 cur = filmList; while (cur!=NULL) pre = cur; cur = pre-next; delete pre; coutnBye!endl;高级的数据表示高级的数据表示2012年02月 张华

16、武汉大学18案例分析：程序的演进案例分析：程序的演进思考：程序演进的驱动力和方向思考：程序演进的驱动力和方向实现三较好的解决了存储的问题。实现三较好的解决了存储的问题。但是，实现三还不是一个好的软件工程。因为它（的设计但是，实现三还不是一个好的软件工程。因为它（的设计思想）应对新需求的能力不足。思想）应对新需求的能力不足。例如，新的功能需求：可以删除一条观影记录。例如，新的功能需求：可以删除一条观影记录。 状况：实现三没有提供从电影列表中删除一部电影记录的功能。状况：实现三没有提供从电影列表中删除一部电影记录的功能。 应对：可以增加删除项目的代码。应对：可以增加删除项目的代码。 后果：函数的代

17、码增加，可读性更差。后果：函数的代码增加，可读性更差。随着需求的增加，电影列表程序将何去何从？随着需求的增加，电影列表程序将何去何从？既然不足的根源在于设计思想，那么有必要采用更合适的既然不足的根源在于设计思想，那么有必要采用更合适的设计思想。设计思想。高级的数据表示高级的数据表示2012年02月 张华 武汉大学19案例分析：程序的演进案例分析：程序的演进程序设计和开发的问题之一：如何应对需求的变化。程序设计和开发的问题之一：如何应对需求的变化。最初设计程序时就应该考虑便于以后扩充（修改）程序。最初设计程序时就应该考虑便于以后扩充（修改）程序。前面的设计和实现过程未遵循此原则。前面的设计和实现

18、过程未遵循此原则。设计的误区：把编码的细节和概念模型混在一起。设计的误区：把编码的细节和概念模型混在一起。此案例的概念模型是：此案例的概念模型是： 创建电影列表创建电影列表 往列表中添加电影往列表中添加电影 显示列表显示列表考虑设计一个数据类型考虑设计一个数据类型列表。列表。一个列表不仅可以存储若干数据项，（数据存储）一个列表不仅可以存储若干数据项，（数据存储）还提供添加、删除、遍历等操作。（数据操作）还提供添加、删除、遍历等操作。（数据操作）怎样设计兼顾数据存储和操作的数据表示方式？怎样设计兼顾数据存储和操作的数据表示方式？高级的数据表示高级的数据表示2012年02月 张华 武汉大学20数据

19、表示数据表示数据抽象数据抽象寻找正确的数据表示方式常常不仅仅是从存储数据的角度寻找正确的数据表示方式常常不仅仅是从存储数据的角度考虑选择一种数据类型，还必须考虑对数据要做哪些必要考虑选择一种数据类型，还必须考虑对数据要做哪些必要的操作。的操作。例如，例如，C+语言中整数和指针的语言中整数和指针的*运算运算例如，职工工资管理程序例如，职工工资管理程序 求工资表中的工资总额、平均值。求工资表中的工资总额、平均值。 按工资高低对表中的记录进行排序。按工资高低对表中的记录进行排序。可以把所需的操作编写为函数来实现。可以把所需的操作编写为函数来实现。那么，设计数据类型包括确定如何存储数据，以及设计一那么

20、，设计数据类型包括确定如何存储数据，以及设计一系列函数来管理数据。系列函数来管理数据。最好采用系统的方法来定义数据类型。最好采用系统的方法来定义数据类型。高级的数据表示高级的数据表示2012年02月 张华 武汉大学21数据抽象数据抽象类型包括两个部分：一个属性集和一个操作集。类型包括两个部分：一个属性集和一个操作集。例如，例如，int类型类型它的属性是它表示一个整数值，因此它拥有整数的属性。它的属性是它表示一个整数值，因此它拥有整数的属性。它允许的算术操作是改变一个它允许的算术操作是改变一个int数的符号、两个数的符号、两个int数相加、两个数相加、两个int数相减等。数相减等。声明一个变量为

21、声明一个变量为int类型，就意味着它可以保存一个整数值，并且只类型，就意味着它可以保存一个整数值，并且只能进行上述操作。能进行上述操作。定义一个数据类型定义一个数据类型首先，要确定存储数据的方式。首先，要确定存储数据的方式。其次，要确定操作数据的方式。其次，要确定操作数据的方式。高级的数据表示高级的数据表示数据结构数据结构+算法算法2012年02月 张华 武汉大学22数据抽象数据抽象定义新数据类型的过程包括以下几个步骤定义新数据类型的过程包括以下几个步骤为类型的属性和可对该类型数据执行的操作提供一个抽象为类型的属性和可对该类型数据执行的操作提供一个抽象的描述。的描述。不应受特定的实现和编程语言

22、的约束。不应受特定的实现和编程语言的约束。这种正式的抽象描述被称为这种正式的抽象描述被称为抽象数据类型抽象数据类型（Abstract Data Type，ADT）。构造该构造该ADT的编程接口。的编程接口。即说明如何存储数据，并描述用于执行所需操作的函数集合。即说明如何存储数据，并描述用于执行所需操作的函数集合。例如，提供一个结构体类型的定义，同时提供用来操作该类结构体例如，提供一个结构体类型的定义，同时提供用来操作该类结构体的函数的原型。的函数的原型。编写代码实现这个接口。编写代码实现这个接口。高级的数据表示高级的数据表示2012年02月 张华 武汉大学23案例分析：从抽象到具体案例分析：从

23、抽象到具体问题问题个人观影记录程序。个人观影记录程序。分析分析需要一个电影列表。需要一个电影列表。列表中的每个项目包括片名和评价等级。列表中的每个项目包括片名和评价等级。能在列表的末尾添加新项目，和显示列表内容。能在列表的末尾添加新项目，和显示列表内容。高级的数据表示高级的数据表示2012年02月 张华 武汉大学24案例分析：从抽象到具体案例分析：从抽象到具体设计设计定义一个抽象数据类型：列表定义一个抽象数据类型：列表属性：保存一个项目序列属性：保存一个项目序列操作：操作： 把列表初始化为空列表把列表初始化为空列表 确定列表是否为空确定列表是否为空 确定列表是否已满确定列表是否已满 确定列表中

24、项目的个数确定列表中项目的个数 向列表末尾添加项目向列表末尾添加项目 遍历列表，处理列表中每个项目遍历列表，处理列表中每个项目 清空列表清空列表高级的数据表示高级的数据表示2012年02月 张华 武汉大学25案例分析：从抽象到具体案例分析：从抽象到具体实现实现第四种实现的程序文件结构第四种实现的程序文件结构xlist.h 电影结构体类型的定义电影结构体类型的定义 列表数据类型编程接口的定义（属性集的定义，操作函数的声明）列表数据类型编程接口的定义（属性集的定义，操作函数的声明）xlist.cpp 列表数据类型编程接口的实现（操作函数的定义）列表数据类型编程接口的实现（操作函数的定义）FilmL

25、ist4.cpp 利用列表数据类型解决个人观影记录管理问题的程序利用列表数据类型解决个人观影记录管理问题的程序高级的数据表示高级的数据表示2012年02月 张华 武汉大学26案例分析：从抽象到具体案例分析：从抽象到具体构造接口构造接口（xlist.h）描述数据如何表示描述数据如何表示描述实现描述实现ADT操作的函数操作的函数#ifndef _XLIST_H_#define _XLIST_H_/特定于程序的声明特定于程序的声明/const int TITLESIZE=51; /存放片名的数组长度存放片名的数组长度/表示一部电影的信息表示一部电影的信息struct MyFilm char titl

26、eTITLESIZE; int rating;高级的数据表示高级的数据表示2012年02月 张华 武汉大学27案例分析：从抽象到具体案例分析：从抽象到具体构造接口构造接口/一般类型定义一般类型定义/Item是列表中的项目类型是列表中的项目类型typedef MyFilm Item;/表示列表的链表存储结构中的一个节点表示列表的链表存储结构中的一个节点struct Node Item item; Node *next;/XList是列表类型是列表类型typedef Node * XList;高级的数据表示高级的数据表示2012年02月 张华 武汉大学28案例分析：从抽象到具体案例分析：从抽象到具

27、体构造接口构造接口/函数原型函数原型/操操 作：初始化一个列表作：初始化一个列表/操作前：操作前：list引用一个列表引用一个列表/操作后：该列表操作后：该列表被被初始化为空列表初始化为空列表void InitializeList(XList &list);/操操 作：确定列表是否为空列表作：确定列表是否为空列表/操作前：操作前：list引用一个已初始化的列表引用一个已初始化的列表/操作后：如果该列表为空则返回操作后：如果该列表为空则返回true，否则返回，否则返回falsebool ListIsEmpty(const XList &list);/操操 作：确定列表是否已满作：确定列表是否已满

28、/操作前：操作前：list引用一个已初始化的列表引用一个已初始化的列表/操作后：如果该列表已满则返回操作后：如果该列表已满则返回true，否则返回，否则返回falsebool ListIsFull(const XList &list);高级的数据表示高级的数据表示2012年02月 张华 武汉大学29案例分析：从抽象到具体案例分析：从抽象到具体构造接口构造接口/操操 作：确定列表中项目的个数作：确定列表中项目的个数/操作前：操作前：list引用一个已初始化的列表引用一个已初始化的列表/操作后：返回列表中项目的个数操作后：返回列表中项目的个数unsigned int ListItemCount(c

29、onst XList &list);/操操 作：在列表的尾部添加一个项目作：在列表的尾部添加一个项目/操作前：操作前：item是要被添加到列表的项目是要被添加到列表的项目/ list引用一个已初始化的列表引用一个已初始化的列表/操作后：如果可能的话，在列表的尾部添加一个新项目，操作后：如果可能的话，在列表的尾部添加一个新项目，/ 成功则返回成功则返回true，否则返回，否则返回falsebool AppendItem(Item item, XList &list);/操操 作：作：遍历列表，遍历列表，把一个函数作用于列表中的每个项目把一个函数作用于列表中的每个项目/操作前：操作前：list引用

30、一个已初始化的列表引用一个已初始化的列表/ pFun指向一个函数，该函数接受一个指向一个函数，该函数接受一个Item引用参数，引用参数，/ 并且无返回值并且无返回值/操作后：操作后：pFun指向的函数被作用到列表中的每一个项目一次指向的函数被作用到列表中的每一个项目一次void Traverse(const XList &list, void (*pFun)(const Item &item);高级的数据表示高级的数据表示2012年02月 张华 武汉大学30案例分析：从抽象到具体案例分析：从抽象到具体构造接口构造接口/操操 作：释放已分配的内存作：释放已分配的内存/操作前：操作前：list引用

31、一个已初始化的列表引用一个已初始化的列表/操作后：为该列表分配的内存已被释放，操作后：为该列表分配的内存已被释放，/ 且该列表被置为空列表且该列表被置为空列表void ClearList(XList &list);#endif高级的数据表示高级的数据表示2012年02月 张华 武汉大学31案例分析：从抽象到具体案例分析：从抽象到具体使用新数据类型使用新数据类型（FilmList4.cpp）使用抽象数据类型的程序不需要知道该类型接口的实现细使用抽象数据类型的程序不需要知道该类型接口的实现细节。节。用伪代码表示程序的算法用伪代码表示程序的算法创建创建XList变量变量filmList创建一个创建一

32、个Item变量变量film初始化列表初始化列表filmList为空表为空表当列表当列表filmList不满且有有效的输入时重复执行下面的操作不满且有有效的输入时重复执行下面的操作把输入的新数据放进把输入的新数据放进film把把film添加到列表添加到列表filmList的末尾的末尾顺序访问列表顺序访问列表filmList中每一个项目中每一个项目film，并显示其内容，并显示其内容高级的数据表示高级的数据表示2012年02月 张华 武汉大学32案例分析：从抽象到具体案例分析：从抽象到具体使用新数据类型使用新数据类型#include #include #include #include “xlis

33、t.hvoid ShowFilm(const Item &item); /显示一个列表项目的内容显示一个列表项目的内容void main() XList filmList; Item film;高级的数据表示高级的数据表示2012年02月 张华 武汉大学33案例分析：从抽象到具体案例分析：从抽象到具体使用新数据类型使用新数据类型 /初始化列表初始化列表 InitializeList(filmList); if (ListIsFull(filmList) cout错误：内存不足！错误：内存不足！endl; exit(1); /读取数据，创建列表读取数据，创建列表 cout“请输入第一请输入第一部

34、部电影的片名：电影的片名：endl; cin.getline(film.title, TITLESIZE); while (film.title0!=0) cout请输入你的评价等级（请输入你的评价等级（09）：）：film.rating; cin.get();高级的数据表示高级的数据表示2012年02月 张华 武汉大学34案例分析：从抽象到具体案例分析：从抽象到具体使用新数据类型使用新数据类型 if (!AppendItem(film, filmList) cout错误：分配内存错误！错误：分配内存错误！endl; break; if (ListIsFull(filmList) cout错误

35、：列表已满！错误：列表已满！endl; break; cout“请输入下一请输入下一部部电影的片名：电影的片名：endl; cin.getline(film.title, TITLESIZE); 高级的数据表示高级的数据表示2012年02月 张华 武汉大学35案例分析：从抽象到具体案例分析：从抽象到具体使用新数据类型使用新数据类型 /输出列表输出列表 if (ListIsEmpty(filmList) cout你没有输入有效的数据！你没有输入有效的数据！endl; else cout下面是你输入的电影列表：下面是你输入的电影列表：endl; /遍历列表，并用遍历列表，并用ShowFilm()函

36、数显示每一个项目函数显示每一个项目 Traverse(filmList, ShowFilm); cout你一共输入了你一共输入了ListItemCount(filmList)部电影。部电影。endl;高级的数据表示高级的数据表示2012年02月 张华 武汉大学36案例分析：从抽象到具体案例分析：从抽象到具体使用新数据类型使用新数据类型 /清除清除 ClearList(filmList); coutnBye!endl;void ShowFilm(const Item &film) coutsetw(TITLESIZE+1)setiosflags(ios:left) film.titlefilm.

37、ratingendl;高级的数据表示高级的数据表示2012年02月 张华 武汉大学37案例分析：从抽象到具体案例分析：从抽象到具体实现接口实现接口（xlist.cpp）为接口中声明的函数编写代码。为接口中声明的函数编写代码。#include #include “xlist.h/把把Item项目拷贝到列表的一个项目拷贝到列表的一个Node节点的节点的item成员中成员中static void CopyToNode(const Item &item, Node &node);void InitializeList(XList &list) list = NULL;bool ListIsEmpty(

38、const XList &list) if (list=NULL) return true; else return false;高级的数据表示高级的数据表示2012年02月 张华 武汉大学38案例分析：从抽象到具体案例分析：从抽象到具体实现接口实现接口bool ListIsFull(const XList &list) Node *pNode = new Node; if (pNode=NULL) return true; else delete pNode; return false; 高级的数据表示高级的数据表示2012年02月 张华 武汉大学39案例分析：从抽象到具体案例分析：从抽象到

39、具体实现接口实现接口unsigned int ListItemCount(const XList &list) unsigned int count=0; Node *pNode = list; while (pNode != NULL) count+; pNode = pNode-next; return count;高级的数据表示高级的数据表示2012年02月 张华 武汉大学40案例分析：从抽象到具体案例分析：从抽象到具体实现接口实现接口bool AppendItem(Item item, XList &list) Node *pNewNode, *pNode=list; pNewNode

40、 = new Node; if (pNewNode = NULL) return false; CopyToNode(item, *pNewNode); pNewNode-next = NULL; if (pNode = NULL) list = pNewNode;高级的数据表示高级的数据表示2012年02月 张华 武汉大学41案例分析：从抽象到具体案例分析：从抽象到具体实现接口实现接口 else while (pNode-next != NULL) pNode = pNode-next; pNode-next = pNewNode; return true;高级的数据表示高级的数据表示201

41、2年02月 张华 武汉大学42案例分析：从抽象到具体案例分析：从抽象到具体实现接口实现接口void Traverse(const XList &list, void (*pFun)(const Item &item) Node *pNode = list; while (pNode != NULL) pFun(pNode-item); pNode = pNode-next; 高级的数据表示高级的数据表示2012年02月 张华 武汉大学43案例分析：从抽象到具体案例分析：从抽象到具体实现接口实现接口void ClearList(XList &list) Node *pNode = list, *

42、pTemp; while (pNode != NULL) pTemp = pNode; pNode = pNode-next; delete pTemp; static void CopyToNode(const Item &item, Node &node) node.item = item; /结构体直接赋值实现拷贝结构体直接赋值实现拷贝高级的数据表示高级的数据表示2012年02月 张华 武汉大学44案例分析：从抽象到具体案例分析：从抽象到具体比较电影列表的第三种和第四种实现比较电影列表的第三种和第四种实现ADT的优点的优点第四种实现表达程序的方式是根据要解决的问题，而不是第四种实现表达程

43、序的方式是根据要解决的问题，而不是根据解决问题所需的低级工具。根据解决问题所需的低级工具。可读性好。可读性好。都使用相同的数据结构（动态分配的链表）。都使用相同的数据结构（动态分配的链表）。但是第三种实现暴露了所有的编程细节。但是第三种实现暴露了所有的编程细节。 分配内存、重置指针等分配内存、重置指针等而第四种实现隐藏了这些细节，并使用与任务直接相关的语言来表而第四种实现隐藏了这些细节，并使用与任务直接相关的语言来表达程序。达程序。 创建列表、向列表添加项目等创建列表、向列表添加项目等高级的数据表示高级的数据表示2012年02月 张华 武汉大学45案例分析：从抽象到具体案例分析：从抽象到具体比

44、较电影列表的第三种和第四种实现比较电影列表的第三种和第四种实现ADT的优点的优点xlist.h和和xlist.cpp共同组成可重用的资源。共同组成可重用的资源。如果需要另一个列表，仍然可以使用这些文件。如果需要另一个列表，仍然可以使用这些文件。例如，构造联系人列表，只需重新定义例如，构造联系人列表，只需重新定义xlist.h中的中的Itemstruct Person char name20; char relationShip20; char address50; char phone20;typedef struct Person Item;高级的数据表示高级的数据表示2012年02月 张华

45、 武汉大学46案例分析：从抽象到具体案例分析：从抽象到具体比较电影列表的第三种和第四种实现比较电影列表的第三种和第四种实现ADT的优点的优点编程接口是根据抽象的操作来定义的，而不是根据特定的编程接口是根据抽象的操作来定义的，而不是根据特定的数据表示和算法定义的。那么，可以自由地修改接口的实数据表示和算法定义的。那么，可以自由地修改接口的实现而不用改动最后的程序。现而不用改动最后的程序。例如，可以用数组来保存电影列表例如，可以用数组来保存电影列表需要修改需要修改xlist.cpp，但是不用修改使用列表的程序（但是不用修改使用列表的程序（FilmList4.cpp）。）。#define MAXSI

46、ZE 100struct list Item entriesMAXSIZE; int items;typedef struct list XList;高级的数据表示高级的数据表示2012年02月 张华 武汉大学47案例分析：从抽象到具体案例分析：从抽象到具体比较电影列表的第三种和第四种实现比较电影列表的第三种和第四种实现ADT的优点的优点程序便于维护，灵活应对需求的变更。程序便于维护，灵活应对需求的变更。如果有些功能运行不正常，可以将问题集中到一个函数上。如果有些功能运行不正常，可以将问题集中到一个函数上。如果想用更好的办法来完成一个任务，比如添加项目，则只需重新如果想用更好的办法来完成一个任

47、务，比如添加项目，则只需重新编写那一个函数。编写那一个函数。如果需要增加新的属性或操作，则修改抽象数据类型即可。如果需要增加新的属性或操作，则修改抽象数据类型即可。高级的数据表示高级的数据表示2012年02月 张华 武汉大学48案例分析：从抽象到具体案例分析：从抽象到具体数据抽象是向面向对象编程跨越的思想基础。数据抽象是向面向对象编程跨越的思想基础。面向对象的思想通过对象把数据抽象的观点发展得更远。面向对象的思想通过对象把数据抽象的观点发展得更远。例如，对象封装了属性集和操作集，对象之间有继承关系等。例如，对象封装了属性集和操作集，对象之间有继承关系等。面向对象程序的模块化具有更高级的抽象，便

48、于构造大型面向对象程序的模块化具有更高级的抽象，便于构造大型程序。程序。例如，程序由若干个类的定义组成，一个类包含了一组数据的定义例如，程序由若干个类的定义组成，一个类包含了一组数据的定义和对这些数据进行操作的算法实现。和对这些数据进行操作的算法实现。高级的数据表示高级的数据表示2012年02月 张华 武汉大学49常用的抽象数据类型常用的抽象数据类型列表类抽象数据类型列表类抽象数据类型对列对列（Queue）项目只能在列表的一端被添加，在列表的另一端被删除。项目只能在列表的一端被添加，在列表的另一端被删除。是一种先进先出（是一种先进先出（FIFO）的数据形式。）的数据形式。栈栈（Stack）项目

49、只能在列表的一端被添加和删除。项目只能在列表的一端被添加和删除。 项目被描述成项目被描述成“压入压入”栈和栈和“弹出弹出”栈。栈。是一种后进先出（是一种后进先出（LIFO）的数据形式。）的数据形式。高级的数据表示高级的数据表示2012年02月 张华 武汉大学50案例分析：队列案例分析：队列队列的抽象定义队列的抽象定义定义一个抽象数据类型：队列定义一个抽象数据类型：队列属性：保存一个规则的项目序列属性：保存一个规则的项目序列操作：操作： 把队列初始化为空队列把队列初始化为空队列 确定队列是否为空确定队列是否为空 确定队列是否已满确定队列是否已满 确定队列中项目的个数确定队列中项目的个数 向队列尾

50、端添加项目向队列尾端添加项目 从队列首端删除项目从队列首端删除项目 清空队列清空队列高级的数据表示高级的数据表示2012年02月 张华 武汉大学51案例分析：队列案例分析：队列队列的应用举例队列的应用举例假设小王在商业街上设了一个提供建议的摊位假设小王在商业街上设了一个提供建议的摊位”金点金点子子”。顾客可购买一分钟、两分钟或三分钟的建议。为确。顾客可购买一分钟、两分钟或三分钟的建议。为确保交通通畅，商业街规定排成一队等待的顾客数目最多为保交通通畅，商业街规定排成一队等待的顾客数目最多为10。假设顾客的出现是随机的，并且他们花在咨询上的时。假设顾客的出现是随机的，并且他们花在咨询上的时间随机分

51、布于三种选择。间随机分布于三种选择。那么小王平均每小时要接待多少顾客？每位顾客平均要等那么小王平均每小时要接待多少顾客？每位顾客平均要等多长时间？队伍平均有多长？多长时间？队伍平均有多长？高级的数据表示高级的数据表示2012年02月 张华 武汉大学52案例分析：队列案例分析：队列队列的应用举例：队列的应用举例：“金点子金点子”摊位摊位用队列来模拟解决问题。用队列来模拟解决问题。定义队列中的项目定义队列中的项目typedef struct Customer long arrive; /一位顾客加入队列的时间一位顾客加入队列的时间 int processTime; /该顾客需要的咨询时间该顾客需要

52、的咨询时间 Item;高级的数据表示高级的数据表示2012年02月 张华 武汉大学53案例分析：队列案例分析：队列队列的应用举例：队列的应用举例：“金点子金点子”摊位摊位定义和实现队列的接口定义和实现队列的接口xqueue.hxqueue.cpptypedef Customer Item; /队列中的项目队列中的项目typedef Node * XQueue; /队列队列void InitializeQueue(XQueue &queue);bool QueueIsEmpty(const XQueue &queue);bool QueueIsFull(const XQueue &queue);

53、unsigned int QueueItemCount(const XQueue &queue);bool AppendQueueItem(Item item, XQueue &queue);bool DeleteQueueItem(Item &item, XQueue &queue);void Traverse(const XQueue &queue, void (*pFun)(Item &item);void EmptyQueue(XQueue &queue);高级的数据表示高级的数据表示2012年02月 张华 武汉大学54案例分析：队列案例分析：队列队列的应用举例：队列的应用举例：“金点

54、子金点子”摊位摊位用队列来模拟摊位的等候队伍用队列来模拟摊位的等候队伍设计算法设计算法让时钟每一分钟嘀嗒一次。让时钟每一分钟嘀嗒一次。在每分钟里，检查是否有一位新的顾客到来。在每分钟里，检查是否有一位新的顾客到来。如果有一个新的顾客到来并且队列未满，则将此顾客添加到队列。如果有一个新的顾客到来并且队列未满，则将此顾客添加到队列。 包括顾客到达的时间：当前时钟已嘀嗒的次数包括顾客到达的时间：当前时钟已嘀嗒的次数 和他需要咨询的时间：和他需要咨询的时间：1、2或或3分钟分钟如果队列已满，就拒绝此顾客加入。如果队列已满，就拒绝此顾客加入。为了做统计，需要保存顾客的总数、被拒绝的顾客数。为了做统计，需

55、要保存顾客的总数、被拒绝的顾客数。高级的数据表示高级的数据表示2012年02月 张华 武汉大学55案例分析：队列案例分析：队列队列的应用举例：队列的应用举例：“金点子金点子”摊位摊位设计算法设计算法如果队列非空且摊主未被前面的顾客占用，则删除位于队列首端的如果队列非空且摊主未被前面的顾客占用，则删除位于队列首端的项目，即开始为一个顾客提供服务。项目，即开始为一个顾客提供服务。通过比较顾客加入队列的时间和当前时间，就可以得到此顾客在队通过比较顾客加入队列的时间和当前时间，就可以得到此顾客在队列中等待的时间。列中等待的时间。此顾客的咨询时间将决定占用摊主的时间。用一个变量来跟踪此时此顾客的咨询时间

56、将决定占用摊主的时间。用一个变量来跟踪此时间。如果摊主正忙（正为一个顾客提供咨询服务），没人可以间。如果摊主正忙（正为一个顾客提供咨询服务），没人可以“出出列列”。那么，该变量的值必须随时钟的嘀嗒递减。那么，该变量的值必须随时钟的嘀嗒递减。高级的数据表示高级的数据表示2012年02月 张华 武汉大学56案例分析：队列案例分析：队列队列的应用举例：队列的应用举例：“金点子金点子”摊位摊位主程序主程序（GoodIdea.cpp）#include #include #include #include queue.h#define MIN_PER_HOUR 60#define MAX-OF_LINE

57、10/有新顾客来吗？有新顾客来吗？bool NewCustomer(double x);/设置顾客的参数设置顾客的参数Item CustomerTime(long when);高级的数据表示高级的数据表示2012年02月 张华 武汉大学57案例分析：队列案例分析：队列队列的应用举例：队列的应用举例：“金点子金点子”摊位摊位主程序主程序void main() Queue line; Item customer; int hours; /模拟的小时数模拟的小时数 int perHour; /每小时顾客的平均数每小时顾客的平均数 long cycle, cycleLimit; /循环计数器和计数器的

58、上界循环计数器和计数器的上界 long turnaways = 0; /因队列已满而被拒绝的顾客数因队列已满而被拒绝的顾客数 long customers = 0; /被加入队列的顾客数被加入队列的顾客数 long served = 0; /在模拟期间得到服务的顾客数在模拟期间得到服务的顾客数 long sum_line = 0; /累计的队列长度累计的队列长度 int wait_time = 0; /从当前到摊主空闲所需的时间从当前到摊主空闲所需的时间 double min_per_customer; /顾客到来的平均间隔时间顾客到来的平均间隔时间 long line_wait = 0; /

59、队列累计等待时间队列累计等待时间高级的数据表示高级的数据表示2012年02月 张华 武汉大学58案例分析：队列案例分析：队列队列的应用举例：队列的应用举例：“金点子金点子”摊位摊位主程序主程序 InitializeQueue(line); srand(time(0); cout案例研究：案例研究：“金点子金点子”摊位摊位endl; cout输入模拟的时间（小时数）：输入模拟的时间（小时数）：hours; cycleLimit = MIN_PER_HOUR * hours; cout输入每小时顾客的平均数：输入每小时顾客的平均数：perHour; min_per_customer = MIN_PER_HOUR / perHour;高级的数据表示高级的数据表示2012年02月 张华 武汉大学59案例分析：队列案例分析：队列队列的应用举例：队列的应用举例：“金点子金点子”摊位摊位主程序主程序 /时钟每一分钟嘀嗒一次时钟每一分钟嘀嗒一次 for (cycle=0; cycle=MAX_OF_LINE) turnaways+; else customers+; customer = CustomerTime(cycle); AppendQueueItem(customer, line); 高级的数据表示高级的数据表示2012年02月 张华 武汉大学60案例分析：队列