《数据结构》课件（C语言）第01章.ppt

1、第一章第一章 绪论绪论第1页数数 据据 结结 构构主 讲：马慧芳 副教授办公地点：教9-C502电子邮件：联系电话：13919465723第一章第一章 绪论绪论第2页1、 什么是数据结构 2、 基本概念和术语 3、 抽象数据类型(ADT)4、 类C语言语法规则5、 算法的描述和算法分析第一章第一章 绪论绪论第3页一、一、数据结构数据结构教学计划教学计划英文名称 Data Structure先修课程 计算机导论、计算机高级语言、离散数学后续课程 操作系统、数据库技术、编译方法、人工 智能引论、信息系统原理与工程等授课学时 60学时上机实践 10机时第一章第一章 绪论绪论第4页配套题集 数据结构题

2、集，严蔚敏等编 清华大学出版社，2011.11参考教材1. Fundamentals of Data Structures in C ，李建中 张岩 李治军 译 机械工业出版社，2006.72. 数据结构:C语言描述 ，殷人昆著机械工业出版社，2011.63. 数据结构与算法分析，冯舜玺 译，机械工业出版社，2004.1注：可参考数据结构的C+语言方面的书籍。第一章第一章 绪论绪论第5页课程地位本课程不仅是一般的程序设计的基本训练，而且是设计和实现编译程序、操作系统、数据库系统、人工智能系统和其它系统程序的重要基础，是一门核心课程，对培养计算机及有关专业高层次科技人才具有重要意义。第一章第一章

3、 绪论绪论第6页课程任务课程任务讲授那些最重要、最常用的数据结构，阐明数据结构内在的逻辑关系，讨论它们在计算机中的存储表示，并结合各种典型应用说明它们在进行各种运算时的动态性质和实现操作的算法。第一章第一章 绪论绪论第7页第一章第一章 绪论绪论第8页章 次 内 容 授 课 学 时 一 二 三 四 五 六 七 八 九 十 绪 论 线 性 表 栈 和 队 列 串 数 组 和 广 义 表 树 和 二 叉 树 图 动 态 存 储 管 理 查 找 内 部 排 序 3 5 9 9 小 计 第一章第一章 绪论绪论第9页要求：、了解数据结构、算法的概念、基本的逻辑结构和存储结构、基本操作；、掌握类C语言体系和

4、抽象数据类型的概念；、知道算法的时间复杂性和空间复杂性概念。重点：、数据结构与算法的概念；、类C语言体系；、抽象数据类型。第一章第一章 绪论绪论第10页第一章第一章 绪论绪论第11页第一章第一章 绪论绪论第12页第一章第一章 绪论绪论第13页数据结构在计算机科学技术中是一门综合性的专业基础课专业基础课，计算机科学技术各个领域都要用到多种数据结构。在我国计算机各专业的教学计划中，它是核心课程之一。在我院教学计划中，数据结构已成为我院各专业一门公共必修课程。中国已列入93年计算机教程中。推荐学时为100学时。 其基本内容包括：基本数据结构，抽象数据类型基本数据结构，抽象数据类型，递归算法，复杂性分

5、析，排序和搜索，可计算性和，递归算法，复杂性分析，排序和搜索，可计算性和不可判定性，问题求解策略，并行和分布式算法不可判定性，问题求解策略，并行和分布式算法等。第一章第一章 绪论绪论第14页客观事物的符号表示，是计算机程序加工的原料。它是信息的载体，能被计算机识别、存储和加工处理。随着计算机软、硬件的发展，计算机应用领域的不断扩大，数据的含义也随之拓广。文字、表格、图像、声音、光和电的输入等等均可列入数据的范畴。第一章第一章 绪论绪论第15页是数据的基本单位，即数据这个集合中的一个实体。通常作为整体进行考虑和处理。有些情况下，数据元素也称为元素、结点、顶点、记录等。一个数据元素可能仅含一个数据

