数据结构与算法分析新视角（第2版） 课件 周幸妮 第1-4章 绪论-数组和串

数据结构与算法分析

新视角前言Chapter

0DatastructuresandAlgorithms从新视角来看待旧问题，需要有创造性的思维，这标志着科学的真正进步。——爱因斯坦数据结构与其他课程的关系4Web信息处理人工智能数据库操作系统编译原理图形图像算法分析与设计数据结构计算复杂性理论概率统计计算概论集合与图论教学内容1绪论3运算特殊的线性表——栈和队列4内容特殊的线性表——字符串和多维数组2结点逻辑关系为线性的结构——线性表5结点逻辑关系分层次的非线性结构——树7数据的处理方法——排序技术8数据的处理方法——索引与查找技术6结点逻辑关系任意的非线性结构——图9经典算法绪论Chapter

1DataStructuresandAlgorithmAnalysis主要内容数据结构的概念算法设计的基本要求从时间和空间角度分析算法效率的方法学习目标了解数据结构课程的意义掌握数据结构的概念掌握算法设计与程序设计的步骤掌握算法效率的分析评价方法1.1CONTENTS从编程说起程序要处理的数据1.21.3数据结构的引入1.4数据结构的要素1.5如何设计算法如何评价算法的优劣1.61.7算法性能的事前分析方法1.8算法性能的综合考量1.1CONTENTS从编程说起程序要处理的数据1.21.3数据结构的引入1.4数据结构的要素1.5如何设计算法如何评价算法的优劣1.61.7算法性能的事前分析方法1.8算法性能的综合考量1.1从编程说起程序的公式表达12算法+数据结构

=程序尼古拉斯·沃斯NiklausWirth1934年2月15日——算法是处理问题的策略，数据结构是描述问题信息的数据模型，程序则是计算机按照处理问题的策略处理问题信息的一组指令集计算机解决问题的过程1314程序的开发程序解题软件工程具体工作建模型需求分析阶段提取问题要完成的功能；分析问题涉及的数据对象，找出数据对象之间的关系。设计设计阶段数据结构设计、软件的结构设计、算法设计

编程编码阶段编写程序代码验证测试软件测试与调试1.1CONTENTS从编程说起程序要处理的数据1.21.3数据结构的引入1.4数据结构的要素1.5如何设计算法如何评价算法的优劣1.61.7算法性能的事前分析方法1.8算法性能的综合考量1.2程序要处理的数据17数值与非数值问题数值计算非数值计算数值计算，具体地说就是有效利用计算机求解数学问题近似解的方法与过程，可以通过抽象出合适的数学模型，然后设计相应的算法来解决。数值计算问题，以浮点算术运算为主，算法成熟所谓“非数值计算”问题，是为了区分前面提到的“数值问题”而言。非数值问题涉及到的数据及数据间的相互关系，一般无法用数学公式、方程等来描述，如排序问题、检索问题等，需要另外设计数据的描述方法和相应的算法来处理。18从下面的无限序列中计算出π的值。输出一个表格，在该表格中显示根据这个序列中的1项、2项、3项等等所得的近似π值。在第一次得到3.14之前，必须使用这个序列的多少项？如果是得到3.141呢？3.1415呢？3.14159呢？数值问题的例子通用公式数据对象数据间关系数据初始化建模型m=1;i=1-1偶数1奇数m取值i取值项数：当前已经用到的项数i系数：控制序列项的正负号

m4+（-1）*m*4/(2*i+1)例19算法顶部伪代码描述赋初值：累加和x=4;m=1;项数i=1；根据通用公式,x做循环累加直到x=3.14时中断循环输出x及i值；算法细化描述累加和x=4;m=1;i=1；dox=x+（-1）*m*4/(2*i+1)

i增加1；

m=m*(-1)直到x=3.14时中断循环输出x及i值；设计数值问题的例子20数值问题的例子voidmain(){floatx=4;inti=1,m=1;while(1){ x=x+(float)(-1)*m*4/(2*i+1); i++; m=m*(-1); if(x>=3.14-0.000001&&x<=3.14+0.000001)break;} printf("i=%d,x=%f\n",i,x);}编程要求对任意给出的一个姓名，查找电话号码非数值问题例子1——电话号码查询客户姓名电话身份证号地址张1138*****6101131980******李2152*****6101131981******王1139*****6101131990******张2139*****6101131972******李1188*****6101131976******………"表""关键字""数据项"关键字关键字是能唯一标识一个结点的那些数据项"数据元素"或"结点"例方法1客户姓名电话身份证号地址张1138*****6101131980******李2152*****6101131981******王1139*****6101131990******张2139*****6101131972******李1188*****6101131976******王2138*****6101131986******………顺序结构顺序查找非数值问题例子1——电话号码查询问题涉及的对象每客户及其相应的数据项；对象之间的关系数据元素顺序排列；查找指定数据项，输出相应数据项建模型设计非数值问题例子1——电话号码查询方法1顺序结构顺序查找有序结构折半查找方法2客户姓名电话身份证号地址李1188*****6101131976******李2152*****6101131981******王1139*****6101131990******王2138*****6101131986******张1138*****6101131980******张2139*****6101131972******………非数值问题例子1——电话号码查询问题涉及的对象每客户及其相应的数据项；对象之间的关系数据元素有序排列；折半查找指定数据项，输出相应数据项建模型设计非数值问题例子1——电话号码查询有序结构折半查找方法2索引结构分级查找客户姓名电话身份证号地址李1188*****6101131976***0x2000李2152*****6101131981******………张1138*****6101131980***0x4000张2139*****6101131972******………王1139*****6101131990***0x6000王2138*****6101131986******………姓氏表内地址数量李0x2000***张0x4000***王0x6000***………索引表数据表方法3非数值问题例子1——电话号码查询问题涉及的对象索引表客户姓氏、对应数据表中的地址数据表每个客户及其相应的数据项；对象之间的关系索引表数据元素有序排列数据表数据元素顺序排列；建模型先索引表，后数据表设计非数值问题例子1——电话号码查询索引结构分级查找方法328非数值问题例子1——电话号码查询数据的组织方式和数据的存储方式，都会影响算法的效率结论29在十字路口，要设置几种颜色的交通灯才可保持正常的交通秩序？BCDA十字路口交通灯管理问题非数值问题的例子2问题涉及的对象对象之间的关系表示AC、BD不能同时通行BDAC用表示AC间有一条通路AC建模型某方向通行时，另外某些方向不能通行四个路口ABCD，及相应的通路；例30ACABADBDBABCCACDCBDBDCDABCDA“图”“数据元素”或“结点”对图中的圆圈上色，同一连线上的两个圆圈不同色且颜色种类最少设计非数值问题的例子231非数值问题的例子3rootbinlibuseretcmathdsswsunzhouzhaoStack.cppTree.cppQueue.cpp……"树"“数据元素”或“结点”计算机文件系统结构的表示与管理例1.1CONTENTS从编程说起程序要处理的数据1.21.3数据结构的引入1.4数据结构的要素1.5如何设计算法如何评价算法的优劣1.61.7算法性能的事前分析方法1.8算法性能的综合考量1.3数据结构的引入问题解决信息表述信息处理计算机解题过程先找出问题中要处理的数据及数据间的联系、组织形式、存储方式、表示方法等，设计适合计算机解题的模型按要求有效地解决问题

