《徐敏232httpxuminiecnueducnxumin1025@sinacom.ppt》由会员分享，可在线阅读，更多相关《徐敏232httpxuminiecnueducnxumin1025@sinacom.ppt（60页珍藏版）》请在三一文库上搜索。
1、徐敏(232) http:/ ,t,数据结构,学习课程前你需要了解的,教材与资料,作业和测验,答疑,学习目的,教材和资料,一.教材 1.数据结构（c语言版） -严蔚敏，吴伟民 编著 -清华大学出版社 2.数据结构题集（c语言版） -严蔚敏，吴伟民，米宁 编著 -清华大学出版社 二.资料 1.数据结构与算法 自编练习册（包含三个练习） 2.数据结构学习与实验,作业和测验,一.测验 1.两次或三次测验 2.测验题目部分来自 3.共占总评 15%-20%,二.作业 1.书面作业 2.上机实验作业,答疑,1.周二、周四中午（12：30-13：20） -232 2.电子邮件答疑 -,掌握数据结构的目的,
2、掌握常用的数据结构及其应用 学会数据抽象，合理地组织数据， 有效地表示数据和处理数据 掌握算法设计技术和分析技术 掌握使用计算机解决问题的方法和技能，提高程序设计水平,第一章 绪论,1.1 什么是数据结构,1.2 基本概念和术语,1.3 抽象数据类型,1.4 算法及其分析,1.1什么是数据结构,1.电子计算机的主要用途：,主要用于数值计算,处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。,早期,后来,1.1什么是数据结构,Niklaus Wirth 尼古拉斯沃斯 Algorithm + Data Structures = Programs (算法+数据结构=程序 ),程
3、序设计 算法 数据结构,为计算机处理问题编制一组指令集,处理问题的策略,问题的数学模型,1.1什么是数据结构,2.用计算机解决问题的途径,建立模型,构造求解算法,选择存储结构,编写程序,测试,描述问题的共性,将问题涉及的数据存储到计算机中,描述问题的求解方法,1.1什么是数据结构,3.引例,3.1书目自动检索系统的数学模型,书目文件,1.1什么是数据结构,3.引例,1.1什么是数据结构,线性表,3.2人机对奕问题的数学模型,树,3.3十字路口的交通灯管理问题的数学模型,图,1.1什么是数据结构,3.求解非数值计算的问题,主要考虑的是设计出合适的数据结构及相应的算法。 即：考虑对相关的各种信息如
4、何表示、组织和存储？,数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。,1.1什么是数据结构,?,学习数据结构有什么用？,ANSWER,计算机内的数值运算依靠数学方程，而非数值运算（如表、树、图等）则要依靠数据结构。,同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。,1.1什么是数据结构,4.数据结构课程的形成和发展,形成阶段 60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。 1968年，美唐欧克努特教授开创了数据结构的最初体系，计算机程序设计技巧第一卷基本算法 ，“数据结构”被列入美国一些大学计算机
5、科学系的教学计划。 发展阶段 数据结构的概念不断扩充，包括了集合代数论、关系等“离散数学结构”的内容。 70年代后期，80年代初，我国高校陆续开设该课程。,1.1什么是数据结构,5.数据结构课程所处的地位,介于数学、计算机硬件和计算机软件三者之间的一门核心课程。,1.2基本概念和术语,1.基本概念,1.1 数据（data） 数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合, 是计算机程序加工的“原料”。,分类,数值性数据 非数值性数据,1.2基本概念和术语,1.2 数据元素（data element）,- 数据的基本单位。 在计算机程序中
6、常作为一个整体进行考虑和处理。有时一个数据元素可以由若干数据项(Data Item)组成。 - 数据项是数据不可分割的最小标识单位。 - 数据元素又称为元素、结点、记录。,1.2基本概念和术语,1.3 数据对象（data object）,- 数据对象是具有相同性质的数据元素的集合。 - 正整数数据对象 N = 0, 1, 2, - 字母字符数据对象 C=A，B，Z - 学生成绩数据对象 Cj=（101，jane，80）， （102，jack，90）， （103，jerry，75）,1.2基本概念和术语,1.4 数据结构(data structure),数据结构是相互之间存在一种或多种特定关系的
7、数据元素的集合。 在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构(Structure)。 数据结构是一堆数据元素和这些数据元素之间的关系的总和。,按数据元素之间关系的不同特性，通常有4类基本结构: （1）集合 结构中的数据元素除了“同属于一个集合”外，别无其它关系。 （2）线性结构 结构中的数据元素之间存在一对一的关系。 （3）树型结构 结构中的数据元素之间存在一对多的关系。 （4）图状结构或网状结构 结构中的数据元素之间存在多对多的关系。,1.2基本概念和术语,用一个二元组表示，记为： Data_Structure = （D, S）
8、其中，D 是数据元素的有限集（即一个数据对象） S 是该对象中所有数据成员之间的关系的有限集合。,在计算机科学中，对复数的定义：复数是一种数据结构 Complex=(C,R) 其中：C是包含两个实数的集合 C1, C2 , R=P,P是定义在C上的一种关系 。,1.4 数据结构(data structure),1.2基本概念和术语,例1.用数据结构如何描述2行3列矩阵：,它是一个含6个数据元素a1,a2,a3,a4,a5,a6 的集合，且集合上存在“行关系”和“列关系”两个次序关系,行关系为 ， 列关系为 ， 意为 x 和 y 之间存在 “x领先于y“ 的次序关系。,a1 a2 a3 a4 a
9、5 a6,思考： 如何描述一个一行六列的矩阵？,例2 假设我们需要编制一个事务管理的程序，管理学校科学研究课题小组的各项事务，则首先要为程序的操作对象课题小组设计一个数据结构。假设每个小组由一位教师、一至三名研究生及一至六名本科生组成，小组成员之间的关系是：教师指导研究生，而由每位研究生指导一至两名本科生。 则可以如下定义数据结构： Group = (P，R) 其中: P = T，G1，Gn，S11Snm 1 | 1 | 1=i=n, 1=j=m, 1=n=3, 1=m=2,1.2基本概念和术语,1.2基本概念和术语,1.5 数据的逻辑结构,数据的逻辑结构从逻辑关系上描述数据，可以看作是从具体
10、问题抽象出来的数据模型，与数据的存储无关，也与数据元素本身的形式、内容、相对位置无关；,数据的逻辑结构分类： 线性结构 线性表、栈、队列 、串 非线性结构 树 、图（或网络）,1.2基本概念和术语,1.6 数据的存储结构,数据结构在计算机中的表示(或称映象)称为数据的存储结构，又称为物理结构。 （1）数据元素的表示 （2）关系的表示两种基本的存储方法： 顺序映像（顺序存储结构） 连续 存储单元 逻辑 相邻，物理 相邻 非顺序映像（链式存储结构） 不连续 存储单元 逻辑 相邻，物理 未必 相邻 指针,1.2基本概念和术语,1.7 数据类型（data type）,数据类型是一个值的集合和定义在这个
11、值集上的一组操作的总称。 数据类型可分两类：原子类型和结构类型。 例如：在C语言中 原子类型：整型、实型、字符型等 结构类型：数组、结构体、联合等,1.2基本概念和术语,1.8 抽象数据类型 (Abstract Data Type简称ADT),指一个数学模型以及定义在此数学模型上的一组操作。 它与数据类型实质上是一个概念，其特征是使用与实现分离，实行信息的封装和隐蔽（独立于计算机）。 例如：计算机拥有的整数类型。 抽象数据类型的范围更广,不仅仅局限于固有数据类型,还包括用户自定义的数据类型。,1.2基本概念和术语,抽象数据类型的描述方法,抽象数据类型可用（D，S，P）三元组表示，其中，D是数据
12、对象，S是D上的关系集，P是对D的基本操作集。 ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名,数据对象和数据关系的定义用伪码（不真正执行的符号）描述。,基本操作的定义格式为： 基本操作名（参数表） 初始条件：初始条件描述 操作结果：操作结果描述,引用类型,引用可以看作是一个变量的别名，通过引用一个变量，我们可以让引用变量和被引用变量共享同一个存储数据。,(1)引用的定义 关键字：type,描述了使用引用和指针的不同之处。 #include void main() int i; int ,程序运行结果： i = 30
13、 j = 30 *k = 30 i = 80 j = 80 *k = 80 i = 100 j = 100 *k = 100 Address of i is 0x0012FF7C Address of j is 0x0012FF7C Address of k is 0x0012FF74,1.2基本概念和术语,基本操作名（参数表） 初始条件：初始条件描述 操作结果：操作结果描述,基本操作有两种参数： 赋值参数只为操作提供输入值； 引用参数以&打头， 除了可以提供输入值外，还将返回操作结果。 “初始条件”描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。若初始
14、条件为空，则省略之。 “操作结果” 说明了操作正常完成之后，数据结构的变化状况和应返回的结果。,1.2基本概念和术语,举例:抽象数据类型复数的定义,ADT Complex 数据对象：De1,e2e1,e2RealSet 数据关系：R1| e1是复数的实数部分, e2 是复数的虚数部分 基本操作： InitComplex( &Z, v1, v2 ) 操作结果：构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。 DestroyComplex( &Z) 操作结果：复数Z被销毁。,1.2基本概念和术语,GetReal( Z, &realPart ) 初始条件：复数已存在。 操作结果：用realPa
15、rt返回复数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,1.3 抽象数据类型的表示与实现,抽象数据类型可通过固有数据类型来表示和实现，即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。,1.类C语言简要说明,(1)预定义常量和类型： /函数
16、结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE 1 #define OVERFLOW 2 /Status是函数的类型，其值是函数结果状态代码 typedef int Status；,1.3 抽象数据类型的表示与实现,(2)基本操作的算法都用以下形式的函数描述： 函数类型 函数名(函数参数表) /算法说明 语句序列 /函数名 除了函数的参数需要说明类型外，算法中使用的辅助变量可以不作变量说明，必要时对其作用给予注释。 一般: a、b、c、d、e等用作数据元素名; i、k、1
17、、m、n等用作整型变量名; p、q、r等用作指针变量名。 当函数返回值为函数结果状态代码时，函数定义为Status类型。,1.3 抽象数据类型的表示与实现,(3)赋值语句有 简单赋值 变量名 = 表达式； 串联赋值 变量名1 = 变量名2 = = 变量名k = 表达式； 成组赋值 (变量名1，变量名k) = (表达式1，表达式k)； 结构名 = 结构名； 结构名 = (值1，值k)； 变量名 = 表达式； 变量名起始下标终止下标= 变量名起始下标终止下标 交换赋值 变量名变量名； 条件赋值 变量名 = 条件表达式?表达式 T : 表达式 F,1.3 抽象数据类型的表示与实现,(5)循环语句有
18、for语句 for(赋初值表达式序列 ；条件；修改表达式序列) 语句； while语句 while(条件)语句； do-while语句 do语句序列；while(条件)； (6)结束语句有 函数结束浯句 return 表达式； return； case结束语句 break； 异常结束语句 exit(异常代码) ;,1.3 抽象数据类型的表示与实现,(7)输入和输出语句有 输入语句 scanf ( 格式串，变量1, ，变量n)； 或 cin变量1变量n; 输出语句 printf( 格式串，表达式1， ，表达式n); 或 cout表达式1表达式n;,(8)注释 - 行注释 /文字序列,1.3 抽象
19、数据类型的表示与实现,求最大值 max (表达式l，表达式n) 求最小值 min (表达式1，表达式n) 求绝对值 abs (表达式) 求不足整数值 floor(表达式)向下取整 求进位整数值 ceil(表达式)向上取整 判定文件结束 eof(文件变量)或eof 判定行结束 eoln(文件变量)或eoln,(9)基本函数有,1.3 抽象数据类型的表示与实现,2.抽象数据类型实现示例,例如抽象数据类型“复数”如下描述： / 存储结构的定义 typedef struct float realpart; float imagpart; complex; / 基本操作的函数原型说明 void Assi
20、gn( complex / 以 sum 返回两个复数 z1，z2 的和基本操作的实现 ,void add( complex z1, complex z2, complex ,1.4 算法和算法分析,2.算法的特性(要素) 有穷性 算法应在执行有穷步后结束,且每一步都在有穷时间内完成 确定性 每步定义都是确切、无歧义的 可行性 算法中描述的操作应能通过执行有限次已经实现的基本运算而实现 输入 有0个或多个输入 输出 有一个或多个输出(处理结果),1.算法的定义 是对特定问题求解步骤的一种描述,是一个有穷的指令集，这些指令表示一个或多个操作。,1.4 算法和算法分析,3.算法设计的要求,正确性：不
21、含有语法错误；对于各种合法的输入数据能够得到满足规格说明要求的结果。 可读性：要求程序有较好的人机交互性,有助于人们对算法的理解。 健壮性：对输入的非法数据能作出适当的响应或处理。 效率与低存储需求：主要指算法的执行时间和所需的最大存储空间，这两方面主要和问题的规模有关。,1.4 算法和算法分析,4.算法效率的度量,(1)算法的后期测试 在算法中的某些部位插装时间函数 time ( )测定算法完成 某一功能所花费时间。 (2)算法的事前估计：时间复杂度，空间复杂度,(3)程序运行所需要的时间取决于下列因素：,依据的算法选用何种策略。 问题的规模。 书写程序的语言。 编译程序所生成目标代码的质量
22、。 硬件的速度。,可以认为一个特定算法“运行工作量”大小，只依赖于问题的规模（通常用整数n表示），或者说，它是问题规模的函数。,1.4 算法和算法分析,一个算法所耗费的时间，应该是该算法中每条语句的执行时间之和，而每条语句的执行时间又是该语句的执行次数（频度）与该语句执行一次所需时间的乘积。 语句的频度指的是该语句重复执行的次数。 我们假定，每条语句一次执行的时间都是相同的，为单位时间，这样我们对时间的分析就可以独立于软硬件系统。 时间复杂度是问题规模的函数T( n )。,语句频度举例,（a） +x; s=0；,（b） for (i=1; i=n; +i) +x; s+=x;,（c） for
23、(j=1;j=n;+j) for (k=1;k=n;+k) +x; s+=x;,(a)+x 的频度为1 (b)+x的频度为n (c)+x的频度为n2,1.4 算法和算法分析,5.时间复杂度,设解决一个问题的规模为n f(n)表示基本操作被重复执行的次数，它是n的一个函数 假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作： T (n) = O(f(n) 其中T（n）叫算法的渐进时间复杂度，简称时间复杂度， O是Order（数量级）的首字母，意思是T（n）与f（n）只差一个常数倍。,比较同一问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题是基本操作的原
24、操作，以该基本操作重复执行的次数作为算法的时间量度。 基本操作的原操作,大多数情况下它是最深层循环内的语句中的原操作，它的执行次数和包含它的语句的频度相同。,1.4 算法和算法分析,6.渐进时间复杂度的计算,加法规则 针对并列程序段 T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m) 乘法规则针对嵌套程序段 T (n, m) = T1 (n) * T2 (m) = O(f (n)*g (m) 注：c log2n n nlog2n n2 n3 2n 3n n!,1.4 算法和算法分析,6.渐进时间复杂度的计算,T(n) = T1(n)+T2(n)+T3
25、(n) = O( max( 1, n, n2 ) ) = O(n2),x = 0; y = 0; for ( int k = 0; k n; k + ) x +; for ( int i = 0; i n; i+ ) for ( int j = 0; j n; j+ ) y +;,T1(n) = O(1),T2(n) = O(n),T3(n) = O(n2),1.4 算法和算法分析,对 n 个整数的序列进行选择排序。其中序列的“长度” n 为问题的规模。,void selectSort ( int a , int n ) /对n个整数a0,a1,an-1按递增顺序排序 for ( int i
26、= 0; i n-1; i+ ) int k = i; /从ai查到an-1, 找最小整数, 在ak for ( int j = i+1; j n; j+ ) if ( aj ak ) k = j; temp = ai; ai = ak; ak = temp; ,算法的时间复杂度为O (n2) 。,1.4 算法和算法分析,有时, 算法的时间复杂度不仅依赖于问题规模n，还与输入实例的初始排列有关。 例如：在数组 An 中查找给定值 k 的算法： int i = n-1; while ( i = 0 算法的语句 i- 的频度不仅与 n 有关，还与 A i 中各元素的取值，以及 k 的取值有关。,1
27、.4 算法和算法分析,O符号：表示算法的最坏时间复杂度，也就是算法运行时间的上限。,定义：对于给定的函数 g(n), 记O(g(n) = f(n) : 存在c和 n0 ，对于任意nn0，满足0f(n)cg(n)的函数集。并记f(n) =O(g(n)，它表示f(n) 是O(g(n)中的一个元素。,注意： O(g(n)的定义要求任意f(n) =O(g(n)都是渐进非负的。,1.4 算法和算法分析,符号：表示算法的平均时间复杂度。,定义：对于给定的函数 g(n), 记(g(n) = f(n) : 存在三个正常数c1, c2, n0 ，对于任给nn0，满足0c1g(n) f(n)c2g(n)的函数集。
28、并记f(n) =(g(n)，它表示f(n) 是(g(n)中的一个元素。,1.4 算法和算法分析,符号：表示算法的最好时间复杂度，也就是算法运行时间的下限。,定义：对于给定的函数 g(n), 记(g(n) = f(n) : 存在c和 n0 ，对于任意nn0，满足0cg(n) f(n)的函数集。并记f(n) = (g(n)，它表示f(n) 是(g(n)中的一个元素。,注意： (g(n)的定义要求任意f(n) = (g(n)都是渐进非负的。,1.4 算法和算法分析,7.算法的空间复杂度,空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，记作： S(n) = O(f(n),算法的存储量包括
29、,输入数据所占空间 程序本身所占空间 辅助变量所占空间,1.4 算法和算法分析,7.算法的空间复杂度,例：假设CPU每秒处理10 6 个指令，对于输入规模为108的问题，时间代价T(n) = 2n2的算法要运行多长时间？,操作次数为T(n) = T(108) = 2(108)2 = 21016 运行时间为21016/106 = 21010秒 每天有86,400秒，因此需要231,481 天(634年）,1.4 算法和算法分析,7.算法的空间复杂度,例：假设CPU每秒处理106个指令，对于输入规模为108的问题，时间代价为nlog n 的算法要运行多长时间？,操作次数为 T(n) = T(108
30、) = 108 log 108 = 2.66109 运行时间为2.66109/106 = 2.66103秒= 44.33分钟,1.4 算法和算法分析,说明,算法的所有性能之间都存在着或多或少的相互影响；,- 因此，当设计一个算法，特别是大型算法时，要综合考虑算法的各项性能、算法的使用频率、算法处理的数据量的大小、算法描述语言的特性及算法运行的机器系统环境等各方面因素，才能设计出比较好的算法。,第一章 绪论,本章小结,与数据结构相关的几个名词概念 数据结构研究的内容： 数据的逻辑结构 数据的物理结构（存储结构） 在数据结构上的操作 抽象数据类型 算法分析：时间复杂度、空间复杂度,写出下列程序的执行结果，并分析原因,