6、项，亦可包含若干个数据项。亦称字段、域,数据项是具有独立含义的不可分割的最小标识单位。第一章第一章 绪论绪论第16页性质相同的数据元素的集合，是数据的一个子集。数据对象可以是有限的，也可以是无限的。如：整数对象是集合N=0,1, 2,.；字母字符的集合等。第一章第一章 绪论绪论第17页简称类型简称类型，一个值的集合和定义在值集上的一组操作的总称。它显式地或隐含地规定了变量或表达式所有可能的取值范围以及在这些值上允许进行的操作。原子类型原子类型(Atomic Type)：如C中的标量类型（整型、实型、字符型）以及指针类型等。结构类型结构类型(Structured Type）：）：亦称结构类型，如

7、C中的数组、记录、文件类型等。抽象数据类型抽象数据类型(Abstract Data Type, ADT）：）：下面有专门介绍。第一章第一章 绪论绪论第18页 对数据进行诸如查找、插入、删除、合并、排序、统计、简单计算、输入、输出等的操作过程。相互关联的元素之间的构成关系。这种关系可以是物理上的，也可以是逻辑上的，或其它关系。第一章第一章 绪论绪论第19页定义：是相互之间存在一种或多种特定关系的数据元素的集合。 组成：由某一数据对象及该对象中所有数据成员之间的关系组成。Data Structure = （ Data Object, Relationships ） 数据结构是指在程序中信息的逻辑组

8、织方法，一般来说，这种方法也受到所选择的程序设计语言的限制。2、基本概念和术语第一章第一章 绪论绪论第20页 数据的逻辑结构：指各数据元素之间的逻辑关系，是用户按使用需要建立起来的，呈现在用户面前的结构形式。 数据的物理结构：亦称数据的物理结构、存储结构，是指数据在计算机内的表示方法，即存储形式。2、基本概念和术语第一章第一章 绪论绪论第21页逻辑结构存储结构操作第一章第一章 绪论绪论第22页例例1： 一个线性表 逻辑结构：逻辑结构：哪个元素是表中第一个元素；哪个元素是表中最后一个元素；哪些元素在一个给定元素之前或之后；等等。 存储结构：存储结构：它的元素在存储器中是顺序地邻接存放，还是用指针

9、连接在一起的；等等。 运算：运算：在表中查找一个元素；从表中删去一个元素；向表中插入一个元素；等等。第一章第一章 绪论绪论第23页1）从逻辑角度看，数据可归结为四种基本结构：集合、线性结构、树结构和图结构2）从存储角度看，数据可归结为四种基本结构：顺序结构、链接结构、索引结构和散列结构第一章第一章 绪论绪论第24页集合集合：结构中的数据元素之间除“同属于一个集合”的关系，无其他关系第一章第一章 绪论绪论第25页 链接存储结构 不要求逻辑上相邻的结点其物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。 顺序存储结构 把逻辑上相邻的结点存储在物理位置上相邻存储单元里，结点间的逻辑关系由存

10、储单元的邻接关系来体现。 散列存储结构 根据结点的关键字直接计算出该结点的存储地址。 索引存储结构 通常在存储结点信息的同时，还建立附加的索引表，索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址），关键字是能唯一标识一个结点的那些数据项。第一章第一章 绪论绪论第26页删除(Delete) 删去数据结构中某个指定的数据元素。插入(Insert) 在数据结构中的指定位置上增添新的数据元素。 更新(Update) 改变数据结构中某个数据元素的值，在概念上等价于删除和插入操作的组合。查找(Find) 在数据结构中寻找满足某个特定要求的数据元素(位置或值)。第一章第一章 绪论绪论第27页排

11、序(Sort) （在线性结构中）重新安排数据元素之间的逻辑顺序关系，使之按值由小到大或大到小（即递增、不降或递减、不增）的次序排列。注：注：一般将插入、删除与修改统称为更新；查找亦称搜索(Search) 。 第一章第一章 绪论绪论第28页 同一种逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，主要是使其运算方便及根据算法的时空要求来具体确定。 常将同一逻辑结构的不同存储结构以不同的数据结构的命名。如线性表顺序表、链表、散列表。 给定了数据的逻辑结构和存储结构，若定义的运算集合及其运算的性质不同，也可能导致完全不同的数据结构。如线性表中的栈、队列、顺序栈

12、、链栈、链队列。第一章第一章 绪论绪论第29页抽象数据类型(Abstract Data Type,ADT)是指一个数学模型以及定义在这个模型上的一组操作。抽象数据类型仅取决于它的逻辑特性，与其在计算集中的表示无关。即无论其内部结构如何变化，只要它的数学特性没有变化，都不影响其外部使用。一个ADT的定义并不涉及它的实现细节，这些实现细节对于ADT的用户是隐蔽的封装性封装性/信息隐蔽信息隐蔽数据结构是ADT的物理实现。第一章第一章 绪论绪论第30页第一章第一章 绪论绪论第31页ADT包括以下三部分内容： ADT的规格说明(Specification) ADT的表示(Representation)

13、ADT的实现(Implementation)用元组表示：ADT = ( 数据对象, 关系集, 处理集 )3、抽象数据类型(ADT)第一章第一章 绪论绪论第32页本书的表示格式：ADT 抽象数据类型名 数据对象： 数据关系： 基本操作： ADT 抽象数据类型名3、抽象数据类型(ADT)用伪码表示基本操作名(参数表) 初始条件： 操作结果：第一章第一章 绪论绪论第33页 在具体实现时，完成任务的算法、数据类型、数据结构、程序的逻辑组织，甚至采用哪种程序设计语言都是可以自由选择的 与具体实现无关。 ADT的主要目的之一是对用户隐蔽所有的表示方法，算法的详细细节、实现操作的具体代码以及其它所有对外界不

14、必要的细节，都被局限于具体实现的模块内部，从而实现了信息的隐蔽。 ADT的一个重要优点是其简单性。ADT的目的是将数据的本质特征、它们的结构及操作同它们的非本质的具体表示及实现细节相区分开来，从而得到了简化。第一章第一章 绪论绪论第34页例4：在数据结构中，复数可定义为一种简单的抽象数据类型：Complex=(C,R)其中C是含有两个实数的集合C1,C2，R=P，P是定义在集合C上的一种关系，有序偶表示C1是复数的实部，C2是复数的虚部。第一章第一章 绪论绪论第35页Specification Complex元素（元素（Elements）元素的集合为两个实数的笛卡儿乘积 Z = R R 其中R

15、表示实数集，Z表示复数集。结构（结构（Structure）Complex的元素之间不存在任何结构，每一个元素表示定义在复数域Z中的一个孤立的值。第一章第一章 绪论绪论第36页ADT Complex Data Objects: D = C1,C2 | C1,C2 实数; Data Relationships: R = |C1,C2 实数 Operations: InitComplex( &T, E1, E2 ) 操作结果：构造复数，E1,E2分别代替C1,C2。 Add( &T, E1, E2 ); 初始条件：复数T已知 操作结果：E1,E2分别加C1,C2 Sub( &T, E1, E2 );

16、 初始条件：复数T已知 操作结果： E1,E2分别减C1,C2 ADT Complex第一章第一章 绪论绪论第37页抽象数据类型Complex具体的表示和实现依赖于所采用的计算机语言。用户可以用某种高级语言的固有数据类型和自定义数据类型，并借助于过程和函数来表示和实现抽象数据类型Complex。C语言表示如下：3、抽象数据类型(ADT)struct Complex real RealPart; real ImagPart;；第一章第一章 绪论绪论第38页在Complex上可定义下列操作1）函数InitComplex生成一个复数Z，Z=x+iyComplex InitComplex( real

17、x, real y );2）函数Add求两个复数Z1与Z2之和。Complex Add( Complex Z1, Complex Z2 );或Complex Add( Complex Z, real R1, real R2 );3）函数Sub，求两个复数Z1与Z2之差Complex Sub( Complex Z1, Complex Z2 );或Complex Sub(Complex Z, real R1, real R2 );继下页第一章第一章 绪论绪论第39页4）函数Multiply求两个复数之积Complex Multiply( Complex Z1, Complex Z2 );Compl

18、ex Multiply( Complex Z, real R1, real R2);5）函数GetRealPart 取复数Z的实部real GetRealPart( Complex Z );6）函数GetImagPart取函数Z的虚部real GetImagPart( Complex Z );续上页第一章第一章 绪论绪论第40页以上关于ADT的定义（规格说明、表示）没有涉及到实现。正象ADT的名字所暗示的那样，它是作为实现的公共特征的抽象。但是，从ADT的角度研究数据结构的最终目的仍在于应用，因此必须仔细考虑表示方法、算法、实现的技术及细节。而当ADT被实现时，ADT中的元素成了数据结构的一个

19、实例,而那些操作就成了算法。由于在ADT的规格说明中，只指明了其功能而未指定要采用何种方法，因此，实现的独立性是显而易见的。第一章第一章 绪论绪论第41页Complex Create( real x, real y ) Complex Z; Z.RealPart = x; Z.ImagPart = y; return Z;Complex Add( Complex Z1, Complex Z2 ) Complex Sum; Sum.RealPart = Z1.RealPart + Z2.RealPart; Sum.ImagPart = Z1.ImagPart + Z2.ImagPart; ret

20、urn Sum;(以下略以下略) 抽象数据类型Complex的C语言实现：第一章第一章 绪论绪论第42页 由于C语言是面向过程的语言，它能支持ADT的实现，但是不能很好的反映ADT的数据隐蔽原则。在Pascal语言中，库单元(Unit)是ADT的较好表示和实现。 随着面向对象技术的成熟，用面向对象中的对象/类来描述和实现ADT是非常好的方法。这种方法在面向对象程序设计方面已经成熟，已经广泛应用于不同程序设计语言及开发环境当中（如：C+，Object Pascal, VB, Java, PowerBuilder等等）。 第一章第一章 绪论绪论第43页下面是Complex采用C+的定义：class

21、 Complex private: real RealPart; real ImagPart; public: Complex( real x, real y );/构造函数构造函数 Complex( Complex &Z );/拷贝构造函数拷贝构造函数 Complex Add( Complex Z );/加法加法 Complex Sub( Complex Z );/减法减法 Complex Multiply( Complex Z );/乘法乘法 real GetRealPart( void );/取实部取实部 real GetImagPart( void );/取虚部取虚部 C+实现略实现略

22、第一章第一章 绪论绪论第44页类C语言是介于伪码语言和高级语言之间的一种算法描述语言。使用类C语言描述算法的好处：1. 保持C结构清晰、明确直观等特色；2. 但又略去一些次要环节，抓住主干精华。第一章第一章 绪论绪论第45页函数类型 过程名(参数表) /算法说明 语句组; return 结果； /过程名当返回状态结果时，函数定义为Status类型。第一章第一章 绪论绪论第46页简单赋值 变量名 = 表达式；串联赋值 变量1 = 变量2 = = 表达式；成组赋值 (变量名1,变量名k)=(表达式1,表达式k);结构名 = 结构名;结构名 = (值1, ,值k)；第一章第一章 绪论绪论第47页变换

23、赋值 变量1 变量2；if( 条件 ) 语句1;if( 条件 ) 语句1; else 语句2；/可以嵌套第一章第一章 绪论绪论第48页switch( 表达式 ) case 条件1：语句1；break; case 条件n：语句n; break; default: 语句 n+1switch case 条件1：语句1；break; case 条件n：语句n; break; default: 语句 n+1第一章第一章 绪论绪论第49页For语句： for( 处置表达式序列; 条件; 修改表达式系列 ) 语句；While语句： while( 条件 ) 语句； Do-While语句： do 语句; whi

24、le ( 条件 );第一章第一章 绪论绪论第50页具体参见P10页第一章第一章 绪论绪论第51页第一章第一章 绪论绪论第52页算法算法( (Algorithm)是对特定问题求解步骤的一种描述，是能在计算机上经过有限时间完成的、毫不含糊的指令的有限序列。其中每一条指令表示一个或多个操作。问题问题（Problem）是一个函数，或是输入和输出的一种联系。程序程序（Program）是用计算机程序设计语言实现的完成一定功能的代码。算法的实现一定是程序，但程序不一定是算法的实现。第一章第一章 绪论绪论第53页算法的五个重要特性第一章第一章 绪论绪论第54页第一章第一章 绪论绪论第55页一个算法可以用各种不

25、同的方法来进行描述。比如可使用某种高级语言、汇编语言甚至机器语言来描述某个算法，亦可使用伪码语言或框图等其它形式来描述它。这里我们采用上讲介绍的类C语言来描述算法第一章第一章 绪论绪论第56页在程序设计中，对算法进行分析是十分重要的。对于一个具体的应用实例，通常可能有若干个算法可供选用，应判断哪一个算法在现有的计算机环境中对解决某个问题是最优的long BetterSum( int n ) return (n+1)*n/2;第一章第一章 绪论绪论第57页第一章第一章 绪论绪论第58页1 1）正确性）正确性(Correctness) 能满足具体问题的需求。正确性对于选择算法来说，是首要的问题。正

26、确性的四个层次： a. 程序不含语法错误； b. 程序对于输入数据能够得出满足规格说明要求的结果 (要算对)； c. 程序对于精心选择的典型、苛刻而带有刁难性的输入 数据能够得出满足规格说明要求的结果； d. 程序对于一切合法的输入数据都能产生满足规格说明 要求的结果。第一章第一章 绪论绪论第59页2 2）可读性）可读性(Readability)希望一个算法易于理解、易于编码，也易于调试。3 3）健壮性）健壮性(Robustness)对于异常的处理能力。能作出判断，并给出适当的提示或警告信息，以等待操作员的干预或能自动进行适当处理。4 4）效率）效率(Efficiency)与与低存储需求低存储

27、需求效率指算法执行时间。同一问题，算法执行时间越短，效率越高。存储量需求指算法执行过程中所需的最大存储空间。此所谓时（执行时间）、空（运行空间）效应第一章第一章 绪论绪论第60页算法执行时间的度量算法执行时间的度量时间复杂度时间复杂度执行时间取决于下列因素： a. 选用哪种算法 b. 问题的规模（输入的大小/复杂程度）； c. 所选用的语言； d. 编译程序所产生可执行代码的质量； e. 机器执行指令的速度。1 1）事后统计）事后统计 对算法程序的执行进行计时。（有缺陷）2 2）事前估计）事前估计事先估算的主要因素问题的规模。第一章第一章 绪论绪论第61页 一个算法是由控制结构（顺序、分支和循

28、环）和原操作（指固有数据类型的操作）构成的，算法时间取决于两者的综合效果。但是，为便于比较同一问题的不同算法，通常的做法是：从算法中选取一种对于所研究的问题（或算法类型）来说是基本运算的原操作，以该基本运算重复执行的次数作为算法的时间量度的依据。2 2）事前估计）事前估计第一章第一章 绪论绪论第62页两个nn矩阵相乘，令乘法运算作为基本运算for( i = 1; i = n; i+ ) for( j = 1; j = n; j+ ) Cij = 0; for( k = 1; k n0，T(n) Mf(n)都成立。如果一个程序的时间复杂度是O(f(n)，就说该程序的运行时间增加率的一个上界为f(

29、n)，或说T(n)是f(n)的大O函数。设T(n)=n2+4n，则有f(n)=n2，即有：n2 + 4n = O(n2).因为存在M=2，n0=4，使对于一切nn0，恒有n2 +4n2 n2第一章第一章 绪论绪论第64页大大O O运算规则运算规则规则一规则一 对于任何的常数k和任何的函数f，恒有kf(n)=O(f(n)，即大O忽略常数因子。 规则二规则二 若f(n)=O(g(n)且g(n)=O(h(n)，则f(n)=O(h(n)，即大O的概念是传递的。 规则三规则三 若定义maxf(n)，g(n)为f(n)与g(n)两者中增长率较快的函数，则有f(n)+g(n)=O(maxf(n),g(n).

30、 规则四规则四 若f1(n)=O(g1(n)且f2(n)=O(g2(n)，则f1(n)f2(n)=O(g1(n) g2(n)，即大O符合乘法规则。有关数学问题有关数学问题：/型不定式极限有关数学定理有关数学定理：罗比塔法则第一章第一章 绪论绪论第65页求时间函数8nlog(n)+4n3/2的大O. (1) log(n)=O(n1/2) 定义 (2) nlog(n)=O(nn1/2)= O(n3/2) 规则四 (3) 8nlog(n)=8O(n3/2)= O(n3/2) 规则一 (4) 4n3/2=O(n3/2) 规则一 (5) 8nlog(n)+ 4n3/2 =O(max8nlog(n)， 4

31、n3/2） 规则三 max8nlog(n)， 4n3/2 = maxO(n3/2) ， O(n3/2) = O(n3/2) 8nlog(n)+ 4n3/2= O(O(n3/2) 所以有 = O(n3/2) 规则二 8nlog(n)+ 4n3/2= O(n3/2).第一章第一章 绪论绪论第66页算法所需存储空间的度量空间复杂度（性）算法的空间复杂度S(n)就是一个算法或程序所需要的存储单元数。一个非递归程序，并且不含有动态数据结构，在它还未开始执行前，所需存储单元总数即已确定。为简化计算，在算法的空间复杂度分析中，将忽略程序中所有的简单变量和程序的执行代码本身所占的内存空间，而只统计与问题大小有

32、关的数组等结构变量所需的内存量，有时当一些数据、结构变量要占用相当可观的常数量单元时，也可进行统计。含有动态数据结构的程序应统计内存分配过程的次数乘以该过内存分配过程的次数乘以该过程产生的动态变量所占单元的大小程产生的动态变量所占单元的大小。递归调用情况较复杂，所需内存单元数等于递归调用的最大深度乘以该递归过程本身所需的内存量，后者包括简单变量、参数变量、调用时系统所需的辅助内存量等。 第一章第一章 绪论绪论第67页l基本内容 *数据和数据结构等名词和术语的确定含义 *抽象数据类型（ADT） *描述算法的类C语言 *从时间和空间角度分析算法的方法l学习要点 *熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系 *了解怎样以ADT的角度来描述数据结构 *熟悉类C语言的书写规范 *理解算法五要素 *掌握计算语句频度和估算算法时间复杂度的方法第一章第一章 绪论绪论第68页