简析数据结构——可变数组

这次我们先简单了解一下数据结构以及我们程序员常见的一个引用类型-数组【可变长】。

 

一、集合框架类
       1、数据结构： 存储数据的容器，不同的结构体现为数据的存储方式以及数据之间的关系不一样

            结构包括：结构体，类，数组，长度可变数组，堆栈，向量，队列，集合，映射，链表，树[二叉树]， 图

            数据结构的具体操作：

                                      1.增加数据

                                      2.删除数据

                                      3.修改数据

                                      4.查询数据  

                                      5.取出数据      

                                      6.数据的个数

        2、泛型：从jdk1.5新增加的语法
                       在定义的时候将类定义成一个变量，等到具体使用的时候[创建对象的时候]在明确这个类的类型
                       只能用在成员方法和构造方法中
                       泛型的具体化必须是一个引用类型

                       如果创建对象的时候没有给泛型具体化，会默认使用Object类来具体化泛型

 

        3、可变数组的具体实现

/**
 * 自定义长度可变数组
 * @author liuqingjian
 */
//<E>是泛型的定义，便于各种类型使用
public class MyAarry_<E> {
	private Object[] src = new Object[0];
	//初始长度
	private int num = 0;
	private int initsize = 10;// 容量值，每次扩充的长度，方便减少损耗时间

	//构造方法，用于用户初始化容量值
	public MyAarry_(int initsize) {
		this.initsize = initsize;
		Object[] dest = new Object[src.length + initsize];
		src = dest;
	}

	/**
	 * 存放数据
	 * 
	 * @param s
	 *            要存放的数据
	 */
	public void add(E s) {
		// 如果没放满，继续放
		if (num >= src.length) {
			// 如果已经满了，就增加数组容量
			Object[] dest = new Object[src.length + initsize ];
			// 将原数组拷贝到新数组
			System.arraycopy(src, 0, dest, 0, src.length);
			//还原到原数组
			src = dest;
		}
		src[num++] = s;
	}

	/**
	 * 取出数据
	 * 
	 * @param index
	 *            要取出数据的下标
	 */
	public E get(int index) {
		if (index >= 0 && index < num) {
			//定义一个Object的变量储存src的下标为index值
			Object s = src[index];
			//返回下标为index的值
			return (E) s;
		}

		//没有则返回null
		return null;
	}

	/**
	 * 根据下标删除数据
	 * 
	 * @param index
	 *            删除数据的下标
	 */
	public void delete(int index) {
		//将index之后的数据往前挪一位
		System.arraycopy(src, index + 1, src, index, num - index - 1);
		num--;
		if (num % initsize  == 0) {
			// 如果容量超过数量容量initsize 了，就减少数组容量
			Object[] dest = new Object[num];
			// 将原数组拷贝到新数组
			System.arraycopy(src, 0, dest, 0, num);
			src = dest;
		}
	}

	/**
	 * 删除数据
	 * 
	 * @param s
	 *            要删除的数据，如果有重复的数据，就删除下标最小的
	 */
	public void delete(E s) {
		//标记
		int index = -1;

		//逐个寻找s的下标
		for (int i = 0; i < num; i++) {
			if (s.equals(src[i])) {
				index = i;
				break;
			}
		}
		if (index == -1) {
			//没有就返回错误
			System.err.println("该数组中没有" + s);
		} else {
			//否则就删除该下标的数据
			delete(index);
		}
	}

	/**
	 * 将数据插入到指定位置
	 * 
	 * @param index
	 *            要插入的位置
	 * @param s
	 *            要插入的数据
	 */
	public void insert(int index, E s) {
		//如果src数组里还有空白，则index以及之后的数据往后挪一位
		if (num >= 0 && num < src.length) {
			for (int i = num; i > index; i--) {
				src[i] = src[i - 1];
			}
		} else {//否则就需要开辟新的空间，再复制
			Object dest[] = new Object[src.length + initsize];
			System.arraycopy(src, 0, dest, 0, index);
			System.arraycopy(src, index, dest, index + 1, num - index);
			src = dest;
		}
		src[index] = s;
		num++;
	}

	/**
	 * 修改数据
	 * 
	 * @param index
	 *            要修改的数据的下标
	 * @param s
	 *            修改后的数据
	 */
	public void update(int index, E s) {
		//直接改变src数组下标index的值
		src[index] = s;
	}

	/**
	 * 获得数组长度
	 * 
	 * @return 数组长度
	 */
	public int size() {
		return num;
	}
}