C#与数据结构

问题描述

线性表线性表是最简单也是最常用的一种数据结构。例如,英文字母表(A,B,…,Z)是一个线性表,表中的每一个英文字母是一个数据元素;又如成绩单是一个线性表,表中的每一行是一个数据元素,每个数据元素又是由学号、姓名、成绩等数据项组成。线性表是最简单的数据结构,而顺序表和链表作为线性表的两种重要存在形式,是堆栈、队列、串以及树和图等数据结构的实现基础,内容非常重要,一定要认真对待。本章将介绍线性表的定义、线性表的顺序存储结构和链式存储结构以及相关算法实现。这些存储结构在C#类库中都有相对应的集合类,本章也将对这些集合类的原理、实现及使用做进一步地探讨。线性表的定义线性表(LinearList)是具有相同特性的数据元素的一个有限序列(如图2.1所示)。该序列中所含元素的个数称作线性表的长度。线性表中的元素在位置上是有序的,好比储户去银行排队取钱,人们依次排列,排在前面的先取钱,排在后面的后取钱。这种位置上的有序性就是一种线性关系。由此可以看出线性表的前后两个元素存在一一对应的关系。但是需要注意,这种前后关系是逻辑而非物理意义上的。就好比银行进行了改革,使用排队机进行排队,所有储户分散在银行的各个角落,他们取钱的顺序是依据从排队机获取的纸条上的号数来决定的。线性表的顺序存储结构—顺序表线性表的顺序存储结构是指用一块地址连续的存储空间依次存储线性表的数据元素。这种存储方式好比改革前的银行,需要在业务窗口前排队取钱。由此可以看出顺序表中逻辑上相邻的元素在物理上也是相邻的。顺序表的特点1.容量固定存储顺序表的元素需要一整块内存空间,因而顺序表的容量一旦确定,便不能更改。为了理解这一点,可以把内存空间想象成一栋学生宿舍楼,一个班集的学生就是一张线性表,宿舍楼的每个房间都可以住10个学生。如图2.2所示,在新生入学时A班的40个学生被安排进了前4个宿舍(101~104),B班的50个学生被安排进了随后的5个宿舍(105~109)。当两个班的学生住进宿舍之后,A班又补录了10个学生,这时如果希望A班的所有学生住在连续的5间宿舍已经变得不可能,因为105宿舍已经住进了B班的学生。其实计算机的内存也存在同样的情况,当为某个表分配了一片固定的内存空间后,这个空间周围的其它内存空间极有可能马上被占用,你无法任意地改变已经分配的内存空间的大小。1.访问速度快在顺序表使用索引访问数据元素是非常简单、快速的。如图2.3所示,假设顺序表中的第一个元素的位置是Loc,每个数据元素所占用的存储空间为n,那么可以很快地计算出第i个元素的存储地址为:Loc+(i–1)*n。2.2.2数组线性表的顺序存储结构在C#中的最直接表现形式就是数组。在C#语言中,数组是最基础也是存取速度最快的一种集合类型。数组是引用类型,保存它们所需的内存空间会在托管堆上分配,一旦数组被创建,其中的所有元素将被初始化为它们的默认值。int[]arrInt=newint[5];arrInt[2]=5;arrInt[4]=3;以上代码声明了一个值类型int的数组,并把它的长度初始化为5,最后分别给第3和第5个元素赋值。它在内存中的分布如图2.4所示:从图2.4可以得知,newint[5]会在托管堆中会划分一块能够存放5个整型数据的内存空间,并且每个元素都会被初始化为0,这意味着数组在被创建的同时就拥有了值。另外数组的长度一旦确定就不能再被更改,这使得数组没有添加和删除元素的操作。任何对于数组的添加和删除元素的操作都只能是逻辑意义上的。注意:在托管堆中创建数组时,除了数组元素,数组对象所占有的内存块还包含一个类型对象指针、同步真索引等额外成员。也就是说newint[5]在内存中划分的空间大于20个字节,图2.4省略了这些额外成员。当数组元素为值类型时,数组对象存放的是值类型对象本身。当元素为引用类型时,数组对象存放的则是对象的引用(指针)。Control[]arrCtrl=newControl[5];arrCtrl[0]=newButton();arrCtrl[3]=newLabel();以上代码声明了一个引用类型Control的数组,并把它的长度初始化为5,最后分别给第1和第4个元素赋值。两个值是分别Button和Label对象,虽然它们都继承自Control类,但两者却是不同类,它们的大小不一样。但数组中各个元素的大小是相同的,这些大小不同的对象是如何存储的呢?下面是arrCtrl数组的内存分布图:由图2.5可知,newControl[5]在托管堆中划分了一块能够存放5个指针的内存空间,并且每个元素都被初始化为null。当使用arrCtrl[0]=newButton()给数组元素赋值时,首先在托管堆中创建一个Button对象,然后把Button的内存地址存放在数组的第一个元素中,这样就可以通过数组中的指针访问Button对象了。数组有很多优点,但它的缺点也非常明显。在实际编程中,经常需要对集合中的元素进行添加和删除,也需要动态地改变集合的大小,数组显然无法满足这些需求。怎么样才能使数组具有改变空间大小的功能呢?原文地址:

