数据结构(C_语言版).docx

《数据结构(C_语言版).docx》由会员分享，可在线阅读，更多相关《数据结构(C_语言版).docx（255页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、刖 S编者在写这本书时遇到了两个问题。第一个问题是关于数据结构教材。应该说关于数 据结构的教材已经很多了。自从美国唐欧.克努特教授用汇编语言写的计算机程序设计 技巧第一卷基本算法问世以来，已经出现了用PASCAL、C、C+、JAVA等语言写的 数据结构书。所以，在编者写本书之前，曾经感到很为难。目前，C#语言作为微软在新一 代开发平台.NET推出的、完全面向对象的语言，凭着其简洁、高效、模板、标准化的特性， 使得C#语言像程序设计语言中的一件艺术品，也吸引着越来越多的开发人员。这也使得我 院的可视化专业进行专业改革时，决定以C#语言作为该专业的主要开发语言。所以说，用 C#语言来讲授数据结构课

2、程是我院专业改革的结果。而用C#语言写的数据结构教材目 前国内基本上是空白。鉴于此，编者决定写本书。在接下来的写作过程中，编者遇到了另外一个问题，那就是C#语言和.NET Framework 的发展。当作者写这本书时，是以C#语言和.NET Framework的2。版本来写的。但是，到 目前为止，C#语言和.NET Framework已经出现3.0版本了。这使得编者感到了微软技术的 发展之快，发出了“学习微软的东西在某种程度上是一种痛苦”之叹！也使编者曾产生了放 弃写该书的念头。但作为教师的责任和对新东西的执著使得编者一直坚持，直到该书完稿。 也附带说一句：如果读者在阅读过程中，发现有些技术不

3、是最新的技术也不要惊奇，本书是 以C#语言和.NET Framework2.0版本来写的。本书的内容本书分为8章，第1章介绍了数据结构和算法的基本概念及本书用到的数学和C#的知 识；第2章至第6章分别讨论了线性表、栈和队列、串和数组、树型结构和图结构等常用的 数据结构及其应用，以及在.NET框架中相应的数据结构；第7、8两章分别讨论了排序和查 找常用的各种方法及其应用以及在.NET框架中相应的算法。本书特点将数据结构与C#语言和.NET框架结合是本书的一大特点。.NET平台是微软推出的一 个新的开发平台，目的是让“不同的语言共享同一平台。.NET很可能成为下一代Windows 操作系统的一部分

4、。而C#语言作为新一代完全面向对象的语言，是.NET的母言。本书所有 的数据结构和算法都是用C#语言进行描述，并在相应章节的末尾介绍了在.NET框架中常用 的数据结构和算法。用C#在.NET平台开发的技术人员可以从本书中获得许多有益的知识和 技术。使用配套光盘本书配套光盘中包含以下内容：I、code目录是本书所有的代码及一个学生信息管理系统的代码。code目录包含 案例和chapter 1-chapters等9个子目录。案例子目录中是学生信息管理系统的代码。学生信息管理系统是学生上学期学 习C#初级编程课程所做的一个小系统，是学生在没有学过数据结构课程时算法。 日的在于让学生比较采用数据结构和

5、算法与不采用数据结构与算法的不同。所以，把这个小 的系统作为数据结构（C#）课程的学习素材。考虑到有些学校在选用本教材时学生没有 做过这个系统，所以，把代码全部给了出来。chapter 1-chapters等8个口录分别对应本书的相应章节。其中每个目录中的source子目 录是本书中的有关源代码，涉及各个数据结构的接口、结点类、数据结构类的C#代码及常 用算法都放在相应章节目录卜的source子目录中。chapter 1-chapters等目录中还有一个project子目录，里面有一个或多个项目，是使用各 种数据结构和常用的排序和查找算法来解决学生信息管理系统的项目，是案例内容在数 据结构中的

6、推广和延伸。所有的代码都没有完成，可作为教师教学、学生实验、课程设计等 的素材使用。其中，chapter1中的project子目录是各个例题中问题应用的项目。chapter4由 于string和array是经常使用的数据结构和数据类型，所以，没有project子目录而只有source 子El录。chapter6由于图的内容高职层次的学生很少涉及，所以也没有project子目录而只有 source子 目录。2、ppt目录下是本书的电子课件，可作为教师教学参考、学生自学之用。3、pdf目录下是本书的电子版本，可作为电子图书供读者在电脑上学习使用。4、pictures目录下本书中比较大的图，是用Mi

