《浙江万里学院计算机系》由会员分享，可在线阅读，更多相关《浙江万里学院计算机系（26页珍藏版）》请在金锄头文库上搜索。
1、浙江万里学院计算机系,1,数据结构课件,第1章 绪论 第2讲 2004年9月,浙江万里学院计算机系,2,本讲主要内容,1.3 C+语言复习1.4 算法描述与分析,浙江万里学院计算机系,3,1.4 算法描述与分析,1.4.1 什么是算法 1.4.2 算法描述工具选用+ 1.4.3 算法分析技术,浙江万里学院计算机系,4,1.4.1 什么是算法,算法(algorithm)是对特定问题求解步骤的一种描述，是指令的有限序列。 描述算法需要一种工具（语言），可以是自然语言、数学语言或是某种计算机语言。,浙江万里学院计算机系,5,算法的五个重要特性,(1) 输入： 一个算法应该有一个或多个输入。 (2)有
2、穷性： 一个算法必须在执行有穷步骤之后正常结束，而不能形成无穷循环。 (3) 确定性： 每一条指令必须有确切的含义，不能产生多义性。 (4) 可行性： 每一条指令必须是切实可执行的，即原则上可以通过已经实现的基本运算执行有限次来实现。 (5) 输出： 一个算法应有零个或多个输出，是同输入有某个特定关系的量。,浙江万里学院计算机系,6,1.4.2 算法描述工具-C+,(1) 问题的规模尺寸用MAXSIZE表示， (2) 数据元素类型一般写成ElemType， 需要预先定义例如：const MAXSIZE =100 ;typedef int ElemType ;ElemType SMAXSIZE;
3、,浙江万里学院计算机系,7,1.4.2 算法描述工具-C+,(3) 一个算法以函数形式的给出：类型标识符 函数名（形参表）语句组,例如：int sum( int a, int b ) c=a+b;return c;,浙江万里学院计算机系,8,再如： 算法1.1,void simsort( ar a , int n ) for (i=1; in; i+)for (j=i; j=n; j+)if (ai.data aj.data) m=ai; ai=aj; aj=m; for (i=1; i=n; i+)couti“ ”ai.num；cout“ ” ai.dataendl; ,浙江万里学院计算机系
4、,9,1.4.3 算法分析技术,1. 问题的规模 所谓问题的规模是指算法中数据元素的数量，下文常用小写字母n来表示。2.空间 所谓算法的空间代价（或称空间复杂性）指的是：当问题的规模以某种单位由1增至n时，解决该问题的算法实现所占用的空间也以某种单位由1增至f(n)。则称该算法的空间代价是f(n)。,浙江万里学院计算机系,10,1.4.3 算法分析技术,3. 时间 (1)语句频度(frequency count)是指在一个算法中,该条语句重复执行的次数。 写成关于问题规模n的函数: f(n) 。,浙江万里学院计算机系,11,算法1.2 分析,1: float pingjun( float a
5、, int n ) 2: int i; float sum, pv; 3: sum=0; 4: for (i=0; in; i+) 5: sum=sum+ai; 6: pv=sum/n; 7: return pv; 8: ,语句3:的语句频度是1，语句5:的语句频度是n,浙江万里学院计算机系,12,1.4.3 算法分析技术,(2)算法的渐近时间复杂度(1asymptotic time complexity)依据算法中最大语句频度来估算，它是问题规模n的某个函数f(n)。： 记作 : T(n)=O(f(n) 简称时间复杂度。,浙江万里学院计算机系,13,分析下列3个算法(片段),(a) x=x+
6、1;语句频度 :1 时间复杂度:T(n)=O(1) (b) for(i=1; i=n; i+) x=x+1;语句频度:n 时间复杂度:T(n)=O(n) (c) for (j=1; j=n; j+)for (k=1; k=n; k+) x=x+1;语句频度:n2 时间复杂度:T(n)=O(n2),浙江万里学院计算机系,14,分析算法1.1,void simsort( ar a , int n ) for (i=1; in; i+)for (j=i; j=n; j+)if (ai.data aj.data) m=ai; ai=aj; aj=m; for (i=1; i=n; i+)couti“
7、”ai.num“ ” ai.data n2/22. 忽略常系数 n2/2 - n2,最大 语句频度：,3. 所以算法的时间复杂度:T(n)=O(n2),浙江万里学院计算机系,16,浙江万里学院计算机系,17,1.4.3 算法分析技术,研究分析算法的时间复杂度， 是研究随着问题规模n的逐渐增大， 时间消耗的增长趋势（很快、缓慢、很少）。,几个述语：问题的规模: n 语句频度: f(n)时间复杂度: T(n)=O( f(n) ),浙江万里学院计算机系,18,1.3 C+语言简介,1.3.1 基本输入/输出 1.3.2 函数与参数传递 1.3.3 函数模版与函数重载 1.3.4 结构体及运用 1.3
8、.5 类的基本概念及运用 1.3.6 运算符重载,浙江万里学院计算机系,19,作业: 习题一 4，5,复习，今天内容 再复习c+ 预习 第2章 线性表,浙江万里学院计算机系,20,1.3 C+语言,1.3.1 基本输入/输出 图书档案类问题、 棋类对奕问题、 交通或通信网问题、,浙江万里学院计算机系,21,1.3 C+语言,1.3.2 函数与参数传递 图书档案类问题、 棋类对奕问题、 交通或通信网问题、,浙江万里学院计算机系,22,1.3 C+语言,1.3.3 函数模版与函数重载 图书档案类问题、 棋类对奕问题、 交通或通信网问题、,浙江万里学院计算机系,23,1.3 C+语言,1.3.4 结构体及运用 图书档案类问题、 棋类对奕问题、 交通或通信网问题、,浙江万里学院计算机系,24,1.3 C+语言,1.3.5 类的基本概念及运用 图书档案类问题、 棋类对奕问题、 交通或通信网问题、,浙江万里学院计算机系,25,1.3 C+语言,1.3.6 运算符重载 图书档案类问题、 棋类对奕问题、 交通或通信网问题、,浙江万里学院计算机系,26,研究内容包括数据的逻辑结构、数据在计算机内的存储结构以及定义在它们之上的一组运算。 数据结构是专业基础课、核心课 ADT DT OOP,“数据结构”课程,
