数据结构研究的内容

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第一讲,：,数据结构及其研究的内容,Data Structure Curriculum&Its Research Field,山东师范大学传播学院 李大锦,Communication school of SDNU Li Da-Jin,一、数据结构课程的产生与发展,计算机处理的数据,最初是为了纯粹的数值计算,随着计算机的发展，,人们逐步探求用计算机来 处理和加工非数值问题,：,字符、图像、声音、表格等。处理非数值数据为程序设计提出了新的课题：,数据的表示？,+,数据的组织存储？,+,数据对象的有效运算？,数据结构,1,、,“,数据结构,”,作为一门独立的课程在国外是从,1968,年才开始设立的。,2,、,1968,年美国唐,欧,克努特教授开创了数据结构 的最初体系。,3,、,“,数据结构,”,在计算机科学中是一门综合性的专业基础课。,4,、数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。,二、数据结构课程的研究内容,计算机处理问题：,问题的数学模型,编程求解,数据结构,+,算法,=,程序设计,算法：,处理问题的策略,数据结构：,问题的数学模型,结构静力问题,线性方程组模型,人口增长问题,微分方程模型,更多的非数值计算问题无法用严格的数学方程来表示,1,、图书馆的书目检索问题：,每本书有一条记录，记录包括,:,书号、书名、作者、出版社、出版年月。书目的检索按记录中的任意数据项作为关键字进行查询。,记录在数据库中按顺序排列，对象之间是简单的线性关系这类数学模型称之为：,线性的数据结构,算法：,查找,模型,：,线性结构,2,、人机对弈问题,将每一种可能的棋盘格局存储在计算机里，对弈过程就是根据当前棋局搜索最优的棋局对策。棋盘格局之间的关系是一颗倒立的,树结构,算法：,搜索最优棋盘格局,模型：,树,3,、煤气管道敷设问题,这是一个称之为,图的结构,算法,：,如何规划总投资最少？,模型：,图（网）,概括的说,:,数据结构是一门讨论“,描述现实世界实体的数学模型,(,非数值计算,),及其上的操作在计算机中如何表示和实现,”的学科,三、相关的概念,1,、数据：,数据是客观事物的符号的表示，在计算机中指能够输入到计算机并被计算机程序处理的符号的总合。是计算机加工的,“,原料,”,。,如整数、实数、字符、图像、声音等。,2,、数据元素：,是数据结构中讨论的数据的基本单位，在计算机里通常作为一个整体进行考虑。,是数据结构中讨论的基本单位。数据元素有时包含若干,数据项,。,如描述一个职工的纪录：,数据元素,编号 姓名 性别 年龄 职务 职称,数据项,3,、数据对象：,是性质相同的数据元素的集合，是数据的一个子集。,4,、数据结构,：,是相互存在着某种逻辑关系的数据元素的集合。,带,结构,的数据元素的集合,指的是数据元素之间存在的,关系,线性结构,树结构,图结构,集合,数据结构的定义,数据结构可以用一个二元组来定义：,Data_srtuct=(D,S),D,是数据元素的有限集,，,S,是,D,上的关系,。,例：,复数的表示,：,Complex=(C,R),C,是两个实数的集合,c1,，,c2,，,R,是两个实数的关系,。,C2,是虚部。,例：,课题小组的管理程序,:,每个课题小组由一位老师、,1,至,3,名研究生和,1,至,6,名本科生组成。小组成员的关系是：教师指导研究生，研究生指导,1-2,名本科生。,Group=(P,R),其中：,P=T,G,1,G,2,G,n,S,11,S,12,S,nm,1n3 1m2,R=R,1,R,2,R1=1in 1n3,R2=1in 1jm 1n3 1m2,数据结构包括,“,逻辑结构,”,和,“,物理结构,”,两个层面。,逻辑结构：,是对数据元素之间的,逻辑关系,的描述。,物理结构：,是逻辑结构在计算机中的表示和实现（,映像,），故又称,“,存储结构,”,，存储结构中的每一个数据元素叫做,节点,，节点中的数据项称为,数据域,。,如前面所述的职工档案管理程序，可如下定义数据元素：,typedef struct,int NO,；,char name10;,int age;,bool sex;,char position20;,char pos_rank20;,char department20;,RecordType;,数据在计算机中表示方式：,顺序映像（顺序存储结构）：,以相 对的存储位置表示后继 关系。如前述的职工档案管理程序，所有职工的纪录组成一张表，这张表就使一个顺序存储结构。计算机在为这张表分配存储空间时分配一个连续的存储空间。,非顺序映像（链式存储结构）：,链式存储结构里相邻节点间的具体存储位置不是一个顺序关系，查询节点需要借助于,指针。,在不同的编程环境中，,存储结构可有不同的描,述方法。当用高级程序,设计语言进行编程时，,通常可用高级编程语言,中提供的数据类型描述,之。,5,、数据类型：,在程序设计时，我们必须先对变量进行声明，,不同的数据类型他的取值范围不同，施加其上的操作也不同：,如：整型,（,int,）,取值范围：,-32768 32767,可行的操作：,+,，,-,，*，,/,，,%,对于浮点型来说，不可以进行,%,操作。,数据类型,是一个值的集合和定义在此集合上的一组操作的总称,。,尽管同一个数据类型在不同的,CPU,上处理的方法不同，对程序原来说他们是相同的，程序员可以不考虑具体机器的,实现方法,。也就是说这些数据类型仅仅取决于它的,逻辑特性,，与在计算机内的,实现,无关。在,数学抽象,的角度上看可以称之为,抽象数据类型,。,抽象数据类型,：,（,A,bstract,D,ata,T,ype,：,ADT,）,抽象数据类型,是指一个,数学模型,以及定义在该模型上的一组,操作,。,抽象数据类型可以用一个三元组来表示：,（,D,，,S,，,P,）,D,是数据对象，,S,是,D,上的关系集，,P,是,D,的基本的操作集,。,ADT,抽象数据类型名,数据对象：,数据对象的定义,数据关系：,数据关系的定义,基本操作：,基本操作的定义,ADT,抽象数据类型名,如：,定义复数的抽象数据类型,ADT Complex,数据对象：,D,e1,e2,e1,e2RealSet,数据关系：,R,1,|e1,是复数的实数部分,e2,是复,数的虚数部分,基本操作：,AssignComplex(&Z,v1,v2),操作结果：构造复数,Z,其实部和虚部，分别被,以参数,v1,和,v2,的值。,DestroyComplex(&Z),操作结果：复数,Z,被销毁,GetReal(Z,&realPart),操作结果：用,r,ealpart,返回复数,Z,的实部值。,GetImag(Z,&ImagPart),操作结果：用,imgpart,返回复数,Z,的虚部值。,Add(z1,z2,&sum),用,sum,返回两个复数,z1,z2,的和值。,ADT Complex,6,、抽象数据类型的表示与实现,课后自己阅读。,四、算法和算法分析,算法,是为了解决某类问题而规定的一个有限长的操作序列，,算法的特征：,1,有穷性,2,确定性,3,可行性,4,有输入,5,有输出,有穷性：,在执行有穷步骤之后一定能结束。,确定性：,对于每种情况下所应执行的操作，,在算法中都有确切的规定,。,可行性：,算法中的所有操作都可以通过已经,实现的基本操作运算有限次实现之,。,有输入输出：,每个算法都要有算法需要加工,的数据，经加工后获得一定的结果。,1,、算法设计的要求：,正确性、可读性、健壮性、效率与低存储量要求。,2,、算法分析：,算法的效率：,指算法的时间效率。,衡量算法效率的方法：,1,、事后统计法：,2,、事前分析法：,一个算法所需要的时间取决于多个方面,：,1,、算法采用的策略,2,、问题的规模,3,、采用的语言,4,、机器的运算速度,5,、,编译程序产生的机器代码的质量,一个特定算法的,“,运行工作量,”,的大小，只依赖于问题的,规模,（通常用整数量,n,表示），或者说，它是问题规模的函数。,如：,int s;,for(int i=0;in;i+),s+=i;,问题的规模是,n,程序的运算工作量和,n,成线性的增长关系，或者说它可以看作是,n,的函数,f(n),。,随着规模的增大，算法执行所需要的时间的增长率和,f(n),的增长率是相同的。用,时间复杂度,来表示,算法的时间效率,，,T(n)=O(f(n),称,T(n),为算法的,(,渐近,),时间复杂度,如何估算时间复杂度？,算法,=,控制结构,+,原操作,（固有数据类型的操作）,算法的执行时间,=,原操作,的执行次数,原操作,的执行时间,算法的实行时间和原操作的执行次数是成正比的。从算法中选取一种对于所研究的问题来说是,基本操作,的,原操作,，以该,基本操作,在算法中,重复执行的次数,作为算法运行时间的衡量准则。,如上例中，时间复杂度为,O(n),例：,（,a,）,+x;s+=x;,（,b,）,for(i=1;i=n;+i)+x;s+=x;,（,c,）,for(j=1;j=n;+j),for(k=1;k=n;k+)+x;s+=x;,基本操作：,+x;s+=x;,a,的执行次数：,1,时间复杂度,O(1),b,的实行次数：,n,时间复杂度,O(n),c,的执行次数：,n,2,时间复杂度,O(n,2,),例：两矩阵相乘,#define n 100,void MatrixMultiply(int Ann,int Bnn,int Cnn),int i,j,k,for(i=1;i=n;+i)n+1,for(j=1;j=n;+j)n*(n+1),Cij=0;n,2,for(k=1;k=n,k+)n,2,(n+1),Cij=Cij+aik*bkj;n,3,最后的时间复杂度为,O(n,3,),。,算法的空间效率：,是指除输入和程序之外的辅助变量所占额外空间。,thanks!,