7、crosoft Office Visio 2003软件画的，目 的是为了让教师更好地备课与上课。主要是第5章以后章节的部分图。5,有一个stuinfo.txt文件，是30位虚拟学生的信息，可根据实际需要进行增删，但 必须修改相应的程序代码。使用本书及光盘的工具z Microsoft Visual Studio 2005 （如果您想运行本书中的程序，那么您需要在计算机中 安装它）；z Microsoft Office PowerPoint 2003 （如果您想使用ppt目录中的内容，那么您需要在 计算机中安装它）；z Microsoft Office Visio 2003 （如果您想使用pict

8、ures目录中的内容，那么您需要在 计算机中安装它）；z Adobe Acrobat 7.0 Professional （如果您想使用pdf目录中的内容，那么您需要在计 算机中安装它）；致谢没有许多人的帮助，编者是不可能完成本书的。尤其要感谢下面这些人。2张应辉院长和胡锦德院长一直关注和支持可视化专业的专业改革。特别是胡院长， 亲自指导了专业改革，并多次询问该书的进度并对其中的问题给予指示。如果没 有二位领导，该书是不可能产生和完成的。2 出版社的周凌波和郭朝晖老师为本书的修订和出版做了大量的工作。与他们的合 作非常愉快，他们尽力使本书的东西通顺流畅。没有他们的工作，本书不可能出 版。2最后，

9、编者要感谢自己的家人。为了写这本书，编者投入了大量的时间和精力， 牺牲了许多的周末和节假臼。没有胥璐（编者的妻子）和段楚榆（编者的女儿） 的支持，根本不可能有这本书的问世。多少次，编者都想花些时间陪伴家人，但 都因为本书而放弃了。现在，本书总算告一段落，编者可以有更多时间幸福地听 到女儿的笑声了。尽管编者在写作过程中非常认真和努力，但由于编者水平有限，书中难免存在错误和 不足之处，恳请广大读者批评指正。如果您对本书或光盘有什么意见、问题或想法，欢迎您 通过下面的邮件通知编者，编者将不胜感激：Ema i l:duanez 请在邮件的主题栏中注明：数据结构（C#）.编者2006年12月第1章绪论1

10、1.1 数据结构11 .1.1学习数据结构的必要性12 . 1.2基本概念和术语11.2 算法41. 2.1算法的特性41. 2.2算法的评价标准51.2 .3算法的时间复杂度61.3 数学预备知识71.3. 1集合71.3.2 常用的数学术语81.3.4 递归91. 4C#预备知识101.4. 1接口101. 4. 2泛型编程13本章小结20习题一20第2章 线性表222. 1线性表的逻辑结构222. 1. 1线性表的定义222.1 . 2线性表的基本操作222.2 顺序表242. 2. 1顺序表的定义242. 2.2顺序表的基本操作实现292. 2.3顺序表应用举例352.3单链表382.

11、 3. 1单链表的定义392. 3.2单链表的基本操作实现462. 3.3单链表应用举例562.4 其他链表612. 4. 1双向链表613. 4. 2循环链表642.5 C#中的线性表64本章小结67习题二67第3章 栈和队列693. 1 栈693. 1. 1栈的定义及基本运算693.1.3栈的应用举例.823. 1.4C#中的栈873.2队列873. 2.2队列的存储和运算实现894. 2.3队列的应用举例1033. 2.4 C#中的队列104本章小结105习题三105第4章 串和数组1064. 1 串1064. 1. 1串的基本概念1064. 1.2串的存储及类定义1065. 1.4C#

12、中的串1154.2 数组1174. 2. 1数组的逻辑结构1175. 2. 2数组的内存映象1186. 2.3 C#中的数组119习题四二121第5章树和二叉树1237. 1树1236. 1. 1 树的定义1237. 1.2树的相关术语1248. 1.3树的逻辑表示1259. 1.4树的基本操作1265. 2二叉树1265. 2. 1二叉树的定义1275. 2.2二叉树的性质1285. 2.3二叉树的存储结构1295. 2. 4二叉链表存储结构的类实现1325. 2.5二叉树的遍历1375.3树与森林1415. 3.2树、森林与二叉树的转换1445. 3.3树和森林的遍历1475. 4哈夫曼树

