数据结构（Python Java）（微课版） 课件 第1章 数据结构与算法概论

数据结构与算法设计计算机解决问题的步骤非数值数学模型1.1问题求解计算机求解现实问题计算机解决问题的步骤一个长75cm、宽60cm的长方形纸板，平均切割成大小相等的正方形纸板，使每个正方形纸板的面积最大，共可切割成多少个正方形纸板？人要和计算机进行有效交流，必须通过程序计算机世界机器语言现实世界自然语言程序计算机解决问题的步骤分析问题、设计算法、编写程序、执行程序人：分析问题、确定解决方案、编写程序计算机：执行程序最终获得问题的解数据模型数值问题：数学方程非数值问题：线性表、树、图等数据结构数据模型一个简单的图书信息检索系统包括一张按索书号、条码号和书名的顺序排列的图书信息表。图书信息表中的顺序关系可以被抽象成线性结构图书信息检索系统——线性数据结构书名条码号索书号书架号什么是算法90073160TP393.92/1811-12-3数据库原理与应用70002001TP391.41/3141-12-1软件测试项目实践00777680TP311.52/8371-13-2Linux系统编程50010241TP316.76/4541-10-2Python程序设计90115601TP311.56/1291-14-1对弈问题——树人机对弈问题是一个古老的人工智能问题，对弈过程是在一定规则约束下的随机过程。其解决问题的思路是将对弈策略事先存入计算机，包括对弈过程中所有可能出现的情况和相应的对策。城市道路问题——图假设某人要从地点A骑车到地点G，使用导航系统查询合适的骑行路线。导航系统为解决这个问题，须建设地区交通的数学模型，描述各个地点及其之间的交通情况。对于这类问题，通常采用“图”来描述路况——将地点抽象成一个点，地点之间的路线抽象成一条线，路线的距离用线上的数字描述。这些点、线就组成了一个图。小结1.1问题求解计算机解决问题的步骤非数值数学模型数据结构与算法设计数据结构的相关概念抽象数据类型1.2数据结构概述数据(data)信息的载体，是对客观事物的符号表示，能够被计算机识别、存储和加工处理。图像、声音、视频等都可通过编码由计算机处理，因此也属于数据的范畴数据元素(dataelement)数据的基本单位,也称为元素、结点或记录数据项数据元素可由若干个数据项（字段、域）构成数据项是数据不可分割的最小单位数据结构的相关概念数据对象数据的子集具有相同性质的数据元素的集合姓名班级学号小明3020112小红302027小方3020232姓名课程名成绩小明高数85小红高数90小红英语88数据数据元素数据对象数据项数据结构数据元素的集合中，元素相互之间的关系数据的逻辑结构集合线性结构树型结构图状结构数据的物理(存储)结构数据在存储器中位置的关系数据逻辑结构表示： Data_Structures=(D,S)D是数据元素的有限集S是数据元素关系的有限集GROUP=(P，R)P={M，D1，D2，E11，E12，E13，E21，E22，E23}R={<M,D1>,<M,D2>,<D1,E11>,<D1,E12>…<D２,E23>}D1D2E11E12E13E21E23E22M某公司有1名经理(M)，2个部门经理(D)，每个部门各有3名职员(E)。人员之间的关系是：经理指导部门经理的工作，部门经理指导职员的工作。GROUP=(P，R)P={M，D1，D2，E11，E12，E13，E21，E22，E23}R={<D1,M>,<M,E11>,<E11,E21>,<E21,E12>…<E22,E23>}D1D2E11E12E13E21E23E22M某公司有1名经理，2个部门经理，每个部门各有3名职员。人员之间的关系是：按人员年龄从大到小排列。GROUP=(P，R)P={M，D1，D2，E11，E12，E13，E21，E22，E23}R={(M,D1),(M,D2),(D1,D2),(D2,E12)…(D２,E22)}D1D2E11E12E13E21E23E22M某公司有1名经理，2个部门经理，每个部门各有3名职员。人员之间的关系是：人员之间的友好关系。数据的存储结构数据元素的存储用二进制位(bit)的位串表示数据元素(321)10=(501)8=(101000001)2‘A’=(101)8=(01000001)2关系的存储顺序存储结构用元素之间存储的相对位置表示关系链式存储结构用存储元素的引用（指针）表示关系抽象数据类型抽象数据类型是描述数据结构的一种理论工具，其目的是使人们能够独立于程序的实现细节来理解数据结构的特性。抽象数据类型一般通过数据对象、数据关系以及基本操作来定义。ADT抽象数据类型名{

数据对象D：<数据对象的定义>

数据关系R：<数据关系的定义>

基本操作P：<基本操作的定义>}小结1.2数据结构概述数据结构的相关概念抽象数据类型数据结构与算法设计算法及其特性算法设计的要求算法描述方法1.3算法概述算法评价算法(Algorithm)对特定问题求解步骤的一种描述是指令的有限序列算法的特性有穷性确定性可行性输入输出算法及其特性正确性：算法应当满足具体问题的需求，按算法编码好的计算机程序的执行结果应当符合预先设定的功能和性能要求。可读性：一个算法应当思路清晰、层次分明、易读易懂。可读性好，易于理解。健壮性：指一个算法对不合理数据输入的反应能力和处理能力，也被称为容错性。高效性：一个算法应当有效使用存储空间和有较高的效率。对于同一个问题，通常可以有多个解决算法，其中执行时间短、占用存储空间少的算法即“好的算法”。算法设计的要求自然语言算法描述框图算法描述伪代码算法描述高级程序语言编写的程序或函数算法描述方法事前估算法（定性分析）：对算法所消耗资源的一种估算方法算法的策略问题的规模书写程序的语言编译程序产生的机器代码的质量机器执行指令的速度事后统计法（定量分析）：将算法实现，测算其时间和空间开销评价算法算法评价指标执行程序需要占用多少机器资源时间资源算法运行时花费的时间代价空间资源程序执行中占用的内存空间代价时间复杂性和空间复杂性T(n)：2n3+3n2+2n+1算法的时间复杂性分析算法中所有语句执行时间之和语句的执行时间：该语句的频度(语句重复执行的次数)，与该语句执行一次所需时间的乘积。//求两个n阶方阵的乘积C=A*BWhile(i<n){//n+1while(j<n){//n*(n+1)C[i][j]=0//n*n while(k<n){//n*n*(n+1) C[i][j]=C[i][j]+A[i][k]*B[k][j]

