辅导01引论.ppt

《辅导01引论.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、了解数据结构的基本概念。了解数据的逻辑结构、存储结构、算法的概念。理解数据类型、抽象数据类型的概念。理解时间复杂度、空间复杂度的概念。第一章引论1算法定义性能分析与度量什么是数据结构抽象数据类型2算法定义定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列特性：输入有0个或多个输入输出有一个或多个输出(处理结果)确定性每步定义都是确切、无歧义的有穷性算法应在执行有穷步后结束3性能分析与度量算法的后期测试算法的事前估计*4算法的后期测试在算法中的某些部位插装时间函数time()测定算法完成某一功能所

2、花费时间5算法的事前估计空间复杂度时间复杂度*6空间复杂度度量存储空间的固定部分程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占空间可变部分尺寸与问题规模有关的成分变量所占空间、递归栈所用空间、通过malloc和free命令动态使用空间7时间复杂度度量运行时间=算法每条语句执行时间之和。每条语句执行时间=该语句的执行次数（频度）*语句执行一次所需时间。语句执行一次所需时间取决于机器的指令性能和速度和编译所产生的代码质量，很难确定。设每条语句执行一次所需时间为单位时间，

3、则一个算法的运行时间就是该算法中所有语句的频度之和。8例求两个n阶方阵的乘积C=ABvoidMatrixMultiply(intA[][],intB[][],intC[][],intn){for(inti=0;i

4、度T(n)是问题规模n的函数。当n趋于无穷大时，称时间复杂度的数量级为算法的渐进时间复杂度T(n)=O(n3)10渐进时间复杂度求函数的阶，用大O表示加法规则针对并列程序段T1(n)=O(f(n))T2(m)=O(g(m))T(n,m)=T1(n)+T2(m)=O(max(f(n),g(m)))并列11变量计数x=0;y=0;for(intk=0;k

5、)T(n)=T1(n)+T2(n)+T3(n)=O(max(1,n,n2))=O(n2)12乘法规则针对嵌套程序段T1(n)=O(f(n))T2(m)=O(g(m))T(n,m)=T1(n)*T2(m)=O(f(n)*g(m))嵌套13c=0&&A[i]!=k)i--;returni;算法的语句i--的频度不

6、仅与n有关，还与A[]中各元素的取值，以及k的取值有关。15数据（data）数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。数值性数据非数值性数据16数据元素(dataelement)数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。有时一个数据元素可以由若干数据项(DataItem)组成。数据项是具有独立含义的最小标识单位。数据元素又称为元素、结点、记录。17什么是数据结构定义:指某一数据元素集合中的所有数据成员之间的关系。反映数据的内部组成。

7、逻辑结构：数据元素间的逻辑关系存储结构：数据元素及其关系在计算机存储内的表示18数据的逻辑结构分类线性结构线性表非线性结构树图（或网络）19线性结构树形结构树二叉树二叉搜索树1413121123456789103158710119987456623131bindevetclibuser120堆“最大”堆“最小”堆12354871110291641012115123698721图结构网络结构1256431254361133181466516192122数据的存储结构数据的存储结构是逻辑结构用计算机语言的实现；数据的

8、存储结构依赖于计算机语言。顺序存储表示非顺序存储表示23抽象数据类型数据类型定义：一组性质相同的值的集合。C语言中的基本数据类型charintfloatdoublevoid字符型整型浮点型双精度型无值抽象数据类型定义：数据类型+运算。24抽象数据类型查找登录删除修改符号表25函数与参数传递函数声明：<函数类型符>函数名（<行参列表>）；函数定义：<函数类型符>函数名（<行