13、1475. 4.1 哈夫曼树的基本概念1476. 4.2哈夫曼树类的实现1497. 4.3哈夫曼编码1538. 5应用举例1549. 6 C#中的树157本章小结158习题五159第6章 图1616.1 图的基本概念1616.1.1 图的定义1616. 1.3图的基本操作1656.2图的存储结构1666. 2. 1邻接矩阵1677. 2.2邻接表1726.3 图的遍历1856. 3.1深度优先遍历1857. 3.2广度优先遍历1886.4 图的应用1896. 4. 1最小生成树1897. 4. 2 最短路径1996. 4.3拓扑排序207习题六210第7章 排序2137. 1基本概念2137.

14、 2简单排序方法2147. 2. 1直接插入排序2147. 2. 2冒泡排序2168. 2.3简单选择排序2172 .3快速排序2197 . 4堆排序2228 .5归并排序2309 . 6基数排序2327. 6. 1多关键码排序2328. 6. 2链式基数排序2337.7各种排序方法的比较与讨论2357.8 C#中排序方法235本章小结236习题七236第8章 查找2388.1基本概念和术语2388.2静态查找表2388. 2. 1顺序查找2388. 2.2有序表的折半查找2399. 2.3索引查找2429.4 哈希表2528. 4.2常用的哈希函数构造方法2539. 4.3处理冲突的方法25

15、49.5 C#中的查找方法256本章小结256习题八256参考文献257第1章绪论数据是外部世界信息的计算机化，是计算机加工处理的对象。运用计算机处 理数据时，必须解决四个方面的问题：是如何在计算机中方便、高效地表示和 组织数据；二是如何在计算机存储器（内存和外存）中存储数据；三是如何对存 储在计算机中的数据进行操作，可以有哪些操作，如何实现这些操作以及如何对 同一问题的不同操作方法进行评价；四是必须理解每种数据结构的性能特征，以 便选择一个适合于某个特定问题的数据结构。这些问题就是数据结构这门课程所 要研究的主要问题。本章首先说明学习数据结构的必要性和本书的目的，然后解 释数据结构及其有关概

16、念，接着讨论算法的相关知识，最后简单介绍本书所要用 到的相关数学知识和C#知识。1.1 数据结构1.1.1 学习数据结构的必要性我们知道，虽然每个人都懂得英语的语法与基本类型，但是对于同样的题目， 每个人写出的作文，水平却高低不一。程序设计也和写英语作文一样，虽然程序 员都懂得语言的语法与语义，但是对于同样的问题，程序员写出来的程序不一样。 有的人写出来的程序效率很高，有的人却用复杂的方法来解决一个简单的问题。当然，程序设计水平的提高仅仅靠看儿本程序设计书是不行的。只有多思索、 多练习，才能提高自己的程序设计水平；否则，书看得再多，提高也不大。记得 刚学程序设计时，常听人说程序设计水平要想提高

17、，最重要的是多看别人写的程 序，多去思考问题。从别人写的程序中，我们可以发现效率更高的解决方法；从 思考问题的过程中，我们可以了解解决问题的方法常常不只一个。运用先前解决 问题的经验，来解决更复杂更深入的问题，是提高程序设计水平的最有效途径。数据结构正是前人在思索问题的过程中所想出的解决方法。一般而言，在学 习程序设计一段时间后，学习“数据结构”便能让你的程序设计水平上一个台阶。 如果只学会了程序设计的语法和语义，那么你只能解决程序设计三分之一-的问 题，而且运用的方法并不是最有效的。但如果学会了数据结构的概念，就能在程 序设计上，运用最有效的方法来解决绝大多数的问题。数据结构这门课程的目的有

18、三个。第一个是讲授常用的数据结构，这些 数据结构形成了程序员基本数据结构工具箱（toolkit）。对于许多常见的问题，工 具箱里的数据结构是理想的选择。就像.NET Framework中Windows应用程序开 发中的工具箱，程序员可以直接拿来或经过少许的修改就可以使用，非常方便。 第二个是讲授常用的算法，这和数据结构一样，是人们在长期实践过程中的总结， 程序员可以直接拿来或经过少许的修改就可以使用。可以通过算法训练来提高程 序设计水平。第三个目的是通过程序设计的技能训练促进程序员综合能力的提 高。1. 1.2基本概念和术语在本小节中，将对一些常用的概念和术语进行介绍，这些概念和术语在以后 的

