《数据结构一章节绪论》由会员分享，可在线阅读，更多相关《数据结构一章节绪论（37页珍藏版）》请在金锄头文库上搜索。
1、中国科大数据结构数据结构一章节绪论Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望中国科大数据结构选用教材l选用教材：严蔚敏 吴伟民 编著.清华出版社出版数据结构数据结构(C语言版语言版)l推荐参考书：宁正元编著 清华大学出版社出版数据结构学习辅导数据结构学习辅导1- 中国科大数据结构课程意义p数据结构是计算机专业的一门专业基础课。数据结构是计算机专业的一门专业基础课。p数据结构是关于数据组织和处理的基本技术的一门学科。数据结构是关于数据组织和处理的基本技术的一门学科。p程序程序 =
2、 数据结构数据结构 + 算法算法 + 文档文档p数据结构是一门实践性很强的课程。数据结构是一门实践性很强的课程。1- 中国科大数据结构1.1 什么是数据结构？问题问题1：图书检索自动化：图书检索自动化p图书的基本信息：书名，作者，分类号，出版单位，出图书的基本信息：书名，作者，分类号，出版单位，出版时间版时间作者简介，内容简介等等。作者简介，内容简介等等。p操作：检索，排序，等等操作：检索，排序，等等p数据之间的关系：线性关系数据之间的关系：线性关系p数据表示和算法操作的设计：与需求有关数据表示和算法操作的设计：与需求有关1- 中国科大数据结构1.1 什么是数据结构？ L003006清华大学出
3、版社清华大学出版社1979刘永年刘永年 运筹学运筹学K005005清华大学出版社清华大学出版社1958栾汝书栾汝书 线性代数线性代数L002004清华大学出版社清华大学出版社1982张之张之 化学化学M003003高教出版社高教出版社1965罗远祥罗远祥 理论力学理论力学S002002高教出版社高教出版社1964樊映川樊映川 高等数学高等数学L001001 出版社出版社出版时间出版时间 作作 者者 书书 名名 书书 号号书目文件书目文件 004 线性代数线性代数 003 化学化学 002 理论力学理论力学 001 高等数学高等数学索引表索引表按书名按书名004栾汝书栾汝书003张之张之002罗
4、远祥罗远祥001樊映川樊映川按作者名按作者名002S003M005K001,004,006L按分类按分类线性表线性表1- 中国科大数据结构1.1 什么是数据结构？问题问题2：井子棋：井子棋p 好的棋手不仅要看当好的棋手不仅要看当前的格局，还要预测前的格局，还要预测棋局发生的趋势，甚棋局发生的趋势，甚至最后的胜负结局至最后的胜负结局p 如何表示一个棋局如何表示一个棋局p 数据的逻辑结构：表数据的逻辑结构：表示棋局之间的演化关示棋局之间的演化关系：树型结构系：树型结构p 算法如何设计算法如何设计基于数据表示的基础基于数据表示的基础上算法设计上算法设计棋盘的当前格局棋盘的对弈树局部棋盘的对弈树局部树
5、树1- 中国科大数据结构数据结构课程的主要任务p研究和解决非数值数据的组织和处理研究和解决非数值数据的组织和处理n描述非数值计算问题的数学模型，不再是数学方程描述非数值计算问题的数学模型，不再是数学方程n例如：前述的三个例子：数据的线性结构，树型结构，图例如：前述的三个例子：数据的线性结构，树型结构，图p算法算法+数据结构数据结构=程序程序n算法和数据结构之间的关系算法和数据结构之间的关系n软件系统的框架应当建立在数据之上，而不是建立在操作之上软件系统的框架应当建立在数据之上，而不是建立在操作之上p数据结构的作用范畴数据结构的作用范畴n抽象数据对象的数学模型（逻辑结构）例：图状结构抽象数据对象
6、的数学模型（逻辑结构）例：图状结构n明确操作（运算的定义）明确操作（运算的定义） 例：查找、插入、例：查找、插入、n在存储结构上映射数据（存储结构）在存储结构上映射数据（存储结构） 例：顺序存储例：顺序存储n实现操作实现操作1- 中国科大数据结构p基本术语基本术语n数据：被计算机加工处理的对象。数据：被计算机加工处理的对象。n数据元素：数据元素：是数据的基本单位。在计算机程序中是数据的基本单位。在计算机程序中通常作为一个整体考虑和处理通常作为一个整体考虑和处理。n数据项：数据项：是数据不可分割的最小单位是数据不可分割的最小单位。n一个数据元素可由若干个数据项组成。一个数据元素可由若干个数据项组
7、成。 组合项组合项 年 月 日 学号学号 姓名姓名 班号班号 性别性别 出生日期出生日期 入学成绩入学成绩原子项原子项1.2 基本概念和术语1- 中国科大数据结构1.2 基本概念和术语p数据对象数据对象 是性质相同的数据元素的集合。是性质相同的数据元素的集合。 p什么叫数据结构？什么叫数据结构？ 具有结构的数据元素的集合。它包具有结构的数据元素的集合。它包括数据元素的括数据元素的逻辑结构逻辑结构、存储结构存储结构和相适应的和相适应的运算运算。学号 姓名班号性别出生日期入学成绩001刘影01女19840417623002李恒01男19831211679003陈诚02男19840910638004
8、数据元素数据元素整个表是学生成绩数据对象整个表是学生成绩数据对象1- 中国科大数据结构 数据元素之间的逻辑关系，与计算机无关。数据元素之间的逻辑关系，与计算机无关。 可用一个二元组表示：可用一个二元组表示：Data_Structure = (D,R)Data_Structure = (D,R) D D：数据元素的有穷集合，：数据元素的有穷集合，R R：集合：集合D D上关系的有穷集合。上关系的有穷集合。 例例 设有数据结构设有数据结构 B = (D,R) B = (D,R) ， 其中其中 D= d1, d2, d3, d4, d5, d6 D= d1, d2, d3, d4, d5, d6，
9、R=r R=r， r=, , r=, , , , , , ， 试画出其逻辑结构图。试画出其逻辑结构图。 d1d2d3d4d5d6逻辑结构1- 中国科大数据结构（以班级学生关系为例）（以班级学生关系为例）(1)(1)集合结构集合结构 数据元素除了数据元素除了“属于同一集合属于同一集合”的联系之外，没有其的联系之外，没有其它的关系。它的关系。(2)(2)线性结构线性结构 数据元素之间存在一对一的关系。数据元素之间存在一对一的关系。(3)(3)树型结构树型结构 数据元素之间存在一对多的关系。数据元素之间存在一对多的关系。(4)(4)图状结构图状结构或或网状结构网状结构 数据元素之间存在多对多的关系。
10、数据元素之间存在多对多的关系。成员关系长幼关系管理关系朋友关系四种基本的逻辑结构1- 中国科大数据结构数据的逻辑结构1- 中国科大数据结构示例p用图形表示下列数据结构，并指出它用图形表示下列数据结构，并指出它 们是属于线性结构还是非线们是属于线性结构还是非线性结构。性结构。S=(D, R)D= a, b, c, d, e, f R=(a,e), (b,c), (c,a), (e,f), (f,d)p解：上述表达式可用图形表示为：解：上述表达式可用图形表示为：b c a e f d此结构为此结构为线性线性的。的。1- 中国科大数据结构示例p用图形表示下列数据结构，并指出它用图形表示下列数据结构，
11、并指出它 们是属于线性结构还是非线们是属于线性结构还是非线性结构。性结构。 S=(D, R) D=di | 1i5 R=(di , dj ), ij解：上述表达式可用图形表示为：解：上述表达式可用图形表示为：d1d2d3d4d5该结构该结构是非线性的。是非线性的。1- 中国科大数据结构存储结构存储结构：数据的逻辑结构在计算机中如何表示。：数据的逻辑结构在计算机中如何表示。p数据元素的映象数据元素的映象 用二进制位用二进制位(bit)(bit)的位串表示数据元素。的位串表示数据元素。 每个数据元素的映象称为每个数据元素的映象称为结点结点 每个数据项的映象称为每个数据项的映象称为数据域数据域p关系
12、的映象关系的映象两种基本方法及其组合使用。两种基本方法及其组合使用。n顺序映象顺序映象：以相对的存储位置表示关系以相对的存储位置表示关系n链式映象链式映象：以附加信息：以附加信息( (指针指针) )表示关系表示关系在不同的编程环境下，存储结构有不同的描述方式。在不同的编程环境下，存储结构有不同的描述方式。用高级程序语言编程时，直接用其提供的数据类型描述。用高级程序语言编程时，直接用其提供的数据类型描述。存储结构1- 中国科大数据结构顺序存储和链式存储(1) 顺序存储顺序存储：数据元素依次放在连续的存储单元中。：数据元素依次放在连续的存储单元中。 (2) 链式存储链式存储：在存储结点中增加若干指
13、针域，记录后继或者相关：在存储结点中增加若干指针域，记录后继或者相关结点的地址（指针）。结点的地址（指针）。 10001004a1a2aian节点节点12721220an122412761004100010721340ai1220a1节点节点指针指针1- 中国科大数据结构p运算（操作）运算（操作）：在数据逻辑结构上定义的一组数据被使用的方式，：在数据逻辑结构上定义的一组数据被使用的方式，其具体实现要在存储结构上进行。其具体实现要在存储结构上进行。p常用的运算有：常用的运算有： (1)建立数据结构建立数据结构 (6)检索检索* (2)清除数据结构清除数据结构 (7)更新更新 (3)插入数据元素插
14、入数据元素 (8)判空和判满判空和判满* (4)删除数据元素删除数据元素 (9)求长求长* (5)排序排序p 操作为操作为引用型操作引用型操作，即数据值不发生变化；，即数据值不发生变化； 其它为其它为加工型操作加工型操作。数据运算1- 中国科大数据结构这三个方面的关系这三个方面的关系p数据的逻辑结构独立于计算机，是数据本身所固有的。数据的逻辑结构独立于计算机，是数据本身所固有的。p存贮结构是逻辑结构在计算机存贮器中的映像，必须依存贮结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。赖于计算机。p运算是指所施加的一组操作总称。运算的定义直接依赖运算是指所施加的一组操作总称。运算的定义直接依
15、赖于逻辑结构，但运算的实现必须依赖于存贮结构。于逻辑结构，但运算的实现必须依赖于存贮结构。1- 中国科大数据结构数据结构的三个方面 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：检索、排序、插入、删除、修改等数据的运算：检索、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构1- 中国科大数据结构1.3 数据类型和抽象数据类型 p数据类型：是一个数据类型：是一个值的集合值的集合和定义在这个值集上和定义在这个值集上一组操一组操作作总称。总称。pp分类：分类：分类：分类
16、：( (按值的不同特性按值的不同特性按值的不同特性按值的不同特性) )n原子类型原子类型 ：每一个对象仅由单值构成的类型：每一个对象仅由单值构成的类型 ；n结构类型结构类型 ：每一个对象可由若干成分按某种结构：每一个对象可由若干成分按某种结构构成的类型。构成的类型。1- 中国科大数据结构p抽象数据类型抽象数据类型 ADTADT（Abstract Data TypeAbstract Data Type）p作用：抽象数据类型可以使我们更容易描述实际问题。作用：抽象数据类型可以使我们更容易描述实际问题。例：用线性表描述学生成绩表，用树或图描述遗传关系。例：用线性表描述学生成绩表，用树或图描述遗传关系
17、。p定义：一个数学模型以及定义在该模型上的一组操作。定义：一个数学模型以及定义在该模型上的一组操作。p好处：可提高软件的复用程度。使用它的人可以只关心好处：可提高软件的复用程度。使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。同样不必要关心它如何存储。抽象数据类型1- 中国科大数据结构p例：线性表这样的抽象数据类型，其数学模型是：数据元素的例：线性表这样的抽象数据类型，其数学模型是：数据元素的集合，该集合内的元素有这样的关系：除第一个和最后一个外，集合，该集合内的元素有这样的关系：除第一个和最后一个外
18、，每个元素有唯一的前趋和唯一的后继。可以有这样一些操作：每个元素有唯一的前趋和唯一的后继。可以有这样一些操作：插入一个元素、删除一个元素等。插入一个元素、删除一个元素等。原子类型原子类型值不可分解，如值不可分解，如int固定聚合固定聚合类型类型值由确定数目的成分按某种值由确定数目的成分按某种结构组成，如复数结构组成，如复数可变聚合可变聚合类型类型值的成分数目不确定，如学值的成分数目不确定，如学生基本情况生基本情况抽象数据类型分类抽象数据类型分类中国科大数据结构抽象数据类型表示法p表示方法：表示方法：三元组表示：（三元组表示：（D D，S S，P P）其中：其中：D D是数据对象，是数据对象，S
19、 S是是D D上的关系集，上的关系集，P P是对是对D D的基本操的基本操作集。作集。p标准定义格式：标准定义格式：ADT ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象： 数据关系：数据关系： 基本操作：基本操作： ADT ADT 抽象数据类型名抽象数据类型名1- 中国科大数据结构名称线性表解释数据对象D=ai| ai(-ElemSet,i=1,2,.,n,n=0任意数据元素的集合数据关系R1=| ai-1,ai(- D,i=2,.,n除第一个和最后一个外，每个元素有唯一的直接前趋和唯一的直接后继基本操作ListInsert(L,i,e)L为线性表，i为位置，e为数据元素。List
20、Delete(L,i,e).例：线性表的表示中国科大数据结构p算法的概念算法的概念 建立在数据结构基础上的、求解问题的一系列确切的步骤。建立在数据结构基础上的、求解问题的一系列确切的步骤。p算法的算法的五五个特性个特性n有穷性：有穷性：对任何合法输入执行有穷步后能结束。对任何合法输入执行有穷步后能结束。n确定性：确定性：每条指令必须有确切的含义。每条指令必须有确切的含义。n可行性：可行性：算法的每一条指令均能执行。算法的每一条指令均能执行。n输入：输入：有零个或多个输入。有零个或多个输入。n输出：输出：有一个或多个输出。有一个或多个输出。p算法和程序的关系算法和程序的关系两者相似而又有区别。程
21、序不一定满足有穷性（死循环）；程两者相似而又有区别。程序不一定满足有穷性（死循环）；程序中的指令必须是机器可执行的，而算法中的指令则无此限制。序中的指令必须是机器可执行的，而算法中的指令则无此限制。一个算法若用计算机语言来书写，则它就可以是一个程序。一个算法若用计算机语言来书写，则它就可以是一个程序。1.4 算法和算法分析1- 中国科大数据结构p正确性正确性(Correctness)n算法应满足具体问题的需求算法应满足具体问题的需求n对于典型的、苛刻而带有刁难性的一组有效输入得到正确的对于典型的、苛刻而带有刁难性的一组有效输入得到正确的结果结果p可读性可读性(Readability)n算法应该
22、好读。以有利于阅读者对程序的理解。算法应该好读。以有利于阅读者对程序的理解。p健壮性健壮性(Robustness) n算法应具有容错处理。当输入非法数据时，算法应对其作出算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙或随机的输出结果。反应，而不是产生莫名其妙或随机的输出结果。p高效性高效性(Efficiency)n效率指的是算法执行时间效率指的是算法执行时间。对于解决同一问题的多个算法，。对于解决同一问题的多个算法，执行时间短的算法效率高。执行时间短的算法效率高。n存储量需求指算法执行过程中所需要的最大存储空间。存储量需求指算法执行过程中所需要的最大存储空间。n时
23、间复杂度和空间复杂度都与问题的规模有关。时间复杂度和空间复杂度都与问题的规模有关。评价算法优劣的基本标准1- 中国科大数据结构算法效率的度量p事后统计的方法：求出该算法的一个时间界限函数；事后统计的方法：求出该算法的一个时间界限函数；p事前分析估算的方法；要考虑以下的因素：事前分析估算的方法；要考虑以下的因素： n问题的规模；问题的规模；n编写程序时所用的程序设计语言；编写程序时所用的程序设计语言； n机器的速度；机器的速度； n算法所用的策略。算法所用的策略。p渐近时间复杂度（时间复杂度）：一般情况下，算法中基本操作重渐近时间复杂度（时间复杂度）：一般情况下，算法中基本操作重复执行的次数是问
24、题规模复执行的次数是问题规模n n的某个函数，算法的时间量度记作的某个函数，算法的时间量度记作 T(n)=O(f(n)T(n)=O(f(n)称作算法的渐近时间复杂度，简称时间复杂度。称作算法的渐近时间复杂度，简称时间复杂度。p频度：是指该语句重复执行的次数。频度与问题的基本操作执行次频度：是指该语句重复执行的次数。频度与问题的基本操作执行次数相同，故时间复杂度可通过频度来计算。数相同，故时间复杂度可通过频度来计算。p估算时间复杂度的方法估算时间复杂度的方法 ：从算法中选取一种对于所研究的问题来：从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作说是基本
25、操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则为算法运行时间的衡量准则 。1- 中国科大数据结构时间复杂度pnn问题规模，一般为数据的输入量问题规模，一般为数据的输入量pf(n)n算法中基本操作重复执行的次数算法中基本操作重复执行的次数频度频度n是问题规模是问题规模n n的某个函数的某个函数p算法的时间量度、时间复杂度算法的时间量度、时间复杂度n算法中各语句的频度之和算法中各语句的频度之和T(n)nT(n)=O( f(n) )n随问题规模的增大，算法执行时间的增长率和随问题规模的增大，算法执行时间的增长率和f(n)的增长率相同的增长率相同pO的含义的含义n 存在正的
26、常数存在正的常数c和和n0，使得，使得当当n n0时，时， 0 T(n) c* f(n) 1- 中国科大数据结构时间复杂度计算例例1： x+; s = 0;用频度法分析：将用频度法分析：将x+看成是基本操作，语句频度为看成是基本操作，语句频度为T(n)=2算法的时间复杂度：算法的时间复杂度：O(1)-常量阶常量阶例例2: for (i = 0; in; i+) /执行执行n+1次次 x+; /语句频度为：语句频度为：n s += x; /语句频度为：语句频度为：n T(n)=2n+n+1=3n+1，则时间复杂度为：，则时间复杂度为：O(n)也可以这样考虑：将也可以这样考虑：将x x自增看成是基
27、本操作，则语句频度为：自增看成是基本操作，则语句频度为：n n其其时间复杂度为：时间复杂度为：O(n)O(n)，即时间复杂度为线性阶。，即时间复杂度为线性阶。1- 中国科大数据结构例例3: 矩阵相乘矩阵相乘C=AxB for (i =0; i n; i+)/n+1 for (j = 0; j n; j+) /n*(n+1) cij = 0;/n2 for (k = 0; k n; k+) /n2 *(n+1) cij += aik * bkj; /n3 T(n)= 2n3 +3n2+2n+1算法的时间复杂度：算法的时间复杂度：O(n3)p计算方法计算方法1：由于是一个三重循环，每个循环从：由于
28、是一个三重循环，每个循环从1到到n，则总次数为，则总次数为: nnn=n3 故时间复杂度为故时间复杂度为T(n)=O(n3)。p计算方法计算方法2：由于：由于“乘法乘法”运算是本例的基本操作，故整个算法的运算是本例的基本操作，故整个算法的执行时间与该基本操作（乘法）重复执行的次数执行时间与该基本操作（乘法）重复执行的次数n3成正比，故时间成正比，故时间复杂度为复杂度为T(n)=O(n3)。时间复杂度计算1- 中国科大数据结构例例4:分析以下程序段的时间复杂度分析以下程序段的时间复杂度i=1; /语句频度为：语句频度为：while (i=n) i=i*2 /语句频度为：语句频度为：f(n)因为：
29、因为：f(n)n，即：，即：f(n)log2n，取最大值，取最大值f(n)=log2n ，则该程序，则该程序的时间复杂度为：的时间复杂度为：T(n)=1+f(n)=1+ log2n=O(log2n)时间复杂度计算1- 中国科大数据结构时间复杂度计算p补充补充)定理：若定理：若A(n)=a m n m +a m-1 n m-1 +a1n+a0是一个是一个m次多次多项式，则项式，则A(n)=O(n m)（证略）。（证略）。例例for(i=2;i=n;+i) for(j=2;j=0 & Ai!=K ) (3) i=i-1;(4) RETURN(i);最好情况的时间复杂度最好情况的时间复杂度 T(n)
30、=O(1)最坏情况的时间复杂度最坏情况的时间复杂度 T(n)=O(n)平均时间复杂度：平均时间复杂度：所有可能的输入实例以等概率出现的情况所有可能的输入实例以等概率出现的情况 T(n)=(1+2+.+n)/n算法的时间复杂度：算法的时间复杂度：O(n)1- 中国科大数据结构渐近复杂度的数学定义p定义：如果存在两个正常数定义：如果存在两个正常数c和和n0，对于所有的，对于所有的nn0，有，有f(n) cg(n) ，则称函数，则称函数f(n)当当n充分大时有上界，且充分大时有上界，且g(n)是它的一是它的一个上界，记为个上界，记为 f(n)=O(g(n)此时，可以说此时，可以说f(n)的阶不高于的
31、阶不高于g(n)。p大大O标记法的几个性质：标记法的几个性质：（1）O(f(n)+O(g(n)=O(max(f(n),g(n) (2) O(f(n)+O(g(n)=O(f(n)+g(n) (3) O(f(n)O(g(n)=O(f(n)g(n) (4) O(cf(n)=O(f(n) (5) f(n)=O(f(n)1- 中国科大数据结构时间复杂度按数量递增排列及增长率p一个算法时间为一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间因此，总的时间由一个常数（即零次多项式）来限界。而一个时间
32、为为O(n2)的算法则由一个二次多项式来限界。的算法则由一个二次多项式来限界。 以下六种计算算法时间的多项式是最常用的。其关系为：以下六种计算算法时间的多项式是最常用的。其关系为： O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)p 指数时间的关系为：指数时间的关系为：O(nk)O(2n)O(n!)O(nn) 当当n取得很大时，指数时间算法和多项式时间算法在所需时间上非取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个
33、伟大的成就。化简为多项式时间算法，那就取得了一个伟大的成就。 1- 中国科大数据结构空间复杂度(Time Complexity)p类似于算法的时间复杂度，空间复杂度可以作为算法所需存储空间类似于算法的时间复杂度，空间复杂度可以作为算法所需存储空间的量度。记作：的量度。记作：S(n)=O(f(n)S(n)=O(f(n)其中其中n n为问题规模的大小。主要包括三个部分：为问题规模的大小。主要包括三个部分：（1 1）输入数据所占用的空间。）输入数据所占用的空间。（2 2）程序本身所占用的空间。）程序本身所占用的空间。（3 3）辅助变量所占用的空间。）辅助变量所占用的空间。p存储密度存储密度d=d=数据本身存储量数据本身存储量/ /实际所占存储量实际所占存储量1- 中国科大数据结构习题p本章习题参见教师网页：本章习题参见教师网页：http:/
