数据结构语言版第一章引论

2023/11/181数据结构福州大学计算机科学与技术系22023/11/18第1章引论理解算法的概念理解什么是程序，程序与算法的区别和内在联系能够列举求解问题的基本情况掌握算法在最坏情况、最好情况和平均情况下的计算复杂性概念掌握算法复杂性的渐近性态的数学表述了解表达算法的抽象机制熟悉数据类型和数据结构的基本概念理解数据结构、数据类型和抽象数据类型三者的区别和联系掌握用C语言描述数据结构与算法的方法。理解递归的概念32023/11/18第一章引论1.1什么是数据结构

程序=数据结构+算法例1书目自动检索系统书目文件按书名按作者名按分类号索引表线性表42023/11/18例2人机对奕问题树……..……..…...…...…...…...52023/11/18多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图62023/11/181.2算法的描述和算法分析简介算法（algorithm）—解决某一特定问题的具体步骤的描述，是指令的有限序列算法特性—算法的描述—采用C语言算法的评价—衡量算法优劣的标准正确性(correctness)可读性(readability)健壮性(robustness)效率与低存储量72023/11/18评价算法的标准： 评价一个算法主要看这个算法所占用机器资源的多少，而这些资源中时间代价与空间代价是两个主要的方面，通常是以算法执行所需的机器时间和所占用的存储空间来判断一个算法的优劣。

82023/11/18时间复杂度：基本操作重复执行的次数的阶数T(n)=o(f(n))空间复杂度：s(n)=o(f(n))算法语句对应的语句频度

1 for（i=0；i<n;i++）n2 for（j=0；j<n;j++）n23{c[i][j]=0;n24for(k=0;k<n;k++)n3c[i][j]=c[i][j]+a[i][k]*b[k][j];n3

}

总执行次数：Tn=2n3+2n2+n语句频度：是指该语句在一个算法中重复执行的次数。92023/11/18

空间效率的分析一个算法的空间效率是指在算法的执行过程中，所占据的辅助空间数量。辅助空间就是除算法代码本身和输入输出数据所占据的空间外，算法临时开辟的存储空间单元。在有些算法中，占据辅助空间的数量与所处理的数据量有关，而有些却无关。后一种是较理想的情况。在设计算法时，应该注意空间效率。102023/11/181.3数据类型和抽象数据类型

具有相同数据结构的数据属同一类。同一类数据的全体称为一个数据类型。在高级程序设计语言中，数据类型用来说明数据在数据分类中的归属。它是数据的一种属性。简单数据类型对应于简单的数据结构。复杂的数据结构允许成分数据本身具有复杂的数据结构，因此，构造数据类型允许复合嵌套。数据类型包括对成分数据的运算。112023/11/18抽象数据类型基本数据类型概念的引伸和发展。数据模型连同定义在该模型上并作为数据模型构件的一组运算。抽象数据类型明确地把数据模型与该模型上的运算紧密地联系起来。

122023/11/18AbstractDataType(ADT)user1user2usern……...实现1实现2实现3132023/11/18

从使用的角度看，一个抽象数据类型隐藏了所有使用者不关心的实现细节。使程序模块的实现与使用分离，从而能够独立地考虑模块的外部界面、内部算法和数据结构的实现。在许多程序设计语言中预定义的类型，例如整数类型、浮点类型、指针类型等，都可以看作是简单的抽象数据类型。

从原则上讲，数据结构课程中讨论的各种表、栈、队列、二叉树和字典等，也可以像整数、浮点数等一样定义为程序设计语言预定义的抽象数据类型。

142023/11/18使用抽象数据类型的好处

算法顶层的设计与底层的实现分离，使得在进行顶层设计时不考虑它所用到的数据和运算将分别如何表示和实现；算法设计与数据结构设计隔开，允许数据结构自由选择，从中比较，优化算法和程序运行的效率。数据模型和该模型上的运算统一在抽象数据类型中编出来的程序自然地呈现模块化，而且抽象的数据类型的表示和实现都可以封装起来，便于移植和重用。152023/11/181