小r的博客 普通的博客

数组的多种用法与理解

2016-11-09
XiaoR

声明

这篇文章是给刚学习编程语言,且最好使用的是c语言的人看的。

导论

数组,一般理解为存放数据的一个最基本的数据结构。

但是其若能得当使用,威力也相当的大。

数组本质上是一种一一映射的关系,a[n]=b,其实和f(n)=b的函数没有什么区别。也就是说,数组可以作为一个映射关系来使用。

这个映射关系的好处是,查询a[n]的值,这个步骤的速度是极快的。如果有某种数据映射需要大量查询,数组或许是个好方法。

举个最简单的例子,假如一个程序需要频繁调用(1«i)的值(«是c语言里的左移运算符),那么我提前写一个a[n]的数组,并提前写好以下运算:

for(int i=0;i<n;i++){
	a[i] = 1<<n;
}

如此一来,每次只需调用a[i]即可知道1«i的值,当然,1«i的速度和a[i]差不多,但是面对更复杂的运算时,后者就会相当有效。

  • 如何判断一个10位数是否包含了0-9 10个数字?

我给出下面一份类c的伪代码

function bool is(a){
	bool h[10];
	for(;a!=0;a/=10){
		h[a%10] = true;
	}
	
	for(int i=0;i<10;i++){
		if(!h[i]){
			return false;
		}
	}
	return true;
}

这里用到了一些小技巧,比如如何优雅的取出这个十位数的每一位数字,当然,如果你用string读取了它,那么这一步就变成了简单的循环。

利用return立即结束函数的性质,可以避免flag变量的使用,也简洁了代码。

当然最重要的,这里的数组不再是数字的容器,而是成了标记这个数字是否出现过的记录表。事实上,把数组想象成记录表而不是一个普通的数字序列,应该是编程技巧入门的第一步。

接下来给出另一个例子。

  • 一个编号为0-n的有n个节点的图,某些点间有带权重的连线,权重为i,如何存储这张图?

最简单,粗暴的方法便是用一个Map[n][n]的数组来记录这一切,这里的Map就像是一张表格。

缺陷

当然,你应该意识到了其缺陷,在第二个例子中,假如n的值达到了10000,你的数组便不堪重负,而且其间充斥着null,因为有很多点直接没有连线。(c语言没有null,所以一般标记为-1等特定的数。)

另一个缺陷是其不擅长记录一个自变量区间很大的映射关系,比如一个1一个1e16,你不能为他们两组映射而创建一个1e16的数组出来。当然这时候你可以想办法用点数学运算压缩他们的区间,这种方法被称作Hash(哈希)。

进化

高级语言解决了我们的这个烦恼,名为Map的类可以任意添加映射关系,名为HashMap的类拥有和数组一样的速度—-而且你不必考虑复杂的Hash(相对的,Map采用的是很有效率的树状数据结构存储,但是其比数组法要慢一个数量级,前者是O(logn),后者是O(1),如果你知道y=logn和y=1的图像,就知道他们依然有着差距)。

另一种名为lua的语言更为可怕,以至于其整个代码本身就是一个数组,估计只有解释语言才能做到这一点。如果学这个语言估计满脑子只剩数组了。

因此,如果你不是c语言初学者,说不定已经拿出了这些好用的工具。但是我得指出,这类基础的理解,依然很重要的。而且数组比起那些类来说,其实轻便的多。


Similar Posts

Comments