[翻译]C#数据结构与算法 ? 前言&第一章

前言

在专业程序员的成长过程中数据结构与算法的学习是至关重要的。虽然有许多书籍介绍数据结构与算法,但这些书大部分是作为高校教材并且以大学中常用于面向对象教学的Java或C++来讲述的。C#正在成为一种流行的语言。此书适合C#程序员们来学习数据结构与算法的基础知识。

C#是一个基于.Net Framework这个丰富的开发环境的语言。.Net Framework的类库中包括了一系列与数据结构相关的类型(也被称作集合类)。这些类包括了从Array,Arraylist与集合类型到Stack与Queue类到HashTable与SortedList这众多的类型。读者可以先学着怎样使用这些类而不用急着明白怎样实现这些类。在这之前,教学者不得不先抽象讨论数据结构的结构的原理(如堆栈),直到完整的构建出这样一个数据结构。现在教学者们可以先给学生演示怎样使用堆栈完成一些如数值转换的计算,从而快速演示这些类的使用。有了这些背景,学生们可以回过头来学习这些数据结构(或算法)的基础,甚至给出了他们自己的实现。

本书对所有程序员都需要知道并理解的数据结构和算法做了一个实用的概述。基于这个原因,本书不包括对这些数据结构与算法的正式分析。因此,本处没有单一的数学公式也没有提到大O分析(如果你不知道这是什么意思,可以参考本书中提到的任何一本书)。取而代之,不同的数据结构及算法被用做解决问题的工具,以此来展示他们。简单的时间测试被用来比较书中讨论的数据结构及算法的性能。

预备知识

本书唯一需要读者具有的预备知识是对C#有一个大概了解。特别是C#面向对象编程这方面。

章节组织

第1章介绍了数据结构作为一个数据集合的概念,线性与非线性集合类的概论;演示了集合类。本章也引入了泛型编程的概念,它允许程序员编写一个适用于多种数据类型的类或方法。泛型是C#中添加的一个重要的特性,以至于针对(用于C#2.0及以后的版本)泛型数据类型在System.Collections.Generic命名空间下增加了一个专门的类库。当此类库中有某一数据结构的泛型实现的时候,我们将研究它的用法。在本章末尾,我们将讨论衡量本书介绍的数据结构与算法性能的方法。

第2章回顾了数组是怎样构建的同时演示了Array类的一些特性。Array类封装了许多与数组操作有关的功能(如UBound,LBound等等)。ArrayList是一种特殊的数组,其提供了动态调整大小的能力。

第3章介绍了基本的排序算法,向冒泡排序,插入排序。第4章研究了大部分基本的内存查找算法,顺序查找与二分查找。

第5章讨论了两种经典的数据结构,栈与队列。本章的重点是这些数据结构在解决每天遇到的数据处理问题时的实用。第6章包含了BitArray类,其可以被用来高效的表示大量的整型数值,如测试分数。

字符串通常不是数据结构的图书所讨论的内容,但第7章介绍了字符串,包括String类和StringBuilder类。C#中许多数据操作是对字符串执行的,读者应该了解这两个类中所包含的特殊技巧。第8章讲解了正则表达式在进行文本处理及样式匹配时的作用。正则表达式提供了比传统字符串处理函数及方法更强大更高效的处理能力。

第9章介绍了字典这种数据结构的使用。字典以及基于它们的其它不同的数据结构,将数据存储为键/值对。本章给读者展示了基于DictionaryBase这个抽象类来创建自己的类型的方法。第10章涵盖了哈希表,讲述了使用HashTable这种特殊的字典类型的哈希方法在内部保存数据的方法。

第11章讲述了另一个经典的数据结构 ? 链表。C#中的链表并不像如C++这种基于指针的程序设计语言中的链表一般重要。但在C#编程中也有它自己的角色。第12章介绍了另一种经典的数据结构 ? 二叉树。二叉树中的一种特殊形式 ? 二叉查找树是本章的主题,其它类型的二叉树被安排在第15章讨论。

第13章演示了怎样在集合类中存储数据。当只能在某一数据结构中存储独一无二的数据值时这种数据类型相当有用。第14章包括了更多的高效排序算法,如流行且高效的快速排序,这也是实现.Net Framework类库过程中所用到的大部分排序过程的基础。第15章研究了在讨论二叉查找树时没有涉及到的三种提供有用的查找功能的数据结构 ? AVL树,红-黑树及跳跃表。

