C#数据结构揭秘一
这里，我们 来说一说C#的数据结构了。
①什么是数据结构。数据结构，字面意思就是研究数据的方法，就是研究数据如何在程序中组织的一种方法。数据结构就是相互之间存在一种或多种特定关系的数据元素的集合。 程序界有一点很经典的话，程序设计=数据结构+算法。用源代码来体现，数据结构，就是编程。他有哪些具体的关系了，
(1) 集合(Set)：如图 1.1(a)所示，该结构中的数据元素除了存在“同属于一个集合”的关系外，不存在任何其它关系。 集合与数学的集合类似，有无序性，唯一性，确定性。
(2) 线性结构(Linear Structure)：如图 1.1(b)所示，该结构中的数据元素存在着一对一的关系。我们.net程序员做的最多的工作就是对数据库的表crud，二表的最小的数据单元是行。每行数据是最明显的线性结构。
(3) 树形结构(Tree Structure)：如图 1.1(c)所示，该结构中的数据元素存在着一对多的关系。现实中，家族关系中是最明显的树形结构。如图所示
而对于我们.net程序员来说，操作的树形控件是也是最明显的树形结构
(4) 图状结构(Graphic Structure)：如图 1.1(d)所示，该结构中的数据元素存在着多对多的关系。在现实中，图应用的太多了，如图所示：
对于我们。net程序员应用的较少，当你用C++作一些底层应用，如搜索引擎，地图导航应用的蛮多的。
以上是针对数据结构的介绍。
做过开发的人员都知道这个道理，算法与数据结构和程序的关系非常密切。 进行程序设计时，先确定相应的数据结构，然后再根据数据结构和问题的需要设计相应的算法。
②那什么是算法了？算法，就是计算的方法了，就是解决问题的方案，就是对某一特定类型的问题的求解步骤的一种描述， 是指令的有限序列。 用源代码体现，算法就是编程的体现。一个算法应该具备以下 5个特性：
1、有穷性(Finity)：一个算法总是在执行有穷步之后结束，即算法的执行时间是有限的。我们初学.net时候，经常写着死循环，这不是算法，因为这是无穷的。
2、确定性(Unambiguousness)：算法的每一个步骤都必须有确切的含义，即无二义，并且对于相同的输入只能有相同的输出。对于我们.net程序员写出二义性的源代码，编译器根本让你通不过。
3、输入(Input)：一个算法具有零个或多个输入。它即是在算法开始之前给出的数据结构这些输入是某数据结构中的数据对象。编程是解决问题的，如果不能输入的话，怎么解决问题了。
4、 输出(Output)：一个算法具有一个或多个输出，并且这些输出与输入之间存在着某种特定的关系。 编程就是解决了生活中问题，你不让用户看到最后的结果，这就失去了编程的意义。
5、 能行性(realizability)：算法中的每一步都可以通过已经实现的基本运算的有限次运行来实现。这与有穷性息息相关。
那算法的评价标准又是什么了？
评价一个算法优劣的主要标准如下：1、 正确性(Correctness)。2、可读性(Readability)3、健壮性(Robustness)。4、运行时间(Running Time)。5、占用空间(Storage Space)。
前3个性质，我们很好拿捏。与我们程序员息息相关的是运行时间与占用空间。然而，随着硬件越来越便宜，面对占用空间，我们无非增加硬件。面对海量数据，我们尤为关心是运行时间(Running Time)。这此时的计算机的运行时间由以下因素决定：
1、硬件条件。包括所使用的处理器的类型和速度（比如，使用双核处理器还是单核处理器） 、可使用的内存（缓存和 RAM）以及可使用的外存等。
2、实现算法所使用的计算机语言。实现算法的语言级别越高，其执行效率相对越低。
3、所使用的语言的编译器/解释器。一般而言，编译的执行效率高于解释，但解释具有更大的灵活性。
4、所使用的操作系统软件。操作系统的功能主要是管理计算机系统的软件和硬件资源，为计算机用户方便使用计算机提供一个接口。各种语言处理程序如编译程序、解释程序等和应用程序都在操作系统的控制下运行。
评价运行时间就是一个算法时间复杂度， 一个算法的时间复杂度(Time Complexity)是指该算法的运行时间与问题规模的对应关系。
算法中的基本操作一般是指算法中最深层循环内的语句，因此，算法中基本操作语句的频度是问题规模n的某个函数f(n)，记作：T(n)=O(f(n))。其中“O”表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，或者说，用“O”符号表示数量级的概念。 这些 都只是一些理论的概念，我们这里用计时器来证明这个理论概念。
如：
①x=n; /*n>1*/
y=0;
while(y < x)
{
y=y+1; ①
}
从理论上分析这是一重循环的程序，while 循环的循环次数为 n，所以，该程序段中语句①的频度是 n，则程序段的时间复杂度是 T(n)=O（n） 。
从程序上验证，当n=10时，运行结果如图所示：
当n=100000时，运行结果如图所示
由此证明，其中算法的时间复杂度确实是接近于O(n)
②
for(i=1；i<n；++i) {
for(j=0；j<n；++j)
{
A[i][j]=i*j; ①
}
}
理论上解释为这是二重循环的程序，外层for循环的循环次数是n，内层for循环的循环次数为n，所以，该程序段中语句①的频度为n*n，则程序段的时间复杂度
为T(n)=O（n²） 。
从程序上证明，当n=10,其运行效果如图所示：
当n=100000,其运行效果如图所示：
由此证明，其中算法的时间复杂度确实是接近于O(n²)
③x=n; /*n>1*/
y=0;
while(x >= (y+1)*(y+1))
{
y=y+1; ①
}
这是一重循环的程序，while 循环的循环次数为 n，所以，该程序段中语句①的频度是 n，则程序段的时间复杂度是 T(n)=O（√n） 。
从程序证明：当n=10时，运行效果如图所示：
当n=100000时，运行效果如图所示：
由此证明，其中算法的时间复杂度确实是接近于O(√n)
本文一介绍了数据结构的基本概念 而介绍了算法的基本概念，并且重点讨论了算法时间复杂度，并且用程序予以证明。
相关推荐
-
C#数据结构之堆栈(Stack)实例详解
本文实例讲述了C#数据结构之堆栈(Stack).分享给大家供大家参考,具体如下: 堆栈(Stack)最明显的特征就是"先进后出",本质上讲堆栈也是一种线性结构,符合线性结构的基本特点:即每个节点有且只有一个前驱节点和一个后续节点. 相对前面学习过的顺序表.链表不同的地方在于:Stack把所有操作限制在"只能在线性结构的某一端"进行,而不能在中间插入或删除元素.下面是示意图: 从示意图中可以看出,堆栈有二种实现方式:基于数组的顺序堆栈实现.类似链表的链式堆栈实现 先抽
-
C#数据结构与算法揭秘四 双向链表
首先,明白什么是双向链表.所谓双向链表是如果希望找直接前驱结点和直接后继结点的时间复杂度都是 O(1),那么,需要在结点中设两个引用域,一个保存直接前驱结点的地址,叫 prev,一个直接后继结点的地址,叫 next,这样的链表就是双向链表(Doubly Linked List).双向链表的结点结构示意图如图所示. 双向链表结点的定义与单链表的结点的定义很相似, ,只是双向链表多了一个字段 prev.其实,双向链表更像是一根链条一样,你连我,我连你,不清楚,请看图. 双向链表结点类的实现如下所示
-
C#数据结构与算法揭秘五 栈和队列
这节我们讨论了两种好玩的数据结构,栈和队列. 老样子,什么是栈, 所谓的栈是栈(Stack)是操作限定在表的尾端进行的线性表.表尾由于要进行插入.删除等操作,所以,它具有特殊的含义,把表尾称为栈顶(Top) ,另一端是固定的,叫栈底(Bottom) .当栈中没有数据元素时叫空栈(Empty Stack).这个类似于送饭的饭盒子,上层放的是红烧肉,中层放的水煮鱼,下层放的鸡腿.你要把这些菜取出来,这就引出来了栈的特点先进后出(First in last out). 具体叙述,加下图. 栈通常记
-
C#数据结构之单链表(LinkList)实例详解
本文实例讲述了C#数据结构之单链表(LinkList)实现方法.分享给大家供大家参考,具体如下: 这里我们来看下"单链表(LinkList)".在上一篇<C#数据结构之顺序表(SeqList)实例详解>的最后,我们指出了:顺序表要求开辟一组连续的内存空间,而且插入/删除元素时,为了保证元素的顺序性,必须对后面的元素进行移动.如果你的应用中需要频繁对元素进行插入/删除,那么开销会很大. 而链表结构正好相反,先来看下结构: 每个元素至少具有二个属性:data和next.data
-
C#数据结构与算法揭秘三 链表
上文我们讨论了一种最简单的线性结构--顺序表,这节我们要讨论另一种线性结构--链表. 什么是链表了,不要求逻辑上相邻的数据元素在物理存储位置上也相邻存储的线性结构称之为链表.举个现实中的例子吧,假如一个公司召开了视频会议的吧,能在北京总公司人看到上海分公司的人,他们就好比是逻辑上相邻的数据元素,而物理上不相连.这样就好比是个链表. 链表分为①单链表,②单向循环链表,③双向链表,④双向循环链表. 介绍各种各样链表之前,我们要明白这样一个概念.什么是结点.在存储数据元素时,除了存储数据元素本身的信息
-
C#数据结构之双向链表(DbLinkList)实例详解
本文实例讲述了C#数据结构之双向链表(DbLinkList).分享给大家供大家参考,具体如下: 这是继上一篇<C#数据结构之单链表(LinkList)实例详解>的继续,对于双向链接,节点上除了Next属性外,还要有Prev属性用来指向前一个节点,DbNode定义如下: namespace 线性表 { public class DbNode<T> { private T data; private DbNode<T> prev; private DbNode<T&g
-
C#数据结构与算法揭秘一
这里,我们 来说一说C#的数据结构了. ①什么是数据结构.数据结构,字面意思就是研究数据的方法,就是研究数据如何在程序中组织的一种方法.数据结构就是相互之间存在一种或多种特定关系的数据元素的集合. 程序界有一点很经典的话,程序设计=数据结构+算法.用源代码来体现,数据结构,就是编程.他有哪些具体的关系了, (1) 集合(Set):如图 1.1(a)所示,该结构中的数据元素除了存在"同属于一个集合"的关系外,不存在任何其它关系. 集合与数学的集合类似,有无序性,唯一性,确定性. (2)
-
C#数据结构与算法揭秘二 线性结构
上文对数据结构与算法,有了一个简单的概述与介绍,这篇文章,我们介绍一中典型数据结构--线性结构. 什么是线性结构,线性结构是最简单.最基本.最常用的数据结构.线性表是线性结构的抽象(Abstract), 线性结构的特点是结构中的数据元素之间存在一对一的线性关系. 这 种一对一的关系指的是数据元素之间的位置关系,即: (1)除第一个位置的数据元素外,其它数据元素位置的前面都只有一个数据元素: (2)除最后一个位置的数据元素外,其它数据元素位置的后面都只有一个元素.也就是说,数据元素是一个接一个的排
-
C#数据结构之队列(Quene)实例详解
本文实例讲述了C#数据结构之队列(Quene).分享给大家供大家参考,具体如下: 队列(Quene)的特征就是"先进先出",队列把所有操作限制在"只能在线性结构的两端"进行,更具体一点:添加元素必须在线性表尾部进行,而删除元素只能在线性表头部进行. 先抽象接口IQuene<T> namespace 栈与队列 { public interface IQuene<T> { /// <summary> /// 取得队列实际元素的个数 /
-
C#数据结构与算法揭秘二
上文对数据结构与算法,有了一个简单的概述与介绍,这篇文章,我们介绍一中典型数据结构--线性结构. 什么是线性结构,线性结构是最简单.最基本.最常用的数据结构.线性表是线性结构的抽象(Abstract), 线性结构的特点是结构中的数据元素之间存在一对一的线性关系. 这 种一对一的关系指的是数据元素之间的位置关系,即: (1)除第一个位置的数据元素外,其它数据元素位置的前面都只有一个数据元素: (2)除最后一个位置的数据元素外,其它数据元素位置的后面都只有一个元素.也就是说,数据元素是一个接一个的排
-
C#数据结构之循环链表的实例代码
复制代码 代码如下: public class Node { public object Element; public Node Link; public Node() { Element = null; Link = null; } public Node(object theElement) { Element = theElement;
-
C#数据结构之顺序表(SeqList)实例详解
本文实例讲述了C#数据结构之顺序表(SeqList)实现方法.分享给大家供大家参考,具体如下: 线性结构(Linear Stucture)是数据结构(Data Structure)中最基本的结构,其特征用图形表示如下: 即:每个元素前面有且只有一个元素(称为"前驱"),同样后面有且只有一个元素(称为"后继")--注:起始元素的前驱认为是空,末尾元素的后继认为也是空,这样在概念上就不冲突了. 线性表(List)是线性结构的一种典型实现,它又可以分为:顺序表(SeqLi