欢迎来到天天文库
浏览记录
ID:49412379
大小:241.50 KB
页数:10页
时间:2020-02-06
《数据结构与算法分析第1章.ppt》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、数据结构与算法分析APracticalIntroductiontoDataStructuresandAlgorithmAnalysis陈星第1章数据结构和算法-课程学习目的介绍常用的数据结构,为高效数据处理提供工具。增强“权衡”(Tradeoff)概念,讨论每类数据结构的代价和效益。数据结构或算法有效性的评估方法。最终目的:有效地组织数据,获得高效的数据处理。第1章数据结构和算法1.1.1学习数据结构的必要性数据结构:一类数据的表示及相关操作。用数据结构组织数据更有效的算法.更强大的计算机更复杂的应用.更
2、复杂的应用更多和更复杂的计算.复杂的计算算法偏离日常生活经验更远不同的数据结构不同的计算效率算法的效率一种算法能在所要求的资源限制(Resourceconstraint)内将问题解决好,则称算法是有效率的.空间(内存空间限制或外存空间限制)时间算法的代价是指算法消耗的资源量。选择数据结构的步骤选择数据结构的步骤:分析问题,以确定任何算法均会遇到的资源限制。确定必须支持的基本操作,并度量每种操作所受到的资源限制。选择最接近这些开销的数据结构。1.1.2代价与效益每一种数据结构都有代价和效益。几乎没有一种数据
3、结构在任何情况下都比其它数据结构好。每一种数据结构都需要:-数据存储空间-基本操作计算时间-编写程序代码1.2抽象数据类型和数据结构类型(Type):一组值的集合。数据类型(DataType):一种类型和定义在该类型上的一组操作。抽象数据类型(AbstractDataType,ADT):数据结构作为一个软件组件的实现.-每一个ADT操作由它的输入和输出定义.-封装(Encapsulation):隐藏数据类型的实现细节.ADT的封装举例:汽车采用ADT的目的:将复杂问题抽象化,从而重视主要问题而忽略不必要的细节。
4、数据结构数据结构是ADT的实现。数据结构通常指存储在计算机内存中的数据。文件结构指外存储器中数据的组织。数据项有逻辑形式和物理形式两个方面。由ADT给出的数据项的定义是它的逻辑形式。例:数学意义上的整数。数据结构中对数据项的实现是它的物理形式。例:16位(32位)整数。数据类型ADT:类型操作数据项:逻辑形式数据项:物理形式数据结构:存储空间子程序1.3问题、算法和程序问题:需要完成的任务一组输入就有一组相应的输出。问题的定义应该包含对任何可行方案所需资源的限制。问题数学函数算法:解决问题的一种方法或者一个过
5、程。问题看作函数,算法就是将输入转换为输出。一个问题可以用多种算法来解决。算法的性质:正确性、具体步骤、确定性、有限性、可终止性。程序:使用某种程序设计语言对一种算法的具体实现
此文档下载收益归作者所有