数据结构与算法复习与习题解析(第1-5讲）第一讲绪论了解数据结构有关概念的含义，特别是数据的逻辑结构和存储结构之间的关系；（重点）熟悉类C语言的书写规范；了解计算算法时间复杂度的方法。（难点）25/12/242数据结构的定义按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。基本概念和术语【数据】是对信息的一种符号表示。是可以输入计算机中，能被计算机识别处理和输出的一切符号集合。【数据元素】是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。也称为记录。【数据项】一个数据元素可由若干个数据项组成。是数据不可分割的最小单位。【数据对象】是性质相同的数据元素的集合。是数据的一个子集。25/12/244【数据结构】相互之间存在一种或多种特定关系的数据元素的集合计算机如何解决问题25/12/245问题机外表示处理要求逻辑结构基本运算数学模型存储结构编程实现实现建模求精研究数据结构是为了帮计算机解决问题！数据结构的研究内容25/12/246【数据结构的三个方面研究内容】具体来说，数据结构包含三个方面的内容，即数据的逻辑结构，数据的存储结构和对数据所施加的运算（操作）。数据的逻辑结构（面向人类）数据的存储结构（面向计算机）数据的运算（操作）：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队列树形结构图形结构散列存储索引存储串及数组四种基本逻辑结构25/12/247【集合】——数据元素间除了“同属于一个集合”外，无其他关系。【线性结构】——1对1的关系比如线性表、栈、队列。【树形结构】——1对多的关系比如树。【图形结构】——多对多的关系比如图。算法与数据结构算法与数据结构关系密切选择的数据结构是否恰当直接影响算法的效率；而数据结构的优劣由算法的执行来体现。“算法+数据结构=程序”算法!=程序算法是供人阅读的，程序是让机器执行的算法用计算机语言实现时就是程序程序不具有算法的有穷性算法的概念算法是解决某个特定问题的求解步骤的描述。算法在计算机中表现为指令的有限序列，每条指令表示一个或多个操作。计算机对数据的操作可以分为数值性和非数值性两种类型。在数值性操作中主要进行的是算术运算；而在非数值性操作中主要进行的是检索、排序、插入、删除等等。程序不等于算法：计算机程序是算法的具体实现。25/12/249（1）有穷性：一个算法必须在执行有穷步之后结束。（2）确定性：算法中的每一步，必须有确切的含义，在他人理解时不会产生二义性。（3）可行性：算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现。（4）输入：一个算法应该有零个或多个输入。（5）输出：一个算法应该有一个或多个输出。这里所说的输出是指与输入有某种特定关系的量。算法的性质算法设计的要求正确性（四个境界）没有语法错误对于合法的输入数据能够产生满足要求的输出对于非法的输入数据能够得出满足规格说明的结果对于任何测试数据都有满足要求的输出结果可读性：便于阅读、理解和交流健壮性：不合法数据也能合理处理时间效率高和存储量低25/12/2411算法效率的度量方法事后统计方法通过设计好的测试程序和数据，利用计算机测量其运行时间。缺陷：需要先编写程序；和计算机软硬件相关；和测试数据相关。事前分析估算方法（我们的选择）依据统计方法对算法进行估算。m=f(n)，m是语句总的执行次数，n是输入的规模。和问题输入规模相关，独立于程序设计语言和计算机软硬件25/12/2412算法时间复杂度25/12/2413在进行算法分析时，语句的总执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，用“大O记法”记作：T(n)=O(f(n))。由此得到的T(n)的数量级叫“大O阶”。它表示随问题规模n的增大，算法执行时间增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。其中f(n)是问题规模n的某个函数。一般...
