数据结构与算法分析第1章.ppt

《数据结构与算法分析第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、程。问题看作函数，算法就是将输入转换为输出。一个问题可以用多种算法来解决。算法的性质：正确性、具体步骤、确定性、有限性、可终止性。程序：使用某种程序设计语言对一种算法的具体实现