计算机软件技术基础--数据结构ppt课件

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数据结构概述,2007,东北大学网络学院计算机软件技术基础课程组,*,计算机软件技术基础-数据结构ppt课件,主要内容,数据结构讨论的范畴,基本概念,抽象数据类型,算法的特性、分类及度量,数据结构的选择和评价,主要内容,数据结构,讨论的范畴,程序=数据结构+算法,数据结构：问题的数据模型,数据的逻辑结构,数据的物理结构,数据的运算,算法：求解问题的策略,查找,排序,数据结构讨论的范畴,数据结构讨论的范畴,数值计算,的程序设计问题,圆的面积（函数）,结构静力分析计算,（线性,代数,方程组）,人口增长预报（微分方程）,数据结构讨论的范畴,数据结构讨论的范畴,非数值计算问题,的程序设计问题,学生信息管理系统（表）,算法：需要检索的项目如何检索、用户界面,模型：各种表格,人机对弈（树）,算法：,对弈的规则和策略,模型：,棋盘及棋盘的格局,教学计划编排问题（图）,算法：,课表编排的规则,模型：,课程以及课程间关系,数据结构讨论的范畴,计算机软件技术基础-数据结构ppt课件,计算机软件技术基础-数据结构ppt课件,计算机软件技术基础-数据结构ppt课件,数据结构讨论的范畴,数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科,学习数据结构的目的,是为了了解计算机处理对象的特性，将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理,通过算法训练来提高学生的思维能力，通过程序设计的技能训练来促进学生的综合应用能力和专业素质的提高,数据结构讨论的范畴,数据结构基本概念,数据（data),所有能输入到计算机中去的描述客观事物的符号,是计算机操作的对象的总称,是计算机处理的信息的某种特定的符号表示形式,数据元素（data element）,数据结构中讨论的基本单位,，也称结点（node）,或记录（record）,是数据（集合）中的一个“个体”,例如：学生信息检索系统中学生信息表中的一个记录、对弈问题中状态树的一个状态、排课问题中的一个顶点等，都被称为一个数据元素,数据结构基本概念,数据结构基本概念,数据项（data item）,有独立含义的数据最小单位，也称域(field),数据元素可以是数据项的集合,数据对象,是性质相同的数据元素的集合，,是数据的一个子集。数据元素是数据对象的一个实例,例如,整数数据对象是集合N=-2,-1,0,1,2.,数据结构基本概念,数据结构基本概念,数据结构（data structure),数据结构是相互之间存在着某种逻辑关系的数据元素的集合,例如：在一维数组 a1,a2,a3,a4,a5,a6 的数据元素之间存在如下的次序关系|i=1,2,3,4,5,数据结构基本概念,什么是数据结构？,数据结构的三个方面,数据的逻辑结构,从具体问题抽象出来的数学模型，它与数据的存储无关,线性结构：线性表、栈、队列,非线性结构：树、图,数据的存储结构,数据结构在计算机中的标识（又称映像）称为数据的,物理结构，,数据的逻辑结构在计算机,存储器中的实现,顺序存储,链式存储,数据的运算,检索、排序、插入、删除、修改等,什么是数据结构？,什么是数据结构？,(1),数据的逻辑结构,数据的逻辑结构可以用一组数据（表示为结点集合D），以及这些数据之间的一组二元关系（关系集合S）来表示：(D，S),其中,D 是数据元素的有限集，,是由有限个结点组成的集合，每一个结点都代表一个数据或一组有明确结构的数据,S 是 D上关系的有限集，,是定义在集合D上的一组关系，用它描述结点数据之间的逻辑关系,Data_Structures=(D,S),什么是数据结构？(1)Data_Structures=,什么是数据结构？,(2),数据的逻辑结构,结点的数据类型,高级语言中指数据的取值范围及其上可进行的操作的总称,例C,语言中,基本数据类型：int,char,float,double等,构造数据类型：数组、结构体、共用体、枚举,指针、空(void)类型,用户也可用typedef 自己定义数据类型,结点的类型可以是基本数据类型，也可以根据应用的需要来灵活定义,typedef struct,int num;,char name20;,float score;,STUDENT;,STUDENT stu,*pstu;,什么是数据结构？(2)typedef struct,什么是数据结构？,(3),数据的逻辑结构,关系S阐明数据结构的特性,线性结构（linear structure）,一个对一个,树型结构（tree structure）,一个对多个,图状结构（graph structure）,多个对多个,什么是数据结构？(3),什么是数据结构？,(4),数据的逻辑结构,线性结构,关系S 是一种线性关系，或称为前后关系，有时也称为大小关系。关系S是有向的，且满足全序性和单索性等约束条件,全序性,线性结构的全部结点两两皆可以比较前后（关系S）,单索性,每一个结点a都存在唯一的一个直接后继结点b,什么是数据结构？(4),什么是数据结构？,(5),数据的逻辑结构,树型结构,树型结构又称为层次结构，其关系S称为层次关系,树型结构的最高层次的结点称为根（root）结点,只有它没有父结点,每一个结点可以有多于一个的子结点，但是它只能有唯一的父结点,图状结构,也称为结点互联的网络结构，允许结点具有多个父结点,图结构的关系S没有任何约束，无法利用关系S的约束来设计图结构的存储结构,因特网的web网页链接关系,是一个非常复杂的图结构,什么是数据结构？(5)因特网的web网页链接关系,什么是数据结构？,(6),数据的逻辑结构,三种结构的区别,树结构和图结构的基本区别就是“每个结点是否仅仅从属一个父结点”,线性结构和树结构的基本区别是“每个结点是否仅仅有一个直接后继”,什么是数据结构？(6),什么是数据结构？,(7),数据的存储（物理）结构,数据的逻辑结构在计算机存储器中的实现（,逻辑结构在存储器中的映象）,计算机的主存储器的特性,存储空间提供了一种具有,非负整数地址编码的，相邻单元的集合,其基本的存储单元是,字节,计算机的指令具有,按地址随机访问存储空间内任意单元的能力,，访问不同地址所需的访问时间基本相同,什么是数据结构？(7),什么是数据结构？,(8),数据的存储（物理）结构,数据的存储结构是建立一种映象，对于数据逻辑结构（D,s）,其中sS,“数据元素”的映象,对它的结点集合D建立一个从D到存储器的单元的映射：对于每一个结点dD都对应一个唯一的连续存储区域。,“关系”的映象,每一个关系元组（d1,d2）s（其中d1,d2D是结点），d1,d2的逻辑后继关系应映射为存储单元的地址顺序关系（或链接关系）,什么是数据结构？(8),什么是数据结构？,(9),数据的存储（物理）结构,顺序存储结构,用一块无空隙的存储区域存储数据称为顺序存储,借助元素在存储器中的相对位置来表示数据元素间的逻辑关系,结点间的逻辑后继关系用存储单元的自然顺序关系来表达,链式存储结构,借助指示元素存储地址的指针表示数据元素间的逻辑关系,两个结点的逻辑后继关系可以用指针的指向来表达,什么是数据结构？(9),什么是数据结构？,(10),数据的存储（物理）结构,L,o,Lo+m,Lo+(i-1)*m,Lo+（n-1)*m,存储地址,存储内容,Loc(,元素i)=Lo+（i-1)*m,顺序存储,元素1,元素2,元素i,元素n,head,什么是数据结构？(10)LoLo+mLo+(i-1)*mL,什么是数据结构？,(11),数据的逻辑结构与存储结构密切相关,算法设计 逻辑结构,算法实现 存储结构,什么是数据结构？(11)算法设计 逻辑结构,抽象数据类型（Abstract Data Type 简称ADT）,抽象数据类型是描述数据结构的一种理论工具,特点是把数据结构作为独立于应用程序的一种抽象代数结构来描述,抽象数据类型不同于具体的数据结构,目的是使人们能够独立于程序的实现细节来理解数据结构的特性,抽象数据类型（Abstract Data Type 简称AD,抽象数据类型,（1）,抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关,即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用,抽象数据类型（1）,抽象数据类型,(2),是指一个数学模型以及定义在此数学模型上的一组操作,。,“抽象”的定义在于数据类型的数学抽象特性,抽象数据类型的形式定义：,ADT=（D，S，P）,其中：D是数据对象；S是D上的关系集；P是对D的基本操作集。,ADT,抽象数据类型名,数据对象：,数据对象的定义,数据关系：,数据关系的定义,基本操作：,基本操作的定义,ADT,抽象数据类型名,抽象数据类型(2)ADT 抽象数据类型名,例如，抽象数据类型复数的定义：,ADT Complex,数据对象：,De1,e2e1,e2RealSet ,数据关系：,R1|e1是复数的实数部分；|e2 是复数的虚数部分,基本操作：,AssignComplex(&Z,v1,v2),操作结果：构造复数 Z,其实部和虚部分别被赋以参数 v1 和 v2 的值。,DestroyComplex(&Z),操作结果：复数Z被销毁。,GetReal(Z,&realPart),初始条件：复数已存在。,操作结果：用realPart返回复数Z的实部值。,GetImag(Z,&ImagPart),初始条件：复数已存在。,操作结果：用ImagPart返回复数Z的虚部值。,Add(z1,z2,&sum),初始条件：z1,z2是复数。,操作结果：用sum返回两个复数z1,z2 的和值。,ADT Complex,例如，抽象数据类型复数的定义：,抽象数据类型,(3),ADT 重要特征,数据抽象,用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）,数据封装,将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节,抽象数据类型(3),抽象数据类型,(4),ADT,与数据类型的关系,抽象数据类型和数据类型实质上是一个概念,“抽象”的意义在于数据类型的数学抽象特性。,抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现,抽象数据类型的范畴更广，它不再局限于各处理器中已定义并实现的数据类型，还包括用户在设计软件系统时自己定义的数据类型,抽象数据类型(4),抽象数据类型,(4),抽象数据类型(4),算法的特性与度量,算法（algorithm）,解决某一特定问题的,具体步骤的描述,，是指令的有限序列,程序是算法的一种实现，计算机按照程序逐步执行算法，实现对问题的求解,算法的特性与度量,算法的特性与度量,算法的特性,有穷性,对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成,确定性,对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径,算法的特性与度量,算法的特性与度量,(1),算法的特性,可行性,算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之,输入,作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中,输出,它是一组与“输入”有确,定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能,算法的特性与度量(1),算法的特性与度量,(2),算法,设计的原则,正确性(correctness),可读性(readability),健壮性(robustness),高效率与低存储量,正确性：算法应当满足以特定的“规,格说明”方式给出的需求以下四个层,次：,无语法错误、随意数据、刻意,数据、一切合法数据,可读性：,算法主要