19、章节中会多次出现。1、数据ata）数据是外部世界信息的载体，它能够被计算机识别、存储和加工处理，是计 算机程序加工的原料。计算机程序处理各种各样的数据，可以是数值数据，如整 数、实数或复数；也可以是非数值数据，如字符、文字、图形、图像、声音等。 2、数据元素ata Element）和数据项ata Item）数据元素是数据的基本单位，在计算机程序中通常被作为一个整体进行考虑 和处理。数据元素有时也被称为元素、结点、顶点、记录等。个数据元素可由 若干个数据项(Data Item)组成。数据项是不可分割的、含有独立意义的最小数据 单位，数据项有时也称为字段(Field)或域(Domain)。例如，在

20、数据库信息处理系 统中，数据表中的一条记录就是一个数据元素。这条记录中的学生学号、姓名、 性别、籍贯、出生年月、成绩等字段就是数据项。数据项分为两种，一种叫做初 等项，如学生的性别、籍贯等，在处理时不能再进行分割；另一种叫做组合项， 如学生的成绩，它可以再分为数学、物理、化学等更小的项。3、数据对象(Data Object)数据对象是性质相同的数据元素的集合，是数据的一个子集。例如，整数数 据对象是0,土 1,2,3,字符数据对象是a,b,c,。4、数据类型ata Type)数据类型是高级程序设计语言中的概念，是数据的取值范围和对数据进行操 作的总和。数据类型规定了程序中对象的特性。程序中的每

21、个变量、常量或表达 式的结果都应该属于某种确定的数据类型。例如,C#语言中的字符串类型(String, 经常写为string)。一个String表示一个恒定不变的字符序列集合，所有的字符序 列集合构成String的取值范围。我们可以对String进行求长度、复制、连接两个 字符串等操作。数据类型可分为两类：一类是非结构的原子类型，如C#语言中的基本类型 (整型、实型、字符型等)；另一类是结构类型，它的成分可以由多个结构类型 组成，并可以分解。结构类型的成分可以是非结构的，也可以是结构的。例如， C#语言中数组的成分可以是整型等基本类型，也可以是数组等结构类型。5、数据结构(Data Struc

22、ture)数据结构是相互之间存在一种或多种特定关系的数据元素的集合。在任何问 题中，数据元素之间都不是孤立的，而是存在着一定的关系，这种关系称为结构 (Structure)o根据数据元素之间关系的不同特性，通常有4类基本数据结构： (1)集合(Set)：如图1.1(a)所示，该结构中的数据元素除了存在“同属于一个集 合”的关系外，不存在任何其它关系。(2)线性结构(Linear Structure)：如图1.1(b)所示，该结构中的数据元素存在着一 对一的关系。(3)树形结构(Tree Structure)：如图1.1(c)所示，该结构中的数据元素存在着一对 多的关系。(4)图状结构(Grap

23、hic Structure)：如图1.1(d)所示，该结构中的数据元素存在着 多对多的关系。(a)集合(b)线性结构(c)树形结构(d)图状结构图1.1 4类基本数据结构关系图由于集合中的元素的关系极为松散，可用其它数据结构来表示，所以本书不 做专门介绍。关于集合的概念在1.3.1小节中有介绍。数据结构的形式化定义为：数据结构（Data Structure）简记为DS,是一个二元组，DS = （D,R）其中：D是数据元素的有限集合，R是数据元素之间关系的有限集合。下面通过例题来进一步理解后3类数据结构。【例1-1】 学生信息表（如表L1所示.）是一个线性的数据结构，表中的每 一行是一个记录（在

24、数据库信息处理系统中，表中的一个数据元素称为一个记 录）。一条记录由学号、姓名、行政班级、性别和出生年月等数据项组成。表中 数据元素之间的关系是一对一的关系。表1.1学生信息表学号姓名行政班级性别出生年月040303001雷洪软件04103男1986.12040303002李春软件04103女1987.3040303003周刚软件04103男1986.9【例1-2】家族关系是典型的树形结构，图1.2是一个三代的家族关系。在 图中，爷爷、儿子、女儿、孙子、孙女或外孙女是一个结点（在树形结构中，数 据元素称为结点），他们之间是一对多的关系。其中，爷爷有两个儿子和一个女 儿，这是一对三的关系；一个儿

