考察数据结构新.docVIP

 HYPERLINK /wayfarer/archive/2004/04/08/5526.html 考察数据结构——第一部分:数据结构简介[译] 相关文档：  HYPERLINK /wayfarer/archive/2004/04/12/5852.aspx 考察数据结构——第二部分：队列、堆栈和哈希表  HYPERLINK /wayfarer/archive/2004/07/16/24703.aspx 考察数据结构——第三部分：二叉树和BSTs 第一部分:数据结构简介 ? 原文链接： HYPERLINK /vcsharp/default.aspx?pull=/library/en-us/dv_vstechart/html/datastructures_guide.asp Part 1: An Introduction to Data Structures ? 介绍:本文是介绍在.Net平台下使用数据结构的系列文章,共分为六部分,这是本文的第一部分.本文试图考察几种数据结构,其中有的包含在.Net Framework的基类库中,有的是我们自己创建的.如果你对这些名词不太熟悉,那么我们可以把数据结构看作是一种抽象结构或是类,它通常用来组织数据,并提供对数据的操作.最常见并为我们所熟知的数据结构就是数组array,它包含了一组连续的数据,并通过索引进行访问. 在阅读本文内容之前,让我们先看看这六部分的主要内容.如果你有什么想法,或觉得本文有什么遗漏之处,希望你通过e-mail( HYPERLINK mailto:mitchell@4 mitchell@4)和我联系,共同分享你的思想.假如有时间的话,我很高兴将你的建议放到合适的部分,如有必要,可以在这篇系列文章中加上第七部分. 第一部分:首先介绍数据结构在算法设计中的重要性.决定数据结构的优劣在于其性能.我们将经过严格分析数据结构的各种性能.此部分还将介绍.Net Frameword下两种常用的数据机构:Array 和ArrayList.我们将考察其结构的操作方式及其效率. 第二部分:我们将继续从更多细节上分析ArrayList结构,同时还将介绍Queue类和Stack类.和ArrayList一样,Queue和Stack存放的都是一组连续的数据集合,都属于.Net Framework基类库.与ArrayList不同的是,Stack和Queue只能以预先规定的序列顺序读取其数据(先进先出和先进后出),而ArrayList可以任意获取数据项.我们将通过示例程序来考察Queue,Stack,并通过扩展ArrayList类来实现它们.之后,我们还要分析哈希表HashTable,它象ArrayList一样可以直接访问数据,不同的是它以key(字符串)为索引. ArrayList对数据直接读取和存储是一种理想的数据结构,同时,它也是支持数据有哪些信誉好的足球投注网站的候选方案.在第三部分,我们将考察二叉树结构,对于数据有哪些信誉好的足球投注网站而言,它比ArrayList更加有效. .Net Framework并不包含此种内置数据结构,因此需要我们自己创建. 二叉树有哪些信誉好的足球投注网站的效率受制于插入到树中的数据的顺序.如果我们插入的是有序或近似有序的数据,实际上,它的效率不如ArrayList.为了将这两种的优势结合起来,在第四部分,我门将考察一种有趣的随机数据结构——SkipList. SkipList既保留了二叉树有哪些信誉好的足球投注网站的高效率,同时输入数据的顺序对其效率影响甚微. 第五部分我们将注意力转向通常用来表现图形的数据结构.图(graph)是众多节点以及节点之间边的集合.举例来说,地图就可以图的形式来表现.城市是节点,公路则是连接节点之间的边.许多现实问题都可以抽象成图的形式,因此,图也是我们经常要用到的数据结构. 最后,第六部分我们将谈到reprisent sets(表示集?)和disjoint sets(非关联集,即交集为空?)集合是一种无序数据的集中.非关联集是指它和另外一个集合没有共同的元素.我们在程序编写时会经常用到集合和非关联集.我们将在这一部分中详细描述它. 数据结构性能分析 当我们在思考一个特别的应用程序或者程序的问题时,多数开发人员(包括我自己)都将兴趣集中到算法上以解决手头的难题,或者为应用程序加上一个很酷的特色以丰富用户的经验.我们似乎很少听到有人会为他所使用的数据结构而激动不已,啧啧赞叹. 然而,用在一个特定算法中的数据结构能够很大程度上影响其性能.最常见的例子就是在数据结构中查找一个元素.在数组中,查找过程所耗时间是与这个数组中元素的个数是成正比的.采用二叉数或者SkipLists(我找不到合适的翻译,按前所述,它包含了随机数的集合,也许看了后面的部分会想到合适的中文),耗时与数据个数比例成线