数据结构严蔚敏PPT(完整版).ppt

1、算法与数据结构，教材：数据结构(C语言版本)。严为民，吴伟民编辑。清华大学出版社。参考文献：1数据结构。张选平，雷主编，审核。机械工业出版社。2数据结构和算法分析。作者：克利福德谢弗，由张明和刘小丹翻译。电子工业出版社。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所示，数据有一对多的关系，这是一个典型的具有非线性关系结构的树形结构。图1-1树形结构，示例3:交通网络图可以有从一个地方到另一个地方的多条路径。这是一个典型的网络结构问题，数据和数据之间的关系是多对多的，是一种非线性关系结构。数据：它是客观事物的象征性表现。在计算机科学中，它指的是可以输入计算机并由计算机程序处理的所有符号。数据元素：它是数据的基本单位，通常在程序中作为一个整体来考虑和处理。一个数据元素可以由几个数据项组成。数据项是不可分割的最小数据单元。数据项是对客观事物特征的数据描述。数据对象：它是具有相同属性的数据元素的集合和数据的子集。例如字符集C=A，B，C，1.1.2基本概

5、念和术语，数据结构：它是指相互之间有一定联系(关系)的数据元素的集合。元素之间的关系称为逻辑结构。数据元素之间有四种基本类型的逻辑结构，如图1-3所示。集合：结构中的数据元素除了“属于同一个集合”之外，没有其他关系。线性结构：结构中的数据元素之间存在一对一的关系。树形结构：结构中的数据元素之间有一对多的关系。图结构或网络结构：结构中的数据元素之间存在多对多的关系。数据结构的形式定义是一个二进制组：数据结构=(D，s)，其中：D是数据元素的有限集合，s是D上关系的有限集合.例2:让数据逻辑结构B=(K，r) k=k1，k2，k9r=，画出这个逻辑结构的图，并确定哪些是起点，哪些是终点，1.1.3

6、数据结构的形式定义，图1-3四个基本结构图，1.1.1它也可以是一个人为定义的关系，以便于处理问题。这种自然或人为定义的“关系”称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。计算机内存中数据结构的存储包括数据元素的存储和元素之间关系的表示。在计算机中有两种不同的方法来表达元素之间的关系：顺序表示法和非顺序表示法。因此，获得了两种不同的存储结构：顺序存储结构和链式存储结构。顺序存储结构：数据元素之间的逻辑结构(关系)由数据元素在内存中的相对位置来表示。链式存储结构：在每个数据元素中添加一个指针来存储另一个元素的地址，并使用这个指针来表示数据元素之间的逻辑结构(关系)。示例：有两种不同的存储

7、结构，数据集a=3.0、2.3、5.0、-8.5和11.0。序列结构：存储数据元素的地址是连续的；链式结构：对于存储数据元素的地址是否连续没有要求。数据的逻辑结构和物理结构是不可分割的两个方面。算法的设计取决于所选择的逻辑结构，而算法的实现取决于所采用的存储结构。在c语言中，顺序存储结构用一维数组表示；用结构类型表示链式存储结构。数据结构有三个组成部分：逻辑结构：数据元素之间逻辑关系的描述存储结构：数据元素在计算机中的存储和逻辑关系的表达称为数据的存储结构或物理结构。数据操作：对数据执行的操作。本课程将讨论的三种逻辑结构及其存储结构如图1-4所示。数据类型：指一组值和在该组值上定义的一组操作。

8、数据类型是一个与数据结构密切相关的概念。在C语言中，数据类型有：基本类型和构造类型。数据结构不同于数据类型和数据对象。它不仅描述了数据类型的数据对象，还描述了数据对象元素之间的关系。1.1.5数据类型，数据结构的主要操作包括：创建数据结构；破坏数据结构；从数据结构中删除数据元素；将数据元素插入到数据结构中；访问数据结构；修改数据结构(其中的数据元素)；对数据结构进行排序；数据结构是搜索。1.1.6数据结构操作，抽象数据类型(ADT):指数学模型和在模型上定义的一组操作。ADT的定义只是一组逻辑特征的描述，与它在计算机中的表示和实现无关。因此，无论ADT的内部结构如何变化，只要它的数学特性保持不