数据结构研究的问题

经典数据结构数据表示方法数据存储形式数据运算1.1CONTENTS从编程说起程序要处理的数据1.21.3数据结构的引入1.4数据结构的要素1.5如何设计算法如何评价算法的优劣1.61.7算法性能的事前分析方法1.8算法性能的综合考量1.4数据结构的要素1.4.11.4.2数据结构基本术语数据结构的三个要素数据的基本单位可包含多个数据项38基本概念和术语数据元素由某一数据对象及该对象中所有数据成员之间的关系组成数据元素中的不可分割的最小单位客观对象在计算机中的符号表示数据结构数据项数据数据结构基本术语1.4数据结构的要素1.4.11.4.2数据结构基本术语数据结构的三个要素数据结构数据的逻辑结构体现各结点间的相邻关系，由数据本身内在特性所决定，独立于计算机数据的存储结构数据元素及其逻辑关系在计算机存储器内的表示数据的运算对数据施加的操作数据结构的三个要素数据结构的三个要素数据逻辑结构集合结点间无关系线性结构结点间一对一关系树形结构结点间是一对多关系图形结构结点间是多对多关系数据的逻辑结构数据的逻辑结构数据的存储结构42数据存储结构顺序存储结点的逻辑关系由存储单元的邻接关系来体现链式存储结点的逻辑关系由附加的指针字段表示索引存储索引项：（关键字，地址）散列存储结点地址＝F（关键字）数据的运算43数据运算运算的定义建立在数据的逻辑结构上运算的实现以数据的存储结构为基础常见运算：初始化

判空

求长度

查找

遍历

取值

置值

插入

删除

1.1CONTENTS从编程说起程序要处理的数据1.21.3数据结构的引入1.4数据结构的要素1.5如何设计算法如何评价算法的优劣1.61.7算法性能的事前分析方法1.8算法性能的综合考量1.5如何设计算法1.5.11.5.2算法的定义及表示方法算法设计与函数设计的关系1.5.31.5.4软件设计描述算法设计的一般步骤1.5如何设计算法1.5.11.5.2算法的定义及表示方法算法设计与函数设计的关系1.5.31.5.4软件设计描述算法设计的一般步骤47算法

在有限步骤内求解某一问题所使用的一组定义明确的操作序列，能够在有限时间内，对一定的规范的输入获得所要求的输出。算法算法特征1有穷性：一个算法必须保证在执行有限步骤后结束，而不是无限的。3可行性：每一个操作步骤都必须在有限的时间内完成。4输入：一个算法可以有多个输入，也可以没有输入。2确定性：算法中每一条指令必须有明确的含义，而不能是含糊不清的有歧义。5输出：一个算法可以有一个或多个输出，没有输出的算法是没有实际意义的。算法的表示49可以帮助程序员开发算法的，由字符组成的非正式语言。可以引用任何具有表达力的方法来最清晰、最简洁地表达算法。伪代码本书对算法的描述采用伪代码的方式1.5如何设计算法1.5.11.5.2算法的定义及表示方法算法设计与函数设计的关系1.5.31.5.4软件设计描述算法设计的一般步骤longfactorial(intn);

有关函数的概念函数类型函数名（形参类型说明表）{

声明部分； 语句部分；}函数的定义形式函数类型函数名（形参类型说明表）;函数的声明形式函数名(实参表);函数的调用形式longfactorial(intn){

inti;

long

t=1;

for(i=1;i<=n;i++)

t=t*i;

return(t);}intm;longc；scanf(“%d”,&m);c=factorial(m);输入的数据输出的结果输出结果的类型实际参数C函数实际参数与形式参数的关系52函数类型函数名（形式参数表）

