搜索
目录第一章数据结构与算法程序设计就是使用计算机解决现实世界中的实际问题。对于给定的一个实际问题，在进行程序设计时，首先要把实际问题中用到的信息抽象为能够用计算机表示的数据；第二要把抽象出来的这些数据建立一个数据模型，这个数据模型也称为逻辑结构，即建立数据的逻辑结构；第三要把逻辑结构中的数据及数据之间的关系存放到计算机中，即建立数据的存储结构；最后在所建立的存储结构上实现对数据元素的各种操作，即算法的实现。本章就是要使大家了解计算机中的数据表示，理解数据元素、逻辑结构、存储结构和算法的有关概念；掌握基本逻辑结构和常用的存储方法，能够选择合适的数据的逻辑结构和存储结构；掌握算法及算法的五个重要特性，能够对算法进行时间复杂度分析，从而选择一个好的算法，为后面的学习打下良好的基础。1.1数据结构的概念1、数据（Data）数据是信息的载体。它能够被计算机识别、存储和加工处理，是计算机程序加工的“原料”。随着计算机应用领域的扩大，数据的范畴包括：整数、实数、字符串、图像和声音等。2、数据元素（DataElement）数据元素是数据的基本单位。数据元素也称元素、结点、顶点、记录。例如：学生的信息，包括：学号、姓名、成绩。一个学生的信息就是一个数据元素。3、数据项（Dataitem）数据项是具有独立含义的最小标识单位。一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。4、数据结构（DataStructure）数据结构指的是数据之间的相互关系，即数据的组织形式。数据结构一般包括以下三方面内容：①数据的逻辑结构：数据元素之间的逻辑关系。例如：某个班学生成绩表，包括：学号、姓名和各科成绩，每一个学生的信息都是一个数据元素。数据元素之间有这样的逻辑关系：在一个数据元素的前面最多有一个与其相邻的数据元素（称为直接前驱），在一个数据元素的后面也最数据结构2多有一个与其相邻的数据元素（称为直接后继）。数据元素之间的这种关系构成了学生成绩表的逻辑结构。数据（逻辑）结构的形式定义：数据结构是一个二元组（D，R），其中D是数据元素的有限集，R是D上关系的有限集。②数据的存储结构：数据元素及数据元素之间的关系在计算机存储器内的表示。③数据的运算：即对数据施加的操作。数据的运算定义在数据的逻辑结构上，只有确定了存储结构，才能具体实现这些运算。数据结构就是研究数据的逻辑结构和存储结构，以及它们之间的相互关系和所定义的算法如何在计算机上实现，它包括数据的逻辑结构、存储结构和数据的运算三个方面。1.2数据的逻辑结构与存储结构1、数据的逻辑结构①线性结构：有且仅有一个开始结点和一个终端结点，且所有结点都最多只有一个直接前驱和一个直接后继。②非线性结构：一个结点可能有多个直接前驱和多个直接后继。2、基本逻辑结构①集合结构：数据元素的有限集合。数据元素之间除了“属于同一个集合”的关系之外没有其他关系。②线性结构：数据元素的有序集合。数据元素之间形成一对一的关系。③树型结构：树是层次数据结构，树中数据元素之间存在一对多的关系。④图状结构：图中数据元素之间的关系是多对多的。如果用小圆圈表示结点，用连线表示结点之间的逻辑（邻接）关系，四种基本逻辑结构如图1.1所示：集合结构线性结构第二章线性表3树型结构网状结构3、存储结构存储结构可用以下四种存储方法得到：①顺序存储方法：把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。顺序存储结构通常是借助于程序语言的数组来描述的。②链式存储方法：该方法不要求逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑关系是由附加的指针字段来表示的。由此得到的存储表示称为链式存储结构。链式存储结构通常是借助于程序语言的指针来描述的。如下图1.2所示：③索引存储方法：除建立结点信息外，还要建立附加的索引表来标识结点的地址。④散列存储方法：根据结点的关键字直接计算出该结点的存储地址。1.3算法及算法分析一、算法及其特性1、算法：是对特定问题求解步骤的一种描述，是指令的有限序列。一个算法是一系列将输入转换为输出的计算步骤。2、算法的重要特性①输入：一个算法应该有零个或多个输入。②有穷性：一个算法必须在执行有穷步骤之后正常结束，而不能形成无穷循环。③确定性：算法中的每一条指令必须有确切的含义，不能产生多义性。300010301103031032510318……89.54000……90.53050……833020……78NULLhead3000400030503020图1.2链式存储图1.1四种基本逻辑结构数据结构4④可行性：算法中的每一条指令必须是切实可执行的，即原则上可以通过已经实现的基本运算执行有限次来实现。⑤输出：一个算法应该有一个或多个输出，这些输出是同输入有某个特定关系的量。3、算法描述：算法描述的方法主要有以下4种：①框图算法描述：使用流程图或N-S图来描述算法；②非形式算法描述：使用自然语言（中文或英文）和程序设计语言中的语句来描述算法。这类描述方法自然、简洁，但缺乏严谨性和结构性。③类高级语言算法描述：使用类C或C++的所谓伪语言来描述算法。这种算法不能直接在计算机上运行，但专业设计人员经常使用它来描述算法，它具有容易编写、阅读和格式统一的特点。④高级语言算法描述：使用高级语言来描述算法。这是可以在计算机上运行并获得结果的算法描述。本课程将采用C语言进行算法描述。4、算法与程序的关系算法和程序都是用来表达解决问题的逻辑步骤；算法是对解决问题的方法的具体描述，程序是算法在计算机中的具体实现；程序是算法，但算法不一定是程序。二、算法分析1、算法设计的要求在算法设计中，对同一个问题可以设计出求解它的不同的算法，如何评价这些算法的优劣？从而为算法设计和选择提供可靠的依据。通常从以下五个方面评价算法的质量：①正确性：算法应能正确地实现预定的功能和处理要求。②易读性：算法应易于阅读和理解，便于调试、修改和扩充。③健壮性：正确的输入能得到正确的输出。当遇到非法输入时应能作适当的反应或处理，而不会产生不需要或不正确的结果。④高效性：解决同一问题的执行时间越短，算法的时间效率就越高。⑤低存储量：解决同一问题的占用存储空间越少，算法的空间效率就越高。2、影响算法运行时间的因素①计算机硬件；②实现算法的语言；③编译生成的目标代码的质量；④问题的规模。第二章线性表5在各种因素都不能确定的情况下，很难比较出算法的执行时间，即使用执行算法的绝对时间来衡量算法的效率是不合适的。为此，可以将与计算机软硬件相关的因素确定下来，这样，一个特定算法的运行工作量就只依赖于问题的规模，即算法的运行时间是问题规模n的函数T(n)。3、算法的时间效率分析一个算法所耗费的时间，应该是该算法中每条语句的执行时间之和，而每条语句的执行时间是该语句的执行次数（也称为频度）与该语句执行一次所需时间的乘积。但当算法转换为程序之后，每条语句执行一次所需的时间取决于机器的指令性能、速度以及编译所产生的代码质量，这是很难确定的。我们假设每条语句执行一次所需的时间均是单位时间，这样，一个算法的时间耗费，就是该算法中所有语句的频度之和。于是，我们就可以独立于机器的软、硬件系统来分析算法的时间耗费。4、算法的时间复杂度①定义：设问题的规模为n，把一个算法的时间耗费T(n)称为该算法的时间复杂度，它是问题规模为n的函数。②算法的渐进时间复杂度设T(n)为一个算法的时间复杂度，如果当n趋向无穷大时T(n)与函数f(n)的比值的极限是一个非零常数M，即MnfnTn)()(lim，记作T(n)=O(f(n))，则称O(f(n))为算法的渐进时间复杂度，简称时间复杂度，也称T(n)与f(n)的数量级相同，通常，f(n)应该是算法中频度最大的语句的频度。③常用的算法的时间复杂度的顺序O(1)O(lgn)O(n)O(n·lgn)O(n2)O(n3)…O(2n)④算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。例如：在数组A[0...n-1]中查找给定值K的算法如下：(1)i=n-1;(2)while(i=0&&(A[i]!=k))(3)i--;(4)returni;此算法中的语句(3)的频度不仅与问题规模n有关，还与输入实例中A的各元素取值及K的取值有关：若A中没有与K相等的元素，则语句(3)的频度f(n)=n；若A的最后一个元素等于K,则语句(3)的频度f(n)是常数0。⑤最坏时间复杂度和平均时间复杂度数据结构6最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何情况下更长。平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。例1求下列交换两个变量i和j的值的算法的时间复杂度。(1)i=10;(2)j=20;(3)t=i;(4)i=j;(5)j=t;解：各行语句的执行次数均为1，所以该算法的时间耗费T(n)=1+1+1+1+1=5，该算法的时间耗费T(n)与问题的规模n无关，因此，该算法的时间复杂度T(n)=O(1)。例2求两个n阶方阵的乘积C=A×B，其算法如下，计算该算法的时间耗费。程序段：(1)for(i=0;in;i++)(2)for(j=0;jn;j++)(3){c[i][j]=0;(4)for(k=0;kn;k++)(5)c[i][j]+=a[i][k]*b[k][j];}解：解法1计算程序段中的每一行的执行次数。第(1)行for(i=0;in;i++)中只考虑循环条件表达式in的执行次数（忽略初始化表达式i=0和修正表达式i++的执行次数，下同），表达式in共执行n+1次（i为0到n-1时该表达式非零，共n次，i为n时该表达式为零，共1次，合计执行n+1次），所以，第(1)行共执行n+1次；第(2)行for(j=0;jn;j++)，在第(1)行for(i=0;in;i++)中的表达式in非零时（共n次）都要执行一遍，而每一遍同样要执行n+1次，所以，第(2)行共执行n（n+1）次；第(3)行c[i][j]=0;在表达式in和jn均非零时执行，共执行n2次；第二章线性表7第(4)行for(k=0;kn;k++)在表达式in和jn均非零时执行一遍，而每一遍同样要执行n+1次，所以，第(4)行共执行n2（n+1）次；第(5)行c[i][j]+=a[i][k]*b[k][j];在表达式in、jn和kn均非零时执行，共执行n3次；因此，各行执行次数分别为：n+1，n（n+1），n2，n2（n+1），n3。如果用T(n)表示该算法的时间耗费，则T(n)=n+1+n（n+1）+n2+n2（n+1）+n3=2n3+3n2+2n+1由此可知，该算法的时间耗费T(n)是矩阵阶数n的函数，T(n)=O(n3)。解法2只计算执行频度最高的行。显然，在该程序段中，执行频度最高的行为c[i][j]+=a[i][k]*b[k][j];在表达式in、jn和kn均非零时执行，而表达式in、jn和kn均有n次非零，所以，该行共执行n3次。因此，该算法的时间耗费T(n)是矩阵阶数n的函数，T(n)=O(n3)。例3求下列算法的时间复杂度。(1)x=1;(2)for(i=1;i=n;i++)(3)for(j=1;j=i;j++)(4)for(k=1;k=j;k++)(5)x++;分析：该程序段中频度最大的语句是(5)，内循环语句(4)和(3)虽然与n无关，但外循环(2)与n有关。所以，可以从内层循环向外层分析语句(5)的执行次数。解：循环结构(4)的循环体(5)执行了j次，循环结构(3)的循环体执行了i次，(2)的循环体执行了n次，即语句(5)的执行次数为：niiijiij1n112/)1(2)/61)(nn(2/)2/)1(6/)12)(1((2/)(