数据结构课程教程第一章课件.ppt

1、1.1 数据结构讨论的数据结构讨论的范畴范畴1.2 基本概念基本概念1.3 算法和算法的量度算法和算法的量度1.11.1 数据结构讨论的范畴数据结构讨论的范畴(数据结构在软件开发中的地位)系统分析系统分析系统设计系统设计系统实现系统实现系统维护系统维护 结构静力分析计算结构静力分析计算 例如例如:数值计算的程序设计问题数值计算的程序设计问题 线性代数方程组线性代数方程组 环流模式方程环流模式方程 (球面坐标系球面坐标系)全球天气预报全球天气预报 这些可以建模为数学方程（组）的这些可以建模为数学方程（组）的问题的计算方法是问题的计算方法是数值计算数值计算研研究的内容。究的内容。例例1-1 1-1

2、 书目检索自动化问题书目检索自动化问题登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片001高等数学樊映川S01002理论力学罗远祥L01003高等数学华罗庚S01004线性代数栾汝书S02书目文件按书名按作者名按分类号高等数学001，003理论力学002，.线性代数004，.樊映川001,华罗庚002,.栾汝书004,.L002,S001,003,索引表线性表 计算机处理的对象之间存在着线性关系，称为线计算机处理的对象之间存在着线性关系，称为线性的数据结构。性的数据结构。例例1-2 1-2 人机对奕问题人机对奕问题树.CEDABABACADBABCBDDADBDCEAEBEC

3、ED图例例1-3 1-3 多岔路口交通灯的管理问题多岔路口交通灯的管理问题概括地说：概括地说：数据结构是一门研究非数值数据结构是一门研究非数值计算的程序设计问题中的计算的程序设计问题中的操操作对象作对象以及它们之间以及它们之间关系和关系和操作操作等的学科等的学科.1.2 基本概念基本概念一、数据与数据结构一、数据与数据结构二、数据类型二、数据类型三、抽象数据类型三、抽象数据类型一、数据与数据结构一、数据与数据结构 所有能所有能被输入被输入到计算机中，且能被计算到计算机中，且能被计算机机处理的符号处理的符号(数值、字符等数值、字符等)的集合。的集合。数据数据:是计算机操作的对象计算机操作的对象的

4、总称。是计算机处理的是计算机处理的信息的信息的某种特定的符某种特定的符号号表示形式表示形式。是数据（集合）中的一个是数据（集合）中的一个“个个体体”,在计算机中通常作为一个整在计算机中通常作为一个整体进行考虑和处理。是数据结构中体进行考虑和处理。是数据结构中讨论的讨论的基本基本单位。单位。数据元素数据元素:如如:整数整数“5 5”,”,字符字符“N N”等。等。-是不可分割的是不可分割的“原子原子”其中每个项称为一个其中每个项称为一个“数据项数据项”它是数据结构中讨论的它是数据结构中讨论的最小最小单位单位数据元素也可以由若干项构成。数据元素也可以由若干项构成。例如：例如：描述一个学生的数据元素

5、描述一个学生的数据元素称之为组合项称之为组合项年年 月月 日日姓姓 名学名学 号班号班 号性别出生日期入学成绩号性别出生日期入学成绩原子项原子项数据结构：数据结构：带带结构结构的数据元素的集合的数据元素的集合有一个特性相同的数据元素的集合，有一个特性相同的数据元素的集合，如果在数据元素之间存在一种或多种如果在数据元素之间存在一种或多种特定的关系，则称为一个数据结构。特定的关系，则称为一个数据结构。指的是数据元素之间存在的关系指的是数据元素之间存在的关系例，在例，在 2 行行 3 列的二维数组列的二维数组中六个元素中六个元素a1,a2,a3,a4,a5,a6之间存在两个关系之间存在两个关系:行的

