课件-数据结构及应用算法教程-严蔚敏版

1、算法和数据结构，教材：数据结构(c语言版)。 严蔚敏，吴伟民编着。 清华大学出版社。 参考文献： 1数据结构。 张选平、雷咏梅篇、严蔚敏审。 机械工业出版社。 2数据结构和算法分析。 Clifford A. Shaffer着、张铭、刘晓丹译。 电子工业出版社。 3数据结构的练习问题和分析(c语言实语言版)。 李春葆。 清华大学出版社。 4数据结构和算法。 夏克俭编着。 防卫工业出版社。 第一章绪论，目前计算机深入社会生活的各个领域，其应用不仅用于科学计算，还用于控制、管理、数据处理等非数值计算领域。 计算机是用计算机研究信息的显示和处理的科学。 其中存在信息的显示、信息的处理这两个问题。 信息

2、的显示和组织直接关系到处理信息的程序的效率。 随着应用问题的复杂化，导致了信息量的激增和信息范围的扩大，许多系统程序和应用规模大，结构也变得相当复杂。 因此，必须分析应该处理的问题中的对象特征和各对象的关系。 这就是数据结构这一课中应该研究的问题。 制定解决实际问题的程序的一般过程：如何以数据形式解释问题？ 从问题中抽象出适当的数学模型。如何将数据存储在与问题相关的数据量大小和数据之间的关系计算机上，以表达数据之间的关系？ 处理问题需要什么样的计算？ 制作的程序的性能好吗？ 上述问题基本上通过数据结构课程来回答。 计算机解决问题的一般程序、1.1数据结构及其概念、算法和数据结构是计算机科学中的

3、综合专业基础课。 是介于数学、计算机硬件、计算机软件三者之间的核心课程，不仅是一般程序设计的基础，还设计和实现了编译器、操作系统、数据库系统、其他系统程序和大型应用程序另外，1.1.1数据结构的例子，例1 :假定在电话号码查询系统中提供有记录n人的名字和与其对应的电话号码的电话号码簿，如(a1，b1)、(a2，b2)、(an，bn )那样配置。 在此，ai、bi (I=1，2n )分别表示某人的名字和电话号码。 这个问题是典型的代表问题。 如表1-1所示，数据和数据是单纯的一对一线性关系。 表1-1线性表结构，例2 :在盘目录文件系统的目录下有很多子目录和文件，每个子目录可以包含多个子目录和文

4、件，但每个子目录只有一个父目录图1-1树结构，例子3 :交通网络图可以从一个位置到另一个位置具有多个路径。 本问题是典型的网格结构问题，数据与数据的对多关系是非线性关系结构。 数据(Data ) :客观事物的符号表示。 在计算机科学中，是输入计算机并由计算机程序处理的所有符号的总称。 数据元素(Data Element ) :数据的基本单位，程序总是将它作为一个整体来处理。 数据元素可以由几个数据项组成。 数据项是数据不可分割的最小单位。 数据项目是关于客观事物某一方面特性的数据记述。 数据对象(Data Object ) :具有相同性质的数据元素的集合，是数据的子集。 字符集C=A、b和c。

5、 1.1.2基本概念和术语、数据结构(Data Structure ) :相互具有一定联系(关系)的数据元素的集合。 要素间的相互关系(关系)称为逻辑结构。 数据元素之间的逻辑结构有四种基本类型，如图1-3所示。 集合：结构中的数据元素除了“属于同一集合”之外没有其他关系。线性结构：结构内的数据元素之间有一对一的关系。 树结构：结构内的数据元素之间有一对多的关系。 图表结构或网格结构：结构内的数据元素之间有多对多的关系。 数据结构的形式定义是两组，数据结构=(d，s )。 其中d是数据元素的有限集合，s是d上的关系的有限集合。 例2 :数据逻辑结构B=(K，R) K=k1，k2，k9 R=，k

6、=k 1，k2，k9 R=， 画出该逻辑结构的图，它们是起点，它们是终点，1.1.3数据结构的形式定义，图1-3的基本结构图，1.1.4数据结构的存储方式， 数据元素之间的关系可以是表示元素之间的某种意义的自然关系，并且可以是人为地定义的关系，以方便处理问题，这样的自然或人为地定义的“关系”被称为数据元素之间的逻辑关系，并且相应的结构被称为逻辑结构。 另外，数据结构对计算机存储器的存储包括数据要素的存储与要素之间的关系的表现。 元素之间的关系在计算机上有两种不同的表达方式。 顺序表示和非顺序表示。 因此，可以获得两种不同的存储结构：顺序存储结构和链存储结构。 顺序存储结构：用数据元素在存储器中

7、的相对位置来表示数据元素之间的逻辑结构(关系)。 链式存储结构：为每个数据元素添加一个存储不同元素地址的指针，以表示数据元素之间的逻辑结构(关系)。 例如，数据集a=3.0、2.3、5.0、-8.5、11.0，有两种不同的存储结构。 顺序结构：存储数据元素的地址是连续的。链结构：不要求存储数据元素的地址是连续的。 数据的逻辑结构和物理结构是不可分割的两个方面，其中一种算法的设计取决于所选的逻辑结构，算法的实现取决于所使用的存储结构。 在c语言中，用一维排列表现顺序记忆结构的链型记忆结构用结构体类型来表示。 数据结构的三个组成部分：逻辑结构：数据元素之间的逻辑关系的描述D_S=(D，s )存储结

