数据结构教程--绪言.ppt

算法与数据结构,上课:48学时 上机:24学时,1+2+3+100 S=0 S=S+1 S=S+2 : : S=S+100,s=0; for (i=1;i=100;i+) s=s+i; sum=s;,计算机解决具体问题的一般步骤,从具体问题中抽象出一个适当的数学模型 设计一个解此数学模型的算法 编写程序 进行测试 得到最终解答,1+2+3+100 S=0 S=S+1 S=S+2 : : S=S+100,酒店管理系统中的客房分配问题,电话号码查询问题,姓名 丁一 马二 张三 李四 王五,项目1 跳高A 标枪D 标枪D 铅球E 跳远B,项目2 跳远B 铅球E 100米C 200米F 200米F,项目3 100米C 200米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,k9 R=, , , 画出这个逻辑结构的图示,并确定相对于关系R, 哪些结点是开始结点,哪些结点是终端结点,基本概念与术语,算法:对特定问题求解步骤的一种描述 是指令的有限序列 算法的五个特性 有穷性 确定性 可行性 输入 输出,算法设计的要求,正确性 程序不含语法错误 对于几组输入数据能够得出满足规格说明要求的结果 对于精心选择的典型输入数据能够得出满足规格说明要求的结果 程序对于一切合法的输入数据都能产生满足规格说明要求的结果,算法设计的要求,正确性 可读性 健壮性 效率与低存储量需求 效率:指算法执行时间 存储量需求:算法执行过程中所需要的最大存储空间,算法效率的度量,事后统计的方法 依据算法选用何种策略 问题的规模 书写程序的语言 编译程序所产生的机器代码和质量 机器执行指令的速度 事前分析估算的方法,时间复杂度,运行时间: 指一个算法在计算机上运行所花费的时间 简单操作的次数*一次简单操作所用的时间 时间复杂性: 算法中包含简单操作次数的多少 问题的规模 n T(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),参考书推荐,算法与数据结构 清华大学出版社 软件专业技术资格和水平考试教材 (软件知识) 清华大学出版社 数据结构 北京航空航天大学出版社 数据结构习题与解析 清华大学出版社 计算机等级