{声明部分;语句部分;}函数定义格式函数名（实际参数表）函数调用格式形式参数表中放参数的定义形式如基本变量：intx如指针：int*ptr如数组：inta[]如结构：structnodestu实际参数表中放参数的使用形式如基本变量：x如指针：ptr如数组：a如结构：stuC函数实际参数与形式参数的关系算法设计与函数设计的关系功能描述输入信息输出信息函数名形参函数类型接口及功能描述此处输出的含义，是指函数传递给调用者的，不是输出到显示器上的此处信息输入方式是调用者传递给函数，不是通过键盘等方式输入1.5如何设计算法1.5.11.5.2算法的定义及表示方法算法设计与函数设计的关系1.5.31.5.4软件设计描述算法设计的一般步骤软件设计方法55根据问题的功能要求，按照输入数据的正常情形、边界或特例情形、异常情形等各种情形，给出测试样例。测试用例设计1给出问题包含信息与信息联系的存储结构，用C语言数据类型描述。数据结构描述2根据问题的功能、输入、输出，对应确定函数类型、形参、返回值。函数结构设计3按照自顶向下逐步求精的方法，描述问题的解决步骤。算法描述4按照细化的伪代码给出代码实现，必要时按照测试样例给出测试结果。程序实现5分析问题的时间复杂度、空间复杂度。算法效率分析61.5如何设计算法1.5.11.5.2算法的定义及表示方法算法设计与函数设计的关系1.5.31.5.4软件描述方法算法设计的一般步骤算法设计的一般步骤571设定算法初始条件3按问题的普遍规律给出算法处理的流程4考虑临界点或特殊点的处理2确定算法的结束条件5考虑异常情况算法设计实例5858算法设计的例子——求n！递推公式S=S*Tn!1n<=1n*(n-1)!n>1step11*2=>sstep2s*3=>sstep3s*4=>sstep4s*5=>sS：累乘之积T：乘数递推法定义例59算法设计实例——

求n！功能描述输入信息输出信息factorialintnint值异常：-1正常：n！的结果测试用例设计1接口及功能描述2情形测试数据预期结果问题的一般情形n>1按照n！一般定义得出的值临界点或特殊点n=0，n=1按照n！边界定义得出的值异常情况n<0给出错误提示信息

60算法设计实例——

求n！顶部伪代码描述输入n求n！输出结果第一步细化输入n初始化S=1，T=1由1乘2开始结果放到乘积S中，乘数T每次增1当T>n结束输出结果S第二步细化输入n设S=1，乘数T=1

doS=S*TT增加1

Until(T>n)输出：S算法描述3算法设计实例——求n！61

一般情形边界值异常情形测试值51001-1测试结果120362880011-1floatfactorial(intn){inti;floatt=1;if(n<0)return(-1);for(i=1;i<=n;i++)

t=t*i;return(t);}函数实现4测试结果562伪代码描述要点简洁明晰按程序结构特点描述算法步骤，注意格式缩进。内容完整算法开始阶段初始化信息输入信息算法处理阶段循环要素、判断条件等算法结束阶段输出信息程序结构：顺序、循环、分支63n!的例子#include<stdio.h>floatfactorial(intn);floatfactorial(intn){inti;floatt=1;for(i=1;i<=n;i++)t=t*i;return(t);}main(){floatc;intm;printf(〞inputm〞);scanf(〞%d〞,&m);c=factorial(m);printf(〞The%d!is%8.1f〞,

m，c);}函数说明函数调用函数定义1.1CONTENTS从编程说起程序要处理的数据1.21.3数据结构的引入1.4数据结构的要素1.5如何设计算法如何评价算法的优劣1.61.7算法性能的事前分析方法1.8算法性能的综合考量1.6如何评价算法的优劣1.6.11.6.2算法设计的要求算法效率的度量方法1.6如何评价算法的优劣1.6.11.6.2算法设计的要求算法效率的度量方法67算法设计的要求正确性程序不含语法错误对输入数据能得出满足要求的结果随意的数据精心选择的典型、苛刻而带有刁难性的几组数据一切合法的输入数据可读性程序员的效率第一健壮性算法对不合理数据输入应该有反应能力和处理能力高效性时间效率高效率指的是算法执行的时间（时间复杂性）；存储空间少存储量需求指算法执行过程中所需要的最大存储空间（空间复杂性）空间和时间可以互相转化1.6如何评价算法的优劣1.6.11.6.2算法设计的要求算法效率的度量方法69算法性能的事后统计#include<time.h>longstart,stop;time(&start);

/*******************

此处放要测定运行时间的函数********************/time(&stop);

longrunTime=stop-start;printf("%ld\n",runTime);例

硬件的速度

程序选用语言目标代码质量

问题的规模

算法选用的策略算法效率因素算法时间效率相关因素分析算法性能的事前分析71时间效率空间效率算法性能分析算法的时间效率分析——找出与算法运行时间相关的因素与特征函数，从时间角度来评价算法。算法的空间效率分析——找出算法运行所需的辅助存储空间特征函数，从空间角度来评价算法。1.1CONTENTS从编程说起程序要处理的数据1.21.3数据结构的引入1.4数据结构的要素1.5如何设计算法如何评价算法的优劣1.61.7算法性能的事前分析方法1.8算法性能的综合考量

硬件的速度

程序选用语言目标代码质量

问题的规模

算法选用的策略算法效率因素算法时间效率相关因素分析与算法执行时间相关的因素中，哪些是关键因素？算法时间效率相关因素分析算法运行时间=算法中每条语句执行时间之和每条语句执行时间==>该语句的执行次数74语句频度将程序的运行时间表示为其输入的函数若问题的规模为n，一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)。1.7算法性能的事前分析方法1.7.11.7.2问题的规模与算法的策略算法时间效率的上限与下限1.7.31.7.4渐进的上限——算法的时间复杂度时间复杂度的综合讨论1.7.5算法的空间效率分析方法1.7算法性能的事前分析方法1.7.11.7.2问题的规模与算法的策略算法时间效率的上限与下限1.7.31.7.4渐进的上限——算法的时间复杂度时间复杂度的综合讨论1.7.5算法的空间效率分析方法77问题的规模与算法的策略每个卡片只看一次，共100次将数字1～100写在卡片上，乱序后再按序排好。排序时所有卡片的查找次数是多少？先找1、再找2、找3、…最多要看(100+1)*100/2次法一法二问题规模为n时的比较次数f(n)=n2/2+n/2问题规模为n时的比较次数

