大学计算机重要课程第一章绪论.ppt

《大学计算机重要课程第一章绪论.ppt》由会员分享，可在线阅读，更多相关《大学计算机重要课程第一章绪论.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数数 据据 结结 构构计算机工程学院计算机工程学院郑如滨郑如滨网络教研室网络教研室 407 407课程介绍课程介绍n课程名称：数据结构课程名称：数据结构n教材：教材：数据结构数据结构(C语言版语言版)，严蔚敏，严蔚敏 吴伟民吴伟民 编著，清华大学出版社，编著，清华大学出版社，2007年年4月月n教学方式：授课（教学方式：授课（54）+上机实践（上机实践（18）ndatastructurendatastructure课程考核方式课程考核方式n考核方式：期末闭卷考核方式：期末闭卷60%，平时成绩，平时成绩40%。平时成绩组成：平时成绩组成：n考勤考勤:缺勤缺勤1/3直接取消考试资格。请假需课前提前

2、通知教师直接取消考试资格。请假需课前提前通知教师（电话或假条的方式）。无故未到一次，扣（电话或假条的方式）。无故未到一次，扣10%。n作业作业：未交一次，扣未交一次，扣10%。未认真完成作业，敷衍交作业，一次未认真完成作业，敷衍交作业，一次10%抄袭作业，一次抄袭作业，一次20%绝对禁止上课前，写本课程的作业。绝对禁止上课前，写本课程的作业。n实验：平时实验：平时+最终的实验报告，以平时课堂上检查为主。完成最终的实验报告，以平时课堂上检查为主。完成情况良好，可加分。情况良好，可加分。n平时表现：课堂回答问题、作业完成情况等、好的问题均可加平时表现：课堂回答问题、作业完成情况等、好的问题均可加分

3、。分。n加分项可部分与扣分项相抵加分项可部分与扣分项相抵n问题：课堂、课后、电子邮件问题：课堂、课后、电子邮件参考书籍参考书籍n编程类：编程类：高质量高质量C+编程编程 专解疑难杂症专解疑难杂症n算法类：算法类：算法导论算法导论(建议：仅供查询建议：仅供查询)程序员实用算法程序员实用算法 代码较详细，对很多数据结代码较详细，对很多数据结构有详细的实现代码构有详细的实现代码 Andrew Binstock、John Rex、陈宗斌陈宗斌 机械工业出版社机械工业出版社(建议：仅供查询建议：仅供查询)n参考书籍参考书籍(深入深入)：算法与数据结构算法与数据结构，傅清祥，傅清祥 王晓东王晓东 编著，电

4、子编著，电子工业出版社，工业出版社，2001数据结构与算法分析数据结构与算法分析C语言描述语言描述M，（美）（美）Mike Allen Weiss著，机械工业出版社，著，机械工业出版社，2004算法导论算法导论(第二版第二版)，Thomas H.Cormen等著，等著，高等教育出版社，高等教育出版社，2002注意事项：今天回去的作业，自己复习注意事项：今天回去的作业，自己复习nC+语言基础，尤其是指针部分最为重要，还有语言基础，尤其是指针部分最为重要，还有结构体、引用部分结构体、引用部分。c语言教科书：错误调试语言教科书：错误调试n常见问题：常见问题：=与与=，引用参数，引用参数&(c+中的中

5、的)的使用。的使用。n上交的作业应包含几部分内容：上交的作业应包含几部分内容：班级，学号，姓名班级，学号，姓名作业不清楚的地方及时提问，善用作业不清楚的地方及时提问，善用baidu等搜索引等搜索引擎擎本课件内快速查找信息请按：本课件内快速查找信息请按：CTRL+F建议每个同学申请网络存储空间，如：金山快盘。建议每个同学申请网络存储空间，如：金山快盘。用于存储自己的常用代码与文档用于存储自己的常用代码与文档学习委员职责学习委员职责n1.收作业，按学号排序。统计未缴同学名单。收作业，按学号排序。统计未缴同学名单。n2.汇总同学的问题与意见，提交给老师。汇总同学的问题与意见，提交给老师。课程结构课程

