数据结构教程-绪言.ppt
算法与数据结构,上课:48学时上机:24学时,1+2+3+100S=0S=S+1S=S+2:S=S+100,s=0;for(i=1;i=100;i+)s=s+i;sum=s;,计算机解决具体问题的一般步骤,从具体问题中抽象出一个适当的数学模型设计一个解此数学模型的算法编写程序进行测试得到最终解答,1+2+3+100S=0S=S+1S=S+2:S=S+100,酒店管理系统中的客房分配问题,电话号码查询问题,姓名丁一马二张三李四王五,项目1跳高A标枪D标枪D铅球E跳远B,项目2跳远B铅球E100米C200米F200米F,项目3100米C200米F跳高A,运动会项目安排,A:跳高B:跳远C:100米D:标枪E:铅球F:200米,电话号码查询问题(线性)酒店管理系统中的客房分配问题(线性)运动会项目安排(图)计算机和人对弈问题(树)N个城市之间搭设通讯线路最短问题(图),算法与数据结构,绪言线性表串内部排序数组树树的查找与树的应用图,第一章 绪言,什么是算法与数据结构基本概念与术语时间复杂度的运算算法与数据结构的发展简史算法与数据结构在计算机科学中的地位,算法与数据结构,算法与数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科,基本概念与术语,数据对客观事物的符号表示数据元素数据的基本单位,即数据集合中的个体由一个或多个数据项组成数据对象性质相同的数据元素的集合,是数据的一个子集整数数据对象是集合 N=.-2,-1,0,1,2,.字母字符数据对象是集合 C=A,B,.,基本概念与术语,数据结构是相互之间存在一种或多种特定关系的数据元素的集合数据的逻辑结构:线性结构与非线性结构数据的存储结构:值的表示和关系的表示数据的运算:定义在数据的逻辑结构上 实现在存储结构上,数据的基本运算,插入:在数据结构中的指定位置上增添新的 数据元素删除:删去数据结构中某个指定的数据元素更新:改变数据结构中某个数据元素的值查找:在数据结构中寻找满足某个特定要 求的数据元素排序:重新安排数据元素之间的逻辑顺序关系,使之按值由小到大或由大到中的次序排列,数据逻辑结构的表示,二元组B=（K，R）K:是结点,即数据元素的有穷集合.由有限个结点所构成.R:是K上的关系的有穷集合.由有限个关系所构成的集合.后续结点 前驱结点 相邻结点终端结点开始结点内部结点,若k,kK，且R，则称k 是k的后续，k是k的前驱。k与k 为相邻结点若不存在一个k使R,则称k为R的开始结点若不存在一个k 使R,则称k为R的终端结点 若k即不是终端结点又不是开始结点,则称K是内部结点。,设有数据逻辑结构为:B=(K,R)K=k1,k2,k3,k4,k9R=,画出这个逻辑结构的图示,并确定相对于关系R,哪些结点是开始结点,哪些结点是终端结点,基本概念与术语,算法:对特定问题求解步骤的一种描述 是指令的有限序列算法的五个特性有穷性确定性可行性输入输出,算法设计的要求,正确性程序不含语法错误对于几组输入数据能够得出满足规格说明要求的结果对于精心选择的典型输入数据能够得出满足规格说明要求的结果程序对于一切合法的输入数据都能产生满足规格说明要求的结果,算法设计的要求,正确性可读性健壮性效率与低存储量需求效率:指算法执行时间存储量需求:算法执行过程中所需要的最大存储空间,算法效率的度量,事后统计的方法依据算法选用何种策略问题的规模书写程序的语言编译程序所产生的机器代码和质量机器执行指令的速度事前分析估算的方法,时间复杂度,运行时间:指一个算法在计算机上运行所花费的时间 简单操作的次数*一次简单操作所用的时间时间复杂性:算法中包含简单操作次数的多少问题的规模 nT(n):时间复杂性,s=0;for(i=1;i=n;i+)s=s+i;sum=s,累记求和,s=0;1次i=1;1次1 if in then go 2 N+1次 s=s+i;N次 i=i+1;N次 go to 1;N次2 sum=s;1次,T(n)=4n+4,T(n)=4*N+4,矩阵相加,for(i=1;i=n;i+)for(j=1;j=n;j+)ci,j=ai,j+bi,j;,i=1 1次(3)if in then goto(4)N+1次 j=1 N次(1)if jn then goto(2)N(N+1)次 ci,j=ai,j+bi,j N*N次 j=j+1 N*N次 goto(1)N*N次(2)i=i+1 N次 goto(3)N次(4)end,T(n)=2*n+2+4n*n+n+2*n=4n*n+5*n+2,求两个N阶方阵的乘积,for(i=1;i=n;i+)for(j=1;j=n;j+)ci,j=0 for(k=1;k+n;k+)cij=cij+aik*bkj,T(n)=2n*n*n+3n*n+2*n+1,时间复杂度,算法中基本操作重复执行的次数是问题规模的基本函数f(n)算法的时间复杂度记作:T(n)=O(f(n)一般是算法中频率最大的语句频度累计求和:T(n)=O(n)矩阵相加:T(n)=O(n*n)两个n阶方阵的乘积:T(n)=O(n*n*n),在数组An中查找值为k的元素,若找到,则输出其位置i,否则输出0,i=n-1;while(i=0,最坏时间复杂度 T(n)=O(n),参考书推荐,算法与数据结构 清华大学出版社 软件专业技术资格和水平考试教材(软件知识)清华大学出版社数据结构 北京航空航天大学出版社数据结构习题与解析 清华大学出版社计算机等级考试教程 机械工业出版社计算机专业研究生入学考试全真题解 数据结构与程序设计分册 人民邮电出版社数据结构500题 人民邮电出版社,12个乒乓球，其中有一个质量不标准，利用天平最少几次可以在最坏的情况下确定出有问题的球是哪个？是轻了还是重了？,思考题,
