搜索
1数据结构基础教材：《数据结构（C++描述）》（金远平编著，清华大学出版社，2005）讲课教师：陈钢，计算机学院gchen@wiscom.com.cn2参考文献：1E.Horowitz,S.Sahni,D.Mehta,FundamentalsofDataStructureInC++,ComputerSciencePress,19952W.FordandW.Topp,DataStructureswithC++,清华大学出版社（影印版）,19973T.A.Standish,DataStructures,Algorithms&SoftwarePrinciplesinC,Addison-WesleyPublishingCompany,19944钱能，C++程序设计教程（修订版）--设计思想与实现，清华大学出版社，19993讲课注重：概念、数据结构设计、算法思想和方法、关键步骤。算法分析、程序设计风格！•关于C++•关于进度安排（64/48/32）及略去的章节•关于作业•期末考试采用开卷方式。范围不超过讲义及习题。4第1章基本概念和方法本章论述学习和研究数据结构所必须的并且将反复出现的基本概念和方法。51.1数据结构与软件系统P.1•设计解决实际问题的计算机软件系统，首先需要建立被处理对象的数据模型。•数据和世上万物一样，都是具有结构的。人们很自然地用数据结构表示应用领域的被处理对象。例如，树和图。•数据结构由一个数据对象以及该对象中的所有数据元素之间的关系组成。•数据元素本身可以是数据结构，因此，可以构造非常复杂的数据结构。6•数据结构的实现是以下一层数据结构表示上一层数据结构，直至以程序设计语言提供的基本数据类型表示的过程。•为了模拟实际问题的求解过程和现实对象的行为，还必须提供对数据结构的相应操作。•评价数据结构表示能力的标准主要是它能否方便且有效地实现需要的操作，而实现操作的算法设计及其效率高低也依赖于数据结构表示。•数据结构的定义、表示及其操作的实现相互关联，都是数据结构研究的重要内容。7•计算机软件系统可看成是通过不同层次的数据结构及其操作实现的。例如：8•中间层数据结构起着核心作用，称之为建模层。•对数据结构的研究产生了一批通用性强、具有很高实用价值的中间层数据结构，如数组、字符串、集合、线性表、栈、队列、链表、树、图、符号表等。•系统地学习进而掌握数据结构的知识和方法，对于提高设计与开发软件系统尤其是复杂软件系统的能力，无疑是十分重要的。91.2数据抽象与封装P.2•抽象和封装的概念在日常生活中是普遍存在的，例如，人们常用的手机。•通过数据封装，将一个数据对象的内部结构和实现细节对外屏蔽。•通过数据抽象，将一个数据对象的规格说明与其实现分离，对外提供简洁、清晰的接口。Eg.int•数据结构多层表示的过程反过来也就是从基础数据结构到应用领域数据结构的不断抽象与封装的过程。10•数据类型由一个数据对象的集合和一组作用于这些数据对象的操作组成。例如，C和C++的基本数据类型char、int、float和double等。•用抽象数据类型（ADT）描述数据抽象与封装是一种自然、有效的方法。•抽象数据类型是一个数据类型，该数据类型的组织遵循将数据对象及对这些数据对象的操作的规格说明与这些数据对象的表示、操作的实现相分离的原则。11•当强调一个数据对象的结构时，使用数据结构的概念。•与数据结构的概念对比，抽象数据类型包含了一个数据结构的集合，还包含了对数据结构的操作。(C与C++的差别）。•抽象数据类型成为描述数据结构及其操作的有效方式。•定义ADT的语言本质上不依赖具体的程序设计语言，这里采用C++描述。Eg.(C++并非100%的ADT，如friend，inline等)12例1.1抽象数据类型“圆”的定义为：P.3classCircle{//对象:几何圆public:Circle(floatr);//构造函数，创建一个半径为r的对象实例floatCircumference();//返回该实例的周长floatArea();//返回该实例的面积};该抽象数据类型的名称为Circle，数据对象定义为几何圆，操作包括构造函数、计算周长和面积等以及计算结果如何获得。注意：这些定义不依赖于数据对象的具体表示，也没有给出操作实现的过程。13数据抽象和封装机制的意义：（0）便于对软件的理解和使用（对用户）（1）简化软件开发：假设一个问题经分析将使用A、B、C三个数据类型和协调代码求解。（a）四位程序员，可由其中三位程序员各开发一个数据类型，另一位程序员实现协调代码。（b）一位程序员，数据抽象也可减少其在某一具体时间需要考虑的范围。14（2）易于测试和排除错误：如下图所示，数据抽象明显提高了测试和排除错误的效率。15（3）有利于重用：数据抽象和封装机制使开发人员可以将数据结构及其操作实现为可重用的软件组件。这些组件具有清晰的界面定义，更容易从一个软件系统中提取出来，应用于另一个软件系统。（4）便于改变数据类型的表示：由于数据封装，外界不能直接访问数据类型的内部表示。因此，只要操作接口不变，数据类型内部表示和实现的改变不会影响使用该数据类型的其他程序。161.3算法定义(Algorithm)P.5数据结构的操作实际上是以算法的形式实现的。定义：算法是一个有限的指令集合，执行这些指令可以完成某一特定任务。一个算法还应当满足以下特性：输入零个或多个由外界提供的输入量。输出至少产生一个输出量。确定性每一指令都有确切的语义，无歧义。有限性在执行有限步骤后结束。有效性每一条指令都应能经过有限层的表示转化为计算平台的基本指令，即算法的指令必须是可行的。17•程序和算法不同，程序可以不满足有限性。例如，一个软件的总控程序在未接受新的任务之前一直处于“等待”循环中。•实现数据结构操作的程序总是可结束的，因此，后面将不再严格区分算法和程序这两个术语。•必须保证指令的有效性，例如，指令“if（哥德巴赫猜想是真）thenx=y；”是无效的。作业：P25—3181.4递归算法P.6•直接递归：函数在执行过程中调用本身。•间接递归：函数在执行过程中调用其它函数再经过这些函数调用本身。•表达力：函数定义赋值if-elsewhile函数定义赋值if-else递归19•当问题本身是递归定义的，其解法适合用递归描述。例1.3阶乘函数的定义是1当n=1n!=n(n-1)！当n1用递归方法计算阶乘函数简明扼要，易于理解，如下所示：longFactorial(longn){if(n==1)return1;//终止条件elsereturnn*Factorial(n-1);//递归步骤}20用参数n=5调用Factorial的过程如下：P.7Factorial(5)=(5*Factorial(4))=(5*(4*Factorial(3)))=(5*(4*(3*Factorial(2))))=(5*(4*(3*(2*Factorial(1)))))=(5*(4*(3*(2*1))))=(5*(4*(3*2)))=(5*(4*6))=(5*24)=12021•递归算法有四个特性：P.7（1）必须有可最终达到的终止条件，否则程序将陷入无穷循环；（2）子问题在规模上比原问题小，或更接近终止条件；（3）子问题可通过再次递归调用求解或因满足终止条件而直接求解；（4）子问题的解应能组合为整个问题的解。22例1.4全排列生成器：给定一个具有n≥1个元素的集合，打印该集合的全排列。分析四个元素(a，b，c，d)的情况，结果可以如下构造：（1）a后接(b，c，d)的全排列（2）b后接(a，c，d)的全排列（3）c后接(a，b，d)的全排列（4）d后接(a，b，c)的全排列这表明，如果能生成n–1个元素的全排列，就能生成n个元素的全排列。//此处a为（b，c，d）全排列的前缀，其余类推对于只有1个元素的集合，可以连同此时的前缀直接生成其全排列。于是，全排列生成问题的递归步骤和终止条件可以确定。23用n=3和a[0..2]=(a,b,c)调用perm的示意如下：24求解函数perm：voidperm(char*a,constintk，constintn){//n是数组a的元素个数，生成部分元素a[k],…,a[n-1]的全排列inti;if(k==n-1){//终止条件，输出排列for(i=0;in;i++)couta[i]“”;//输出包括前//缀，以构成整个问题的解coutendl;}i。。。。。。。。。。。。。。。。kn-1前缀当前部分元素的全排列25else{//a[k],…,a[n-1]的排列大于1，递归生成for(i=k;in;i++){chartemp=a[k];a[k]=a[i];a[i]=temp;//交换a[k]//和a[i]perm(a,k+1,n);//生成a[k+1],…,a[n-1]的全排列temp=a[k];a[k]=a[i];a[i]=temp;//再次交换a[k]和//a[i],恢复原顺序}}//else结束}//perm结束通过调用perm(a,0,n)，可以生成n个元素的全排列。26•当算法操作的数据结构是递归定义的时候也适合使用递归。后面将有许多此类的重要例子。作业：P25—5，6271.5性能分析P.9•除了正确性、可用性、可读性和容错性以外，算法的性能是评价算法优劣的重要指标。•空间复杂性：算法开始运行直至结束过程中所需要的最大存储资源开销的一种度量。•时间复杂性：算法开始运行直至结束所需要的执行时间的一种度量。•性能评价分为事前估计和事后测量。•性能分析就是指对算法的空间复杂性和时间复杂性进行事前估计。281.5.1空间复杂性P.9•程序P的空间需求S(P)=c+SP(实例特性)其中，c是常数，SP(实例特性)是实例特性的函数。•分析的重点是SP(实例特性)。•对于一个给定问题，首先要确定其实例特性，才可能分析求解算法的空间要求。•确定实例特性与具体问题的规模密切相关。0n-10n-129例如:1floatrsum(float*a,constintn){2if(n=0)return0;//当n=1时返回a[0]3elsereturnrsum(a,n–1)+a[n–1];4}rsum是一个递归求和算法，其实例特性是n。每次递归调用需在栈顶保存n的值、a的值、返回值和返回地址，共需4个存储单元。由于算法的递归深度是n+1，故所需栈空间是4(n+1)，即Srsum(n)=4(n+1)。301.5.2时间复杂性P.10•算法P的运行时间T(P)=c+TP(实例特性)•时间复杂性分析的目的在于揭示算法的运行时间随着其实例特性变化的规律。•将一组与实例特性无关的操作抽象为一个程序步，从而有效地简化性能分析的过程。•程序步：算法中的一个在语法和语义上有意义的指令序列，而且该序列执行时间与算法的实例特性无关。31•各类C++语句的程序步数详见教科书（P11-12）。•可以通过列出各个语句的程序步数确定整个程序的程序步数。例1.5程序sum:计算a[0]+a[1]+…+a[n-1]P91floatsum(float*a,constintn){2floats=0;3for(inti=0;in;i++)4s+=a[i];5returns;6}32其中各语句的程序步数如下所示：其总程序步数是2n+3。33例1.6设rsum(a,n)（见下页）的程序步数为Trsum(n)，其各语句的程序步数如下：可见，当n=0时Trsum(0)=2；当n0时Trsum(n)=2+Trsum(n-1)。341floatrsum(float*a,constintn){2if(n=0)return0;//当n=1时返回a[0]3elsereturnrsum(a,n–1)+a[n–1];4}35通过反复代入可得：Trsum(n)=2+Trsum(n-1)=2+2+Trsum(n-2)=2*2+Trsum(n-2)=2+2+2+Trsum(n-3)=2*3+Trsum(n-3)…