数据结构(C语言版)

前言数据结构（C#语言版）前言编者在写这本书时遇到了两个问题。第一个问题是关于数据结构教材。应该说关于数据结构的教材已经很多了。自从美国唐．欧．克努特教授用汇编语言写的《计算机程序设计技巧》第一卷《基本算法》问世以来，已经出现了用PASCAL、C、C++、JAVA等语言写的数据结构书。所以，在编者写本书之前，曾经感到很为难。目前，C#语言作为微软在新一代开发平台.NET推出的、完全面向对象的语言，凭着其简洁、高效、模板、标准化的特性，使得C#语言像程序设计语言中的一件艺术品，也吸引着越来越多的开发人员。这也使得我院的可视化专业进行专业改革时，决定以C#语言作为该专业的主要开发语言。所以说，用C#语言来讲授《数据结构》课程是我院专业改革的结果。而用C#语言写的数据结构教材目前国内基本上是空白。鉴于此，编者决定写本书。在接下来的写作过程中，编者遇到了另外一个问题，那就是C#语言和.NETFramework的发展。当作者写这本书时，是以C#语言和.NETFramework的2.0版本来写的。但是，到目前为止，C#语言和.NETFramework已经出现3.0版本了。这使得编者感到了微软技术的发展之快，发出了“学习微软的东西在某种程度上是一种痛苦”之叹！也使编者曾产生了放弃写该书的念头。但作为教师的责任和对新东西的执著使得编者一直坚持，直到该书完稿。也附带说一句：如果读者在阅读过程中，发现有些技术不是最新的技术也不要惊奇，本书是以C#语言和.NETFramework2.0版本来写的。本书的内容本书分为8章，第1章介绍了数据结构和算法的基本概念及本书用到的数学和C#的知识；第2章至第6章分别讨论了线性表、栈和队列、串和数组、树型结构和图结构等常用的数据结构及其应用，以及在.NET框架中相应的数据结构；第7、8两章分别讨论了排序和查找常用的各种方法及其应用以及在.NET框架中相应的算法。本书特点将数据结构与C#语言和.NET框架结合是本书的一大特点。.NET平台是微软推出的一个新的开发平台，目的是让“不同的语言共享同一平台”。.NET很可能成为下一代Windows操作系统的一部分。而C#语言作为新一代完全面向对象的语言，是.NET的母言。本书所有的数据结构和算法都是用C#语言进行描述，并在相应章节的末尾介绍了在.NET框架中常用的数据结构和算法。用C#在.NET平台开发的技术人员可以从本书中获得许多有益的知识和技术。本书配套光盘中包含以下内容：使用配套光盘1、code目录是本书所有的代码及一个《学生信息管理系统》的代码。code目录包含案例和chapter1~chapter8等9个子目录。案例子目录中是《学生信息管理系统》的代码。《学生信息管理系统》是学生上学期学习《C#初级编程》课程所做的一个小系统，是学生在没有学过《数据结构》课程时算法。目的在于让学生比较采用数据结构和算法与不采用数据结构与算法的不同。所以，把这个小的系统作为《数据结构（C#）》课程的学习素材。考虑到有些学校在选用本教材时学生没有做过这个系统，所以，把代码全部给了出来。chapter1~chapter8等8个目录分别对应本书的相应章节。其中每个目录中的source子目录是本书中的有关源代码，涉及各个数据结构的接口、结点类、数据结构类的C#代码及常用算法都放在相应章节目录下的source子目录中。chapter1~chapter8等目录中还有一个project子目录，里面有一个或多个项目，是使用各种数据结构和常用的排序和查找算法来解决《学生信息管理系统》的项目，是案例内容在数前言数据结构（C#语言版）据结构中的推广和延伸。所有的代码都没有完成，可作为教师教学、学生实验、课程设计等的素材使用。其中，chapter1中的project子目录是各个例题中问题应用的项目。chapter4由于string和array是经常使用的数据结构和数据类型，所以，没有project子目录而只有source子目录。chapter6由于图的内容高职层次的学生很少涉及，所以也没有project子目录而只有source子目录。2、ppt目录下是本书的电子课件，可作为教师教学参考、学生自学之用。3、pdf目录下是本书的电子版本，可作为电子图书供读者在电脑上学习使用。4、pictures目录下本书中比较大的图，是用MicrosoftOfficeVisio2003软件画的，目的是为了让教师更好地备课与上课。主要是第5章以后章节的部分图。5、有一个stuinfo.txt文件，是30位虚拟学生的信息，可根据实际需要进行增删，但必须修改相应的程序代码。使用本书及光盘的工具*MicrosoftVisualStudio2005（如果您想运行本书中的程序，那么您需要在计算机中安装它）;*MicrosoftOfficePowerPoint2003（如果您想使用ppt目录中的内容，那么您需要在计算机中安装它）;*MicrosoftOfficeVisio2003（如果您想使用pictures目录中的内容，那么您需要在计算机中安装它）;*AdobeAcrobat7.0Professional（如果您想使用pdf目录中的内容，那么您需要在计算机中安装它）;致谢没有许多人的帮助，编者是不可能完成本书的。尤其要感谢下面这些人。*张应辉院长和胡锦德院长一直关注和支持可视化专业的专业改革。特别是胡院长，亲自指导了专业改革，并多次询问该书的进度并对其中的问题给予指示。如果没有二位领导，该书是不可能产生和完成的。*出版社的周凌波和郭朝晖老师为本书的修订和出版做了大量的工作。与他们的合作非常愉快，他们尽力使本书的东西通顺流畅。没有他们的工作，本书不可能出版。*最后，编者要感谢自己的家人。为了写这本书，编者投入了大量的时间和精力，牺牲了许多的周末和节假日。没有胥璐（编者的妻子）和段楚榆（编者的女儿）的支持，根本不可能有这本书的问世。多少次，编者都想花些时间陪伴家人，但都因为本书而放弃了。现在，本书总算告一段落，编者可以有更多时间幸福地听到女儿的笑声了。尽管编者在写作过程中非常认真和努力，但由于编者水平有限，书中难免存在错误和不足之处，恳请广大读者批评指正。如果您对本书或光盘有什么意见、问题或想法，欢迎您通过下面的邮件通知编者，编者将不胜感激：Email:[e-mail]请在邮件的主题栏中注明：数据结构（C#）。编者2006年12月数据结构（C#语言版）目录I第1章绪论...........................................................................................................................11.1数据结构...................................................................................................................11.1.1学习数据结构的必要性...................................................................................11.1.2基本概念和术语...............................................................................................11.2算法...........................................................................................................................41.2.1算法的特性............................................................................................................41.2.2算法的评价标准....................................................................................................51.2.3算法的时间复杂度................................................................................................61.3数学预备知识...........................................................................................................71.3.1集合...................................................................................................................71.3.2常用的数学术语...............................................................................................81.3.3对数...................................................................................................................81.3.4递归...................................................................................................................91.4C#预备知识.............................................................................................................101.4.1接口.................................................................................................................101.4.2泛型编程.........................................................................................................13本章小结.................................................................................................................................20习题一.....................................................................................................................................20第2章线性表.....................................................................................................................222.1线性表的逻辑结构...........................