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

数据结构,计算机工程学院郑如滨网络教研室40715959292920QQ:398620541,课程介绍,课程名称：数据结构教材：数据结构(C语言版)，严蔚敏吴伟民编著，清华大学出版社，2007年4月教学方式：授课（54）+上机实践（18）32datastructuredatastructure,课程考核方式,考核方式：期末闭卷60%，平时成绩40%。平时成绩组成：考勤:缺勤1/3直接取消考试资格。请假需课前提前通知教师（电话或假条的方式）。无故未到一次，扣10%。作业：未交一次，扣10%。未认真完成作业，敷衍交作业，一次10%抄袭作业，一次20%绝对禁止上课前，写本课程的作业。实验：平时+最终的实验报告，以平时课堂上检查为主。完成情况良好，可加分。平时表现：课堂回答问题、作业完成情况等、好的问题均可加分。加分项可部分与扣分项相抵问题：课堂、课后、电子邮件,参考书籍,编程类：高质量C+编程专解疑难杂症算法类：算法导论(建议：仅供查询)程序员实用算法代码较详细，对很多数据结构有详细的实现代码AndrewBinstock、JohnRex、陈宗斌机械工业出版社(建议：仅供查询),参考书籍(深入)：算法与数据结构，傅清祥王晓东编著，电子工业出版社，2001数据结构与算法分析C语言描述M，（美）MikeAllenWeiss著，机械工业出版社，2004算法导论(第二版)，ThomasH.Cormen等著，高等教育出版社，2002,注意事项：今天回去的作业，自己复习,C+语言基础，尤其是指针部分最为重要，还有结构体、引用部分。c语言教科书：错误调试常见问题：=与=，引用参数2.循环直到r=0;2.1m=n;2.2n=r;2.3r=m%n;3.输出n;,#includeintCommonFactor(intm,intn)intr=m%n;while(r!=0)m=n;n=r;r=m%n;returnn;,算法的评价衡量算法优劣的标准正确性(correctness):满足具体问题的需求可读性(readability)：易读、易理解健壮性(robustness):当输入数据非法时，算法能够做出反应或进行处理效率与低存储量:执行时间短、存储空间小,算法效率的度量,算法效率的度量时间代价：算法在计算机上运行时消耗的时间来度量。有两种方法：事后统计的方法：利用计算机内部计时功能，进行计时统计。缺陷必须先运行程序；统计的时间依赖于计算机的软硬件环境，容易掩盖算法本身的优劣。,事前分析估算的方法假设给定的是一台通用计算机，满足：执行一条基本语句或一个基本运算需花一个单位时间基本语句指：赋值语句、输入语句、输出语句基本运算指：算术运算、一次比较（字符比较、数值比较）做法：从算法中选取一种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。例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;,基本操作,时间复杂度：基本操作重复执行的次数是问题规模n的某个函数，记作T(n)=O(f(n)“O”标记的形式定义：若f(n)是正整数n的一个函数，则xnO(f(n)表示存在一个正的常数M，使得当nn0时都满足|xn|M|f(n)|；(换句话就是说，这当整型自变量n趋向于无穷大时，两者的比值是一个不等于0的常数。)例8-2NN矩阵相乘的算法的时间复杂度：基本操作执行的次数：nnn=n3T(n)=O(n3)语句的频度：是指该语句重复执行的次数。与该语句包含的基本操作执行的次数相同。,例8分析语句+x;s=0;的频度。解：将“+x”看成是基本操作，则语句频度为，即时间复杂度为(1)；如果将“s=0”也看成是基本操作，则语句频度为，其时间复杂度仍为(1)，即常量阶。例9分析语句for(i=1;i=n;+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(nm)。(证明略)例11for(i=2;i=(y+1)(y+1)y+;,以下六种计算算法时间复杂度的多项式是最常用的。其关系为：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)指数时间的关系为：O(2n)2，试求下列算法的时间复杂度及变量count的值(以n的函数形式表示)。intTime(intn)count=0;x=2;while(xn/2)x*=2;count+;return(count)/Time3.尝试说明语句频度与时间复杂度的区别。你觉得google搜索引擎给定一个关键字获得搜索结果的时间复杂度是多少？问题的规模依赖于什么？,课后作业,4.写出伪代码：遍历某个指定目录下的所有文件，并输出文件名。指导：1.先思考做这个事情大概有几项任务要完成2.完成这些任务的先后顺序3.具体每步如何实现(这个先不管，完成前两步即可),该题无需上交，但将进行课堂提问,5.Task(程序基础资料查询):2.1详述算法中L.elem=(ElemType*)malloc(LIST_INIT_SIZEsizeof(ElemType)的含义2.2查询资料，进一步说明函数指针作为函数参数的作用？并举出一例子进行说明2.3查询