6、次序关系行的次序关系:row=,col=,a1 a2 a3 a4 a5 a6列的次序关系列的次序关系:若在若在 6 个数据元素个数据元素a1,a2,a3,a4,a5,a6 之间存在如下的之间存在如下的次序关系次序关系:|i=1,2,3,4,5 数据结构是数据结构是相互之间存在着某种逻辑相互之间存在着某种逻辑关系的数据元素的集合关系的数据元素的集合。可见，不同的可见，不同的“关系关系”构成不同的构成不同的“结构结构”则构成一维数组的定义。则构成一维数组的定义。从从关系关系或或结构结构分分，数据结构，数据结构可归结可归结为以下为以下四类四类:（各关系可以用（各关系可以用次序次序关系加以描述）。关系

7、加以描述）。线性线性结构结构树形树形结构结构图状图状结构结构集合集合结构结构数据结构的形式定义：数据结构是一个二元组数据结构的形式定义：数据结构是一个二元组 Data_Structure=(D,S)其中，其中，D 是数据元素的有限集是数据元素的有限集,S 是是D上关系的有限集上关系的有限集例例1-4 复数复数 Complex=(C,R)例例1-5 课题小组课题小组 Group=(P,R)P=T,G1,Gn,S11,Snm1n3，1m2，R=R1,R2R1=|1in,1n3,R2=|1in,1jm,1m2,1.2 基本概念和术语位：在计算机中表示信息的最小单位，二进制数的一位位：在计算机中表示信

8、息的最小单位，二进制数的一位位串：由若干个位组合，表示一个数据元素。（以后称位串：由若干个位组合，表示一个数据元素。（以后称“元素元素”或或“结点结点”）例：整数用一个字长（例：整数用一个字长（1616位）位）表示，字符用表示，字符用8 8位表示位表示子位串：表示一个数据项。（以后称子位串：表示一个数据项。（以后称“数据域数据域”）q数据的逻辑结构数据的逻辑结构只抽象反映数据元素的逻辑关系只抽象反映数据元素的逻辑关系q数据的存储（物理）结构数据的存储（物理）结构数据的逻辑结构在计算机数据的逻辑结构在计算机存储器中的实现存储器中的实现1.2 基本概念和术语数据的逻辑结构与存储结构密切相关 算法设

9、计 取决于选定的逻辑结构 算法实现 依赖于采用的存储结构存储结构分为：顺序存储结构借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系链式存储结构借助指示元素存储地址的指针表示数据 元素间的逻辑关系3数据的两种存储结构数据的两种存储结构元素n.元素i.元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=Loc+（i-1)*m顺序存储顺序存储1536元素21400元素11346元素3 元素41345h存储地址 存储内容 指针 1345 元素1 1400 1346 元素4 .1400 元素2 1536 .1536 元素3 134

10、6 链式存储链式存储 h 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：检索、排序、插入、删除、修改等数据的运算：检索、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构的三个方面：数据结构的三个方面：数据类型：是一个值的数据类型：是一个值的集合集合和定义在这和定义在这个值集上的所有个值集上的所有 的的操作操作。如，整型。如，整型。数据类型可分为：非结构的原子类型和数据类型可分为：非结构的原子类型和结构类型。结构类型。原子类型的值是不可分解的原子类型的值是不

11、可分解的结构类型的值是由若干成分按某种结结构类型的值是由若干成分按某种结构组成的。构组成的。4.数据类型 抽象数据类型 数据类型在高级语言中指数据的取值范围及其上可进行的操作的总称例例 C C语言中，提供语言中，提供intint,char,float,double,char,float,double等基等基本数据类型本数据类型，数组、结构体、共用体、枚举等，数组、结构体、共用体、枚举等构造数构造数据类型据类型，还有指针、空，还有指针、空(void)(void)类型等。用户也可用类型等。用户也可用typedeftypedef 自己定义数据类型自己定义数据类型typedef struct int

12、num;char name20;float score;STUDENT;STUDENT stu1,stu2,*p;数据类型可以看成是已经实现了的数据结构数据类型可以看成是已经实现了的数据结构。抽象数据类型：抽象数据类型：是指一个是指一个数学模型数学模型以及定义在该模以及定义在该模型上的型上的一组操作一组操作。抽象数据类型和数。抽象数据类型和数据类型实质上是一个据类型实质上是一个概念概念，它仅，它仅取决取决于数据类型于数据类型的逻辑性，而的逻辑性，而与其在计算与其在计算机内部如何表示和实现是无关机内部如何表示和实现是无关的。的。也就是说抽象数据类型的定义由一也就是说抽象数据类型的定义由一个个值域