f(n)=n例78问题的规模与算法的策略结论一般地，算法所需时间是和输入规模n同步增长的：对于同一算法

输入量小，速度快；

输入量大，速度慢。对于不同的算法

有可能在n的某一区间，一个算法的速度高于另一个；

而在n的另一区间，情况可能就会相反。对于不同的算法

规模较小时，算法效率接近；

规模扩大，算法效率通常呈上升趋势，各算法之间的差距就比较明显了。791.7算法性能的事前分析方法1.7.11.7.2问题的规模与算法的策略算法时间效率的上限与下限1.7.31.7.4渐进的上限——算法的时间复杂度时间复杂度的综合讨论1.7.5算法的空间效率分析方法81算法分析规则1234596979899100…例将数字1～100写在卡片上，乱序后再按序排好。排序时所有卡片的查找次数是多少？T(n)=n=1001009998979654321…23614578521627789310…最好情形最坏情形平均情形T(n)=(n+1)*n/2=5050T(n)=257582在n张卡片中找一个指定卡片i的平均查找次数ASLn（AverageSearchLength）Pi——查找表中第i个记录的概率Ci——找到该记录时已经比较过的卡片数在n张卡片中找n个指定卡片i的平均查找次数ASLn=100时，T(n)=2575算法分析规则算法效率典型情形83最好效率：算法在最优情况下的效率最差效率：算法在最坏情况下的效率平均效率：“典型”或“随机”输入的情况下，算法具有的效率算法效率典型情形84算法的上限&下限算法运行时间慢快算法运行的时间上限算法运行的时间下限O表示法Ω表示法Θ表示法同一算法算法分析是为了得知近似的执行时间，一般考察的是当问题规模n增加时，运算所需时间的上下界。85渐进表示法记号记号定义含义O定义：f(n)＝O(g(n))若存在两个正常数c和n0，使得当n≧n0时，f(n)≦c*g(n)f(n)的渐进上限为g(n)Ω定义：f(n)＝Ω(g(n))若存在两个正常数c和n0，使得当n≧n0时，f（n）≧c*g(n)f(n)的渐进下限为g(n)Θ定义：f(n)＝Θ(g(n))若存在正常数c1，c2和n0，使得当n≧n0时，c1*g(n)≦f(n)≦c2*g(n)f(n)的渐进确界为g(n)o定义：f(n)＝o(g(n))对任意正常数c，若存在n0，使得当n≧n0时，f(n)<cg(n)g(n)为f(n)的非紧却渐进上界ω定义：f(n)＝ω(g(n))对任意正常数c，若存在n0，使得当n≧n0时，f(n)>cg(n)g(n)为f(n)的非紧却渐进下界说明：f(n)、g(n)均为非负函数

86cg(n)f(n)n0f(n)

O(g(n))cg(n)f(n)n0f(n)

Ω(g(n))f(n)

θ(g(n))BigO算法的渐进运行时间记号注：n0、c、c1、c2均为正数n0c2g(n)f(n)c1g(n)渐进上限渐进下限渐进确界大O符号（BigOnotation）是用于描述函数渐近行为的数学符号。它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。87大O表示法的例子1f(n)=7*2n+n2+n=O(2n)，∵可以找到c=8,n0=4，使得7*2n+n2+n<8*2n

f(n)=10n2+5n+1=O(n2)，∵可以找到c=11,n0=6，使得10n2+5n+1<11n2

f(n)=3n+2=O(n)，∵可找到c=4，n0=2，使得3n+2<4n例88利用极限比较阶数极限值f(n)与g(n)比较结果表示含义存在0f(n)是比g(n)低阶的无穷大f(n)＝o(g(n))f(n)在数量级上严格小于g(n)c≤1f(n)与g(n)是同阶的无穷大（称f与g是同数量级的）f(n)＝O(g(n))f(n)在数量级上小于等于g(n)c=1f(n)=Θ(g(n))f(n)在数量级上等于g(n)c≥1f(n)=Ω(g(n))f(n)在数量级上大于等于g(n)不存在∞f是比g高阶的无穷大f(n)=ω(g(n))f(n)在数量级上严格大于g(n)振荡设f(n)、g(n)是在同一个自变量n的变化过程中的无穷大两个函数的比率求极限c为常数89大O表示法的例子2（3）f(n)=7*2n+n2+n=O(2n)（2）f(n)=10n2+5n+1=O(n2)（1）f(n)=3n+2=O(n)当

n充分大时，该程序的运行时间和n成正比，用O(n)表示；称f(n)和n是同阶的（数量级相同）。当

n充分大时，该程序的运行时间和n2成正比，用O(n2)表示；称f(n)和n2是同阶的。当

n充分大时，该程序的运行时间和2n成正比，用O(2n)表示；称f(n)和2n是同阶的。例1.7算法性能的事前分析方法1.7.11.7.2问题的规模与算法的策略算法时间效率的上限与下限1.7.31.7.4渐进的上限——算法的时间复杂度时间复杂度的综合讨论1.7.5算法的空间效率分析方法91时间复杂度

如果O(f(n))是某个算法的语句执行次数f(n)的上限，那么我们可以说此算法的渐进时间复杂度（简称时间复杂度)或是执行时间为O(f(n))定义92矩阵相乘算法时间复杂度f(n)=O(n3)程序语句频度f(n)1for(i=1;i<=n;i++)2for(j=1;j<=n;j++)3{c[i][j]=0;4for(k=1;k<=n;k++)5c[i][j]+=a[i][k]*b[k][j]}

n阶矩阵相乘算法的时间复杂度分析（C=A*B）例算法的时间复杂度的例子1n+1n(n+1)n2n2(n+1)n3