6、结构n第一部分第一部分：(第第1章章)基本概念基本概念数据结构、逻辑结构、存储结构、抽数据结构、逻辑结构、存储结构、抽象数据类型象数据类型n第二部分第二部分：(第第27章章)各种基本类型的数据结构各种基本类型的数据结构线性表、栈、队列、线性表、栈、队列、串、数组、广义表、树、二叉树和图串、数组、广义表、树、二叉树和图n第三部分第三部分：(第第911章章)讨论查找和排序的各种实现方法及其综合分析比较讨论查找和排序的各种实现方法及其综合分析比较学完该课程后应该掌握的能力学完该课程后应该掌握的能力n1.手写代码或者伪代码的能力。手写代码或者伪代码的能力。n2.利用伪代码或者自然语言描述自己想法的能力

7、利用伪代码或者自然语言描述自己想法的能力n3.熟练掌握基本数据结构的特性，并能利用基本熟练掌握基本数据结构的特性，并能利用基本数据结构思考问题、解决问题。数据结构思考问题、解决问题。n4.了解基本算法了解基本算法第第1章章 绪论绪论n学习要点学习要点:熟悉各名词、术语的含义熟悉各名词、术语的含义掌握基本概念，特别是数据的逻辑结构和存储结构掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系之间的关系了解抽象数据类型的定义、表示和实现方法了解抽象数据类型的定义、表示和实现方法理解算法五个要素的确切含义理解算法五个要素的确切含义掌握计算语句频度和估算算法时间复杂度的方法掌握计算语句频度和估算算法

8、时间复杂度的方法n用计算机解决问题的步骤？用计算机解决问题的步骤？从具体问题抽象出适当的数学模型从具体问题抽象出适当的数学模型设计求解此模型的算法设计求解此模型的算法编出程序实现编出程序实现n如何编写出一个如何编写出一个“好好”的程序？的程序？必须：必须：分析待处理对象的特征以及它们之间的关系分析待处理对象的特征以及它们之间的关系 建立数学模型建立数学模型nNiklaus Wirth：Data Structures+Algorithm=Programs处理问题的策略处理问题的策略问题的数学模型问题的数学模型1.1 什么是数据结构什么是数据结构n非数值计算问题非数值计算问题例例1 书目自动检索系

9、统书目自动检索系统书目文件按书名按作者名按分类号索引表线性表例例2 人机对奕问题人机对奕问题树.例例3 多叉路口交通灯管理问题多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图 数据结构数据结构是一门研究非数值计算的程序设计问题中计算机是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。的操作对象以及它们之间的关系和操作等等的学科。n数据结构的发展简史及其在计算机科学中所处的地位数据结构的发展简史及其在计算机科学中所处的地位n“数据结构数据结构”作为一门独立的课程在国外是从作为一门独立的课程在国外是从1968年才开始设年才

10、开始设立的，立的，1968年美国唐年美国唐欧欧克努特教授开创了数据结构的最初体克努特教授开创了数据结构的最初体系，他所著的系，他所著的计算机程序设计技巧计算机程序设计技巧第一卷第一卷基本算法基本算法是是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。作。n20世纪世纪60年代末到年代末到70年代初：程序设计的实质是选择一种好的年代初：程序设计的实质是选择一种好的结构，加上设计一种好的算法结构，加上设计一种好的算法(DS+Algorithm)n20世纪世纪70年代中期到年代中期到80年代初：迅速发展年代初：迅速发展地位：地位：n“数

11、据结构数据结构”在计算机科学中是一门综合性的专业基础课。在计算机科学中是一门综合性的专业基础课。n数据结构是介于数学、计算机硬件和计算机软件三者之间的一数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。门核心课程。n数据结构这一门课的内容不仅是一般程序设计（特别是非数值数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现性程序设计）的基础，而且是设计和实现编译程序、操作系统、编译程序、操作系统、数据库系统数据库系统及其他系统程序的重要基础。及其他系统程序的重要基础。1.2 基本概念和术语基本概念和术语n数据数据(Data)：P4 所有能所有

12、能被输入被输入到计算机中，且能被计算机到计算机中，且能被计算机处理的符处理的符号号的集合。的集合。是是计算机操作的对象计算机操作的对象的总称。的总称。是计算机处理的是计算机处理的信息的信息的某种特定的符号某种特定的符号表示形式表示形式。n数据元素数据元素(Data Element)：是数据（集合）中的一个是数据（集合）中的一个“个体个体”。是数据结构中讨论的是数据结构中讨论的基本基本单位。单位。数据项数据项：是数据结构中讨论的：是数据结构中讨论的最小最小单位。单位。不可再分割不可再分割 数据元素可以是数据项的集合。数据元素可以是数据项的集合。例如：描述一本书的书目信息为一个数据元素，可例如：描

