数据结构 数组的介绍

数据结构之--数组

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

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

如何使用面向对象操作数据结构：

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

学会将程序划分成类：

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

理解；

抽象的概念：

从what中将how分离出来的过程，即类中的操作如何进行，相对什么事类用户可见的，被称为抽象。抽象是软件工程的重要方面。

把类的功能抽象出来后，可以使程序设计更简单，因为不需要在设计的初期就考虑细节问题；

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

在数组中的查找方式：

线性查找：按顺序，逐一的进行匹配；

二分查找：将数组数据项范围不断对半分割来查找特定的数据项。在有序数组中占有很大的优势；

二分查找的核心代码：

/*使用二分查找的算法*/

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，可以认为其含义是"orderof"（大约是）,我们可以使用大O表示

法来描述线性查找使用了O(N)级时间，二分查找使用了O(logN)级时间，向一个无序数组中的插入

使用O(1),或常数级时间；

大O表示法的实质并不是对运行时间给出实际值，而是表达了运行时间是如何受数据项个数所影响的。

除了实际安装后真正测量一次算法的运行时间之外，这可能是对算法进行比较的最有意义的方法了；