频度和

f(n)=2n3+3n2+2n+193时间复杂度结论

算法的渐进分析，关心的是数据规模n逐步增大时资源开销T(n)的增长趋势，具体是考察数量级大小的比较。如果一个算法的最坏情况运行时间的阶要比另外一个算法的低，我们就常常认为前者更为有效。结论94例程序段频度f(n)与规模n时间复杂度O(f(n))1x=x+1;y=x+2234分析下面各程序段的时间复杂度算法的时间复杂度的例子2for(i=0;i<n;i++)x++;f(n)123…k…f(n)i12222k-12f(n)-1i=i*2222232k2f(n)i=1;while(i<=n)i=i*2;for(i=0;i<n;i++)for(j=0;j<n;j++)x++;O(log2n)2f(n)=nO(n2)f(n)=(n+1)+n*(n+1)+n2O(n)f(n)=2n+1O(1)f(n)=2语句i=i*2执行次数最后一次执行：i=n时

2f(n)-1

=

n1.7算法性能的事前分析方法1.7.11.7.2问题的规模与算法的策略算法时间效率的上限与下限1.7.31.7.4渐进的上限——算法的时间复杂度时间复杂度的综合讨论1.7.5算法的空间效率分析方法算法时间复杂度的实际意义96查找的效率问题对于一组有序的数列（5,13,19,21,37,56,64,75,80,88,92），如何查找效率更高？数据513192137566475808892顺序查找次数1234567891011折半查找次数34234134234可能的概率pi1/n1*202*213*22i*2i-1561952113^h=1h=2h=3h=[log2n]+1层37^80648875^92^每层查找次数例一个结点查找成功的平均次数查找的平均时间复杂度算法时间复杂度的实际意义98算法时间复杂度的实际意义小规模的输入在运行时间上的差别不足以将高效的算法和低效的算法区分开。时间复杂度并不表示一个程序解决问题具体需要花多少时间，而是表示当问题规模扩大后程序运行需要的时间长度增长得有多快。99对于算法分析具有重要意义的函数值c<log2n<n<nlog2n<n2<n3<2n<3n<n!从渐进意义上说更有效的算法是基于大规模输入的比较对于算法分析具有重要意义的函数值常数阶对数阶线性阶线性对数阶平方阶立方阶指数阶阶乘阶O(1)O(lgn)O(n)O(nlgn)O(n2)O(n3)O(2n)O(n!)高效算法不可计算多项式级的复杂度非多项式级1001加法准则T(n,m)=T1(n)+T2(m) =O(max(f(n),g(m)))2乘法准则T(n)=T1(n)*T2(n)=O(f1(n))*O(f2(n))=O(f1(n)×f2(n))3特例情形

算法平均时间复杂度

算法在最坏情况下的时间复杂度时间复杂度的计算规则设程序段1和程序段2的时间分别为T1(n)和T2(n)，总的运行时间为T(n)——针对并列程序段——针对嵌套程序段——基本操作执行次数与问题的输入数据有关时对于复杂算法，可分成几个容易估算的部分。102问题的输入数据影响算法效率的情形在数组A[N]中查找给定值k的算法intsearch（intk）{inti=N-1;//i为要查找的下标

while(i>=0&&A[i]!=k)i--;

returni;}平均情形最坏情形f(n)=nO(f(n))=O(n)f(n)=(1/n)*(1+n)*n/2=(1+n)/2O(f(n))=O(n)时间复杂度的例子基本语句的执行次数是否只和问题规模有关？例103算法效率一般性分析方法非递归算法决定用哪个(些)参数作为输入规模的度量找出算法的基本操作(作为一个规律，它总是位于算法的最内层循环)检查基本操作的执行次数是否只依赖输入规模。如它还依赖一些其他的特性，如输入顺序等，则最差效率、平均效率以及最优效率需要分别研究。建立一个算法基本操作执行次数的求和表达式递归算法用递推式的形式来表达基本操作次数决定用哪些参数作为输入规模的度量找出算法的基本操作检查一下，对于相同规模的不同输入，基本操作的执行次数是否不同。如果不同，则必须对最差效率、平均效率以及最优效率作单独研究对于算法基本操作的执行次数，建立一个递推关系以及相应的初始条件解这个递推式，或者至少确定它的解的增长次数1.7算法性能的事前分析方法1.7.11.7.2问题的规模与算法的策略算法时间效率的上限与下限1.7.31.7.4渐进的上限——算法的时间复杂度时间复杂度的综合讨论1.7.5算法的空间效率分析方法从空间角度来评价算法——找出算法运行所需的辅助存储空间特征函数。105算法的空间效率分析算法空间存储空间代码空间：算法本身的存储空间数据空间：输入／输出数据的存储空间运行空间算法在运行过程中临时占用的存储空间106计算多项式的值算法存储空间分析的例子1-12函数结构设计功能描述输入输出计算多项式的值evaluate系数floatcoef[]floatf(x)变量floatx规模intn函数名形参函数类型例107算法存储空间分析的例子1-12顶部伪代码描述计算函数值第一步细化先计算x的幂,存于数组中,再分别乘以相应的系数第二步细化intA[N]放x的幂floatcoef[N]放系数A[0]=1，i=1当i<nA[i]=x*A[i-1];

i++;f=0,i=0;当i<nf=f+coef[i]*A[i];i++;法一108算法存储空间分析的例子1-12算法一#defineN100floatevaluate(floatcoef[],floatx,intn){floatf;intA[N],i;for(A[0]=1,i=1;i<=n;i++)A[i]=x*A[i-1];/*A[

]放x的幂*/for(f=0,i=0;i<=n;i++)f=f+coef[i]*A[i];return(f);}coef[]属输入输出，为数据空间；A[N]为局部量，是辅助空间算法时间复杂度:O(n)空间复杂度：O(n)109算法存储空间分析的例子1-12顶部伪代码描述计算函数值第一步细化从f()最后一项系数开始逐步乘x，反向处理第二步细化floatcoef[]放系数n为项数f=coef[n],i=n-1;当

