《数据结构》多媒体演示教案.ppt

数 据 结 构 多媒体演示教案,嘉兴学院信息学院 制作者：朱蓉 2005年,第一章 概论,基本内容：介绍数据、数据对象、数据结构、数据类型、算法、算法与数据结构的关系；描述算法的方法及从时间和空间角度分析算法的方法。 重点：掌握数据结构的三个方面和四种基本的存储方法以及算法的五个要素。 难点：掌握估算算法的时间复杂度的方法。 第一节 数据结构的概念及有关术语 第二节 算法,第一节 数据结构的概念及有关术语,数据：是信息的载体，是能够被计算机识别、存储、加工、处理的符号的总称。 数据元素：是数据的基本单位，由数据项组成。 数据对象：性质相同的数据元素的集合。 数据结构：是相互之间存在一种或多种关系的数据元素的集合，即是数据的组织形式。一般包括三方面的内容：1、数据的逻辑结构（线性结构、非线性结构）2、数据的存储结构（顺序存储、链接存储、索引存储、散列存储）3、数据的运算 数据类型：具有相同性质的计算机数据的集合及在这个数据集合上的一组操作。,第一节 数据结构的概念及有关术语,一、数据的逻辑结构 是指从具体问题抽象出来的数据模型，是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。 二元组表示：Data_Structure=(D,S) D：数据元素的有穷集合。 S：D上关系的集合。 数据的逻辑结构分为：线性结构和非线性结构 1、线性结构 逻辑特征：有且只有一个开始结点和一个终端结点，并且所有中间结点都最多只有一个前驱和一个后继。 2、非线性结构 逻辑特征：一个结点可能有多个前驱和后继。 数据的逻辑结构可用图示法形象的表示。,第一节 数据结构的概念及有关术语,二、数据的存储结构 是数据结构在计算机中的映象。 即是数据的物理结构，包括数据元素的映象和关系的映象。 元素的映象：用位串表示。 关系的映象：用存储单元之间的关系表示。 数据的存储结构可用四种基本的存储方法表示。 1、顺序存储方法 把逻辑上相邻的结点存储在物理上相邻的存储单元中。 2、链接存储方法 对逻辑上相邻的元素不要求物理位置相邻，元素之间的逻辑关系是由附加的指针表示。,第一节 数据结构的概念及有关术语,3、 索引存储方法 在存储结点信息的同时，建立附加索引表。 4、 散列存储方法 根据结点的关键字值直接计算出结点的存储地址。 三、数据的运算 数据的运算是定义在数据的逻辑结构上的，但运算的具体实现要在存储结构上进行。,第二节 算法,一、算法的概念及特征 概念：对特定问题求解步骤的一种描述。 特性：有穷性、确定性、可行性、输入与输出。 二、算法的描述 自然语言、伪代码、流程图、N-S图、PAD图等。 三、算法的分析 1、正确性 2、可读性 3、健壮性 4、高效率和低存储量要求 算法分析中最主要的三点： 算法的时间复杂度、算法的空间复杂度、算法本身的复杂度 算法的时间复杂度表示：T(n)=O(f(n) 算法的空间复杂度表示：S(n)=O(f(n),第二节 算法,例1：求两个N阶方阵的乘积 for (i=1;i=n;+i) for(j=1;j=n;+j) cij=0; for(k=1;k=n;+k) cij+=aik*bkj; ,例2：交换A和B的内容 t=a; a=b; b=t;,例3：变量计算 x=0;y=0;s=0; for(k=1;k=n;+k) +x;s+=x; for(i=1;i=n;+i) for(j=1;j=n;+j) +y;s+=y;,例4：变量计算 x=1;s=0; for(i=1;i=n;+i) for(j=1;j=i;+j) for(k=1;k=j;+k) +x;s+=x;,第二节 算法,例5:在数组中查找值为k的元素，若找到则输出其位置i(10 将常见的时间复杂度，按数量级递增排列： 常数阶O(1)，对数阶O(log2n)，线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n2)、立方阶O(n3)、K次方阶O(nk)、指数阶O(2n)。,