13、述一本书的书目信息为一个数据元素，可以以n数据对象数据对象(Data Object)：性质相同性质相同的数据元素的集合。如，整数的数据元素的集合。如，整数n数据结构数据结构(Data Structure)：P5 相互之间相互之间存在一种或多种特定关系存在一种或多种特定关系的数据元素的集的数据元素的集合。合。登录号登录号书名书名作者名作者名分类号分类号数据元素数据元素数据项数据项结构结构.例例4 假设用三个假设用三个4位的十进制数表示一个含位的十进制数表示一个含12位数位数的十进制数。的十进制数。不同的不同的“关系关系”构成不同的构成不同的“结构结构”数据结构的数据结构的形式定义形式定义：二元组

14、：二元组Data_Structure=(D,S)n其中，其中，D是数据元素的有限集，是数据元素的有限集，S是是D上关系的有限上关系的有限集。集。3214,6587,9345 a1(3214),a2(6587),a3(9345)则在数据元素则在数据元素 a1、a2 和和 a3 之间存在着之间存在着“次序次序”关系关系 a1,a2、a2,a3 3214，6587，9345 a1 a2 a3 6587，3214，9345 a2 a1 a3 数据结构是相互之间存在着某种数据结构是相互之间存在着某种逻辑关系逻辑关系的数的数据元素的集合。据元素的集合。逻辑结构逻辑结构集合结构集合结构线性结构线性结构树形结

15、构树形结构图图/网状结构网状结构例例5 linear=(D,R)D=1,2,3,4,5,6,7,8,9,10 R=,例例6 tree=(D,R)D=a,b,c,d,e,f,g,h,i,j,k,l R=,n物理结构物理结构(又称又称存储结构存储结构):(使用计算机处理使用计算机处理.)逻辑结构在存储器中的逻辑结构在存储器中的映像映像。数据元素数据元素的映像：用二进制位的映像：用二进制位(bit)的位串表示数据的位串表示数据元素。如：元素。如：数据元素数据元素之间关系之间关系的映像：的映像：P6 图图n顺序映像顺序映像(顺序存储结构顺序存储结构)：以以相对的存储位置相对的存储位置表示表示后继关系。

16、后继关系。n非顺序映像非顺序映像(链式存储结构链式存储结构)：借助指针元素存储地：借助指针元素存储地址的址的指针指针表示数据元素之间的逻辑关系。表示数据元素之间的逻辑关系。(321)10 =(501)8 =(101000001)2 A =(101)8 =(001000001)2n数据类型数据类型(Data Type)：一个：一个值的集合值的集合和定义在这和定义在这个值集上的个值集上的一组操作一组操作的总称。如，整型变量的总称。如，整型变量.原子类型：其值不可分解。如原子类型：其值不可分解。如C语言中的整型等语言中的整型等结构类型：其值由若干成分按某种结构组成，可以结构类型：其值由若干成分按某种

17、结构组成，可以分解。如数组等分解。如数组等不同类型的变量，其所能取的值的范围不同，不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。所能进行的操作不同。n抽象数据类型抽象数据类型(Abstract Data Type,ADT)：一个：一个数数学模型学模型以及定义在该模型上的以及定义在该模型上的一组操作一组操作。关键关键：使用它的人可以只关心它的逻辑特征，不需：使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式；定义它的人同样不必要关心要了解它的存储方式；定义它的人同样不必要关心它如何存储。它如何存储。分类：原子类型、固定聚合类型、可变聚合类型分类：原子类型、固定聚合类型、可变聚

18、合类型 p8形式定义：三元组形式定义：三元组ADT=(D,S,P)n其中，其中，D是数据对象；是数据对象；S是是D上的关系的集合；上的关系的集合；P是对是对D的基本的基本操作的集合。操作的集合。P9n基本操作的定义格式为：基本操作的定义格式为：基本操作名基本操作名（参数表）（参数表）初始条件初始条件:初始条件描述初始条件描述 操作结果操作结果:操作结果描述操作结果描述两种参数：赋值两种参数：赋值提供输入值提供输入值 引用引用提供输入值、返回操作结果提供输入值、返回操作结果特点：特点：n数据抽象数据抽象：强调的是其本质的特征本质的特征、其所能完成的功能其所能完成的功能以及它和外部用户的接口外部用