i>0

f=f*x+coef[i];i--；法二算法存储空间分析的例子1-12110算法时间复杂度:O(n)空间复杂度：O(1)算法二#defineN100floatevaluate(floatcoef[],floatx,intn){floatf;inti;for(f=coef[n],i=n-1;i>=0;i--)f=f*x+coef[i];return(f);}111算法的空间复杂度定义

S(n)=O(g(n))

其中

n————问题规模

g(n)————执行算法所需的辅助空间算法空间复杂度S(n)空间复杂度含义O(n)表示每个输入元素都分配到固定的储存空间。O(1)代表算法需要固定的储存空间，与输入量无关若所需存储量依赖于特定的输入，则通常按最坏情况考虑。例112给出fibonacci数列前n项的递归与非递归的算法，试分析它们的算法复杂度。(费氏数列——fibonacci数列)fibonacci数列定义

f0=0；f1=1；fn=fn-1+fn-2(n>=2)递归的算法/*递归计算斐波那契数列的第n项*/longFib(longn){ if(n<=1)returnn;//递归边界

elsereturnFib(n-1)+Fib(n-2);//递归条件}0,1,1,2,3,5,8,13,21,……算法分析的综合例子1-13例Fibonacci函数的递归调用树Fib(5)Fib(4)Fib(3)Fib(3)Fib(2)Fib(2)Fib(2)Fib(1)Fib(1)Fib(1)Fib(0)Fib(0)Fib(1)Fib(0)Fib(1)nT(n)递归的运算次数T(n-1)+T(n-2)+141251595311n…76543210114∴T(n)

Ω(2n/2)∴T(n)

O(2n)∴T(n)>2*T(n-2)又∵T(n-1)>T(n-2)∴T(n)<2*T(n-1)∵T(n-1)>T(n-2)T(n)=T(n-1)+T(n-2)+1<2*2*T(n-2)<2*2*2*T(n-3)<…<2n-1T(n-n+1)=2n-1T(1)=2n-1>2*2*T(n-4)>2*2*2*T(n-6)>…>2n/2T(n-n)=2n/2大O：渐进上限Ω：渐进下限算法分析的综合例子1-13115Fibonacci数列通项公式fibonacci数列定义

f0=0；f1=1；fn=fn-1+fn-2(n>=2)二阶线性递推数列的特征方程二阶线性递推数列的通项公式a=1；b=-1；c=-1二阶线性递推数列的一般形式求得数列第n项与n的关系Fibonacci数列通项公式116fibonacci数列定义

f0=0；f1=1；fn=fn-1+fn-2(n>=2)

∵T(n)=T(n-1)+T(n-2)+1117Fib函数递归算法时间复杂度分析结论T(n)

Ω(2n/2)=Ω(1.414n)T(n)

O(2n)大O：渐进上限Ω：渐进下限Θ

渐进确界T(n)

Θ(1.618n)Fib函数递归算法时间复杂度分析曲线1181.1CONTENTS从编程说起程序要处理的数据1.21.3数据结构的引入1.4数据结构的要素1.5如何设计算法如何评价算法的优劣1.61.7算法性能的事前分析方法1.8算法性能的综合考量算法性能的综合考量120若待解决的问题数据量极大，机器的存储空间较小，则相应算法主要考虑如何节省空间时间复杂度空间复杂度逻辑复杂度若该程序使用次数较少，则力求算法简明易懂；对于反复多次使用的程序，应尽可能选用快速的算法；算法评价角度相互制约时空转换问题数据数据处理功能测试：测试样例设计数据引用：数据结构描述模块设计：函数结构设计算法设计：自顶向下逐步细化程序设计：编码算法分析：空间时间复杂度分析含义：数据元素的连接关系种类：集合、线性、非线性逻辑结构存储结构运算含义：数据存储到计算机中种类：顺序、链式、索引、散列存储原则：存数值存联系；存得进取得出含义：数据处理定义：基于数据的逻辑结构实现：基于数据的存储结构本章小结本章小结本章小结

数据结构三要素是逻辑、存储与运算：

逻辑结构说的是问题中的数据元素如何点点相关联；

存储结构把数据值与逻辑关系存放到内存的单元；

运算是由算法描述数据处理的方案。

一种逻辑关系可以用多种方式来存储，

“存数值且存联系”，“存得进并取得出”，

存储两规则，设计存的结构时必遵循的法门无二般，

存储结构不同，则算法效率有快有慢。

算法效率从时间和空间两个方面看，

复杂度用“大欧”的方法来估算，

用的是算法的渐进上限，和运算规模n相关。122结点逻辑关系为线性的结构线性表Chapter

2DataStructuresandAlgorithmAnalysis主要内容

线性表的逻辑结构定义各种存储结构的描述方法

在线性表的两类存储结构上实现基本操作学习目标掌握线性表的两类存储结构及基本操作掌握线性表两种存储结构的不同特点及适用场合2.1CONTENTS从逻辑结构角度看线性表线性表的存储结构方法之一

——顺序表线性表的存储结构方法之二

——链表线性表的应用举例2.22.32.42.52.6顺序表和链表的比较本章小结2.1CONTENTS从逻辑结构角度看线性表线性表的存储结构方法之一

——顺序表线性表的存储结构方法之二

——链表线性表的应用举例2.22.32.42.52.6顺序表和链表的比较本章小结2.1从逻辑结构角度看线性表2.1.12.1.2实际问题中的线性关系线性表的逻辑结构2.1从逻辑结构角度看线性表2.1.12.1.2实际问题中的线性关系线性表的逻辑结构实际问题中的线性关系130排队中的一对一关系实际问题中的线性关系131密码表jkhammotmoyznkvxuikyyulxksubotmyulzcgxkhamycharcode[27]="baefkilcjgdmqzhyoptxvrnwus";明码ABCDEFGHIJKLMNOPQRSTUVWXYZ密码BAEFKILCJGDMQZHYOPTXVRNWUSEBKTBPCAESAR截获敌方情报一份字符串——各字符先后有特定顺序凯撒实际问题中的线性关系132客户姓名电话身份证号地址张1138*****6101131980******李2152*****6101131981******王1139*****6101131990******张2139*****6101131972******李1188*****6101131976******………一个数据元素或一个结点电话号码表结构2.1从逻辑结构角度看线性表2.1.12.1.2实际问题中的线性关系线性表的逻辑结构线性表的逻辑结构134一个线性表是n(n≥0)个同类型结点的有限序列。记作：(a1

a2…ai…an)其中：ai————表示一个结点（1≤i≤n）。

n——线性表长度。n=0时为空表。定义线性表的逻辑结构135a1a2a3a4an……开始结点终端结点线性表结点之间具有先后的、线性的、一维的关系中间结点只有一个前趋和一个后继结点线性表的主要操作136初始化

给线性表相关参数赋初值求长度

求线性表的元素个数取元素

取给定位置的元素值定位

查找给定元素值的位置插入

在指定位置插入给定的值删除

删除指定位置的值或给定的值遍历

从头到尾扫描线性表，做指定的操作2.1CONTENTS从逻辑结构角度看线性表线性表的存储结构方法之一

——顺序表线性表的存储结构方法之二

——链表线性表的应用举例2.22.32.42.52.6顺序表和链表的比较本章小结138线性表中的元素相依次放在一个连续的存储空间中顺序表2.2线性表的存储结构方法之一——顺序表2.2.12.2.2顺序表的存储结构设计顺序表的运算2.2.3顺序表运算的讨论2.2线性表的存储结构方法之一——顺序表2.2.12.2.2顺序表的存储结构设计顺序表的运算2.2.3顺序表运算的讨论顺序表的存储结构设计141012345a0a1a2a3a4a5存数值存联系Ba1a2a0a3a4a5数值存储了，联系存储了吗？线性表结点逻辑特征：一一顺序对应物理地址相邻体现逻辑关系相邻用数组存储线性表，称作线性表的顺序存储结构或顺序映像，用这种方法存储的线性表称作顺序表。142线性表的顺序存储结构——顺序表定义

无论位于数组的什么位置，都能用相等的常量时间访问存储区中的任何元素。随机存取下标01...k-1kk+1...n-1元素a1a2...ai-1aiai+1...an逻辑上相邻对应物理地址相邻任一元素均可随机存取顺序表存储结构的设计143数组下标a1

a2

an

01n-112n内存元素序号LIST_SIZE-1备用空间last怎样设计顺序表的结构，才能完整描述整个顺序表信息？思考&讨论考虑线性表所有可能的情形顺序表存储结构的设计144数组下标a1

a2

an

01n-112n内存元素序号LIST_SIZE-1备用空间last怎样设计顺序表的结构，才能完整描述整个顺序表信息？思考&讨论考虑线性表所有可能的情形顺序表存储结构的设计145typedefintElemType;

//假定线性表元素的类型为整型#defineLIST_SIZE1024

//假定线性表的最大长度为1024typedefstruct{ElemTypedata[LIST_SIZE];

intlast;//指向最后结点的位置}SequenList;sequential:[si‘kwinʃəl]a.连续的(序贯的)list:[list]n.目录,名单,明细表数组下标a1

a2

an

01n-112n内存元素序号LIST_SIZE-1备用空间lastSequenList*LPtr；

//指向SequenList结构的指针结构描述

146例：typedefintElemType;【知识ABC】typedef————为类型取一个新名称typedef是C语言的关键字，用于在原有数据类型（包括基本类型、构造类型和指针等）的基础上，由用户自定义新的类型名称。typedef已有类型名

新命名的类型别名;简化类型声明提高程序可移植性关于结构类型应用的思考与讨论typedefstruct{ElemTypedata[LIST_SIZE];intlast;}SequenList;147这样的结构描述，系统会分配空间吗？Q1148SequenListL；SequenList*L；二者有什么区别？系统怎样分空间？结构类型的定义——类型是存储空间尺寸的描述结构变量的定义——按类型尺寸大小分配存储空间结构指针——指向单元放的是结构类型的数据，指针变量本身占一个int的空间Q2typedefstruct{ElemTypedata[LIST_SIZE];intlast;}SequenList;149定义了结构变量L后，顺序表中的结点如何表示？SequenListL；L.data[0]=a1;X=L.last;

结构成员引用方法1：结构变量

结构成员a1

a2

an

01n-1内存lastQ3用指针p指向结构空间后，其中的结点怎么用p表示？typedefstruct{ElemTypedata[LIST_SIZE];intlast;}SequenList;150SequenListL；Sequenlist*p=&L；p->data[0]=a1;X=p->last;

结构成员引用方法2：结构指针

结构成员a1

a2

an

01n-1内存lastQ4

typedefstructcard{intnum;charname[20];charauthor[10];charpublisher[30];floatprice;}ElemType;编号书名作者出版社价格151

当结点内容有多个数据项，而不是基本类型int时，怎么办？typedefintElemType;typedefstruct{ElemTypedata[LIST_SIZE];intlast;}SequenList;a1

a2

an

01n-1内存lastQ52.2线性表的存储结构方法之一——顺序表2.2.12.2.2顺序表的存储结构设计顺序表的运算2.2.3顺序表运算的讨论顺序表的主要操作153初始化

给线性表相关参数赋初值求长度

求线性表的元素个数取元素

取给定位置的元素值定位

查找给定元素值的位置插入

在指定位置插入给定的值删除

删除指定位置的值或给定的值遍历

从头到尾扫描线性表，做指定的操作顺序表插入运算——定义在线性表第i个（1

i

n+1）元素之前插入一个结点x，使长度为n的线性表

(a1，…ai-1，ai，…，an)变成长度为n+1的线性表

(a1，…ai-1，x，ai，…，an)154定义需将第i至第n共（n-i+1)个元素后移插入的位置，可以是指定的下标位置，也可以是指定的值之前，我们在此按前一种要求设计算法。顺序表插入运算——定义1550a11a2……k-1ai-1kaik+1ai+1…an-1lastan……LIST_SIZE-1