25、子有两个儿子（爷爷的孙子），这是一对二的关 系；另一个儿子有一个儿子（爷爷的孙子）和一个女儿（爷爷的孙女），这是一 对二的关系；女儿有三个女儿（爷爷的外孙女），这是一对三的关系。树形结构 具有严格的层次关系，爷爷在树形结构的最上层，中间层是儿子和女儿，最下层 是孙子、孙女和外孙女。不能把这种关系倒过来，因为绝对不会先有儿子或女儿 再有爷爷，也不会先有孙子或孙女再有儿子、先有外孙女再有女儿。图L2家族关系图【例1-3】 图1.3是四个城市的公路交通图，这是一个典型的图状结构。在 图中，每个城市是-一个顶点（在图状结构中，数据元素称为顶点），它们之间是 多对多的关系。成都与都江堰、雅安直接通公路，

26、都江堰与成都、青城山直接通 公路，青城山与都江堰、成都及雅安直接通公路，雅安与成都、青城山直接通公 路。这些公路构成了一个公路交通网，所以，又把图状结构称为网状结构（Network Structure）图L3四城市交通图从数据类型和数据结构的概念可知，二者的关系非常密切。数据类型可以看 作是简单的数据结构。数据的取值范围可以看作是数据元素的有限集合，而对数 据进行操作的集合可以看作是数据元素之间关系的集合。数据结构包括数据的逻辑结构和物理结构。上述数据结构的定义就是数据的 逻辑结构(Logic Structure),数据的逻辑结构是从具体问题抽象出来的数学模型， 是为了讨论问题的方便，与数据在

27、计算机中的具体存储没有关系。然而，我们讨 论数据结构的目的是为了在计算机中实现对它的操作，因此还需要研究在计算机 中如何表示和存储数据结构，即数据的物理结构(Physical Structure)o数据的物理 结构又称为存储结构(Storage Structure),是数据在计算机中的表示(又叫映像) 和存储，包括数据元素的表示和存储以及数据元素之间关系的表示和存储。数据的存储结构包括顺序存储结构和链式存储结构两种。顺序存储结构 (Sequence Storage Structure)是通过数据元素在计算机存储器中的相对位置来表 示出数据元素的逻辑关系，一般把逻辑上相邻的数据元素存储在物理位置

28、相邻的 存储单元中。在C#语言中用数组来实现顺序存储结构。因为数组所分配的存储 空间是连续的，所以数组天生就具有实现数据顺序存储结构的能力。链式存储结 构(Linked Storage Structure)对逻辑上相邻的数据元素不要求其存储位置必须相 邻。链式存储结构中的数据元素称为结点(Node),在结点中附设地址域(Address Domain)来存储与该结点相邻的结点的地址来实现结点间的逻辑关系。这个地址 称为引用(Reference),这个地址域称为引用域(Reference Domain)(.从20世纪60年代末到70年代初，出现了大型程序，软件也相对独立，人 们越来越重视数据结构，

29、认为程序设计的实质是确定数据结构，加上设计一个好 的算法，这就是人们常说的“程序=数据结构+算法”。下一节谈谈算法的问题。 1.2算法从上节我们知道，算法与数据结构和程序的关系非常密切。进行程序设计时， 先确定相应的数据结构，然后再根据数据结构和问题的需要设计相应的算法。由 于篇幅所限，下面只从算法的特性、算法的评价标准和算法的时间复杂度等三个 方面进行介绍。2. 1 算法的特性算法(Algorithm)是对某一特定类型的问题的求解步骤的一种描述，是指令的 有限序列。其中的每条指令表示一个或多个操作。一个算法应该具备以下5个特 性：1、有穷性(Finity)： 一个算法总是在执行有穷步之后结束

30、，即算法的执行时间是 有限的。2、确定性(Unambiguousness)：算法的每一个步骤都必须有确切的含义，即无二 义，并且对于相同的输入只能有相同的输出。3、输入(Input)： 一个算法具有零个或多个输入。它即是在算法开始之前给出的 量。这些输入是某数据结构中的数据对象。4、输出(Output)： 一个算法具有一个或多个输出，并且这些输出与输入之间存 在着某种特定的关系。5、能行性(realizability)：算法中的每一步都可以通过已经实现的基本运算的有 限次运行来实现。算法的含义与程序非常相似，但二者有区别。一个程序不一定满足有穷性。 例如操作系统，只要整个系统不遭破坏，它将永远