13、值域和定义在该值域上的一组和定义在该值域上的一组操作操作组成。组成。按抽象数据类型值的不同特性，分为三按抽象数据类型值的不同特性，分为三种类型：种类型：原子类型原子类型:变量的值是不可分解的。变量的值是不可分解的。固定聚合类型固定聚合类型:变量的值由确定数目的变量的值由确定数目的成分按某种结构组成。成分按某种结构组成。可变聚合类型可变聚合类型:其值的成分数目不确定。其值的成分数目不确定。抽象数据类型的形式定义抽象数据类型的形式定义 我们用一个三元组我们用一个三元组来表示一个抽象数据类型：（来表示一个抽象数据类型：（D D，S S，P P）D D是数据对象，是数据对象，S S是是D D上的关系集

14、，上的关系集，P P是对是对D D的基本操作。的基本操作。ADT 抽象数据类型名抽象数据类型名数据对象：数据对象的定义数据对象：数据对象的定义数据关系：数据关系的定义数据关系：数据关系的定义基本操作：基本操作的定义基本操作：基本操作的定义ADT 抽象数据类型名。抽象数据类型名。数据基本操作的定义格式：数据基本操作的定义格式：基本操作名（参数表）基本操作名（参数表）初始条件：初始条件描述初始条件：初始条件描述操作结果：操作结果描述操作结果：操作结果描述抽象数据类型格式：抽象数据类型格式：P8-9P8-9例例1-6 1-6 抽象数据类型三元组的定义：抽象数据类型三元组的定义：ADT Triplet

15、ADT Triplet 数据对象：数据对象：D=e1D=e1，e2,e3|e1,e2,e3Elemsete2,e3|e1,e2,e3Elemset (定义了关系运算的某个集合定义了关系运算的某个集合)数据关系：数据关系：R1=R1=e1,e2,e1,e2,基本操作：基本操作：InitTriplet(&T,v1,v2,v3)/InitTriplet(&T,v1,v2,v3)/构造三元组构造三元组T T，e1,e2,e3e1,e2,e3分别被赋以参数分别被赋以参数v1,v2,v3v1,v2,v3的值的值DestroyTripletDestroyTriplet（&T&T）/撤消三元组撤消三元组T T