data[LIST_SIZE]移动元素的个数：last-k+10a11a2……k-1ai-1kXk+1ai…ai+1…an-1lastan…LIST_SIZE-1

插入前插入后数组下标特地用k表示，以与元素标号i区别顺序表插入运算——测试样例设计156

一般情形边界值异常情形插入的下标位置k0≤k≤nk=0,n!(0≤k≤n)顺序表未满未满已满或未满预期结果插入成功插入成功插入失败

顺序表插入运算——函数结构设计157功能描述输入输出顺序表元素的插入Insert_SqList顺序表地址(SequenList*)完成标志(int)0：异常插入值(ElemType)1：正常插入位置(int)函数名形参函数类型顺序表插入运算——数据结构描述158SequenList结构ElemTypedata[LIST_SIZE]intlast顺序表的地址：

SequenList*LPtr要插入的结点值x：ElemTypex插入的位置i：intiLPtrtypedefstruct{ElemTypedata[LIST_SIZE];intlast;}SequenList;0a11a2……k-1ai-1kaik+1ai+1…an-1lastan……LIST_SIZE-1

data[LIST_SIZE]LPtr结构描述

159顺序表插入运算——算法描述在顺序表中第i个位置插入新元素x第一步细化异常情形处理，返回不成功处理标志在顺序表中移动元素，空出下标为k的位置插入新元素x修改元素最后位置指针返回成功处理标志顶部伪代码描述在顺序表中第i个位置插入新元素x问题顺序表插入运算——算法描述160第一步细化第二步细化异常情形处理返回不成功处理标志若顺序表溢出，则return0;若k是非法位置，则return0;在顺序表中移动元素，空出下标为k的位置从顺序表的最后一个元素起向后移动(last–k+1)个元素插入新元素x将x放入表的k位置修改元素最后位置指针Last+1返回成功处理标志return1在顺序表中第i个位置插入新元素x问题161第二步细化若k是非法位置，则return0;若顺序表溢出，则return0;从顺序表的最后一个元素起向后移动(last–k+1)个元素将x放入表的k位置Last+1return1第三步细化if(LPtr->last>=LIST_SIZE－1)return0;if(k<0||k>(LPtr->last＋1))return0;j=LPtr->last;当