解决方案

解决方案二:
谢谢,学习了!
解决方案三:
ArrayList
解决方案四:
散分?
解决方案五:
收藏
解决方案六:
该回复于2008-05-20 18:29:22被版主删除
解决方案七:
该回复于2008-11-26 10:35:29被版主删除
解决方案八:
受教了
解决方案九:
该回复于2008-05-20 18:29:22被版主删除
解决方案十:
学习了
解决方案十一:
mark
解决方案十二:
该回复于2008-05-20 18:29:22被版主删除
解决方案十三:

解决方案十四:
该回复于2008-05-20 18:29:22被版主删除
解决方案十五:
学习了
解决方案:
接分。
解决方案:
学习中
解决方案:
up学习..
解决方案:
该回复于2008-05-20 18:29:22被版主删除
解决方案:
收藏了
解决方案:
该回复于2008-05-20 18:29:22被版主删除

时间: 2024-07-30 02:57:07

C#与数据结构的相关文章

[数据结构] 数组与链表的优缺点和区别

概述 数组 是将元素在内存中连续存放,由于每个元素占用内存相同,可以通过下标迅速访问数组中任何元素.但是如果要在数组中增加一个元素,需要移动大量元素,在内存中空出一个元素的空间,然后将要增加的元素放在其中.同样的道理,如果想删除一个元素,同样需要移动大量元素去填掉被移动的元素.如果应用需要快速访问数据,很少插入和删除元素,就应该用数组. 链表 中的元素在内存中不是顺序存储的,而是通过存在元素中的指针联系到一起,每个结点包括两个部分:一个是存储 数据元素 的 数据域,另一个是存储下一个结点地址的

[数据结构] 栈

栈(stack)又名堆栈,它是一种运算受限的线性表.其限制是仅允许在表的一端进行插入和删除运算.这一端被称为栈顶,相对地,把另一端称为栈底.向一个栈插入新元素又称作进栈.入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素:从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素. 栈的示意图: java中的Stack Stack 类表示后进先出(LIFO)的对象堆栈.它通过五个操作对类 Vector 进行了扩展 ,允许将向量视为堆栈.它提供了通常的 p

[数据结构] Hash表、Hash函数及冲突解决

1.Hash表 哈希表(Hash table,也叫散列表),是根据key而直接进行访问的数据结构.也就是说,它通过把key映射到表中一个位置来访问记录,以加快查找的速度.这个映射函数叫做散列函数,存放记录的数组叫做散列表. 以数据中每个元素的关键字K为自变量,通过散列函数H(k)计算出函数值,以该函数值作为一块连续存储空间的的单元地址,将该元素存储到函数值对应的单元中. 哈希表存储的是键值对,其查找的时间复杂度与元素数量多少无关,哈希表在查找元素时是通过计算哈希码值来定位元素的位置从而直接访问元