16、 Get Get（T,i,&eT,i,&e）/三元组三元组T T已存在，已存在，1=i=31=i=3 用用e e返回第返回第i i元的值元的值 Put(&T,i,e)/Put(&T,i,e)/三元组三元组T T已存在，已存在，1=i=31=i=3 将将T T的第的第i i元值变为元值变为e e IsAscending(T IsAscending(T)/)/三元组三元组T T已存在，已存在，1=i=31=i=3 三元素若升序排列返回三元素若升序排列返回1 1，否则返回，否则返回0 0 IsDescending(T IsDescending(T)Max(T,&e)Max(T,&e)Min(T,&e

17、)Min(T,&e)ADT Triplet 多形数据类型：是其值的成分不多形数据类型：是其值的成分不确定的数据类型。确定的数据类型。如例如例1-6中定义的抽象数据类中定义的抽象数据类型型Triplet，其元素，其元素e1,e2,e3可以可以是整数或字符串，也可以是由多是整数或字符串，也可以是由多种成分构成。种成分构成。1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现 抽象数据类型可通过固有数抽象数据类型可通过固有数据类型来表示和实现，即利用据类型来表示和实现，即利用处理器中处理器中已存在的数据类型已存在的数据类型来来说明新的结构，用说明新的结构，用已经实现的已经实现的操作操作来组合新的

18、操作。来组合新的操作。精选了C 的一个子集，扩充修改，增强了语言的描述功能。预定义常量和类型数据结构的表示：存储结构用类型（typedef）定义来 描述。数据元素类型约定为ElemType.基本操作的算法用函数描述：1类C语言P10-111.4 1.4 算法和算法的衡量算法和算法的衡量一、算法及特点一、算法及特点二、算法设计的原则二、算法设计的原则三、算法效率的衡量方法和准则三、算法效率的衡量方法和准则四、算法的存储空间需求四、算法的存储空间需求 算法是为了解决某类问题而规算法是为了解决某类问题而规定的一个有限长的操作序列。一个定的一个有限长的操作序列。一个算法必须满足以下算法必须满足以下五五

19、个重要特性个重要特性：1 1有穷性有穷性 2 2确定性确定性 3 3可行性可行性4 4有输入有输入 5 5有输出有输出一、算法一、算法1 1有穷性有穷性 对于任意一组合法输入值，在执行有穷步骤有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间有限时间内完成；2 2确定性确定性 对于每种情况每种情况下所应执行的操作，在算法中都有确切确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。3 3可行性可行性 算法中的所有操作都必须算法中的所有操作都必须足足够基本够基本，都可以通过已经实现的基本操作，都可以通过已经实现的基本操作运算有限次实现之；运算有限次实现之；4 4有输入有输入 作为

20、算法加工对象的量值，作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入法表面上可以没有输入，实际上已被嵌入算法之中；算法之中；5 5有输出有输出 它是一组与它是一组与“输入输入”与与确确定关系的量值，是算法进行信息加定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即工后得到的结果，这种确定关系即为算法的功能。为算法的功能。二、算法设计的原则二、算法设计的原则设计算法时，通常应考虑达到以下目标：设计算法时，通常应考虑达到以下目标：1正

21、确性正确性2.可读性可读性3健壮性健壮性4高效率与低存储量需求高效率与低存储量需求1 1正确性正确性 首先，首先，算法应当满足以特定的算法应当满足以特定的“规格规格说明说明”方式给出的需求。方式给出的需求。其次，其次，对算法是否对算法是否“正确正确”的理解可的理解可以有以下四个层次以有以下四个层次（实现为程序后）实现为程序后）a a程序中不含语法错误；程序中不含语法错误；b b程序对于几组输入数据能够得出程序对于几组输入数据能够得出满足要求的结果；满足要求的结果；c c程序对于精心选择的、典型、苛刻且程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足带有刁难性的几组输入数据能

22、够得出满足要求的结果；要求的结果；通常以通常以第第 c c 层层意义的正确性作为衡意义的正确性作为衡量一个算法是否合格的标准。量一个算法是否合格的标准。d d程序对于一切合法的输入数据都能得程序对于一切合法的输入数据都能得出满足要求的结果；出满足要求的结果；2.可读性可读性 算法主要是为了人的阅读与交流，算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该其次才是为计算机执行。因此算法应该易易于人的理解于人的理解；另一方面，晦涩难读的程序；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试；易于隐藏较多错误而难以调试；3健壮性健壮性 当当输入的数据非法输入的数据非法时，算法应当恰当

23、时，算法应当恰当地作出反映或地作出反映或进行相应处理进行相应处理，而不是产，而不是产生莫名奇妙的输出结果。并且，处理出生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。以便在更高的抽象层次上进行处理。4高效率与低存储量需求高效率与低存储量需求 通常，效率指的是通常，效率指的是算法执行算法执行时间时间；存储量指的是算法执行过程；存储量指的是算法执行过程中中所需的最大存储空间所需的最大存储空间。两者都与。两者都与问题的规模有关。问题的规模有关。三三

24、、算法效率的衡量方法和、算法效率的衡量方法和准则准则通常有两种衡量算法效率的方法通常有两种衡量算法效率的方法:事后统计法事后统计法事前分析估算法事前分析估算法缺点：缺点：1 1。必须执行程序。必须执行程序 2 2。其它因素掩盖算法本质。其它因素掩盖算法本质和算法执行时间时间相关的因素因素：1 1算法算法选用的策略的策略2 2问题的规模问题的规模3 3编写程序的语言编写程序的语言4 4编译程序产生的机器代码的质量编译程序产生的机器代码的质量5 5计算机执行指令的速度计算机执行指令的速度 一个特定一个特定算法的算法的“运行工作运行工作量量”的大小，只依赖于的大小，只依赖于问题的问题的规模规模（通常

25、用整数量（通常用整数量n表示），表示），或者说，或者说，它是问题规模的函数。它是问题规模的函数。如何估算如何估算 算法的时间复杂度？算法的时间复杂度？算法效率的度量算法效率的度量算法效率算法效率用依据该算法编制的程序在计算机上执用依据该算法编制的程序在计算机上执行所行所消耗的时间消耗的时间来度量。（来度量。（算法时间是由控制结构和原算法时间是由控制结构和原操作的决定的）操作的决定的）记号记号引用了引用了“O”。“O”表示一个表示一个 数量级的概念。数量级的概念。（常见的量级）（常见的量级）本书中根据算法中语句本书中根据算法中语句执行执行的的最大次数最大次数（频度）来（频度）来 估估算一个算法算

26、一个算法执行时间的执行时间的数量级数量级。时间复杂度：算法中时间复杂度：算法中基本操作基本操作重复执行的重复执行的次数次数是问题是问题规模规模n的某个函数的某个函数f（n），），T（n）=O（f（n）它表示随问题规模它表示随问题规模n的增大，算法执行时间的增长率和的增大，算法执行时间的增长率和f（n）的增长率相同。）的增长率相同。语句的频度：是该语句语句的频度：是该语句重复重复执行的执行的次数次数。#define n 100 void MatrixMultiply(int Ann,int Bnn,int Cnn)int i,j,k for(i=1;i=n;+i)/n+1for(j=1;j=n;

27、+j)/n*(n+1)Cij=0;/n2for(k=1;k=n,k+)n2(n+1)Cij=Cij+aik*bkj;/n3 T(n)=n+1+n*(n+1)+n2+n2(n+1)+n3=2n3+3n2+2n+1量级：量级：T(n)=O(n3)例：求两个n阶方阵的乘积C=AB例：例：（a）+x;s=0;（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增增1”的语句的频度分别为的语句的频度分别为1,n和和n2 时间复杂度是时间复杂度是O(1)、O(n)和和O(n2)。时间复杂度有时与输入有

