清华大学数据结构讲义

数据结构计算机系第一章绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分1.4.1算法1.4.2算法设计的要求1.4.3算法效率的度量1.4.4算法的存储空间的需求第一章绪论计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的表示信息的处理而信息的表示和组又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。1.1什么是数据结构众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。那么，什么是数据结构呢？先看以下几个例子。例1、电话号码查询系统设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：(a1，b1)(a2，b2)…(an，bn)其中ai，bi(i=1，2…n)分别表示某人的名字和对应的电话号码要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。数据的结构，直接影响算法的选择和效率。上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量。假定名字和其电话号码逻辑上已安排成N元向量的形式，它的每个元素是一个数对(ai，bi)，1≤i≤n数据结构还要提供每种结构类型所定义的各种运算的算法。例2、图书馆的书目检索系统自动化问题例3、教师资料档案管理系统例4、多叉路口交通灯的管理问题P3通过以上几例可以直接地认为：数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。1.2基本概念和术语数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(DataElement):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。数据对象(DataObject)：是性质相同的数据元素的集合。是数据的一个子集。数据结构(DataStructure)：是相互之间存在一种或多种特定关系的数据元素的集合。数据结构主要指逻辑结构和物理结构数据之间的相互关系称为逻辑结构。通常分为四类基本结构：一、集合结构中的数据元素除了同属于一种类型外，别无其它关系。二、线性结构结构中的数据元素之间存在一对一的关系。三、树型结构结构中的数据元素之间存在一对多的关系。四、图状结构或网状结构结构中的数据元素之间存在多对多的关系。数据结构的形式定义为：数据结构是一个二元组：Data-Structure=(D，S)其中：D是数据元素的有限集，S是D上关系的有限集。例复数的数据结构定义如下：Complex=(C，R)其中：C是含两个实数的集合﹛C1，C2﹜，分别表示复数的实部和虚部。R={P}，P是定义在集合上的一种关系{〈C1，C2〉}。数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。数据对象可以是有限的，也可以是无限的。数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。抽象数据类型：一个数学模型以及定义在该模型上的一组操作。抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。用三元组描述如下：（Ｄ，Ｓ，Ｐ）数据结构在计算机中有两种不同的表示方法：顺序表示和非顺序表示由此得出两种不同的存储结构：顺序存储结构和链式存储结构顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。链式存储结构：在每一个数据元素中增加一个存放地址的指针（），用此指针来表示数据元素之间的逻辑关系。数据类型：在一种程序设计语言中，变量所具有的数据种类。例1、在FORTRAN语言中，变量的数据类型有整型、实型、和复数型例2、在C语言中数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定义数据对象：某种数据类型元素的集合。例3、整数的数据对象是{…-3，-2，-1，0，1，2，3，…}英文字符类型的数据对象是{A，B，C，D，E，F，…}1.3抽象数据类型的表示和实现P111.4算法和算法分析算法：是对特定问题求解步骤的一种描述算法是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有以下五个特性：（1）有穷性一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。（2）确定性算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。（3）可行性一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。4）输入一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。5）输出一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。1.4.2算法设计的要求评价一个好的算法有以下几个标准:(1)正确性(Correctness)算法应满足具体问题的需求。(2)可读性(Readability)算法应该好读。以有利于阅读者对程序的理解。(3)健状性(Robustness)算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。(4)效率与存储量需求效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。1.4.3算法效率的度量对一个算法要作出全面的分析可分成两用人才个阶段进行，即事先分析和事后测试事先分析求出该算法的一个时间界限函数事后测试收集此算法的执行时间和实际占用空间的统计资料。定义：如果存在两个正常数c和n0，对于所有的n≧n0，有︱f(n)︳≦c｜g(n)︳则记作f(n)=O(g(n))一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，算法的时间量度记作T(n)=O(f(n))称作算法的渐近时间复杂度。例１、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];}由于是一个三重循环，每个循环从1到n，则总次数为:n×n×n=n3时间复杂度为T(n)=O(n3)频度：是指该语句重复执行的次数例２{++x;s=0;}将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1)如果将s=0也看成是基本操作，则语句频度为２，其时间复杂度仍为Ｏ(1)，即常量阶。例３、for(I=1;I=n;++I){++x;s+=x;}语句频度为：2n其时间复杂度为：O(n)即时间复杂度为线性阶。例４、for(I=1;I=n;++I)for(j=1;j=n;++j){++x;s+=x;}语句频度为：2n2其时间复杂度为：O(n2)即时间复杂度为平方阶。定理：若A(n)=amnm+am-1nm-1+…+a1n+a0是一个m次多项式，则A(n)=O(nm)证略。例５for(i=2;i=n;++I)for(j=2;j=i-1;++j){++x;a[i，j]=x;}语句频度为：1+2+3+…+n-2=(1+n-2)×(n-2)/2=(n-1)(n-2)/2=n2-3n+2∴时间复杂度为O(n2)即此算法的时间复杂度为平方阶.一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为O(n2)的算法则由一个二次多项式来限界。以下六种计算算法时间的多项式是最常用的。其关系为：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)指数时间的关系为：O(2n)O(n!)O(nn)当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。例如：Voidbubble-sort(inta[]，intn)for(I=n-1;change=TURE;I1&&change;--I){change=false;for(j=0;jI;++j)if(a[j]a[j+1]){a[j]←→a[j+1];change=TURE}}最好情况：0次最坏情况：1+2+3+…+n-1=n(n-1)/2平均时间复杂度为:O(n2)1.4.4算法的存储空间需求空间复杂度:算法所需存储空间的度量，记作:S(n)=O(f(n))其中n为问题的规模(或大小)第二章线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.3.1线性链表2.3.2循环链表2.3.3双向链表2.4一元多项式的表示及相加2.1线性表的逻辑结构线性表(LinearList)：由n(n≧)个数据元素(结点)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）例3、学生健康情况登记表如下：姓名学号性别年龄健康情况王小林790631男18健康陈红790632女20一般刘建平790633男21健康张立立790634男17神经衰弱……..……..…….…….…….例4、一副扑克的点数（2，3，4，…，J，Q，K，A）从以上例子可看出线性表的逻辑特征是：在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1；其余的内部结点ai(2≦i≦n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。抽象数据类型的定义为：P19算法2.1例2-1利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B。voidunion(List&La，ListLb){La-len=listlength(La);Lb-len=listlength(Lb);for(I=1;I=lb-len;I++){getelem(lb，I，e);if(!locateelem(la，e，equal))listinsert(la，++la-en，e)}}算法2.2例2-2巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。此问题的算法如下：voidmergelist(listla，listlb，list&lc)initlist(lc);I=j=1;k=0;la-len=listlength(la);lb-len=listlength