19、户的接口（即外界使用它的方法外界使用它的方法）。n数据封装数据封装：将实体的外部特性和其内部实现细节分离外部特性和其内部实现细节分离，并且对对外部用户隐藏其内部实现细节。外部用户隐藏其内部实现细节。1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现n抽象数据类型需要通过抽象数据类型需要通过固有数据类型固有数据类型(高级编程语高级编程语言中已实现的数据类型言中已实现的数据类型)来实现。来实现。n本书相关说明见教材本书相关说明见教材P10P11，简介。，简介。课后作业课后作业n0.用自己的一句话说明白数据结构是什么？并列用自己的一句话说明白数据结构是什么？并列举三个例子说明举三个例子说明pp

20、t上面的三种数据结构分别帮我上面的三种数据结构分别帮我们解决了什么问题（不少于们解决了什么问题（不少于100字）字）n1.查询资料，分别说出：查询资料，分别说出：typedef的用法，并举出一例子的用法，并举出一例子struct结构体的用法，并举出一例子结构体的用法，并举出一例子&引用类型参数引用类型参数(c+)的用法，并举出一例子的用法，并举出一例子指向结构体的指针的用法，并举出一例子指向结构体的指针的用法，并举出一例子指向函数的指针的用法，并举出一例子指向函数的指针的用法，并举出一例子n背面还有背面还有课后作业课后作业n2.试仿照三元组的抽象数据类型试仿照三元组的抽象数据类型(p12)写出

21、抽象数写出抽象数据类型复数据类型复数(内有加法与减法操作内有加法与减法操作)的定义。的定义。并尝试并尝试编写测试程序，可上机进行运行。编写测试程序，可上机进行运行。(加分加分)1.3 算法和算法分析算法和算法分析1.3.1 算法算法n定义：定义：对特定对特定问题求解步骤问题求解步骤的一种描述，它是指令的的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。有限序列，其中每一条指令表示一个或多个操作。n特性：特性：有穷性有穷性：一个算法必须在执行一个算法必须在执行有限有限步骤之后结束步骤之后结束确定性确定性：算法的算法的每一步每一步必须是必须是确切定义确切定义的的,不能产生二义性不能

22、产生二义性可行性可行性：算法是能行的算法是能行的输入输入：一个算法有一个算法有零个零个或或多个多个输入输入输出输出：一个算法有一个算法有至少一个至少一个输出输出注意：注意：算法与程序的算法与程序的区别区别！n算法的描述：算法的描述：自然语言自然语言流程图流程图程序设计语言程序设计语言，如，如C语言语言伪代码伪代码介于自然语言和程序设计语言之间的方介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。令可以结合自然语言来设计。例例7 欧几里德算法欧几里德算法辗转相除法求两个自然数辗转相除法求两个自然数m

23、和和n的最大公约数。的最大公约数。算法描述如下：算法描述如下：n自然语言：自然语言：输入输入m和和n；求求m除以除以n的余数的余数r；若若r等于等于0，则，则n为最大公约数，算法结束；否为最大公约数，算法结束；否则执行第则执行第步；步；将将n的值放在的值放在m中，将中，将r的值放在的值放在n中；中；重新执行第重新执行第步。步。n流程图：流程图：N开始输入m和n r=m%nr=0m=n；n=r 输出n结束Yn程序设计语言：程序设计语言：n伪代码：伪代码：1.r=m%n;2.循环直到循环直到r=0;2.1 m=n;2.2 n=r;2.3 r=m%n;3.输出输出n;#includeint Comm

24、onFactor(int m,int n)int r=m%n;while(r!=0)m=n;n=r;r=m%n;return n;n算法的评价算法的评价衡量算法优劣的标准衡量算法优劣的标准正确性正确性(correctness):n满足具体问题的需求满足具体问题的需求可读性可读性(readability)：n易读、易理解易读、易理解健壮性健壮性(robustness):n当输入数据非法时，算法能够做出反应或进行处理当输入数据非法时，算法能够做出反应或进行处理效率与低存储量效率与低存储量:n执行时间短、存储空间小执行时间短、存储空间小算法效率的度量算法效率的度量n算法效率的度量算法效率的度量时间代