9、变，它就不会影响它的外部使用。ADT的形式定义是三重的：ADT=(D，s，p)，其中D是数据对象，s是D上的关系集，p是d. 1.2上的基本操作集。抽象数据类型，ADT的一般定义形式是：ADT数据对象：数据关系：基本操作：ADT，其中数据对象和数据关系的定义用伪代码描述。基本运算的定义是：(1)初始条件：运算结果：初始条件：描述数据结构和参数在执行运算前应该满足的条件；如果不是，操作将失败，并返回相应的错误消息。操作结果：描述数据结构的变化以及操作正常完成后返回的结果。1.3.1算法：它是对解决特定问题的方法(步骤)的描述，它是一个有限的指令序列，其中每个指令代表一个或多个操作。该算法具有以下

10、五个特点：有限性：算法必须总是在执行完有限性步骤后完成，并且每一步都是在有限时间内完成的。确定性：算法中的每条指令都必须有确切的含义。没有含糊之处。该算法只有一个入口和一个出口。可行性：一个算法是可行的。也就是说，算法描述的操作可以通过执行已经实现了有限次数的基本操作来实现。1.3算法分析初步，输入：一个算法有零个或多个输入，这些输入取自特定的对象集。输出：一个算法有一个或多个输出，这些输出是与输入有特定关系的量。一个算法可以用很多方式来描述，包括：用自然语言来描述它；用正式语言来描述；用计算机编程语言来描述。算法和程序是两个不同的概念。计算机程序是使用某种编程语言的算法的具体实现。算法必须是

11、可终止的，这意味着不是所有的计算机程序都是算法。在本课程的学习、作业练习和计算机实践中，算法是用C语言描述的。在实践中，为了检查算法是否正确，应该编写一个完整的C语言程序。要评价一个好的算法，有以下标准：算法应该满足特定问题的需要。可读性：该算法应该便于人们阅读和交流。可读算法有助于理解和修改算法。健壮性：算法应该有容错处理。当输入非法或错误的数据时，算法应该能够做出适当的反应或处理，而不会产生无法解释的输出结果。通用性：算法应该是通用的，即算法的处理结果对通用数据集有效。1.3.2算法设计要求，算法执行时间应由根据运行在计算机上的算法编译的程序所消耗的时间来衡量。通常有两种方法：事后统计：统

12、计计算机的执行时间和实际占用空间。问题：你必须首先运行根据算法编译的程序；根据软硬件环境，很容易掩盖算法本身的优缺点；没有真正的价值。预分析：找到算法的时间限制函数。1.3.3算法效率、效率和存储要求的度量：效率是指算法的执行时间；存储需求是指算法执行过程中所需的最大存储空间。一般来说，两者都与问题的规模有关。相关因素有：根据算法选择哪种策略；问题的规模；编程语言；编译器生成的机器代码的质量；机器执行指令的速度；除了软件和硬件等相关部门的因素外，可以认为特定算法的“运行工作量”的大小仅取决于问题的规模(通常用N表示)，或者是问题规模的函数。以算法分析和应用为例，算法中基本运算的重复执行次数是问

13、题规模n的函数，其时间度量记录为T(n)=O(f(n)，称为算法的渐近时间复杂度。通常，它通常由最深循环语句中原始操作的执行频率(重复执行次数)来表示。“O”的定义：如果f(n)是正整数n的函数，那么O(f(n)代表M0，因此当n为n0时，| f(n) | M | f(n0) |。时间复杂度的顺序如下：O(1):常数时间顺序O (n):线性时间顺序O(n):对数时间顺序O(nn):线性对数时间顺序O (nk): k2，k次幂时间顺序，例如，两个N阶方阵的乘法(I=1，I=N；I)对于(j=1；j=n；j)cij=0；对于(k=1；k=n；k)cij=aik * bkj；因为它是一个三重循环，每个循环是从1到n，总次数是nnn=n3，时间复杂度是T(n)=O(n3)x；s=0；如果把x自增看作一个基本运算，则语句的频率为，即时间复杂度为(1)。如果s=0也被认为是一个基本运算，则语句频率为，其时间复杂度仍为(1)，即常数阶。例如(I=1；I=n；I)x；s=x；语句频率为2n，时间复杂度为O(n)，为线性顺序。例如(I=1；I=n；I)对于(j=1；j=n；j)x；s=x；语句的频率为2n2，时间复杂度为O(n2)，为平方阶。定理：如果A(n)=a m n m a m-1 n m-1 a1n a0是m次多项式，那么A(n)=O