《数据结构-第9章-数据机构应用实例.pptx》由会员分享，可在线阅读，更多相关《数据结构-第9章-数据机构应用实例.pptx（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构 新世纪应用型高等教育新世纪应用型高等教育计算机类课程规划教材计算机类课程规划教材新世纪应用型高等教育教材编审委员会新世纪应用型高等教育教材编审委员会 组编组编 主编主编 曹春萍曹春萍9.1 抽象数据类型与程序设计第第9 9章章排排 序序抽象数据类型抽象数据类型(abstruct data type,ADT)是指一个数学模型以及定义在该模型上是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性没变
2、，都不影如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性没变，都不影响其外部的使用。由此，可以说抽象数据类型实行封装和信息隐蔽，独立于计算机。响其外部的使用。由此，可以说抽象数据类型实行封装和信息隐蔽，独立于计算机。9.2 从问题到程序的求解过程第第9 9章章排排 序序鉴于抽象数据类型在程序设计中的特点，用计算机解决现实中的问题时，我们可采用以鉴于抽象数据类型在程序设计中的特点，用计算机解决现实中的问题时，我们可采用以下的步骤。下的步骤。1 1问题分析问题分析问题分析问题分析首先应该充分地分析和理解问题，明确问题要求做什么，限制条件是什么。准确、完整首先应该充分地分析和理解问题，
3、明确问题要求做什么，限制条件是什么。准确、完整地理解和描述问题是解决问题的第一步。地理解和描述问题是解决问题的第一步。2 2数据类型与系统设计数据类型与系统设计数据类型与系统设计数据类型与系统设计在设计这一步骤中需分概要设计和详细设计两步实现。概要设计指的是，对问题描述中在设计这一步骤中需分概要设计和详细设计两步实现。概要设计指的是，对问题描述中 涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程 序模块和各抽象数据类型。详细设计则为定义相应的存储结构并写出各过程和函数的伪码序模块和各
4、抽象数据类型。详细设计则为定义相应的存储结构并写出各过程和函数的伪码 算算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。9.2 从问题到程序的求解过程第第9 9章章排排 序序3 3编码编码编码编码编码是把详细设计的结果进一步求精为程序设计语言程序。编码是把详细设计的结果进一步求精为程序设计语言程序。4 4测试测试测试测试在测试阶段，要尽可能地排
5、除逻辑错误。一种方法是首先使用能得出已知结果的有效输在测试阶段，要尽可能地排除逻辑错误。一种方法是首先使用能得出已知结果的有效输入数据，来测试对象的各个方法。如果某些数据有值域，则测试该值域的端点值。例如，若入数据，来测试对象的各个方法。如果某些数据有值域，则测试该值域的端点值。例如，若n的输入值域为的输入值域为110，则一定要测试，则一定要测试n为为1和和10的情况。另外，要用无效的数据来测试程序的错的情况。另外，要用无效的数据来测试程序的错误检测能力。尝试一些随机数据，最后尝试一些实际数据误检测能力。尝试一些随机数据，最后尝试一些实际数据。9.3 应用实例第第9 9章章排排 序序问题问题问
6、题问题：图书管理图书管理图书管理图书管理设计一个程序完成学校图书馆中新书入库，废旧图书的清除，图书信息的查询等操作。设计一个程序完成学校图书馆中新书入库，废旧图书的清除，图书信息的查询等操作。【问题分析问题分析问题分析问题分析】1.图书馆中的图书是有序组织的，除第一本和最后一本图书，图书馆中的每一本图书都图书馆中的图书是有序组织的，除第一本和最后一本图书，图书馆中的每一本图书都有惟一的一个前驱和惟一的一个后继。有惟一的一个前驱和惟一的一个后继。2.需要完成图书的插入、删除、查找等操作。需要完成图书的插入、删除、查找等操作。3.在做插入操作时需要输入插入数据的位置和数据值；做删除操作时需输入删除
7、数据的在做插入操作时需要输入插入数据的位置和数据值；做删除操作时需输入删除数据的位置；做查找操作时需要输入待查数据的值。位置；做查找操作时需要输入待查数据的值。4.每执行一项操作，都应显示操作是否正确以及操作后的内容。每执行一项操作，都应显示操作是否正确以及操作后的内容。9.3 应用实例第第9 9章章排排 序序【概要设计概要设计】根据图书馆中图书的特点，我们用线性表组织图书，程序的功能包括根据图书馆中图书的特点，我们用线性表组织图书，程序的功能包括：（1）在线性表的任意位置插入数据）在线性表的任意位置插入数据；（2）在线性表的任意位置删除数据）在线性表的任意位置删除数据；（3）在线性表中查找某
8、一数据在表中的位置。）在线性表中查找某一数据在表中的位置。1为了实现上述功能，首先需定义线性表的抽象数据类型：为了实现上述功能，首先需定义线性表的抽象数据类型：ADT LinkList 数据对象：数据对象：D=ai|ai IntegerSet,i=0,1,2,n,n0数据关系：数据关系：R=|ai,ai+1 D9.3 应用实例第第9 9章章排排 序序基本操作：基本操作：InitLinkList(&L)操作结果：构造一个空的线性表操作结果：构造一个空的线性表L。InsLinkList(&L,pos,e)初始条件：线性表初始条件：线性表L已存在。已存在。操作结果：将数据操作结果：将数据e插入到线性
9、表插入到线性表L的的pos位置。位置。DelLinkList(&L,pos,&e)初始条件：线性表初始条件：线性表L已存在。已存在。操作结果：将线性表操作结果：将线性表L中中pos位置的数据删除，被删数据置入位置的数据删除，被删数据置入e中返回。中返回。LocLinkList(L,e)初始条件：线性表初始条件：线性表L已存在。已存在。操作结果：在线性表操作结果：在线性表L中查找是否存在数据中查找是否存在数据e，若存在，返回该数据在表，若存在，返回该数据在表中的位置。若不存在，返回中的位置。若不存在，返回-1。Menu()操作结果：在屏幕上显示操作菜单。操作结果：在屏幕上显示操作菜单。9.3 应用实例第第9 9章章排排 序序2本程序通过本程序通过7个函数，实现系统的功能。个函数，实现系统的功能。（1）主函数主函数main()（2）初始化线性表表函数初始化线性表表函数InitLinkList()（3）显示操作菜单函数显示操作菜单函数menu()（4）显示线性表内容函数显示线性表内容函数dispLinkList()（5）插入数据函数插入数据函数InsLinkList()（6）删除数据函数删除数据函数DelLinkList()（7)查找数据函数查找数据函数LocLinkList()各函数间关系如图各函数间关系如图9-1所示：所示：图图9-1 函数间的关系函数间的关系感谢收看