//n*n*n k+=1} j+=1}i+=1}#求两个n阶方阵的乘积C=A*Bwhilei<n:#n+1whilej<n:#n*(n+1)C[i][j]=0#n*n whilek<n:#n*n*(n+1) C[i][j]=C[i][j]+A[i][k]*B[k][j]

#n*n*n k+=1 j+=1i+=1//求两个n阶方阵的乘积C=A*BWhile(i<n){//n+1while(j<n){//n*(n+1)C[i][j]=0//n*n while(k<n){//n*n*(n+1) C[i][j]=C[i][j]+A[i][k]*B[k][j]

//n*n*n k+=1} j+=1}i+=1}#求两个n阶方阵的乘积C=A*Bwhilei<n:#n+1whilej<n:#n*(n+1)C[i][j]=0#n*n whilek<n:#n*n*(n+1) C[i][j]=C[i][j]+A[i][k]*B[k][j]

#n*n*n k+=1 j+=1i+=1算法的时间复杂性分析算法时间取决于控制结构和原操作的综合效果f(n)是算法中频度最大的语句频度，通常是最深层循环内的原操作执行的次数。随着n的增长，算法执行时间的增长率和f(n)的增长率相同。算法时间复杂度记作：T(n)=O(f(n))O(n)：n3常见函数比较通常有如下的函数关系

c<log2n<n<nlog2n<n2<n3<2n指数时间的关系为

O(2n)<O(n!)<O(nn)算法的时间复杂度不仅是问题规模n的函数，还与所处理的数据集有关 (1)1,2,3,4,5,6,7,