31、不会停止。还有，一个程序只 能用计算机语言来描述，也就是说，程序中的指令必须是机器可执行的，而算法 不一定用计算机语言来描述，自然语言、框图、伪代码都可以描述算法。在本书中我们尽可能采用C#语言来描述和实现算法，使读者能够阅读或上 机执行，以便更好地理解算法。1.2. 2算法的评价标准对于一个特定的问题，采用的数据结构不同，其设计的算法一般也不同，即 使在同种数据结构下，也可以采用不同的算法。那么，对于解决同一问题的不 同算法，选择哪一种算法比较合适，以及如何对现有的算法进行改进，从而设计 出更适合于数据结构的算法，这就是算法评价的问题。评价一个算法优劣的主要 标准如下：1、正确性(Corre

32、ctness)。算法的执行结果应当满足预先规定的功能和性能的要求， 这是评价一个算法的最重要也是最基本的标准。算法的正确性还包括对于输入、 输出处理的明确而无歧义的描述。2、可读性(Readability)。算法主要是为了人阅读和交流，其次才是机器的执行。 所以，一个算法应当思路清晰、层次分明、简单明了、易读易懂。即使算法已转 变成机器可执行的程序，也需要考虑人能较好地阅读理解。同时，一个可读性强 的算法也有助于对算法中隐藏错误的排除和算法的移植。3、健壮性(Robustness)。一个算法应该具有很强的容错能力，当输入不合法的数 据时，算法应当能做适当的处理，使得不至于引起严重的后果。健壮性

33、要求表明 算法要全面细致地考虑所有可能出现的边界情况和异常情况，并对这些边界情况 和异常情况做出妥善的处理，尽可能使算法没有意外的情况发生。4、运行时间(Running Time)。运行时间是指算法在计算机上运行所花费的时间， 它等于算法中每条语句执行时间的总和。对于同一个问题如果有多个算法可供选 择，应尽可能选择执行时间短的算法。一般来说，执行时间越短，性能越好。5、占用空间(Storage Space)占用空间是指算法在计算机上存储所占用的存储空 间，包括存储算法本身所占用的存储空间、算法的输入及输出数据所占用的存储 空间和算法在运行过程中临时占用的存储空间。算法占用的存储空间是指算法执

34、行过程中所需要的最大存储空间，对于一个问题如果有多个算法可供选择，应尽 可能选择存储量需求低的算法。实际上，算法的时间效率和空间效率经常是对 矛盾，相互抵触。我们要根据问题的实际需要进行灵活的处理，有时需要牺牲空 间来换取时间，有时需要牺牲时间来换取空间。通常把算法在运行过程中临时占用的存储空间的大小叫算法的空间复杂度 (Space Complexity)o算法的空间复杂度比较容易计算，它主要包括局部变量所占 用的存储空间和系统为实现递归所使用的堆栈占用的存储空间。如果算法是用计算机语言来描述的，还要看程序代码量的大小。对于同一个 问题，在用上面5条标准评价的结果相同的情况下，代码量越少越好。

35、实际上， 代码量越大，占用的存储空间会越多，程序的运行时间也可能越长，出错的可能 性也越大，阅读起来也越麻烦。在以上标准中，本书主要考虑程序的运行时间，也考虑执行程序所占用的空间。影响程序运行时间的因素很多，包括算法本身、输入的数据以及运行程序的 计算机系统等。计算机的性能由以下因素决定：1、硬件条件。包括所使用的处理器的类型和速度(比如，使用双核处理器还是 单核处理器)、可使用的内存(缓存和RAM)以及可使用的外存等。2、实现算法所使用的计算机语言。实现算法的语言级别越高，其执行效率相对 越低。3、所使用的语言的编译器/解释器。一般而言，编译的执行效率高于解释，但解 释具有更大的灵活性。4、

