第1章绪论主要内容1.1数据结构的基本概念1.2数据结构的内容1.3算法设计1.4算法描述工具1.5算法的性能评价1.6数据结构与C语言表示1.1数据结构的基本概念本节介绍以下几个基本概念和术语1.数据2.数据元素和数据项3.数据结构4.数据类型5.抽象数据类型1.数据数据是信息的载体，它是能够被计算机识别、存储和加工处理。信息计算机数据数据的主要特征计算机能够识别、能够处理、能够存储的信息。计算机化的信息。数据的含义随着计算机的发展而变化。数据处理的实例例1：要判断某一点是否在三角形之内例2：判断下面这个人是否是某个电影明星例3：判断二条直线是否相交如何要计算机处理这些问题？如何把这些问题表示成计算机能处理的数据呢？数据例子表示物体的位置，我们用两个整数表示。表示物体飞行路径（假设是直线的）则用两个点来描述。假如描述物体运动过程，则要坐标，时间来描述。如何表示声音？结论数据是表示客观事物的数值、文字能够被计算机识别的各种符号集合。说明数据随计算机的发展而变化。最早的计算机：只能处理二进制的数据，需要打孔(punch)。后来可以是十进制数据，再后来可以是英文字符，声音，图像。2.数据元素数据元素（DataElement）数据元素是数据基本单位，在处理过程一般表示其整体性和完整性。数据元素又称为元素，顶点或结点。又称记录(Record)。数据项数据项：是具有独立含义的最小标识。又称为数据域。数据项与数据元素的关系数据元素是由数据项组成的。举例数据元素：一行就是一个数据元素，张三，男，78等是一个数据项。学号姓名性别语文数学物理总分名次201张三男788954202李四女987867203王五男899571数据对象数据对象是性质相同的数据元素的集合，是数据的一个子集。如整数数据对象。某个班级的45位同学的数据（姓名，性别，地址，联系电话，家长姓名，照片）。3.数据结构(DataStructure)数据结构是指数据相互之间存在一种或多种特定关系的数据元素集合。4.数据类型所谓数据类型是一个值的集合以及定义在这些值上的操作的总称。一般高级语言有基本的数据类型，也有根据用户需要创建的类型，即结构体。数据结构课程里经常用到结构体。数据类型原子类型：不可分割，如整型（int,char,float,double)结构类型：其可以分割的，如数组，结构体等(struct,union)。通常数据类型可以看成是程序设计语言中已实现的数据结构。5.抽象数据类型ADTADT包括定义和实现两个方面。定义独立于实现。定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。只从问题本身抽象出来。ADT定义的格式ADT数据对象:结构关系:基本操作:ADTADT说明数据对象定义是用已定义的数据类型定义新的数据对象。数据对象和结构关系采用数学符号和自然语言描述。基本操作定义包括操作名，参数表、初始条件和操作结果四部分内容的定义和描述。其格式是操作名（参数表）操作前提：操作前提描述操作结果：操作结果描述例1-2给出简化线性表的ADT类型定义ADTLinear_List数据对象：所有属于同一类型的数据对象，i=1,2n,n=0结构关系：所有数据元素ai，存在次序关系。a1无前趋，an无后继基本操作：InitList(L):初始化空表续ListLength(L):求线性表的长度GetData(L,i)：取线性表的第i个元素InsList(L,i,b):在L线性表中i位置插入元素b.DelList(L,i):删除L的第i个元素。通过以上描述可以知道，由于它是ADT（抽象），不限于某个特定类开，也不限于某特定的存储类型。用C语言实现ADT在用C语言实现ADT时，要考虑数据的存储类型。譬如前面的例子里，a可以是一个整数，或一个浮点数，或一个学生信息的数据元素。数据存储可以是数组，也可以是链表等，只要能反映它的逻辑结构关系就行。1.2数据结构的内容数据结构这个术语包含三方面的内容:1.逻辑结构2.存储结构3.算法设计1.逻辑结构数据元素之间的逻辑关系，也称数据的逻数据的逻辑结构辑结构（LogicalStructure）；数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。四种逻辑结构集合结构线性结构树形结构图状结构线性结构：线性表、栈，队、串，数组，广义表非线性结构：树和图2.存储结构数据元素及其关系在计算机存储器内的表示，称为数据的存储结构数据的存储结构（StorageStructure）；数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。一般只在高级语言的层次上讨论存储结构。3.数据的运算数据的运算数据的运算，即对数据施加的操作。数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。实例1逻辑结构有若干个人组成一个小团体，它们之间有的是认识，有的不认识。所以它们的关系可以用下面的图来表示。连线表示二人之间是认识的。这个结构图反映对象之间的逻辑关系。FADBCE实例1存储结构为了表示上述图里的各人之间的相互关系，我们用一个二维数来表示它们ABCDEFABCDEF实例1运算或操作现在增加一个人G,G与A，C，D都认识，现在删除一个人如F。实例2某个班级成绩计算机处理一个班级有若干个同学，它们组成如下的表格。逻辑关系是指每个结点的前后关系。学号姓名性别语文数学物理总分名次201张三男788954202李四女987867203王五男899571实例2存储结构存储结构是指如何在计算机里存储上述班级的人员。一般采用数组或链表等。a1a2a3a4a5a6a7a8a1a1a1a1实例2运算或操作同学的增加，删除，移动，查找，修改等操作。结论用数据结构解决实际问题是，一般按下面顺序考虑三个问题：1.首先对问题的逻辑结构分析清楚2.接着考虑存储问题，一般采用结构体方式以数组或链表进行存储(这步相当于定义结构体）3.确定好数据存储结构后，就考虑运算操作的实现（这步相当于编写函数）三者之间的结构关系本书采用这种讨论方法逻辑关系存储结构操作运算（算法）程序员特点逻辑关系不依赖于存储结构和运算操作存储结构与逻辑关系有关与操作运算无关。操作运算与逻辑关系和存储结构都有关系。1.3算法设计算法定义算法的特性算法的定义数据的操作步骤是用算法来描述的。所以算法是数据结构中最重要的内容。什么是算法？本质上说，能够清楚描述操作步骤的都可以称算法。一个算法是将一系列输入转换为输出的计算步骤。所以算法的形式并不唯一，可以自然语言描述，也可以用类Pascal语言，本书采用类C语言算法的五个特性有穷性算法必须是经过有限的步骤操作完成。确定性算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。有任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。可行性可行性一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。输入输入要有多个或零个输入输出输出至少有一个或多个输出（注意！千万不要把这里输出与C语言的printf联系起来）算法的正确性若一个算法对于每个输入实例均能终止并给出正确的结果，则称该算法是正确的。正确的算法解决了给定的计算问题。一个不正确的算法是指对某些输入实例不终止，或者虽然终止但给出的结果不是所渴望得到的答案，一般只考虑正确的算法。不能终止，实际上就是死循环或死机。算法的评价算法的评价选用的算法首先应该是“正确”的。此外，主要考虑如下三点：a.执行算法所耗费的时间；b.时间复杂度c.执行算法所耗费的存储空间，其中主要考虑辅助存储空间；空间复杂度d.可读性健壮性(鲁棒,Robust)时间复杂度一个算法所耗费的时间是算法中每条语句的执行时间之和。而每条语句执行的时间是该语句的频度乘上该语句执行一次所需的时间。一条语句的执行时间与机器的指令性能，速度和编译器质量有关。但是为了简单化我们假设每条语句执行一次的时间为一个单位，则算法的执行是该算法所有语句的频度之和。所以在讨论算法的时间复杂度时，我们就简单计算语句的频度。矩阵的相乘二个矩阵的相乘例1.求两个n阶方阵的乘积C=AB#definen100/n可根据需要定义,这里假定为100voidMatrixMultiply(intAnn，intBnn，intCnn)/右边列为各语句的频度inti,j,k;for(i=0;in;i+)/nfor(j=0;jn;j+)/n2Cij=0;/n2 for(k=0;kn;k+)/n3Cij=Cij+Aik*Bkj;/n3例1的时间复杂度T(n)=2n3+3n2+2n+1当n趋向无限大时则上述式子与n3同阶的的，所以时间复杂度用下面来表示T(n)=O(n3)表示其时间复杂度是与输入规模n的三次方成正比。我们称O(n3)为渐近时间复杂度。简称为时间复杂度。例2级下面算法，计算其时间复杂度x=0;y=0;for(k=1;k=n;k+)x+;for(i=1;i=n;i+)for(j=1;j=n;j+)y+;例2计算下面算法的时间复杂度x=1;for(i=1;i=n;i+)for(j=1;j=i;j+)for（k=1;k=0&(Ai!=k)i-; returni;算法的时间复杂度要根据统计结果例如，把某个数按顺序插入到一个有充列表中。35121821324556最坏、最好和平均情况如果运气好，第一次比较就相等，则只有一次，运气不好比较n次，也找不到该值，所以有时在讨论算法的时间复杂度时就采用最好情况，最坏情况和平均情况。空间复杂度一个算法的空间复杂度(SpaceComplexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。算法的时间复杂度和空间复杂度合称为算法的复杂度。讨论前面的例子算法的空间复杂度算法描述风格一个算法用C语言的一个函数来表示。一个良好风格是指：模块化算法表示形式函数返回值函数名（形式参数）内部数据类型说明；语句;模块化包含文件语句宏定义语句自定义类型所有子函数的原型说明子函数1定义子函数2定义子函数n定义算法描述要点加上注释避免函数返回隐含类型说明预定义常量和类型#defineTRUE1#defineFALSE0#defineMAXSIZE100#defineSUCCESS1#defineERROR0使用有意义的函数名和变量名使用简化的输入/输出语句在函数中尽量少用输出语句。函数结果的带出方式全局变量数组名结构体指针方式