数据结构模版----单链表实现方式总结

数据结构模版----单链表实现方式总结 前面我们提供了四种方式实现的单链表,有带头结点的不带头结点的,而单链表的结构体定义也有两种方式,那么这些实现方式,到底有什么区别呢,为什么会出现这么多种实现方式呢,下面我们就来细细体会 一 单链表结构体的实现区别 首先我们对比一下,单链表结构体 不同方式的单链表实现时,链表结点的实现是相同的,不同之处在于单链表结构体的实现上 单链表结构体的实现 [cpp] view plain copy print? typedef int ElemType;      

sharedpreferences-shareprefeneh和数据结构

问题描述 shareprefeneh和数据结构 部分代码 public static class school_teacherNameReadWrite{ public static SharedPreferences Read(Context context ){ SharedPreferences preferences=null; preferences=context.getSharedPreferences("school_teacherName",Context.MODE_

基本数据结构和算法在Linux内核中使用

基本数据结构和算法在Linux内核中使用 gaufunga day ago 搬运工 Linux内核(源代码的链接在github). 1.链表.双向链表.无锁链表. 2.B+ 树,这是一些你无法在教科书上找到的说明. 一个相对简单的B+树的实现.我把它作为一个学习练习来帮助理解B+树是如何工作的.这同样也被证明是有用的. ... 一个在教科书中并不常见的技巧.最小的值在右侧而不是在左侧.所有在一个节点里用到的槽都在左侧,所有没有用到的槽包含了空值(NUL).大多数操作只简单地遍历所有的槽一次并在第

Scalaz(24)- 泛函数据结构: Tree-数据游览及维护

上节我们讨论了Zipper-串形不可变集合(immutable sequential collection)游标,在串形集合中左右游走及元素维护操作.这篇我们谈谈Tree.在电子商务应用中对于xml,json等格式文件的处理要求非常之普遍,scalaz提供了Tree数据类型及相关的游览及操作函数能更方便高效的处理xml,json文件及系统目录这些树形结构数据的相关编程.scalaz Tree的定义非常简单:scalaz/Tree.scala * A multi-way tree, also kn

顺序存储线性表-数据结构顺序表的操作(c++)

问题描述 数据结构顺序表的操作(c++) 求解答谢谢 解决方案 贴出代码而不是截图.发了帖子你难道自己不看下.这么小的字根本看不清. 解决方案二: 什么是线性表?定义:由n(n>=0)个数据类型相同的数据元素组成的有限序列.特点是:在数据元素的非空有限集合中,除第一个元素无直接前驱,最后一个元素无直接后继外,集合中其余每个元素均有唯一的直接前驱和直接后继.什么是顺序表,在这里回答一下.顺序表就是线性表的顺序存储,其特点是:物理顺序与逻辑顺序是相同的,关系线性化,结点顺序存.线性表顺序存储的表示?

index merge的数据结构和成本评估

1. 概述:index merge的数据结构 index merge的主要数据结构仍然是存放在SEL_TREE中: class SEL_TREE :public Sql_alloc { ... List<SEL_IMERGE> merges; ... }; 在merges这个list中存放了所有可能的index merge.本文将从几个案例,来看看SEL_TREE/SEL_IMERGE如何代表一个index merge访问方式.本文将不再重复介绍SEL_ARG/SEL_TREE的Range相关

数据结构程序设计,完整程序,跪谢!!!

问题描述 数据结构程序设计,完整程序,跪谢!!! 设A=(a1a2......am)B=(b1b2.......bn)均为顺序表,A'和B'分别为A和B中除去最大共同前缀后的子表.若A'=B'=空表,则A=B:若A'=空表,而B'不等于空表,或者两者均不为空表,且A'的首元小于B'的首元,则A<B:否则B<A.试写一个比较A,B大小的程序 解决方案 http://wenku.baidu.com/link?url=9KAndUtOMFznd076u--8Era3F9XH2oKM8YDiTlSqd