第16章讨论了图与图算法。图在展示许多不同类型的数据,尤其是网络的时候十分有用。第17章介绍了算法设计技术的根本:动态算法和贪婪算法。

致谢

许多不同类型的人帮助我完成此书,在此我向他们致谢。首先,谢谢那些首次听我讲述数据结构与算法的学生。他们是(没有前后顺序):Matt Hoffman, Ken Chen, Ken Cates, Jeff Richmond, and Gordon Caffey。 同样我在Pulaski技术学院的同事Clayton Ruff听了我的大部分课程并提供了很有价值的意见与批评。我同样要感谢我的系主任David Durr及系主席Bernica Tackett,他们支持者我的写作。同样我要感谢我的家人在我投身于研究与写作期间给我的支持。最后,要给剑桥出版社我的编辑Lauren Cowles和Heather Bergman很多的感谢,他们回答我的问题,帮助进行标题的更换以及容忍我习惯性的延期。

  1. 介绍集合类,泛型类及计时类

本书讨论了基于C#语言的数据结构和算法的开发与实现。本书使用的数据结构源于.Net Framework类库中System.Collections命名空间中所包含的类。在本章中我们首先实现一个我们自己的集合类(使用数组作为我们自己实现的基础)来建立对于集合的概念,然后学习.Net Framework中的集合类。

C#2.0中引入的一个重要的新特性是泛型。使用泛型C#程序员使用可以编写一个版本的函数 ? 或独立或存在于一个类中,在不用重载此函数多次的情况下即可接受不同的数据类型。C#2.0提供了一个特殊的命名空间,System.Collections.Generic,其中包含了System.Collections中数据结构的实现。本章将给读者介绍泛型编程。

最后,本章将引入一个自定义类型,他将在以后章节中作为测量数据结构或算法性能的工具。这个类将取代大O分析,并不是大O分析不重要。而是因为本身采用一种更实用的方法来讲授数据结构及算法。

集合定义

有序集合是一种用来存储数据的容器类型的数据结构,它提供向此容器添加数据,由其中移除数据,更新其中数据的方法同时提供了操作来设置或返回集合中不同属性的值。

集合类可以被分为两种类型:线性和非线性。线性集合是一个元素的列表,其中后一个元素跟着前一个元素。线性集合中元素按位置(第一个,第二个,第三个等等)排序。在现实生活中,杂货店商品列表就是一个线性集合的好例子,在计算机世界中(现实中也一样),数组被设计为一个线性集合。

非线性集合中的元素设有位置上的先后顺序。组织图标就是一个非线性集合的例子,就像撞球的架子。在计算机中,树,堆,图,无序集合都是非线性集合的例子。

集合,无论是线性的还是非线性,都定义了一系列属性来描述它们,并且定义了在它们上面可以执行的操作。集合的属性的例子有集合Count属性,它保存了集合中元素的数量。集合上定义的操作,也被称为方法。包含了Add(向集合增加一个元素),Insert(在指定位置插入一个元素),Remove(移除指定的元素),Clear(移除集合中所有元素),Contains(确定指定元素是否为集合的一个成员),IndexOf(确定一个指定元素在集合中的位置)。

集合描述

集合的两个主要类型中又包含了几种子类型。线性集合中既可直接访问的集合也有需要顺序访问的类型。同样非线性集合也分为层次化的或分组的。本部分分别讲述了以上这几种子类型。

直接访问集合

直接访问集合中最常见的例子就是数组。数组定义为一系列相同类型元素的集合,且可以通过一个整数索引直接访问它的元素。如图1.1所示

[翻译]C#数据结构与算法 ? 前言&第一章

C# Win32控制台应用
[翻译]C#数据结构与算法 ? 前言&第一章
[连载]C#程序设计(1
[翻译]C#数据结构与算法 ? 前言&第一章
C# 系统应用之通过注
[翻译]C#数据结构与算法 ? 前言&第一章
[连载]C#程序设计(0
分类:默认分类 时间:2015-03-06 人气:11
本文关键词:
分享到:

相关文章

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.049 (s). 9 q(s)