数据结构83.ppt

数据结构;课程内容： 计算机软件的基础知识———数据结构 课时安排： 周二晚上上机——锡昌科技楼402 周四1、2节（单周）——锡昌科技楼505 周五下午——锡昌科技楼505 ;第1章 绪言;例2 计算机和人对奕问题;例3 多叉路口交通灯管理问题;3 .数据结构定义: 是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科;§ 1.2 基本概念和术语 1 .数据元素和数据项： 1)数据（data)—是对客观事物的符合表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 2)数据元素（data element）—数据的基本单位，在程序中作为一个整体而加以考虑和处理。数据元素又为元素、结点、顶点或记录。 3)数据项（data item）—是数据不可分割的最小单位。通常作为数据元素的分量，数据项又称为字段或域。 2 .数据的数据结构（data structure）—相互之间存在一种或多种特定关系的数据元素的集合。;3.数据的逻辑结构: 1)逻辑关系--数据元素间的关联方式或称‘邻接关系’。 2)逻辑结构--数据元素间逻辑关系的整体。它只抽象反映数据元素的逻辑关系。 ;5.数据类型—一个值的集合和定义在这个值集上的一组操作的总称。(操作是指数据结构上需要或能够进行的处理。) 原子类型――非结构。例如C语言中的整型等基本类型 数据类型 结构类型――可以分解，成分可以是结构、非结构。例如数组 ;元素n;1536;;;§1．3 抽象数据类型的表示与实现（略） ; §1．4 算法和算法分析 1.4.1算法的概念 ：算法是特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。 ★算法具有以下重要特性： ;1.4.3.算法效率的度量：算法效率——用依据该算法编制的程序在计算机上执行所消耗的时间来度量 1.事后统计——利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分 缺点：①必须先运行依据算法编制的程序 ②所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣 2.事前分析估计——一个高级语言程序在计算机上运行所??耗的时间取决于： ①依据的算法选用何种策略 ②问题的规模 ③程序语言 ④编译程序产生机器代码质量 ⑤机器执行指令速度 同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，———所以使用绝对时间单位衡量算法效率不合适 ;估算时间复杂度的方法 ：从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则 。;;4.频度：是指该语句重复执行的次数。频度与问题的基本操作执行次数相同，故时间复杂度可通过频度来计算。 例２ {++x;s=0;} 将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1) 即常量阶。 例３、for(I=1;I=n;++I) {++x;s+=x;} 将x自增看成是基本操作，则语句频度为：n　其时间复杂度为：O(n) 即时间复杂度为线性阶。;例４、for(j=1;j=n;++j) 　　　　for(k=1;k=n;++k) {++x;s+=x;} 将x自增看成是基本操作，则语句频度为：n2,　其时间复杂度为：O(n2) 即时间复杂度为平方阶。 (补充)定理：若A(n)=a m n m +a m-1 n m-1 +…+a1n+a0是一个m次多项式，则A(n)=O(n m)　（证略）。 例５for(i=2;i=n;++i) for(j=2;j=i-1;++j) {++x;a[i，j]=x;} 语句频度为： 1+2+3+…+n-2=(1+n-2) ×(n-2)/2 =(n-1)(n-2)/2 =(n2-3n+2)/2 ∴时间复杂度为O(n2) 即此算法的时间复杂度为平方阶。 ; 一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即