25、价时间代价：算法在计算机上运行时消耗的时间来度量。有两：算法在计算机上运行时消耗的时间来度量。有两种方法：种方法：n事后统计的方法事后统计的方法：利用计算机内部计时功能，进行计时统计。：利用计算机内部计时功能，进行计时统计。缺陷缺陷必须先运行程序；统计的时间依赖于计算机的软必须先运行程序；统计的时间依赖于计算机的软硬件环境，容易掩盖算法本身的优劣。硬件环境，容易掩盖算法本身的优劣。n事前分析估算的方法事前分析估算的方法假设给定的是一台通用计算机，满足：假设给定的是一台通用计算机，满足：执行一条基本语句或一个基本运算需花执行一条基本语句或一个基本运算需花一个单位时间一个单位时间基本语句基本语句指

26、：赋值语句、输入语句、输出语句指：赋值语句、输入语句、输出语句基本运算基本运算指：算术运算、一次比较（字符比较、数值比较）指：算术运算、一次比较（字符比较、数值比较）做法做法：从算法中选取一种对于所研究的问题（或算法类型）：从算法中选取一种对于所研究的问题（或算法类型）来说是来说是基本操作基本操作的原操作，以该基本操作的原操作，以该基本操作重复执行的次数重复执行的次数作为算法的时间量度。作为算法的时间量度。例例8-1 两个两个NN矩阵矩阵A和和B相乘的算法。相乘的算法。for(i=0;in;i+)for(j=0;jn;j+)cij=0;for(k=0;kn;k+)cij=cij+aik*bkj

