数据结构-第9章-数据机构应用实例.pptxVIP

9.1抽象数据类型与程序设计第9章排序抽象数据类型(abstructdatatype,ADT)是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性没变，都不影响其外部的使用。由此，可以说抽象数据类型实行封装和信息隐蔽，独立于计算机。

9.2从问题到程序的求解过程第9章排序鉴于抽象数据类型在程序设计中的特点，用计算机解决现实中的问题时，我们可采用以下的步骤。1．问题分析首先应该充分地分析和理解问题，明确问题要求做什么，限制条件是什么。准确、完整地理解和描述问题是解决问题的第一步。2．数据类型与系统设计在设计这一步骤中需分概要设计和详细设计两步实现。概要设计指的是，对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。详细设计则为定义相应的存储结构并写出各过程和函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。

9.2从问题到程序的求解过程第9章排序3．编码编码是把详细设计的结果进一步求精为程序设计语言程序。4．测试在测试阶段，要尽可能地排除逻辑错误。一种方法是首先使用能得出已知结果的有效输入数据，来测试对象的各个方法。如果某些数据有值域，则测试该值域的端点值。例如，若n的输入值域为1~10，则一定要测试n为1和10的情况。另外，要用无效的数据来测试程序的错误检测能力。尝试一些随机数据，最后尝试一些实际数据。

9.3应用实例第9章排序问题：图书管理设计一个程序完成学校图书馆中新书入库，废旧图书的清除，图书信息的查询等操作。【问题分析】1.图书馆中的图书是有序组织的，除第一本和最后一本图书，图书馆中的每一本图书都有惟一的一个前驱和惟一的一个后继。2.需要完成图书的插入、删除、查找等操作。3.在做插入操作时需要输入插入数据的位置和数据值；做删除操作时需输入删除数据的位置；做查找操作时需要输入待查数据的值。4.每执行一项操作，都应显示操作是否正确以及操作后的内容。

9.3应用实例第9章排序【概要设计】根据图书馆中图书的特点，我们用线性表组织图书，程序的功能包括：（1）在线性表的任意位置插入数据；（2）在线性表的任意位置删除数据；（3）在线性表中查找某一数据在表中的位置。1．为了实现上述功能，首先需定义线性表的抽象数据类型：ADTLinkList{数据对象：D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0}数据关系：R={ai,ai+1|ai,ai+1∈D}

9.3应用实例第9章排序基本操作：InitLinkList(L)操作结果：构造一个空的线性表L。InsLinkList(L,pos,e)初始条件：线性表L已存在。操作结果：将数据e插入到线性表L的pos位置。DelLinkList(L,pos,e)初始条件：线性表L已存在。操作结果：将线性表L中pos位置的数据删除，被删数据置入e中返回。LocLinkList(L,e)初始条件：线性表L已存在。操作结果：在线性表L中查找是否存在数据e，若存在，返回该数据在表中的位置。若不存在，返回-1。Menu()操作结果：在屏幕上显示操作菜单。

9.3应用实例第9章排序2．本程序通过7个函数，实现系统的功能。（1）主函数main()（2）初始化线性表表函数InitLinkList()（3）显示操作菜单函数menu()（4）显示线性表内容函数dispLinkList()（5）插入数据函数InsLinkList()（6）删除数据函数DelLinkList()（7)查找数据函数LocLinkList()各函数间关系如图9-1所示：图9-1函数间的关系