《数据结构与算法》课件.ppt

逐步求精的程序设计过程 解：(1)算法是一个死循环,违反了算法的有穷性特征。 (2)算法包含除零错误,违反了算法的可行性特征。 算法的评价（设计准则） 正确性 除了应该满足算法说明中写明的“功能”之外，应对各组典型的带有苛刻条件的输入数据得出正确的结果 。 健壮性 算法应对非法输入的数据作出恰当反映或进行相应处理，一般情况下，应向调用它的函数返回一个表示错误或错误性质的值。 可读性 易于理解、实现和调试。 高效性 执行时间短（时间效率）、占用存储空间少（空间效率） 时间复杂度 一般用算法中语句被执行的次数来表示算法的时间效率（算法的时间复杂度）。 【例1-8】分析下面程序段的时间复杂度。 (1) int i,sum=0; (2) for(i=0;in;i++) (3) sum=sum+i; (4) return sum; T(n)=2n+3，且T(n)是n数量级的。 渐进时间复杂度：忽略次要语句的执行次数，只对重要的语句（原操作）和执行最频繁的语句进行计数，同时对计算结果只取其最高次幂，且略去系数不写。 渐近时间复杂度常简称为时间复杂度，用“大o”表示。 T(n)=2n+3=O(n) （1次） （n+1次） （n次） （1次） 也就是只求出T(n)的最高阶,忽略其低阶项和常系数,这样既可简化T(n)的计算,又能比较客观地反映出当n很大时,算法的时间性能。 例如,T(n)=3n2-5n+10000=O(n2) 本质上讲，是一种最高数量级的比较 一个没有循环的算法的基本运算次数与问题规模n无关,记作O(1),也称作常数阶。 一个只有一重循环的算法的基本运算次数与问题规模n的增长呈线性增大关系,记作O(n),也称线性阶。 其余常用的还有平方阶O(n2)、立方阶O(n3)、对数阶O(log2n)、指数阶O(2n)等。 各种不同数量级对应的值存在着如下关系： O(1)O(log2n)O(n)O(n*log2n)O(n2)O(n3)O(2n)O(n!) 【例1-9】 　分析以下算法的时间复杂度。 int fun(int n) { int i,j,k,s; s=0; for (i=0;i=n;i++) for (j=0;j=n;j++) for (k=0;k=n;k++) s++; return(s); } 基本语句或基本操作 解：该算法的基本操作是语句s++,其频度： T(n)=O(n3) 则该算法的时间复杂度为O(n3)。 数据结构与算法 前期课程 数据结构 计算机基础 C/C++语言 离散数学 线性代数 后期课程 操作系统 计算机组成原理编译原理 数据库原理 软件工程 计算机网络 承上启下 计算机科学课程体系 C/C++语言 数据结构 软件工程 掌握基本编程方法 掌握数据组织和数据处理的方法 掌握大型软件开发方法 学习识字 学习写作文 学习写小说 基本要求 课程关系 与语文学习过程类比 动手能力（上机） 1.1数据结构研究的内容 随着计算机技术的发展，计算机应用的范围更广，所处理的数据更复杂。如果要提高数据处理的效率，就必须研究数据本身的特性、数据之间的关系，已经如何有效地将数据组织存储在计算机内。 理论课 问题 数学模型 数据结构 抽象数据类型 源程序 实验课 数据结构课程的内容 课程设计 用计算机解决具体问题大致需要下列几个步骤： 1）首先从具体问题抽象出一个数学模型； 2）然后设计一个解此数学模型的算法； 3）最后编写程序、测试、调整直至最终解答。 寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。例如，求解预报人口增长情况的数学模型为微分方程。然而，更多的非数值计算问题无法用数学方程加以描述。下面请看三个例子。 【例1-1】公司员工信息管理。 某公司要用计算机管理员工信息。要求做以下操作： 当招聘新员工时，能够把员工信息添加进来； 当有员工辞职时，能够删除该员工信息； 可以修改员工信息； 能够以某种方式检索员工信息。 员工号 姓名 性别 年龄 住址 电话 所属部门 01