您好、欢迎来到现金彩票网!
当前位置:秒速快3官网 > 数组处理器 >

数据结构基础温故而知新(二)——数组

发布时间:2019-06-07 05:44 来源:未知 编辑:admin

  数组可以看成是一种特殊的线性表,是线性表的推广,其特点是数据元素仍然是一个表,即线性表中数据元素本身也是一个线性表

  数组是定长线性表在维数上的扩张,即线性表中的元素又是一个线性表,n维数组是一种“同构”的数据结构,其中每个数据元素类型相同,结构一致。、

  设有n维数组A[b1,b2,,bn],其每一维的下界都为1,bi是第i维的上界。从数据结构的逻辑关系角度来看,A中的每个元素A[j1,j2, ,jn](1jibi)都被n个关系所约束。在每个关系中,除第一个和最后一个元素外,其余元素都只有一个直接后继和一个直接前驱。因此就单个关系而言,仍是线性的。

  以二维数组A[m,n]为例,可以把它看成是一个定长的线性表,它的每个元素也是一个定长线性表。

  (1) 数据元素数目固定,一旦定义了一个数组结构,就不再有元素的增减变化。

  几乎所有的高级程序设计语言都提供了数组类型。实际上,在程序语言中把数组看成是具有共同名字的同一类型多个变量的集合。

  数组一般不作插入和删除运算,一旦定义了数组,则结构中的数据元素个数和元素之间的关系就不再发生变动,因此数组适合于采用顺序存储结构。

  由于计算机的内存结构是一维线性的,因此存储多维数组时必须按某种方式进行降维处理,即将数组元素排成一个线性序列,这就产生了次序约定问题。因为多维数组是由较低一维的数组来定义的,依次类推,通过这种递推关系将多维数组的数据元素排成一个线性序列。

  对于数组,一旦确定了其维度和各维的长度,便可为它分配存储空间。反之,只要给出一组下标便可求得相应数组元素的存储位置,即在数据的顺序存储结构中,数据元素的位置是其下标的线性函数。

  设每个数据元素占用L个单元,m,n为数组的行数和列数,Loc(a11)表示元素a11的地址,那么以行为主序优先存储的地址计算公式为:

  推广至多维数组,按下标顺序存储时,先排最右的下标,从右向左直到最左下标,而逆下标顺序则正好相反。

  C#支持一维数组、多维数组及交错数组(数组的数组)。所有的数组类型都隐含继承自System.Array。Array是一个抽象类,本身又继承自System.Object。所以,数组总是在托管堆上分配空间,是引用类型。任何数组变量包含的是一个指向数组的引用,而非数组本身。当数组中的元素的值类型时,该类型所需的内存空间也作为数组的一部分而分配;当数组的元素是引用类型时,数组包含是只是引用。Array还继承了ICloneable、IList、ICollection、IEnumerable等接口。

  C#中的数组一般是0基数组(最小索引为0),这是为了和其它语言共享代码。C#也支持非0基数组。C#除了能创建静态数组外,还可以创建动态数组,这通过使用Array的静态方法CreateInstance方法来实现。

  Array中的方法有许多。以下列出了Array类型中常用的方法,并对每个方法给出了注释。

  数组是基本的数据结构,因为在所有计算上,它们与内存系统存在直接的对应关系。为了用机器语言从内存中读取内容,就要提供相应的地址。因此,我们可以将整个计算机内存看做一个数组,让内存地址与数组索引对应。大部分计算机语言处理器包含数组的程序翻译成直接访问内存的高效机器语言程序。保守的假定是,数组访问(a[i])只翻译成几条机器指令。

  这个程序的目标是,若i为素数,则设置a[i]为1;若不是素数,则设置为0.首先,将所有数组元素设置为1,表示没有已知的非素数。然后将已知为非素数(即为已知素数的倍数)的索引对应的数组元素设置为0.如果将所有较小素数的倍数设置为0之后,a[i]仍然保持1,则可判断它是所找的素数。

  因为程序使用一个数组来包含最简单元素类型,0和1两个值,如果我们使用位的数组,而不是使用整数的数组,则可获得更高的空间有效性。而且,如果N庞大,一些编程环境可能要求数组为全局,或者可以动态分配它。如下:

  数组不仅深刻地反映在大部分计算机上访问内存中数据的底层机制,而且还有着广泛的用途,因为它们与组织应用中数据的自然方法直接吻合。例如,数组也与向量直接对应,向量是对象索引表(indexed list)的数学术语。

  以下程序模拟了一个伯努利试验(Bernoulli trial)序列,这是源自概率论的一个熟悉的抽象概念。如果我们抛掷硬币N次,K次看到正面头像的概率为:

  如果抛掷硬币N次,看到头像的期望值是N/2次,但实际值也可能是0~N次,在程序中进行M次试验,M和N都从命名行获取。它使用一个数组f来跟踪出现“i次头像”的概率,其中0jN。然后打印试验结果的柱状图,每出现10次用1个星号表示。

  这种近似被称之为正态近似(normal approximation),其曲线为我们熟悉的铃形。计算中的重点是,使用数值作为数值的索引来计算出现的频率。数组支持这类运算的能力是它的优点之一。

  从某种意义上讲,当我们使用计算值来访问大小为N的数组时,就是只用一个运算来考虑N中概率。它对效率的提升非常可观。

  美国 Robert.Sedgewick 周良忠 译 《第1卷:基础、数据结构、排序和搜索》 人民邮电出版社

http://alsunah.net/shuzuchuliqi/183.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有