27、;基本操作基本操作n时间复杂度：基本操作重复执行的次数是问题规模时间复杂度：基本操作重复执行的次数是问题规模n的某个函数，记作的某个函数，记作T(n)=O(f(n)“O”标记的形式定义：标记的形式定义：若若f(n)是正整数是正整数n的一个函数，则的一个函数，则xnO(f(n)表示存表示存在一个正的常数在一个正的常数M，使得当，使得当n n0时都满足时都满足|xn|M|f(n)|；(换句话就是说，这当整型自变量换句话就是说，这当整型自变量n趋向于无穷大时，两趋向于无穷大时，两者的比值是一个不等于者的比值是一个不等于0的的常数常数。)例例8-2 NN矩阵相乘的算法的时间复杂度：矩阵相乘的算法的时间

28、复杂度：基本操作执行的次数：基本操作执行的次数：nnn=n3 T(n)=O(n3)语句的语句的频度频度：是指该语句重复执行的次数。与该语：是指该语句重复执行的次数。与该语句包含的句包含的基本操作执行的次数相同基本操作执行的次数相同。例例8 分析语句分析语句+x;s=0;的频度。的频度。解：将解：将“+x”看成是基本操作，则语句频度为，即看成是基本操作，则语句频度为，即时间复杂度为时间复杂度为(1)；如果将；如果将“s=0”也看成是基本操也看成是基本操作，则语句频度为，其时间复杂度仍为作，则语句频度为，其时间复杂度仍为(1)，即，即常量阶常量阶。例例9 分析语句分析语句for(i=1;i=n;+

29、i)+x;s+=x;解：语句频度为：解：语句频度为：2n，其时间复杂度为：，其时间复杂度为：T(n)=O(n)。即时间复杂度为即时间复杂度为线性阶线性阶。例例10 分析语句分析语句for(i=1;i=n;+i)for(j=1;j=n;+j)+x;s+=x;解：语句频度为：解：语句频度为：2n2，其时间复杂度为：，其时间复杂度为：O(n2)。即时。即时间复杂度为间复杂度为平方阶平方阶。定理定理：若：若A(n)=amnm+am-1nm-1+a1n+a0是一个是一个m次次多项式，则多项式，则A(n)=O(n m)。(证明略证明略)例例11 for(i=2;i=n;+i)for(j=2;j=(y+1)

30、(y+1)y+;n以下六种计算算法时间复杂度的多项式是最常用的。以下六种计算算法时间复杂度的多项式是最常用的。其关系为：其关系为：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)n指数时间的关系为：指数时间的关系为：O(2n)O(n!)1&change;-i)change=false;for(j=0;jaj+1)ajaj+1;change=TURE 分析：分析：问题的输入规模：问题的输入规模：n；基本操作：基本操作：“交换序列中相邻两个整数交换序列中相邻两个整数”；实例：实例：5 1 9 7 3 2 3 1 2 5 9 7“基本操作基本操作”数随数随n变化的规律：变化的规律：

31、a中序列自小至大有序时，中序列自小至大有序时，“基本操作基本操作”数为数为0；a中序列自大至小有序时，中序列自大至小有序时，“基本操作基本操作”数为数为 =(1+2+3+.+(n-1)=n(n-1)/2算法的时间复杂度：算法的时间复杂度：最好情况下的时间复杂度：最好情况下的时间复杂度：0最坏情况下的时间复杂度：最坏情况下的时间复杂度：W(n)=n(n-1)/2平均情况下的时间复杂度：平均情况下的时间复杂度：AV(n)=(1/n)*0+1+2+.+n(n-1)/2=O(n2)总结：总结：n确定确定算法问题算法问题规模规模；n找出找出基本操作基本操作；n分析基本操作是否只依赖于问题规模？分析基本操

32、作是否只依赖于问题规模？是，就直接建立基本操作执行次数的求和表达式，是，就直接建立基本操作执行次数的求和表达式，并求解、用渐进符号表示；并求解、用渐进符号表示；否则，分别对该算法的最好、最坏和平均情况的时否则，分别对该算法的最好、最坏和平均情况的时间复杂度进行分析。间复杂度进行分析。算法的存储算法的存储空间代价空间代价n一个算法的空间效率是指在算法的执行过程中，所一个算法的空间效率是指在算法的执行过程中，所占据的辅助空间数量。占据的辅助空间数量。n空间复杂度：算法所需存储空间的度量，记作空间复杂度：算法所需存储空间的度量，记作S(n)=O(f(n)其中，其中，n为问题的规模。为问题的规模。本章

33、小结本章小结n本章主要介绍了如下一些基本概念：本章主要介绍了如下一些基本概念：数据数据数据元素数据元素数据对象数据对象物理结构物理结构数据类型数据类型抽象数据类型抽象数据类型n算法的概念、特性以及描述算法的概念、特性以及描述n算法的分析算法的分析课后作业课后作业1.设设n为正整数，试确定下列各程序段中前置以记号为正整数，试确定下列各程序段中前置以记号的语句的频度。的语句的频度。(1)i=1;k=0;while(i=n-1)k+=10*i;i+;(2)i=1;k=0;while(i=n-1)i+;k+=10*i;(3)k=0;for(i=1;i=n;i+)for(j=i;j=n;j+)k+;(4

34、)i=1;j=0;while(i+jj)j+;else i+;2.假设假设n为为2的乘幂，并且的乘幂，并且n2，试求下列算法的时间，试求下列算法的时间复杂度及变量复杂度及变量count的值的值(以以n的函数形式表示的函数形式表示)。int Time(int n)count=0;x=2;while(xn/2)x*=2;count+;return(count)/Time3.尝试说明语句频度与时间复杂度的区别。你觉得尝试说明语句频度与时间复杂度的区别。你觉得google搜索引擎给定一个关键字获得搜索结果的搜索引擎给定一个关键字获得搜索结果的时间复杂度是多少？问题的规模依赖于什么？时间复杂度是多少？问

35、题的规模依赖于什么？课后作业课后作业n4.写出伪代码：遍历某个指定目录下的所有文件，写出伪代码：遍历某个指定目录下的所有文件，并输出文件名。并输出文件名。指导：指导：n1.先思考做这个事情大概有几项任务要完成先思考做这个事情大概有几项任务要完成n2.完成这些任务的先后顺序完成这些任务的先后顺序n3.具体每步如何实现具体每步如何实现(这个先不管，完成前两步即可这个先不管，完成前两步即可)该题无需上交，但将进行课堂提问该题无需上交，但将进行课堂提问n5.Task(程序基础资料查询程序基础资料查询):2.1详述算法中详述算法中nL.elem=(ElemType*)malloc(LIST_ INIT_SIZEsizeof(ElemType)的含义2.2查询资料，进一步说明函数指针作为函数参数的作用？并举出一例子进行说明2.3查询引用型参数(&)的含义，举一例子说明。课后实践作业课后实践作业n1.安装好安装好vs 2005,学校学校ftp有下载有下载如果操作系统是如果操作系统是windows 7或者或者windows 8，可以安，可以安装装Visual Studio Express 2012 for Windows Desktop下载地址：下载地址：http:/ world，并运行，并运行