搜索
数据结构计算机科学与技术学院张宏第一章绪论1.1什么是数据结构1.2有关概念和术语1.3算法和算法分析1.3.1算法1.3.2算法设计的要求1.3.3算法效率的度量1.3.4算法的存储空间的需求第一章绪论计算机学科一直处于高速发展中,而且这种发展速度还会持续。计算机科学已经难以完全覆盖学科新的发展，因此扩展后的学科称为计算学科。包括：计算机科学、计算机工程、软件工程、信息系统关键问题：利用计算机进行信息表示和处理的涉及：•信息的表示•信息的处理而信息的表示和组织又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。1.1什么是数据结构众所周知，计算机的程序是对信息进行处理。在大多数情况下，这些信息并不是没有组织的，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。什么是数据结构呢？例子：例1、电话号码查询系统设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：(a1，b1)(a2，b2)…(an，bn)其中(ai，bi)(i=1，2…n)分别表示某人的名字和对应的电话号码。要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的信息。数据结构含义：就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。所有能被输入到计算机中，且能被计算机处理的符号的集合。数据:是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。1.2有关概念和术语是数据（集合）中的一个“个体”数据元素:是数据结构中讨论的基本单位数据结构主要指逻辑结构和物理结构数据之间的相互关系称为逻辑结构。通常分为四类基本结构：一、集合结构中的数据元素除了同属于一种类型外，别无其它关系。二、线性结构结构中的数据元素之间存在一对一的关系。三、树型结构结构中的数据元素之间存在一对多的关系。四、图状结构或网状结构结构中的数据元素之间存在多对多的关系。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。数据对象(DataObject)：是性质相同的数据元素的集合。是数据的一个子集。数据结构(DataStructure)：是相互之间存在一种或多种特定关系的数据元素的集合。数据在计算机中的表示称为数据的物理结构，又称为存储结构。数据对象可以是有限的，也可以是无限的。数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。数据类型：在一种程序设计语言中，变量所具有的数据种类。例1、在FORTRAN语言中，变量的数据类型有整型、实型、和复数型例2、在C++语言中数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定义数据对象：某种数据类型元素的集合。例3、整数的数据对象是{…-3，-2，-1，0，1，2，3，…}英文字符类型的数据对象是{A，B，C，D，E，F，…}1.3算法和算法分析1.3.1算法：是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有以下五个特性：（1）有穷性一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。（2）确定性算法中每一条指令必须有确切的含义。不存在二义性。（3）可行性一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。（4）输入一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。（5）输出一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。1.3.2算法设计的要求设计算法时，通常应考虑达到以下目标：1、正确性2、可读性3、健壮性4、高效率与低存储量需求1．正确性首先，算法应当满足以特定的“规格说明”方式给出的需求。其次，对算法是否“正确”的理解可以有以下四个层次：a．程序中不含语法错误；b．程序对于几组输入数据能够得出满足要求的结果；c．程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；通常以第c层意义的正确性作为衡量一个算法是否合格的标准。d．程序对于一切合法的输入数据都能得出满足要求的结果；2.可读性算法主要是为了人的阅读与交流，其次才是为计算机执行，因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。3．健壮性当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。4．高效率与低存储量需求通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关。1.3.3算法效率的度量通常有两种衡量算法效率的方法:事后统计法事前分析估算法缺点：1．必须执行程序2．其它因素掩盖算法本质和算法执行时间相关的因素：1．算法选用的策略2．问题的规模3．编写程序的语言4．编译程序产生的机器代码的质量5．计算机执行指令的速度一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作：T(n)=O(f(n))称T(n)为算法的(渐近)时间复杂度。如何估算算法的时间复杂度？算法=控制结构+原操作（固有数据类型的操作）算法的执行时间=原操作(i)的执行次数×原操作(i)的执行时间∑算法的执行时间与原操作执行次数之和成正比从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。voidmult(inta[],intb[],intc[]){for(i=1;i=n;++i)for(j=1;j=n;++j){c[i][j]=0;for(k=1;k=n;++k)c[i][j]+=a[i][k]*b[k][j];}//for}//mult基本操作:乘法操作时间复杂度:O(n3)例1例２{++x;s=0;}将x自增看成是基本操作，则语句频度为1，即时间复杂度为Ｏ(1)如果将s=0也看成是基本操作，则语句频度为1，其时间复杂度仍为Ｏ(1)，即常量阶。例３for(i=1;i=n;++i){++x;s+=x;}语句频度为：n其时间复杂度为：O(n)即时间复杂度为线性阶。i=0:赋值１次i=1:赋值2次i=2:赋值3次i=n-1:赋值n次……………..+1+2+3+…+n=(1+n)n/2=n2/2+n/2例４for(i=1;i=n;++i)for(j=1;j=n;++j){++x;s+=x;}语句频度为：n2其时间复杂度为：O(n2)即时间复杂度为平方阶。例５for(i=0;i=n-1;++i)for(j=0;j=i;++j)a[i][j]=0;定义：如果f(n)是正整数n的一个函数，若存在两个正常数c和n0，对于所有的n≥n0，有︱f(n)︳≤c｜g(n)|，则记作f(n)=O(g(n))例：f(x)=anxn+an-1xn-1+…..+a1x+a0，其中an不等0，n为正整数，则f(x)=O(xn)证明：|f(x)|=|anxn+an-1xn-1+…..+a1x+a0|≦|anxn|+|an-1xn-1|+…+|a1x|+|a0|=|an|*|xn|+|an-1|*|xn-1|+…+|a1|*|x1|+|a0|*|x0|当x1=n0，n为正整数时，xn+1xn，所以：|an|*|xn|+|an-1|*|xn-1|+…+|a1|*|x1|+|a0|*|x0|≤|an|*|xn|+|an-1|*|xn|+…+|a1|*|xn|+|a0|*|xn|=(|an|+|an-1|+…+|a1|+|a0|)|xn|=c|xn|其中：n0=1,c=|an|+|an-1|+…+|a1|+|a0|,g(n)=xn一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为O(n2)的算法则由一个二次多项式来限界。以下六种计算算法时间的多项式是最常用的。其关系为：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)指数时间的关系为：O(2n)O(n!)O(nn)当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。1.3.4算法的存储空间的需求算法的空间复杂度定义为:表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。S(n)=O(g(n))算法的存储量包括:1．输入数据所占空间2．程序本身所占空间3．辅助变量所占空间若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。若所需存储量依赖于特定的输入，则通常按最坏情况考虑。注意：时间与空间往往是对矛盾，要综合考虑。－最坏时间复杂性例6：有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。例如：voidbubble-sort(inta[]，intn)for(i=n-1;i0;i--)for(j=0;ji;++j)if(a[j]a[j+1])a[j]←→a[j+1];}时间：最好情况：0次最坏情况：每次都换，Ｏ(n2)空间：一个数据交换的辅助空间--算法原地工作。例7：递归程序的分析intfact(intn){if(n==1)return1;elsereturnn*fact(n-1);}f(n)=c+f(n-1)=c+(c+f(n-2))=2c+f(n-2)………=(n-1)c+f(1)=(n-1)c+c0课时安排与考核学分3:授课2.5(40课时)上机0.5(8+8课时)考核:平时成绩20%作业(课后与课堂)、实验课程考试80%作业：１.计算时间复杂度sum=1;for(i=0;sumn;i++)sum+=i;2.设给定若干n值，比较两函数n2和50nlog2n的增长趋势，并确定在什么范围内，函数n2的值大于50nlog2n的值。第二章线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.3.1线性链表2.3.2循环链表2.3.3双向链表2.4一元多项式的表示及相加2.1线性表的逻辑结构线性表：由n(n≥0)个数据元素(结点)a1，a2，…an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n0)记作：(a1，a2，…an)这里的数据元素ai(1≤i≤n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。例1、26个英文字母组成的字母表（A，B，C、…、Z）例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。（6，17，28，50，92，188）…….…….…….……..……..神经衰弱17男790634张立立健康21男790633刘建平一般20女790632陈红健康18男790631王小林健康情况年龄性别学号姓名例3、学生健康情况登记表如下：从以上例子可看出线性表的逻辑特征是：(1)对非空的线性表，有且仅有一个开始结点a1，它没有直接前驱，而仅有一个直接后继a2；(2)有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前驱an-1；(3)其余的内部结点ai(2≤i≤n-1)都有且仅有一个直接前驱ai-1和一个直接后继ai+1。线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存