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

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