j>=kLPtr->data[j+1]=LPtr->data[j];j--;LPtr->data[k]=x;LPtr->last=LPtr->last+1;return10a11a2……k-1ai-1kaik+1ai+1…an-1lastan……LIST_SIZE-1

顺序表插入运算——程序实现162/*===========================================函数功能：顺序表运算——元素的插入函数输入：顺序表地址，插入值，插入位置函数输出：完成标志——0：异常1：正常=============================================*/intInsert_SqList(SeqList*LPtr,ElemTypex,intk){intj;if(LPtr->last>=LIST_SIZE-1)returnFALSE; //溢出

elseif(k<0||k>(LPtr->last+1))returnFALSE; //非法位置

else{for(j=LPtr->last;j>=k;j--) //从顺序表的最后一个元素起

{LPtr->data[j+1]=LPtr->data[j];//向后移动(last-k)个元素}LPtr->data[k]=x; //将x放入表的k位置

LPtr->last=LPtr->last+1; //修改最后结点指针last}returnTRUE;}顺序表插入运算——算法效率分析a1a2…aia1a2…xa1a2…ai+1…aiai+1…xaiai+1…an…anx…a1a2…aiai+1…an…a1a2…aiai+1…an…a1a2…aiai+1…an…an…O(1)O(n)O(?)最好情况最坏情况一般情况顺序表插入运算——算法效率分析164在第k个位置上插入一个结点的移动次数每一点插入概率Pk均等=1/(n+1)插入下标位置k012...k...n-1n移动次数nn-1n-2...n-k...10算法的平均时间复杂度为O(n)移动元素的平均次数在顺序表上做插入运算，平均要移动表上一半元素顺序表删除运算——定义165将线性表的第i(1≦i≦n)个结点删除，使长度为n的线性表：

(a1，…ai-1，ai，ai+1…，an)

变成长度为n-1的线性表

(a1，…ai-1，ai+1，…，an)定义设第i个结点对应下标为k，则需将第k+1至last共last-k个元素前移。顺序表删除运算——定义166删除前删除后0a11a2……k-1ai-1kaik+1ai+1k+2ai+2…an-1lastan…

data[LIST_SIZE]0a11a2……k-1ai-1kai+1k+1ai+2…an-2lastan-1…

移动元素的个数：last-(k+1)+1=last-kLIST_SIZE-1LIST_SIZE-1顺序表删除运算——测试样例设计

一般情形边界值异常情形删除下标位置k0≤k≤n-1k=0,n-1!(0≤k≤n-1)顺序表非空空非空空非空空预期结果删除成功删除失败删除成功删除失败删除失败删除失败输入：顺序表的地址，要删除的结点下标位置k输出：操作是否成功标志顺序表删除运算