8、构：数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。 数据操作：对数据进行的运算。 本课程中说明的3个逻辑结构及其采用的存储结构如图14所示。 数据类型(datatype ) :一组值和在该值集合中定义的一组操作的总称。 数据类型是与数据结构密切相关的概念。 c语言中的数据类型是基本型和结构型。 数据结构与数据类型不同，与数据对象不同，它不仅描述数据类型的数据对象，还描述数据对象的元素之间的相互关系。 1.1.5数据类型、数据结构的主要运算修改了向数据结构插入数据元素的访问数据结构(的数据元素)，该数据结构从包括数据结构的建立的数据结构中删除数据元素1.1.6数据结构运

9、算，抽象数据类型(Abstract Data Type，ADT )是指数学模型和在该模型中定义的一组操作。 ADT的定义，无论在计算机中的表示和实现，都只是一组逻辑特性的描述。 因此，无论ADT的内部结构如何变化，只要其数学特性不变化，就不会影响其外部使用。 ADT的形式化定义是ADT=(D、s、p )。 其中d是数据对象，s是d上的关系集，p是针对d的基本操作集。 1.2抽象数据类型、ADT的一般定义形式是用伪代码记述ADT数据对象：数据关系：基本操作： ADT中数据对象和数据关系的定义。基本操作的定义为： () 初始条件：操作结果：初始条件：描述在执行操作之前数据结构和参数应满足的条件，如

10、果不满足，操作将失败，并返回相应的错误消息。 操作结果：说明操作成功完成后，数据结构的变化情况和应返回的结果。 另外，1.3.1算法(Algorithm ) :在特定问题解决方法(步骤)的描述中，指令的有限序列，其中每个指令代表一个或多个操作。 算法具有以下五个特性。 一种算法总是在执行贫困步骤后结束，所有的步骤都必须在贫困时间内完成。 确定性：算法的每条指令都需要准确的意义。 不存在二义性。 算法只有一个入口和出口。 可行性：算法是可行的。 也就是说，用算法所描述的操作可以通过执行已经安装的基本运算有限次来实现。 1.3算法初步分析，输入：一个算法有0个以上的输入，这些输入是从特定对象的集合

11、中获得的。 输出：算法有一个或多个输出，这些输出是与输入有特定关系的量。 一种算法可以用几种方式来描述。 主要是用自然语言记述。用形式语言记述用计算机编程语言记述。 算法和程序是两个不同的概念。 计算机程序是使用算法中的编程语言的具体的实现. 并非所有的计算机程序都是该算法的必要性。 在本门课的学习、作业练习、登机实践等过程中，算法都是用c语言记述的。 在网上实践时，为了检查算法是否正确，必须编写完整的c语言程序。 评价好的算法有几个标准正确性，必须满足具体问题的需要。的. 可读性(Readability ) :算法必须容易阅读和交流。 可读性好的算法有助于理解和修改算法。 鲁棒性(Robus

12、tness ) :算法需要容错。 如果输入了不正确的数据或错误的数据，算法必须做出适当的反应或处理，以免产生不可理解的输出结果。 通用性(Generality ) :算法应该具有普遍性，即算法的处理结果对于一般的数据集合是成立的。 另外，对1.3.2算法设计的请求是通过在计算机上执行基于所述算法创建的程序的时间来测量该算法的执行时间。 其方法通常是事后统计：在计算机内部进行执行时间和实际占有空间的统计。 问题：首先要根据算法编制的程序，依赖于硬件和软件的环境，容易隐藏算法本身的优劣，没有实际价值。 先验分析：求出该算法的时间边界函数。 1.3.3算法效率的测量，效率和存储需求：效率是算法运行的

13、时间，存储要求是算法运行所需的最大存储容量。 一般来说，这两者关系到问题的规模。 与此相关的要素是，根据算法选择哪个策略。问题的规模编程语言编译器生成的机器代码的质量机器执行指令的速度除了硬件和软件等相关部门的要素以外，特定的算法“执行工作量”的大小是问题的另外，在算法解析应用例、算法中反复执行基本操作的次数是有问题规模n的函数，其时间尺度记为T(n)=O(f(n ) )，被称为算法的渐近时间复杂度(Asymptotic Time complexity )，简称为时间复杂度通常，用最深的循环内的语句中的原始操作的执行频率(反复执行的次数)来表示。 “o”的定义：如果f(n )是正整数n的函数，

14、则O(f(n ) )表示M0，n0时| f(n) | M | f(n0) |。表示时间复杂度的次数为O(1) :常数时间次数O (n ) :线性时间次数O (n ) :对数时间次数O(nn ) :线性对数时间次数O (nk): k2，k次乘法时间次数例的两个n次平方矩阵的乘法for(i=1，i=n； i) for(j=1； j=n； j) cij=0； for(k=1； k=n； k) cij=aik*bkj； 由于是三重循环，所以各循环为1至n，总次数为nnn=n3的时间复杂度为T(n)=O(n3 )的例子x的s=0； 把x的自增看作基本操作，句子的频度，即时间复杂度为(1)。 另外，s=0也视为基本操作，句子的频度，其时间复杂度还是(1)，即常数阶段。 例for(i=1； i=n； i) x； s=x； 句子的频率为： 2n，其时间复杂度为： O(n )，是线性次数。 例for(i=1； i=n； i) for(j=1； j=n； j) x； s=x； 句子的频率为：2n2，其时间复杂度为： O(n2 )，为平方层。 定理：如果a(n)=amnm-1nm-1a1na0是m次多项式，则A(n)=O(n m