36、所使用的操作系统软件。操作系统的功能主要是管理计算机系统的软件和硬 件资源，为计算机用户方便使用计算机提供一个接口。各种语言处理程序如编译 程序、解释程序等和应用程序都在操作系统的控制下运行。1.2 . 3算法的时间复杂度一个算法的时间复杂度(Time Complexity)是指该算法的运行时间与问题规 模的对应关系。一个算法是由控制结构和原操作构成的，其执行的时间取决于二 者的综合效果。为了便于比较同一问题的不同算法，通常把算法中基本操作重复 执行的次数(频度)作为算法的时间复杂度。算法中的基本操作一般是指算法中 最深层循环内的语句，因此，算法中基本操作语句的频度是问题规模n的某个函 数f(

37、n),记作：T(n)=0(f(n)。其中“0”表示随问题规模n的增大，算法执行时 间的增长率和f(n)的增长率相同，或者说，用“0”符号表示数量级的概念。例 如，如“巧网1-!)，贝1J的数量级与n相同，所以T(n)=0 (n2)o如果一个算法没有循环语句，则算法中基本操作的执行频度与问题规模n无 关，记作0(1),也称为常数阶。如果算法只有一个一重循环，则算法的基本操作 的执行频度与问题规模n呈线性增大关系，记作0(n),也叫线性阶。常用的还有 平方阶0 (/)、立方阶0 (/)、对数阶0(logm)等。下面举例来说明计算算法时间复杂度的方法。【例b4】分析以下程序的时间复杂度。x=n;/*

38、nl*/y=0；while(y x)y=y+l;)解：这是一重循环的程序，while循环的循环次数为n,所以，该程序段中语句的频度是n,则程序段的时间复杂度是T(n)=0 (n)o【例1-5】分析以下程序的时间复杂度。for(i=l； in； +i) for(j=0； jl*/y=0；while(x = (y+l)*(y+l)(y=y+l;解：这是一重循环的程序，while循环的循环次数为所以，该程序段中语句的频度是6，则程序段的时间复杂度是T(n)=0 (6)。【例1-7】分析以下程序的时间复杂度。for(i=0;im;i+)(for(j=0;jt;j+)(for (k=0;k0, a#l）

39、的b次塞等于N,就是ab=N,那么数b叫做以a为 底N的对数（Logarithm）,记作logaN=b,其中a叫做对数的底数，N叫做真数。从定义可知，负数和零没有对数。事实上，因为a0,所以不论b是什么 实数，都有ab0,这就是说不论b是什么数，N永远是正数，因此负数和零没 有对数。编程人员经常使用对数，它有两个用途。第一，许多程序需要对一些对象进 行编码，那么表示n个编码至少需要多少位呢？答案是logzn。例如，如果要存 储1000个不同的编码，至少需要Uog/000=10位（10位可以产生1024个不同 的可用编码）。第二，对数普遍用于分析把问题分解为更小子问题算法。在一个 线性表中查找指

40、定值所使用的折半查找算法就是这样一种算法。折半查找算法首 先与中间元素进行比较，以确定下一步是在上半部分进行查找还是在下半部分进 行查找。然后继续将适当的子表分半，直到找到指定的值（折半查找算法在8.2.3 小节有详细的描述）。一个长度为n的线性表被促逐次分半，直到最后的子表中只 有一个元素，一共需要进行多少次呢？答案是log2n次。本书中用到的对数儿乎都以2为底，这是因为数据结构和算法总是把事情一 分为二，或者用二进制位来存储编码。1.3.4 递归一个算法调用自己来完成它的部分工作，在解决某些问题时，一个算法需要 调用自身。如果一个算法直接调用自己或间接地调用自己，就称这个算法是递归 的(R

41、ecursive)。根据调用方式的不同，它分为直接递归(Direct Recursion)和 间接递归(Indirect Recursion) o比如，在收看电视节目时，如果演播室中也有一台电视机播放的是与当前相 同的节目，观众就会发现屏幕里的电视套有一层层的电视画面。这种现象类似于 直接递归。如果把两面镜子面对面摆放，便可从任意一面镜子里看到两面镜子无数个影 像，这类似于间接递归。个递归算法必须有两个部分：初始部分(Base Case)和递归部分 (Recursion Case) o初始部分只处理可以直接解决而不需要再次递归调用的简单 输入。递归部分包含对算法的次或多次递归调用，每次的调用参

42、数都在某种 程度上比原始调用参数更接近初始情况。函数的递归调用可以理解为：通过一系列的自身调用，达到某一终止条件后， 再按照调用路线逐步返回。递归是程序设计中强有力的工具，有很多数学函数是 以递归来定义的。如大家熟悉的阶乘函数，我们可以对n!作如下定义：r 1-go日4轲1 tt芋取用 rr A0根据定义，如要计算n! (factorial (n),需要先调用factorial (nT)计算 (n-D!,而要计算(n-D!需要先调用factorial (n-2)计算(n-2)!,以此类推，最 终需要调用factorial (0)计算0!,然后程序逐步返回，即可计算出n!。阶乘函数的C#语言实现如下。public static long fact(int n)