28、关。时间复杂度有时与输入有关。从算法中选取一种对于所研究从算法中选取一种对于所研究的问题来说是的问题来说是 基本操作基本操作 的原操的原操作（执行次数最多），以该基本作（执行次数最多），以该基本操作操作 在算法中重复执行的次数在算法中重复执行的次数 作为算法运行时间的衡量准则。作为算法运行时间的衡量准则。（最坏情况下）（最坏情况下）例例二二选选择择排排序序 void select_sort(int&a,int n)/将将 a 中整数序列重新排列成自小至大有序的整数序列中整数序列重新排列成自小至大有序的整数序列。/select_sort基本操作:比较比较(数据元素)操作操作时间复杂度:O(n2)

29、j=i;/选择第选择第 i i 个最小元素个最小元素for(k=i+1;k n;+k)if(ak aj)j=k;for(i=0;i1&change;-i)/bubble_sort基本操作:赋值赋值操作时间复杂度:O(n2)change=FALSE;/change 为元素进行交换标志 for(j=0;j aj+1)aj aj+1;change=TRUE;/一趟起泡四、算法的存储空间需求四、算法的存储空间需求算法的存储量算法的存储量包括:1输入数据输入数据所占空间2程序本身程序本身所占空间；3辅助变量辅助变量所占空间。若输入数据输入数据所占空间只取决与问题 本身，和算法无关和算法无关，则只需要分析除 输入数据和程序之外的辅助变量辅助变量所占额外空间额外空间。若所需额外空间相对于输入数据量若所需额外空间相对于输入数据量 来说是常数，则称此算法为来说是常数，则称此算法为原地工作原地工作。若所需存储量依赖于特定的输入，若所需存储量依赖于特定的输入，则通常按最坏情况考虑。（也是问题则通常按最坏情况考虑。（也是问题规模规模n的函数）。的函数）。1.熟悉各名词、术语的含义，掌握基本概念。2.理解算法五个要素的确切含义。本章学习要点本章学习要点3.掌握计算语句频度和估算算法时间复杂度的方法。