数据结构chap01.ppt

Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Click to edit Master title style,2 数据结构题集（C语言版）,严蔚敏 吴伟民 清华大学出版社,参考教材,1 数据结构（C语言版）,严蔚敏 吴伟民 清华大学出版社,第一章 绪论,第一章 绪论,1.1,数据结构讨论的范畴；,1.2,数据结构的有关基本概念；,1.3,抽象数据类型的表示与实现；,1.4,算法及算法分析（算法评价）,数据结构是什么?,Niklaus Wirth,AlgorithmData Structures Programs,程序设计：,为计算机解题（处理问题）编制的一组,指令集。,算法：,对某类信息进行处理,，,处理问题的策略。,数据结构：,处理的信息怎么表示,，,问题的数学模型。,任何问题都包括这两个方面的问题，包括数值计算和非数值计算,1.1 数据结构讨论的范畴,数值问题与非数值问题,1）数值计算中的程序设计的问题,例1 已知：游泳池的长len和宽wide，求面积area?,建模型：问题涉及的对象：游泳池的长len 宽wide，面积area；,对象之间的关系：area=len,wide （算法）,设计求解问题的方法,1.1 数据结构讨论的范畴,编程,main(),int len,wide,area;scanf(“%d%d%n”,学号 姓名 性别 出生日期 籍贯 入学成绩 所在班级,00201,杨润生 男 82/06/01 广州 561 00计算机200102 石磊 男 83/12/21 汕头 512 00计算机100202 李梅 女 83/02/23 阳江 532 00计算机2,00301 马耀先 男 82/07/12 广州 509 00计算机3,2）非数值计算的程序设计问题,例 2 已知某级学生情况,要求分班按入学成绩排列顺序,。,学生管理数据库系统,1.1 数据结构讨论的范畴,算法：？需要解决的问题？如何解决？用户界面？,模型：？各种各样的表格和数据库,在这类文档管理的数学模型中,计算机处理的对象之间通常存在着一种最简单的线性关系,这类数学模型称为线性模型。,例 3 迷宫问题。在迷宫中，每走到一处，接下来可走的通路有三条。计算机处理的这类对象之间通常不存在线性关系。若把从迷宫入口处到出口的过程中所有可能的通路都画出，则可得一棵“树”,。,入口,出口,算法：？走迷宫的规则和策略,模型：？迷宫、迷宫的每一处,城市间交通网问题,算法：？交通网中要解决的问题？,模型：？每一条通路、每一个路口,综合各种程序设计问题，抽取它具体的物理含义，可以得到几种数学模型，例如：,1、与数值计算相关的问题：,线性代数方程、非线性代数方程、常微分方程（计算机求解的问题就是计算数学要研究的问题）,2、与非数值计算相关的问题：,问题的表示和求解的方法，就是数据结构要讨论的内容。,数据结构的研究问题：,非数值数据之间的结构关系，,及如何表示，如何存储，如何处理。,本课程讨论的问题：,应用中常用的几种数据间的结构关系，,及如何表示,如何存储，如何处理。,1.1 数据结构讨论的范畴,数据：,所有能输入到计算机中,且被计算机处理的符号的集合，,是计算机操作对象的总称；,是计算机处理的信息的某种特定的符号表示形式。,数据元素：,数据中的一个“个体”,数据结构中讨论的基本单位。相当于“记录”,在计算机程序中通常作为一个整体考虑和处理。,1.2 数据结构的有关概念,数据项:,相当于记录的“域”,是数据的不可分割的最小单位,如学号。数据元素是数据项的集合。,例如：运动员（数据元素）,数据对象,：,性质相同的数据元素的集合.,例如:所有运动员的记录集合,姓名,俱乐部名称,出生日期,参加日期,职务,业绩,年,月,日,1.2 数据结构的有关概念,数据结构：,是相互间存在某种关系的数据元素集合,。,例如：一个含有12位数的十进制数，可以用三个4位的十进制数表示,3214,6587,9345-,a1(3124),a2(6587),a3(9345),在a1,a2和a3之间存在“次序”关系，次序不能颠倒,a1,a2,a3!=a2,a1,a3,数据结构是带结构的数据元素的集合,1.2 数据结构的有关概念,又例：2行3列二维数组a1,a2,a3,a4,a5,a6,行的次序关系：,row=,列的次序关系:,col=,a1,a2,a3,a4,a5,a6,数据结构是带结构的数据元素的集合,1.2 数据结构的有关概念,再例，一维数组a1,a2,a3,a4,a5,a6存在,次序关系,：,|i=1,2,3,4,5,6,不同的关系构成不同的结构,数据结构是带结构的数据元素的集合,1.2 数据结构的有关概念,对每种数据结构，主要讨论如下两方面的问题：,1）数据的逻辑结构，数据结构的基本操作；2）数据的存储结构，数据结构基本操作的实现；,数据的逻辑结构：,数据之间的结构关系，是,具体,关系的抽象。,数据结构的基本操作：,指对数据结构的加工处理,数据的存储结构(物理结构)：,数据结构在计算机内存中的表示,数据结构基本操作的实现,：,基本操作在计算机上的实现（方法),1.2 数据结构的有关概念,1数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,1.2 数据结构的有关概念,某班学生基本情况登记表，记录了每个学生的学号 姓名 专业 政治 面貌，表中的记录是按学生的学号顺序排列的。,学号 姓名 专业 政治面藐 001 王洪 计算机 党员 002 孙文 计算机 团员 003 谢军 计算机 团员 004 李辉 计算机 团员 005 沈祥福 计算机 党员,006 余斌 计算机 团员 007 巩力 计算机 团员 008 孔令辉 计算机 团员,学生基本情况登记表的图示,学生间学号顺序关系,是一种线性结构关系,例,一 常用的数据逻辑结构,1,）集合 2）线性结构 3）树结构 4）图结构 5）其它复杂结构,001,003,002,004,006,005,008,007,数据结构的分类及表示,家族的族谱,假设某家族有10个成员A，B，C，D，E，F，G，H，I，J，他们之间的血缘关系可以用如下图表示。,例,家族的成员之间是一种树型结构关系,J,I,A,C,B,D,H,G,F,E,数据结构的分类及表示,J,I,A,C,B,D,H,G,F,E,J,I,A,C,B,D,H,G,F,E,J,I,A,C,B,D,H,G,F,E,J,I,A,C,B,D,H,G,F,E,1,4,2,3,D=1,2,3,4,R=(1,2),(1,3),(1,4),(2,3),(3,4),(2,4),2,1,3,D=1,2,3,R=(1,2),(2,3),(3,2),(1,3),图形结构节点间的连结是任意的,例,数据结构的分类及表示,二数据结构的表示,图示表示,图示表示是由顶点和边构成的图，其中顶点表示数据，边表示数据之间的结构关系；,001,003,002,004,006,005,008,007,学生基本情况表的图示表示,家族树的图示表示,数据结构的分类及表示,J,I,A,C,B,D,H,G,F,E,学生基本情况表的二元组表示（D，S）,二元组表示,二元组表示是用一个二元组（D，S）表示数据结构，其中 D 是数据元素集合，S 是 D 上关系的集合。,D=001，002，003，004，005，006，007，008,S=R,R=,001,003,002,004,006,005,008,007,数据结构的分类及表示,家族树的二元组表示（D，S）,D=A，B，C，D，E，F，G，H，I，J S=R R=A,B,J,I,A,C,B,D,H,G,F,E,.数据元素的映像方法：用二进制位(bit)的位串表示数据元素,（321）,10,=(501),8,=(101000001),2,A=(101),8,=(001000001),2,三 数据的存储结构,逻辑结构在存储器中的映像,2.关系的映像方法,：（表示的方法）,有序对是关系的基本单位，关系的映像就是有序对的映像,J,I,A,C,B,D,H,G,F,E,元素n,.,元素i,.,元素2,元素1,L,o,L,o,+m,L,o,+(i-1)*m,L,o,+（n-1)*m,存储地址,存储内容,Loc(a)=L,o,+（i-1)*m,顺序存储,每个元素所占用,的存储单元个数,以存储位置的相邻来表示后继关系y的存储位置和x的存储位置的次序关系,数据的存储结构,元素n,.,元素i,.,元素2,元素1,存储内容,顺序存储结构常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。,顺序存储结构的三个弱点：,1.作插入或删除操作时，需移动大量元数。,2.长度变化较大时，需按最大空间分配。,3.表的容量难以扩充。,数据的存储结构,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,链式存储,每个节点都由两部分组成：,数据域,和,指针域,。,数据域,存放元素本身的数据，,指针域,存放指针。,数据元素之间逻辑上的联系由指针来体现。,数据的存储结构,1536,元素2,1400,元素1,1346,元素3,元素4,head,1346,元素3,1536,.,.,.,1536,元素2,1400,.,.,.,元素4,1346,1400,元素1,1345,指针,存储内容,存储地址,链式存储,1345,数据的存储结构,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,链式存储,1.比顺序存储结构的存储密度小,(每个节点都由数据域和指针域组成)。,2.逻辑上相邻的节点物理上不必相邻。,3.插入、删除灵活,(不必移动节点，只要改变节点中的指针)。,链接存储结构特点：,数据的存储结构,在不同的编程环境中，存储结构可有不同的描述方法。,当用高级程序设计语言进行编程时，通常可用高级语言中提供的数据类型描述之。,例如：以三个带有次序关系的整数表示一个长整数，可以利用C语言中提供的整数数组类型，定义长整数为：,Typedef int long_int3,一、数据类型,在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。,1.3 抽象数据类型的表示与实现,例如，C 语言中提供的,基本数据类型,有:,整型 int,浮点型 float,字符型 char,逻辑型 bool （C+语言）,双精度型 double,实型（C+语言）,数据类型,数据类型,是一个,值的集合,和定义在此集合上的,一组操作,的总称。,不同类型的变量，其所能取的,值的范围,不同，所能,进行的操作,不同。,数据类型,二、抽象数据类型,(Abstract Data Type 简称ADT),是指,一个数学模型,以及定义在此数学模型上的,一组操作,。,抽象数据类型,例如，抽象数据类型复数的定义：,数据对象：,De1,e2e1,e2RealSet ,数据关系：,R1|e1是复数的实数部分,|e2 是复数的虚数部分,ADT Complex,抽象数据类型,基本操作：,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,抽象数据类型,假设:z1和z2是上述定义的复数,则 Add(z1,z2,z3)操作的结果,z3=z1+z2,即为用户企求的结果,抽象数据类型,ADT,有两个重要特征,:,数据抽象,用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。,数据封装,将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。,抽象数据类型,抽象数据类型的描述方法,抽象数据类型可用,（D，S，P）,三元组表示。,其中：D 是数据对象；,S 是 D 上的关系集；,P 是对 D 的基本操作集。,抽象数据类型,ADT,抽象数据类型名,数据对象：,数据对象的定义,数据关系：,数据关系的定义,基本操作：,基本操作的定义,ADT,抽象数据类型名,其中基本操作的定义格式为:,基本操作名,（参数表）,初始条件：,初始条件描述,操作结果,：操作结果描述,抽象数据类型,赋值参数,只为操作提供输入值。,引用参数,以,&,打头，除可提供输入值外，还将返回操作结果。,初始条件,描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。,操作结果,说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。,抽象数据类型,抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。,例如，对以上定义的复数。,typedef struct,float,realpart；,float,imagpart；,complex；,/-存储结构的定义,/-基本操作的函数原型说明,void,Assign(complex,&Z,float realval,float imagval)；,/,构造复数 Z,其实部和虚部分别被赋以参数,/,realval 和 imagval 的值,float,GetReal(cpmplex Z)；,/返回复数 Z 的实部值,float Getimag(cpmplex Z)；,/返回复数 Z 的虚部值,void add(complex z1,complex z2,complex&sum)；,/以 sum 返回两个复数 z1,z2 的和,/-基本操作的实现,void,add(complex z1,complex z2,complex&sum),/以 sum 返回两个复数 z1,z2 的和,sum.realpart=z1.realpart+z2.realpart;,sum.imagpart=z1.imagpart+z2.imagpart;,其它省略,我们各章都是从抽象数据类型的角度开始讨论数据结构，数据结构和它的操作是一个整体。,一 算法的概念,算法是求解问题的操作序列,算法的基本特征：,1）有输入；2）有输出；3）有穷性；4）确定性；5）可行性。,求两个正整数 m，n 中的最大数MAX的算法,（1）若 m n 则 max=m （2）若 m=n 则 max=n,例,1.4 算法与算法分析,.,有穷性,对于任意一组合法输入值，在执行有穷步骤之后，一定能结束。即：算法中的每一个步骤都能在有限的时间内完成。,.,确定性,在每种情况下所应执行的操作，在算法中都有确定的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。,.,可行性,算法中的所以操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。,4.,有输入,作为算法加工对象的量值，通常体现为算法中的一组变量，有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已经被嵌入算法之中。,5.,有输出,它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。,描述算法的书写规则,所有算法均以函数形式给出,算法的输入数据来自参数表,参数表的参数在算法之前均进行类型说明,有关结点结构的类型定义,以及全局变量的说明等均在算法之前进行说明,评价算法标准（设计算法时，通常要考虑到达的目标）,算法的正确性，可读性，可维护性，健壮性等,.,二、算法效率的衡量方法和准则,通常有两种衡量算法效率的方法,（1）,事后统计的方法,缺点：1、必须执行程序,2、其他因素掩盖算法本质,（2）,事前分析估算的方法,与算法执行时间相关的因素：,算法选用的策略,问题的规模,编写程序的语言,编译程序产生的机器代码的质量,计算机执行指令的速度,一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数n表示），或者说，它是问题规模的函数。假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同。,则可记作：,T(n)=O(f(n),1.4 算法与算法分析,如何估算算法的渐进时间复杂度：,算法控制结构原操作（固有数据类型的操作）,算法的执行时间,原操作（i）的执行次数原操作（i）的执行时间（定值，可忽略）,算法的执行时间与原操作执行次数之和成正比，通称为算法的时间复杂度。,1 算法时间复杂度T（n）,从算法中选取一种对于所研究的问题来说是,基本操作的原操作,，,以该基本操作在算法中重复执行的次数作为算法运行时间的衡量标准,。,1.4 算法与算法分析,O（n,3,）,称为矩阵相乘算法,时间复杂度,；,O（n,3,）,表示矩阵相乘算法执行时间与n,3,成正比,即O（n,3,）与n,3,同一数量级；,n 阶矩阵相乘的算法,For(i=1;i=n;i+)For(j=1;j=n;j+),c i j =0;For(k=1;k=n;k+)c i j +=a i k *b k j,乘法 加法,执行次数均为 n,3,例,矩阵相乘的基本运算：乘法 加法；,1.4 算法与算法分析,有些算法，基本操作执行次数与问题的输入数据有关，这时可考虑 （1）算法平均时间复杂度 （2）算法在最坏情况下的时间复杂度,100元买100支笔,其中钢笔 3元/支,圆珠笔 2元/支,铅笔 0.5元/支.写算法输出各种组合方案。,例,?,解法1,#define N 100,void scheme(),int i,j,k,count,money;,for(i=0;i=N;i+)for(j=0;j=N;j+),for(k=0;k=N;k+),count=i+j+k;money=3*i+2*j+0.5*k;if(count=N&money=N),printf(“%d,%d,%d n%”,i,j,k);,算法的时间复杂度为O(N,3,),解法2,#define N 100,Void scheme(),int i,j;,for(i=0;i=N/3;i+),for(j=0;j=(N-3*i)/2;j+),if(3*i+2*j+0.5*(N-i-j)=N),printf(“%d,%d,%dn%”,i,j,N-i-j);,时间复杂度为O(N,2,),2,算法空间复杂度,S(n,),算法的存储量包括：,输入数据所占的空间；,程序本身所占的空间；,辅助变量所占的空间。,在本课程中，用执行算法所需的辅助空间的大小作为算法所需空间的度量。设执行算法所需的辅助空间是问题规模n的某个函数g(n),则算法空间复杂度记作：,S（n）=O(g(n),表示算法辅助空间的增长率,与g(n)的增长率相同,例,计算,解法1,先计算x 的幂,存于power 中,再分别乘以相应的系数,#define N 100,float evaluate(float coef,float x,int n),float powerN,f;int i;,for(power 0=1,i=1;i=n;i+)poweri=x*poweri-1;for(f=0,i=0;i=0;i-)f=f*x+coefi;,return(f);,时间复杂度为O(n).空间复杂度为O(1),理解什么是数据结构，数据结构这门课程所研究的内容；,理解数据结构这门课程的一些基本概念，掌握数据结构的分类和表示；,理解抽象数据类型含义和表示,学会算法的时间复杂度和空间复杂度的分析,返回目录,本章的学习要点,