数据结构与算法：c_语言描述(中文)

《数据结构与算法：c_语言描述(中文)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、前言数据结构与算法的学习对于进行软件开发的专业程序员而言是非常关键的。虽然有许许多多关于数据结构与算法的书籍，但是这些书籍通常都是大学教材，而且是用在大学里经典讲授的Java语言或C++语言编写的。C#语言正在成为一种广受欢迎的编程语言。这本书为C#语言程序员提供了学习基础数据结构与算法的机会。C#语言根植在一个功能非常丰富的.NET框架开发环境中。在.NET框架库中包含有一套数据结构类（也称为集合类）。这套类的范围从Array类、ArrayList类和Collection类到Stack类和Queue类，再到

2、Hashtable类和SortedList类。学习数据结构与算法的学生在学习如何实现它们之前可以先明白如何使用数据结构。以前老师在构建完整的堆栈数据结构之前只能抽象地讲解堆栈的概念。而现在老师可以立刻通过示范数据结构工具来向学生们展示如何用堆栈执行一些计算，比如数制之间的转换。有了这些知识后，学生可以课后学习数据结构（或算法）的基本原理，甚至可以构造属于他们自己的实现。本书把所有认真的计算机程序员们需要知道和了解的数据结构与算法的实践概述作为主要的写作内容。由于这种情况，本书没有涵盖数据结构与算法的正规的分析

3、。因此，本书没有一个数学公式，也一次没有提及大O分析（如果你不知道大O分析的含义，查看参考文献中提到的任何一本书都可以）。取而代之的，本书把各种各样的数据结构与算法表示成求解问题的工具。书中讨论的数据结构与算法用简单的时间测试来进行性能比较。前提条件阅读本书的唯一前提条件就是需要读者对C#语言有大概的了解。如果会用C#进行面向对象编程更好。章节组织第1章向读者介绍数据结构作为数据集合的概念。介绍线性和非线性集合的概念。示范说明了Collection类。本章还介绍泛型编程的概念。泛型编程允许程序员编写一个类或一

4、种方法，并且把它用于众多数据类型。泛型编程是C#语言一种重要的新特性（在C#2.0以及更高版本中可用）。这种特性是如此重要以至于在System.Collections.Generic命名空间中存在一个专门的泛型数据结构库。当数据结构具有在此库中能找到的泛型实现时，就会讨论它的用途。本章结尾处介绍了衡量书中讨论的数据结构与算法性能的方法。第2章提供了数组构造方法的回顾，并连同示例说明了Array类的特征。Array类把许多与数组相关的函数（UBound函数、LBound函数等等）封装到单独一个包中。ArrayL

5、ists是数组的一种特殊类型，它支持动态地调整容量。第3章是对基础排序算法的介绍，例如冒泡排序和插入排序。而第4章则研究了用于内存查找的最基本算法，顺序查找和二叉查找。第5章探讨了两种经典的数据结构：堆栈和队列。本章节强调的重点是这些数据结构在解决日常数据处理问题中的实际应用。第6章讲述了BitArray类。这种类可以用于有效地表示大量整数值，比如测试成绩。数据结构的书中通常不包含字符串，但是第7章介绍了字符串、String类和StringBuilder类。这是因为在C#语言中许多的数据处理是在字符串上执行的

6、，读者应该接触基于这两种类的特殊方法。第8章分析了用于文本处理和模式匹配的正则表达式的使用。与较传统的字符串函数和方法相比，正则表达式常常会提供更强大更有效的处理。第9章向读者介绍作为数据结构的字典的使用。字典和基于字典的不同数据结构把数据作为键/值对来存储。本章向读者说明了如何创建基于DictionaryBase类的他或她自己的类。DictionaryBase类是一个抽象类。第10章包括散列表和HashTable类。HashTable类是字典的一种特殊类型，它用散列算法对内部数据进行存储。链表作为另外一种经

7、典的数据结构是在第11章介绍。链表在C#语言中不像在C++这样基于指针的语言中那样重要，但是它始终在C#编程中发挥作用。第12章为读者介绍另一种经典数据结构——二叉树。二叉查找树作为二叉树的特殊类型将是本章的主要内容。其他二叉树类型在第15章进行介绍。第13章向读者说明在集合中存储数据的方法。这种方法在数据结构只存储唯一数据值的情况下是很实用的。第14章涵盖了高级排序算法，包括流行且高效的快速排序算法。此算法是大多数在.NET框架库中实现的排序程序的基础。第15章会看到三种数据结构。在无法使用二叉查找树的时候

8、，这三种数据结构证明对查找是很有用的。他们是：AVL树、红黑树和跳跃表。第16章讨论了图以及图的算法。图在表示许多不同的数据类型时非常有用，特别是网络的情况。最后，第17章向读者介绍真正的算法设计技巧是什么：动态算法和贪心算法。致谢在这里我要感谢来自各界帮助我完成此书的人们。首先，我要感谢首批聆听我讲授数据结构与算法开发课程的学生们。这些学生包括有（排名不分先后）：MattHoffman、KenCh