1、内内 容容 简简 介介 数据结构是计算机专业教学计划中的一门核心课程核心课程，也是信息管理、通信电子、自动控制等与计算机技术关系密切的专业的一门基础课程。从事与计算机科学与技术相关的工作，尤其是计算机应用领域的开发和研制工作，必须具备坚实的数据结构的基础。本书对C+语言作了简单介绍，叙述了抽象数据类型和面向对象的概念，介绍了线性表线性表、栈栈、队列队列、数数组组、广义表广义表、树树、图图等数据结构，并介绍了查找查找和排排序序的方法。全书用C+C+语言描述并实现了所有数据结构的类和程序，并附有习题，便于教学。本书是为高等院校开设数据结构课程编著的教材，可供计算机等专业，也可供从事计算机开发和应用
2、的工程技术人员阅读参考。为什么要学习数据结构？作为计算机程序组成部分的数据结构和算法的研究，一直受到计算机领域工作者的高度重视。数据结构是计算机专业教学计划中的一门核心课程，也是信息管理、通信电子、自动控制等与计算机技术关系密切的专业的一门基础课程。要从事与计算机科学与技术相关的工作，尤其是计算机应用领域的开发和研制工作，必须具备坚实的数据结构的基础。数据结构课程的教学目的 数据结构课程的教学目的是使学生学会分析研究计算机所要加工处理的数据的特征，掌握组织数据、存储数据和处理数据的基本方法，并加强在实际应用中选择合适的数据结构和相应算法的训练。为什么用面向对象的观点来描述数据结构？面向对象技术
3、是软件工程领域中的重要技术，它不仅是一种程序设计方法，更重要的是一种对真实世界的抽象思维方式。目前，面向对象的软件分析和设计技术已发展成为软件开发的主流方法。为了适应软件开发方法与技术的发展以及应用领域的要求，就有必要改进和充实数据结构的教学内容。因此，用面向对象的观点来描述数据结构就成为一种既顺理成章又紧迫的选择。采用C+描述数据结构 用面向对象的观点来描述数据结构，要涉及到面向对象程序设计语言的选用问题。目前被广泛采用作为程序设计语言教学的是C语言，C+是以C语言为基础的、使用比较普遍的面向对象程序设计语言。因此本书采用了C+作为数据结构的描述语言。数据结构课程的特点 数据结构课程内容丰富
4、，学习量大；隐藏在各部分内容中的方法和技术多；贯穿于全书的动态链表存储结构和递归技术令不少初学者望而生畏。本书的编写者长期来从事数据结构课程的教学，对该课程的教学特点和难点有比较深切的体会。作者的努力 作者在认真总结总结二十多年讲授数据结构课程的基础上参考了美国ACM/IEEE CS所颁布的计算2001教程，吸收吸收了国内外各种数据结构教材的优点，对多年来形成的数据结构课程的教学内容进行了合理的剪合理的剪裁裁，既强调强调了数据结构的原理和方法，又注重注重了其实践性，使之适应于现代大学生的学习特点和要求。本书的一个重要特点 本书的一个重要特点就是将程序设计的基础与数据结构的方法尽可能的结合起来。
5、第一、二章介绍C+语言时尽可能给出比较完整的程序，使学生能对C+语言有比较全面和深入的了解，也便于上机实习，从而为数据结构课程的实验建立良好的基础。本书的组织结构 全书共分九章，第一、二章介绍了数据结构、算法及其复杂度的基本概念，对C+作了简单介绍，并叙述了抽象数据类型和面向对象的概念。第三章至第五章介绍了线性结构线性表、栈、队列、数组、广义表；第六章和第七章介绍了非线性结构树和图；第八章和第九章分别介绍了查找和排序的方法。1 绪论 1.1（算法（算法+数据结构）数据结构）=程序程序 计算机神通广大，聪明能干。计算机的本领是人是用“程序”来“教”的。让计算机解题实际上就是为计算机编程序。因而解
6、题的过程就不仅仅是编程序，而是一个包括编程序在内的软件开发过程。软件不仅仅指程序，而是包括程序以及开发程序的过程中所产生的各种文档。软件开发的目标是产生能让计算机有效工作的程序，因此程序是软件的核心。程序到底是什么呢？N.Wirth给出的一个著名的公式：算法算法+数据结构数据结构=程序程序曾经产生了深远的影响。现在受到了挑战。20世纪90年代，面向对象的方法受到了很大的重视，并得到比较广泛的推广和应用。在面向对象程序设计中，密切相关的数据与过程被定义为一个整体（即对象），而且一旦作为一个整体定义了之后，就可以使用它，而无需了解其内部的实现细节，从而提高软件开发的效率。封装和数据隐藏是面向对象问
7、题解和面向对象程序设计的基本要素。算法+数据结构=程序 （算法+数据结构）=程序 本书以面向对象的观点来介绍各种数据结构以及与这些数据结构有关的算法的知识。第一章将介绍数据结构以及算法的基本概念，并介绍用来描述数据结构和算法的语言C+。1.2 数据结构的基本概念 计算机科学是一门研究信息表示和处理的科学，人们是用程序来处理信息的。对程序设计方法进行系统的研究。这不仅涉及到研究程序结构和算法，同时也涉及到研究程序加工的对象。用计算机解题：具体问题具体问题 数学模型数学模型设计算法和编制程序设计算法和编制程序从对问题的分析中提取操作的对象，并找出这些操作对象之间的关系，然后用数学的语言加以描述。1
8、.2.1 两个简单的数据结构实例例例 1-11-1 人事登记表 线性数据结构 例例1-21-2 一个典型的学校行政机构层次型数据结构层次型数据结构1.2.2 什么是数据结构 一个水平再高的厨师,尽管他可以把烹调某个菜肴的过程掌握得很好，但如果不给他原料，他是做不出色、香、味俱全的菜。“巧妇难为无米之炊”。对一个程序来讲，数据就是“原料”。大千世界中有各种各样的信息信息，交通灯，交通卡，交易，思想。这些信息必须转换成数据数据才能在计算机中进行处理。“什么是数据什么是数据”以及与之相关的概念 数据数据（data）：信息的载体，数、字符、图形、图象、声音以及所有能输入到计算机中并被计算机程序识别和处
9、理的符号的集合。数据元素数据元素（data element）：数据的基本单位。数据项数据项（data item）：数据的最小单位 数据对象数据对象：数据的子集。自然数集合=0,1,2,是“数”的数据对象；所有的字符是数据，字母集合AS=A,B,Z,a,b,Z是该数据的数据对象。数据结构数据结构(data structure)：数据以及数据元素之间的相互关系。数据结构分为两大类：线性结构线性结构和非线性结构非线性结构。这两类结构通常又可分为下列四类基本结构四类基本结构 集合集合，结构中的数据元素之间就是“同属于一个集合”；线性结构线性结构，结构中的数据元素之间存在的是一种线性关系，即一对一的关系
10、；树形结构树形结构，结构中的元素存在着一对多的关系；图形结构或网状结构图形结构或网状结构，结构中的元素之间存在着多对多的关系。四种不同结构的关系图 数据的逻辑结构逻辑结构属于用户视图，是用户所看到的数据结构，是面向问题的。它描述的是数据元素之间的逻辑关系。数据的物理结构物理结构，又称存储结构，是数据的逻辑结构在计算机中的物理存储方式，它属于具体实现的视图，是面向计算机的。数据的逻辑结构和物理结构是密切相关的两个方面。一般来说，算法设计是基于数据的逻辑结构，而算法实现则基于数据的物理结构。1.3 C+语言基础 本书以面向对象的观点面向对象的观点来介绍数据结构。所涉及的程序设计的方法自然是面向对象
11、的面向对象的程序设计方法程序设计方法。描述数据结构所采用的语言应该是面向对象面向对象的程序设计语言的程序设计语言。选择了目前比较流行的C+C+语言来描述各种数据结构以及相应的算法。实用和易学 C+与C具有许多相同的功能，C+对C有很多扩充的功能。假设读者已经熟悉C语言。1.3.1 程序结构 一个C+程序可由若干个文件组成。C+的文件分为头文件头文件和源文件源文件两类。头文件以.h为后缀，用于存放函数声明，它给出了函数的参数类型，个数以及函数的返回类型，称为原型原型。有一些头文件是系统定义的，如,而另一些头文件是用户定义的；而源文件是用来存放C+的源代码。用于源文件的后缀为.CPP。可通过预处理
12、指令#includeinclude，将头文件包含在适当的文件中。一个典型的C+程序/*头文件hello.h*/#ifndef FILENAME_H#define FILENAME_Hchar *hello(char*)；#endif/*源代码文件hello.cpp*/#include /含有sprint()的原型#include /含有求字符串长度函数strlen()的原型#include /含有hello()的原型char *hello(char*world)char *result=newchar9+strlen(world)；/*Return the string“Hello,world
13、”.*/sprintf(result,”Hello,%s.”,world)；return result；/*源代码文件main.cpp*/#include#include“hello.h”main()cout hello(“Hello,shanghai”)；头文件hello.h 是hello函数的原型。源文件hello.cpp定义了hello 函数，该函数有一个形式参数，其类型为string，返回函数的类型为string。main.cpp 是打印“hello,Shanghai”的主程序，它构造并打印一个欢迎词字符串。sprintf（）是系统内定义的打印函数。main.cpp中调用的hello函
14、数，其参数的类型、个数以及函数的返回类型必须与预处理指令“include”所定向的头文件“hello.h”所给出的原型中的函数的参数类型、个数、函数的返回类型相匹配。C+中有两种注释方法 多行注释多行注释：包含在定界符“/*”和“*/”之间的所有文本，如:/*This book is designed to present the fundamentals of data structures from an object-oriented perspective.*/单行注释单行注释：在符号/之后至本行末的所有文本内容。例如，C注释 /*This is a C+program.*/可写为C+
15、的单行注释 /This is a C+program.1.3.2 数据声明和作用域 数据声明的作用 C+的基本数据类型：charchar、intint、floatfloat和doubledouble，这些数据类型中的某些又可以用shortshort、longlong、signedsigned和unsignedunsigned进行修饰 数据声明的主要形式：常数值 变量：数据类型的实例，可被修改。常量：在其生命期中不可被赋值的变量。如 const intconst int pi=3.1415926。(4)枚举枚举：声明一个整型常数序列的方式。用关键字enum声明的。例如声明：enum month=
16、Jan=1,Feb,Mar,Apr,May,Jun,July,Aug,Sep,Oct,Nov,Dec(5)引用引用：引用类型用于为一个对象提供一个可替换的名字。对于某一个类型的对象的引用，所采用的声明方式就是在该类型后面添上一个符号。例如 int x=9;int y=x;x=13printf(“x=%d,y=%d”,x,y,);在C中，程序块的所有声明都必须出现在所有可执行语句之前。在C+中，声明可放在使用所声明的内容之前的任何地方。例如printf（“Enter two integers：”）；int x,y;printf（“x=%d,y=%d”,x,y,）变量也可以在for结构的初始化部分
17、予以声明，其作用域仍然是在定义for结构的程序块内。例如for（int i=0;i=5;i+）printf（“i=%d”,i）在for结构中把变量i声明为一个整数并把它初始化为0。作用域作用域 函数中声明的变量只能在函数内部使用；在类中定义的变量，只能在该类内部使用。这些变量都称为局部变量局部变量。C+的局部变量的作用域从其声明开始到结束程序块的右花括号终止。因此，变量声明之前的语句即使在同一个程序块内也不能引用该变量。变量声明不能放在while、do/while、for和 if结构的条件中。把变量声明放在靠近首次引用的位置，即用到时再声明后写上使用，可提高程序的可读性。在整个程序中都能引用的
18、变量叫全局变量全局变量。如果一个全局变量在文件1中声明，而在文件2中使用，则在文件2中必须使用关键字externextern对该变量进行声明。在构成一个程序的两个文件中，如果分别声明了具有相同名字的一个全局变量，它们分别代表不同的实体，此时就要在两个文件中分别使用关键字staticstatic对变量进行声明，以保证不发生混淆。如果一个程序块中某个局部变量与某个全局变量同名，但又要在该程序块中引用该全局变量，则可以使用域操作符:来引用全局变量。1.3.3 输入/输出 执行输入输出操作，必须用#include预处理指令包括一个头文件。关键字cincin用于C+中的输入，操作符用于分开输入的变量。空
19、白（即teb键、回车或空格键）用于在标准输入设备上将不同变量的值分开。关键字coutcout用于输出到一个标准输出设备。coutcout和将被输出的每一内容之间用操作符 分开。此外，定向到错误文件的命令由cerrcerr定义。例例1-3程序：C+中的输入输出#includevoid main()int x,y;cin x y;cout“x=”x endl;cout “y=”y endl;执行上述程序时，按照输入格式 5 10 回车或 5 回车 10 回车均使变量X和Y分别得到输入值5和10，并输出如下结果：x=5 y=10 C+中的输入输出，“自由格式”。程序员不必使用格式化符号来指明输入输出
20、项的类型和顺序。输入输出操作符能够被重载。如有对文件的输入输出，则必须在程序中包含头文件 fstream.h，它定义了类 ifstream、ofstream 和 fstream。要创建一个输入流，必须声明它为类ifstream。要创建一个输出流，必须声明它为类ofstream。而执行输入输出的流必须声明为类fstream。例例1-41-4 含有文件输入输出的程序#include#includevoid main（）ofstream outFile（“my.out”,ios:out）；if（!outFile）cerr“can not open my.out”endl；/standard erro
21、r device return；int n=70；floatf=30.2;outFile “n:”n endl;outFile“f:”f endl;1.3.4 函数 C+中有两种函数：常规函数常规函数和成员函数。成员成员函数函数用于类方法的定义，完成一个特定的功能。无论是常规函数还是成员函数，其定义都包括四个部分：函数名 形式参数表 返回类型 函数体。函数的使用者通过函数名来调用函数，调用过程把实际参数传送给相应的形式参数作为数据的输入；然后通过执行函数体中的语句实现该函数的功能；最终得到的返回值由函数名带回给函数的调用者。函数如果有返回值，则该值的类型就是该函数的返回类型。函数的返回值是通过
22、函数体中的returnreturn语句返回的。return return 语句的作用是返回一个其类型与返回类型相同的值，并终止函数的执行。例例1-51-5 一个函数int min（int a,intb）if a b return a;else return b;对于不返回值的函数，其返回类型要声明为 void。在C+中，指定空参数列表的方法是在圆括号中写入void,或什么也不写。下面的程序例子，演示了声明和使用不带参下面的程序例子，演示了声明和使用不带参数的函数的方法。数的函数的方法。例例1-6使用不带参数的函数#includevoid f1()；void f2(void)；main()f1(
23、)；f2()；return 0;void f1()cout “Function f1 takes no arguments n”；void f2(void)cout “Function f2 also takes no argumentsn”；输出结果为：Function f1 takes no arguments Function f2 also takes no arguments1.3.5 参数传递 函数调用时传送给形参表的实参与形参在类型、个数以及顺序上必须保持一致。C+中函数的参数传递有四种方式：值参数传递 引用参数传递 常值参数传递 常值引用参数传递 值参数传递是缺省的参数传递方式
24、。若采用这种传递方式，程序在运行时，对应的实际参数的值传送给形式参数所对应的局部工作区中的单元。当函数的执行终止时，函数修改的是形式参数所对应的工作单元的值，而该值不传回给实际参数。因此值参数的传递方式不会改变对应形式参数的实际参数的值。使用引用参数传递方式时，需要在函数的形参表中将形参声明为引用类型，即在参数名前加上一个“”。当一个实参与一个引用类型形参结合时，被传递的不是实参的值，而是实参的地址，函数通过地址存取被引用的实参。当函数执行时，任何对形式参数的改变也就是对实际参数的改变。当要求一个函数调用返回多于一个参数时，也应采用参数传递方式。此时，将参数中的一个由return语句返回，而其
25、它参数由引用返回。常值引用参数传递方式的格式为const Ta，其中T是参数的类型。在函数体中，不能对常值参数修改。例例1-7参数传递的方式#include int ExampleByValue(inta,int b,intc)int x,y,z;x=a;y=b;z=c;a=3*a;b=3*b;c=3*c;return(x+y+z)/3;int ExampleByRefer(int a,int b,int c)代码同上int ExampleByConsRefer(const inta,const intb,const intc)return(a+b+c)/3；main()int s=0,p=2
26、,q=3,r=4;s=ExampleByValue(p,q,r);cout“p,q,r,and s:”pqrs“n”;s=ExampleByRefer(p,q,r);cout“p,q,r and S:”pqrs“n”;s=ExampleByConsRefer(p,q,r);cout“p,q,r,and s:”pqrs“n”;输出结果：p,q,r and s:2 3 4 3 p,q,r and s:6 9 12 3 p,q,r and s:6 9 12 9函数ExampleByValue以值参数传递方式调用的，第一次输出的p，q，r的值为2、3、4。ExampleByRefer 是以引用参数传递
27、方式调用的，输出的结果p、q、r、s为6，9，12，3。调用 ExampleByConsRefer 时，实际参数p，g、r不会改变，保留字const保证只能对其值初始化一次，因而输出结果为6，9，12，9。1.3.6 函数名重载 在C+中，允许在同一个程序中用同一个名字定义多个函数，但它们的形参表不同。这种能力称为函数名重载函数名重载。在调用一个重载的函数时，编译程序通过检查参数的个数、类型和顺序,自动选择一个合适的函数。函数重载通常用来建立在不同数据类型的基础上完成类似任务的多个同名函数，这可使程序易于阅读和理解。例例1-8 用重载函数sum来计算两个int类型值的和及三个float类型值的
28、和。在该例中，两个sum函数的返回类型不同，参数个数也不同。#includeint sum(int a,int b)return a+b;float sum(float a,float b,float c)return a+b+c;void main()printf(“sum(2,3)=%d”,sum(2,3)；printf(”sum(1.1,2.2,3.3)=%f”,sum(1.1,2.2,3.3);1.3.7 动态内存分配 在ANSI C中，malloc（）和free（）。C+兼容了C语言中的这两个函数，并提供了两个新的操作符：new和 deleteptrtype*ptr 语句中的ptrt
29、ype可以是任何数据类型（如int、char、float等等）。则语句 ptr=new ptrtype 从程序的空闲内存区中为ptrtype类型的对象分配内存。new运算符以类型为参数，自动建立一个具有合适大小的对象，并返回指向该类型对象的指针，此处类型为ptrtype，返回的指针为ptr。如果分配内存不成功，则返回一个空指针，在C+中，以0而不是null来表示空指针。在C+中，用如下语句来释放该对象所占用的空间：delete ptr；运算符delete 只能释放用运算符new分配的内存。把delete 用于空指针对程序执行没有任何影响，但把delete用于已经释放的指针是不允许的。C+允许初
30、始化新分配的对象，例如，语句int *thisptr=new int（57）；建立了一个指向int类型对象的指针thisptr，把新分配的int类型的对象初始化为57。该语句把指针thisptr 的声明与动态内存分配以及初始化放在一条语句中了。虽然new和delete所完成的功能与C语言中的malloc()和free（）类似，但更方便。首先new按指定类型自动分配足够的空间，不要求调用者提供所需存储空间的数量并使用sizeof 运算符进行计算；其次，new自动返回指定类型的指针，不必像malloc（）那样在分配时需要显式地使用强制类型；此外，new和delete 可以重载。1.3.8 结构与联
31、合如果想要把多个不同数据类型的数据项组合成一个数据元素，则可以使用结构这样的数据类型。1结结构构C+用数组存储许多相同类型的相关信息。有些数据信息是由若干不同数据类型的数据所组成。例如，一个职工工资记录包括姓名、工号和工资等，这些数据信息的类型是不一样的，不能用数组直接把它们组织起来。用结构结构变量就可以有组织地把这些不同数据类型的数据信息存放在一起。q结构结构是用户自定义数据类型，它可与int、float等基本数据类型一样被使用。声明结构类型时，先指定关键字struct和结构名，然后用用一对花括号将若干个结构成员及其数据类型的说明括起来。q 通常，结构声明在所有函数之外，位于main函数之前
32、。这就使所声明的数据类型在程序的任何地方都可以被使用。q 声明一个结构并不分配内存，内存分配发生在定义这个新数据类型的变量时。q结构中包含的数据变量称为该结构的成员。q定义了相应结构变量，分配了空间，就可以使用点操作符“”（或称结构成员操作符）来访问结构中的成员。左操作元为结构类型变量，右操作元为结构中的成员。在数组中，称数组分量为元素，在结构中，称结构分量为成员。数组的运算符与结构的点运算符具有相同的运算优先级，它们是所有运算符中优先级最高的。每个分量数据类型可以相异。结构的成员有自己单独的名字。结构可以被赋值。例例1-91-9 声明一个关于职工工资记录的结构，并使用它。/Person-sa
33、lary.cpp#includestruct personchar name 20;/姓名unsignedlong id;/工号int salary;/工资 ;void main()person pr1=Frank Voltaire,12345678,2456;person pr2;pr2=pr1;cout pr2.name pr2.id pr2.salary”（也是一种结构成员操作符）来访问结构成员。例例1-10 定义结构指针，通过结构指针来访问结构成员：/Structure-pointer.cpp#include#include struct person char name 20;uns
34、ignedlong id;int salary;void main()person pr1;person *prPtr;prPtr=&pr1;/定义了一个结构类型的指针 strcpy(prPtr-name,“David Marat”);prPtr-id=987654321;prPtr-salary=2567;cout name id salary member如果变量utype是用来记录存储在uval中的最近类型的，那么可使用下列程序段存取联合中的元素。if (utype=INT)printf(“%dn”,uval.ival);else if (utype=FLOAT)printf(“%dn”
35、,uval.fval);else if (utype=STRING)printf(“%dn”,uval.pval);elseprintf(“bad type%d in utypen”,utype);联合可以和结构、数组组合使用。存取结构中的联合或联合中的结构的记号与存取嵌套结构是一样的。例例1-13 1-13 结构、数组和联合的组合struct char *name;int flags;int utype;union int ival;float fval;char *pval;uval;symtabNSYM;联合是一种形式特殊的结构变量。和结构一样，对联合施加的操作只能是存取成员和取其地址。
36、不能把联合作为参数传递给函数，也不能由函数返回联合。联合只是一种变量，为了弄请在联合中存储的是哪一种类型，通常是在联合外设置一个变量以作表征。正如在systab中，每一个结构，都含有整型变量utype以指出在该结构的联合uval中存储的是什么类型的变量。结构中往往含有几个不同类型的变量。如systab中就有四个变量。1.4 算法性能与复杂度 公元825年，一位名叫阿尔 花拉子米（al-Khowarizmi）的波斯数学家写了一本教科书，书中概括了进行数字四则算术运算的法则，所有的数字都是用今天的印度十进制形式来表示的（按个、十、百位等排列，并有表示小数部位的小数点）。现代名词“算法算法”(alg
37、orithm)就来源于这位数学家的名字。在计算机科学里，算法这个词有一个专门的解释：算法算法用计算机解题的精确描述用计算机解题的精确描述。1.4.1 1.4.1 算法的定义算法的定义通常，人们将算法定义为一个用于实现某个特定任务的有穷指令集，这些指令规定了一个运算序列。一个算法应当具有以下特性：输入性输入性 一个算法必须具有零个或多个输入量。输出性输出性 一个算法应有一个或多个输出量，输出量是算法计算的结果。确定性确定性 算法中的每一条指令应含义明确，无歧义。有穷性有穷性 算法中的指令执行序列是有穷的。有效性有效性 每条指令必须是足够基本的。一个程序与一个算法对于上述是有重大区别的。一个程序可
38、以不满足特性。一个程序可能会不终止。本书中所给出的程序均是可终止的，所以在本书中对“算法”和“程序”这两个术语不作严格的区分。算法设计者在构思和设计了一个算法之后，必须准确清楚地将所设计的解题步骤记录下来，或提供交流，或编写成程序供计算机执行。记录算法中的解题步骤又叫描述算法。常用的描述算法的方式有自然语言、流程图和程序设计语言等。自然语言自然语言(如汉语或英语)：优点：优点：使用者不必对描述工具本身花精力去学习，对写出来的算法的理解是接的。缺 点：缺 点：容易出现二义性；语句一般太长，使得所建立的算法也显得冗长；算法中的分支及循环等结构表示不能清晰地显示出来规定式样的图形、指向线和文字说明组
39、合起来的流流程图方式：程图方式：优点：优点：直观、清晰、易懂，便于检查、修改和交流。缺陷：缺陷：严密性不如程序设计语言，灵活性不及自然语言；此外，对于大型的算法描述有困难。计算机程序设计语言：计算机程序设计语言：优点：优点：显得清晰、明了，写出的算法一步到位，能由计算机处理。事实上，用程序设计语言来描述算法，就是对算法的实现。缺点：缺点：抽象性差一些，可能会使写算法的人拘泥于计算步骤描述的细节，而忽略算法的实质。此外，必须熟练掌握程序设计语言及其编程技巧。考虑到本书的使用者已经熟悉了像C这样的程序设计语言，并且掌握了程序设计的基本方法和技术，并因本书的内容是以面向对象的方法来讨论数据结构，因而
40、采用因而采用C+来描述算来描述算法。它的优点是类型丰富、语句精练，具有面向过程和面向对象的双重特点。此外，C+也支持抽支持抽象数据类型。象数据类型。为了使写出的算法可读性和可理解性更强,本书有时还采用了C+语句与自然语言结合的方式来描述算法，有时对算法加以合适的注释。1.4.2 算法的性能标准算法的设计主要有以下几个标准：(1)(1)正确性正确性 算法应确切地满足所要求解的问题的需求。(2)(2)可用性可用性 算法应能很方便地使用。(3)(3)可读性可读性 算法应是可读的，即易于理解的。(4)(4)效率效率 算法的效率主要是指算法执行时存储单元的开销和运行时间的耗费，前者称为算法的空间代价，后
41、者称为算法的时间代价。(5)(5)健壮性健壮性 当输入非法数据时，算法应能作出适当的处理，而不应当产生不可预料的结果。在设计一个算法时，上述的几条标准有时会有矛盾，如可用性强、可读性强会降低算法的效率。而对效率这个标准，算法的低时间代价和低空间代价也会产生矛盾。例如，有些问题若采用较多的内存空间可使时间代价降低，若采用较少的内存空间，则使时间代价提高。在计算机硬件价格快速下降的趋势下，算法的时间效率应首先予以考虑。1.4.3 算法复杂度算法效率的度量一般采用两种方法:事前估计事前估计 后期测试后期测试例如对于程序运行的时间耗费，后期测试主要通过在算法中的某些部位插装计时函数来测定算法完成某一规
42、定功能所需的时间。但这种方法与算法的运行环境运行环境有关。同样的算法在速度不同的计算机上运行，执行速度相差却非常大；此外，一个算法用不同的编译系统编译系统编译出的目标代码的长度不一样，质量也不一样，完成同样的功能所需时间也不同；还有，对于一个存储需求很大的算法，如果可用的存储空间不够，在运行时不得不频繁地进行内外存交换，需要的运行时间就很多。而如果可用的存储空间足够大，运行时间就可以大大减少。因此，算法的实际运行时间依赖于所用的计算机系统。在不同的机型、不同的编译系统版本、不同的硬软件配置情况下，想通过后期测试的方法来测定算法的复杂度是比较困难的。因此人们常常采用事前估计即对算法进行分析的方法
43、来测定算法的复杂度。因为算法的复杂度与具体的运行环境和编译系统无关，所以可以通过复杂度的分析来对算法进行比较和评估。1.算法的时间复杂度q 算法的时间复杂度与具体的机器以及运行环境无关，它与所求解的问题的规模有关，可以说，它是问题规模的函数。q 一般来说，问题的规模可以从问题的描述中找到。q 例如，在一个具有n n个教职工记录的文件中查找某个名叫李华的教师，则该问题的规模为n。又如，对一个具有n个整数组成的数组进行排序，则问题的规模也是n n。一个算法是由控制结构（顺序、分支和循环）和基本操作构成的，则算法的时间复杂度与这两者有关。为了能比较解同一问题的不同算法，通常的做法是，从算法中选取一种
44、对于所研究的问题来说是基本运算基本运算的操作的操作，即基本操作，以该基本操作重复执行的次数作为算法的时间量度。有时也需要同时考虑几种基本操作，甚至可以对不同的操作赋以不同权值，以反映执行不同操作所需的相对时间，这种做法便于综合比较解决同一问题的那些完全不同的算法。算法的时间效率分析通常采用O(f(n)表示法，读作“大大O的的f(n)”。其定义可叙述为T(n)=O(f(n)当且仅当存在正常数c和n0，使得对所有的n，当nn0时，都满足T(n)cf(n)。换句话说，O(f(n)给出了函数T(n)的上界。T(n)=O(f(n)表示：表示：随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同
45、，称作算法的渐近时算法的渐近时间复杂度间复杂度（asymptotic time complexity）,简称时间复杂度。或者说两者具有相同的数量级。例例1-14设a和b是两个已经赋了值的数组，对如下求解了两个NxN矩阵相乘的算法求其时间复杂度。for (i=0;in;i+)for(j=0;jn;j+)Ci,j=0;/基本操作语句1for(k=0;kn;k+)Cij=Cij+aik*bkj；/基本操作 语句2 解解:设基本操作语句的总执行次数为T(n)，因为(基本)操作语句“cij=0”的执行次数为n2。“cij=Cij+aik*bkj”的执行次数为n3，因此T(n)=n2+n3。而T(n)=n
46、2+n3cn3，选择c2，则T(n)cn3=O(n3)。所以该算法的时间复杂度为O(n3)因为算法的时间复杂度当算法的时间复杂度T(n)和问题的规模n无关时：T(n)c*1，此时算法的时间复杂度T(n)=O(1)，称为常量级常量级；当算法的时间复杂度T(n)与问题规模n为线性关系时，T(n)c*n，此时算法的时间复杂度T(n)=O(n)，称为线线性级性级；当算法的时间复杂度T(n)和问题的规模n为平方关系时，T(n)c*n2，此时算法的时间复杂度T(n)=O(n2)，称为平方级平方级。例例1-15 求出下面三个程序段的时间复杂度。(1)x=x+1 (2)for (i=1;i=n;i+)x=x+
47、1 (3)for (i=1;i=n;i+)for (j=1;i=n;j+)x=x+1解解：这三个程序段中均含基本语句x=x+1，各自所含的次数为1、n和n2，所以这三个程序段所表示的算法的时间复杂度分别O(1)、O(n)和O(n2)依次类推，还有O(logn)、O(2n)等时间复杂度。例例1-16 设n为如下算法处理的数据个数，求出其时间复杂度。for(i=1;i=n;i=2*i)printf(“i=%d n”,i)/基本语句解解：设基本语句的执行次数为T(n)，有2T(n)n，即有T(n)log2n，因T(n)log2nc*log2n=O(logn)，其中c为常数，所以该算法的时间复杂度为O
48、(logn)。由于算法的时间复杂度考虑的是对于问题规模的增长率，则在难以精确计算基本操作语句执行次数的情况下，只需求出它关于n的增长率增长率或数量级数量级即可。在许多情况下，算法的时间复杂度会随着算法中数据元素的取值情况的不同而不同。例如，下面的算法是用冒泡排序法对数组a中的n个整数类型的数据元素（a0an-1）从小到大排序。例例1-17 冒泡排序算法void BubbleSort(int a,int n)int i,j,flag=1;int temp;for(i=1;in&flag=1;i+)flag=0;（接下页）for(j=0;jaj+1)flag=1,temp=aj,aj=aj+1;a
49、j+1=temp;这个算法的时间复杂度随待排序数据的不同而不同。当某次排序过程中没有任何两个数组元素交换位置，则表明数组元素已排序完毕，此时算法将因标记flag=0不满足循环条件而结束。“交换两个相邻的整数”为基本操作，当a中的初始序列为“正序正序”，即自小至大有序时，基本操作的执行次数为0，这是最好的情况最好的情况；当初始序列为“逆序”，即自大至小有序时，基本操作的执行次数为n(n-1)/2，这是最坏情况最坏情况。再从“两个相邻元素比较两个相邻元素比较”这一基本操作来看，当初始序列为“正序”时，则i循环体执行一次，在j循环中进行了n1次关键字之间的比较。反之，若初始序列为“逆序”时，则i循环
50、体执行n一1次，需要进行的关键字之间的比较为(i1)=n(n1)次。对这类算法的分析，一种解决的办法是计算它的平平均值均值，即考虑它对所有可能的输入数据集的期望值期望值，此时相应的时间复杂度为算法的平均时间复杂度平均时间复杂度。如假设a中初始输入数据可能出现n!种排列情况的概率相等，则冒泡排序算法的平均时间复杂度为Ta(n)=O(n2)。然而，在许多情况下，各种输入数据集出现的概率难以确定，算法的平均时间复杂度也就难以确定。因此，另一种更可行也更常用的办法是讨论算法在最坏情况下的时间复杂度，即分析在最坏情况下，估算出算法执行时间的一个上界上界。例如，上述冒泡排序的最坏情况为a中初始序列为自大至
