数据结构 数组的介绍

数据结构之 --数组

数组是应用的最广泛的数据存储结构，它被植入到大部分编程语言中；

对象的名字就是该对象对应内存地址的引用，并不是对象的本身；

如何使用面向对象操作数据结构：
首先将数据存储结构从程序需中分离出，程序的其他部分称为使用这个结构的用户；第二部则是改进存储结构和用户之间的通信；

学会将程序划分成类：
解释：数据存储结构本身就是累，程序中使用这个结构的部分也是类，通过将长须划分成两个类，可以使程序的功能清晰，使之更加容易设计和
理解；

抽象的概念：
从what中将how分离出来的过程，即类中的操作如何进行，相对什么事类用户可见的，被称为抽象。抽象是软件工程的重要方面。
把类的功能抽象出来后，可以使程序设计更简单，因为不需要在设计的初期就考虑细节问题；

小贴士：用来存储数据对象的类有时被称为容器类；(container class);

在数组中的查找方式：
线性查找：按顺序，逐一的进行匹配；
二分查找：将数组数据项范围不断对半分割来查找特定的数据项。在有序数组中占有很大的优势；

二分查找的核心代码：
/* 使用二分查找的算法 */

	long[] b = {1,2,3,4,5,6,7};
	public int find(long searchKey){
		int lower = 0;
		int upper = b.length-1;	//
		int current;
		
		while(true){
			current = (lower+upper)/2;
			if(b[current] == searchKey){
				return current;
			}else if(lower>upper){
				return b.length;
			}else{
				if(b[current]<searchKey){
					lower = current+1;
				}else{
					upper = current-1;
				}
			}
		}
		
	}

有序数组：
优点：使用有序数组最大的优点是查找的速度比无序数组快的多了；
不足：插入删除比较慢；

对数：使用对数的一个方程可以求出二分查找中步数对应的范围；
每次对范围加倍可以创建出一个数列，它是2的幂；设s表示步数，r表示范围，则：
r=2^s
如果已知步数s，通过该方程可以得出范围r;例如：s=6;r=64;

大 O 表示法：用来评价计算机算法的效率；(粗略的度量方法被称作"大O 表示法")；

算法效率示例：

无序数组的插入：无序数组中的插入是见到的唯一一个 与数组中的数据项个数无关的算法，
新数据项总是被放在下一个有空的地方，a[a.length()]，然后该值增加，无论数组中
的数据项个数N有多大，一次插入的总是用相同的时间。那么说明：向一个无序数组中插入一个数据项的
时间T是一个常数K：
                        常数  T=K；

线性查找：与N成正比  (N为数据总数)
寻找特定数据项所需的比较次数平均为数据项总数的一半；因此设N为数据项总数，搜索时间
T与N的一半成正比；
T=K*N/2;
二分查找：
T=K*㏒2(N)
说明：由于所有的对数都和其他对数成比例，那么可以将为底数的常数并入K，不指定底数：
T=K*log(N);


大 O 表示法：
大O表示法在上面表示方法的基础上省去了常数K，当比较算法时，并不在乎具体的微处理芯片或
编译器；真正需要比较的是对应不同的N值，T是如何变化的，而不是具体的数字。因此不需要常数；

大O表示法使用大写字符O，可以认为其含义是"order of"（大约是）,我们可以使用大O表示
法来描述线性查找使用了O(N)级时间，二分查找使用了O(log N)级时间，向一个无序数组中的插入
使用O(1),或常数级时间；

大O表示法的实质并不是对运行时间给出实际值，而是表达了运行时间是如何受数据项个数所影响的。
除了实际安装后真正测量一次算法的运行时间之外，这可能是对算法进行比较的最有意义的方法了；