Java学习笔记：数据结构之数组队列

爱被打了一巴掌 2022-03-22 07:10 130阅读 0赞

# 一、数组的优点和缺点？ #

*  优点：

按索引查找方便、快速。

*  缺点：

1.  根据内容查找元素速度慢；
2.  大小在确定之后不可改变：若空间不够，导致越界，若空间太大，会浪费
3.  一般情况下，只能存储一种类型的数据
4.  增加删除元素很复杂度高
5.  数组的操作需要用户定义

#    二、数组队列的实现原理 #

*  创建数组必须要有大小。
 *  数组名中存储的是数组对象在内存空间的首地址。
 *  数组覆盖可以把新数组的首地址给原地址，原数组由回收机制处理（java虚拟机），释放内存

# 三、数组队列的实现 #

*  数组队列：定义类，封装对数组的操作。
 *  数组队列的要求：

1.  一般情况下，数组队列中只能存储某一种数据类型，如果加入泛型或者用Java的基类Object定义数组，则可以使用任意的数据类型。
2.  泛型<E>、<K、V>、<T>、... 泛型不是Java中的一种数据类型，泛型是一个特殊的符号，在不确定要存储什么类型的数据时，可以用这个符号来代替类型，与C++里面的<Type>/<Template>类似。若不指定类型，默认数组队列的数组类使用的是Object。

相当于

char a; => T a;

值得注意的是在Java中Object是所有类的父类。

若数组队列类中定义的是Object类的数组，那么这个数组可以保存任意的类型。

//类型属性
    	private Object[] array=null;
    	//数组队列中存储的元素
    	private int size=0;
    	/**
    	 * 构造方法
    	 * 
    	 */
    	public MyArrayList(){
    		array=new Object[0];
    	}
    	public MyArrayList(int length){
    		array=new Object [length];
    	}

# 四、练习 #

1.实现数组队列  
2.使用数组队列存储学生信息(名字、学分、年龄)，针对名字、学分、年龄采用不同的排序方式。

学生信息Student类

主要用到的是构造函数、显示学生信息的方法、get分数、年龄、姓名等属性。

package com.MyArrayList;
    
    public class Student {
    	public int score;
    	protected char sex;
    	int age;
    	private String name;
    
    	public Student(int score, char sex, int age, String name) {
    		this.score = score;
    		this.sex = sex;
    		this.age = age;
    		this.name = name;
    	}
    	public int getage(){
    		return age;
    	}
    	public int getscore(){
    		return score;
    	}
    	public String toString() {
    		return "姓名：" + name + "\t年龄：" + age + "\t性别：" + sex + "\tr学分：" + score;
    	}
    
    	// 如果属性的访问修饰符不是public，则要给属性定义public的get和set方法
    	// 定义设置姓名属性值的方法
    	public void setName(String n) {
    		name = n;
    	}
    
    	// 定义获取姓名属性值的方法
    	public String getName() {
    		return name;
    	}
    	// 定义学习方法
    	void study() {
    		score++;
    		System.out.println(name + "正在学习中，学分是" + score);
    	}
    }

数组队列类：

包含了属性的基本操作、插入、删除、清空、交换位置等方法。

由于用到了泛型，在这个类中各个对象的属性会不同，没有添加排序方法。

package com.MyArrayList;
    
    public class MyArrayList <E>{
    	
    	//类型属性
    	private Object[] array=null;
    	//数组队列中存储的元素
    	private int size=0;
    	/**
    	 * 构造方法
    	 * 
    	 */
    	public MyArrayList(){
    		array=new Object[0];
    	}
    	public MyArrayList(int length){
    		array=new Object [length];
    	}
    	/**
    	 * 获取数组元素的个数
    	 * @return
    	 */
    	public int getsize(){
    		return size;
    	}
    	/**
    	 * 获取索引位置的数据
    	 */
    	public E getObject(int index){
    		if(index<0||index>size){
    			return null;
    		}
    		return (E) array[index];
    	}
    	/**
    	 * 获取索引数据的这个索引号
    	 * @param a
    	 * @return
    	 */
    	public int getindex(E a){
    		for(int i=0;i<size;i++){
    			if(array[i]==a){
    				return i;
    			}
    		}
    		return -1;
    	}
    	
    	/**
    	 * 在数组最后一个位置添加一个数据
    	 * @param a
    	 */
    	public void add(E a){
    		//判断数组长度是否为0或者数组是否以满
    		if(array.length==0||array.length==size){
    			//创建一个新的数组对象，长度=array数组的长度+1
    			Object[] newarray=new Object[array.length+1];
    			for(int i=0;i<array.length;i++){
    				newarray[i]=array[i];
    			}
    			//原来的数组首地址等于新的首地址
    			array=newarray;
    		}
    		//将数据存入到array数组中
    		array[size++]=a;
    	}
    	/**
    	 * 在指定位置(index)插入一个数据
    	 * 只能在size中插入数据
    	 * 返回true/false
    	 */
    	public boolean add(int index,E a){
    		if(index<0||index>size){
    			return false;
    		}
    		if(array.length==0||array.length==size){
    			//创建一个新的数组对象，长度=array数组的长度+1
    			Object[] newarray=new Object[array.length+1];
    			for(int i=0;i<array.length;i++){
    				newarray[i]=array[i];
    			}
    			//原来的数组首地址等于新的首地址
    			array=newarray;
    		}
    		for(int i=size;i>index;i--){
    			array[i]=array[i-1];
    		}
    		array[index]=a;
    		size++;
    		return true;
    	}
    	/**
    	 * 指定位置加入一个数组
    	 * 返回true说明插入成功，返回false说明插入失败
    	 */
    	public boolean addArray(int index,MyArrayList <E> mal){
    		//索引判断
    		if(index<0||index>size){
    			return false;
    		}
    		//如果当前数组的位置不够
    		if(array.length==0||array.length-size<mal.getsize()){
    			//创建一个新的数组对象，长度等于array.length+mal.getsize
    			Object []newarray=new Object [array.length+mal.getsize()];
    			for(int i=0;i<array.length;i++){
    				newarray[i]=array[i];
    			}
    			//新地址给原地址
    			array=newarray;
    		}
    		//index位置以后的数据往后移mal.getxize个单位
    		for(int i=size+mal.getsize()-1;i>index+mal.getsize();i--){
    			array[i]=array[i-mal.getsize()];
    		}
    		
    		//插入index位置的数据
    		for(int i=index;i<index+mal.getsize();i++){
    			array[i]=mal.getObject(i-index);
    		}
    		//array[index]=a;
    		size+=mal.getsize();
    		return true;
    	}
    	/**
    	 * 移除一个索引位置的数据
    	 */
    	public E remove(int index){
    		if(index<0||index>=size){
    			return null;
    		}
    		Object a=array[index];
    		for(int i=index;i<size-1;i++){
    			array[i]=array[i+1];
    		}
    		size--;
    		return (E)a;
    	}
    	/**
    	 * 移除一个指定数据
    	 */
    	public int remove(E a){
    		int index=this.getindex(a);
    		if(index>0){
    			this.remove(index);
    		}
    		return index;
    	}
    	/**
    	 *替换索引为index的元素为stu
    	 * @param index
    	 * @param stu
    	 */
    	public E update(int index,E stu){
    		if(index<0||index>=size){
    			return null;
    		}
    		Object a=array[index];
    		array[index]=stu;
    		return (E)a;
    	}
    	
    	/**
    	 * 全部替换为newstu
    	 * @param newstu
    	 */
    	public void updateall(E newstu){
    		for(int i=0;i<size;i++){
    			array[i]=newstu;
    		}
    	}
    	
    	public void swap(int d1,int d2){
    		E s=this.update(d1, this.getObject(d2));
    		this.update(d2, s);
    		
    	}
    	
    	/**
    	 * 清空数组
    	 * @return
    	 */
    	public int clear(){
    		for(int i=0;i<size;i++){
    			array[i]=null;
    		}
    		size=0;
    		return size;
    	}
    	
    }

主函数：

很多操作为了测试程序搞得有点长，如果是有针对性地用数组操作可以选择某一功能

随机数生成方法：

Random rand=new Random();
            int a=rand.nextInt(100);//表示100内的随机数

对分数和年龄排序，用的是简单的冒泡

System.out.println("对mal学分降序排序：");
    		for(int i=0;i<mal.getsize();i++){
    			for(int j=i;j<mal.getsize();j++){
    				if(mal.getObject(i).getscore()<mal.getObject(j).getscore()){
    					mal.swap(i, j);
    				}
    			}
    		}
    		for (int i = 0; i < mal.getsize(); i++) {
    			Object s = mal.getObject(i);
    			System.out.println(s.toString());
    		}
    		
    		System.out.println("对mal年龄降序排序：");
    		for(int i=0;i<mal.getsize();i++){
    			for(int j=i;j<mal.getsize();j++){
    				if(mal.getObject(i).getage()<mal.getObject(j).getage()){
    					mal.swap(i, j);
    				}
    			}
    		}

很长的main函数：

package com.MyArrayList;
    
    import java.util.Random;
    
    public class Manage {
    	public static void main(String [] args){
    		MyArrayList<Student> mal=new MyArrayList <Student> (0);
    		MyArrayList<Student> newmal=new MyArrayList<Student>(0);
    		//随机数生成
    		Random rand=new Random();
    		int a=rand.nextInt(100);//表示100内的随机数
    		/**
    		 * mal
    		 */
    		int size=10;
    		System.out.println("newmal要添加的元素个数为："+size);
    		for(int i=0;i<size;i++){
    			//int score, char sex, int age, String name
    			//随机输入法
    //			Student stu=new Student(rand.nextInt(100), rand.nextInt(2) == 0 ? '男' : '女', rand.nextInt(6) + 17,
    //					"姓名" + ((char) (rand.nextInt(26) + 97)));
    			Student stu=new Student(i*3%10,i%2==0? '男':'女',(i+10)%20,"name"+((char)('A'+i)));
    			mal.add(stu);
    		}
    		/**
    		 * newmal
    		 */
    		size =3;
    		System.out.println("newmal要添加的元素个数为："+size);
    		for(int i=0;i<size;i++){
    			//int score, char sex, int age, String name
    			Student stu=new Student(i*3%10,i%2==0? '男':'女',(i+10)%20,"name"+((char)('a'+i)));
    			newmal.add(stu);
    		}
    		
    		System.out.println("mal数组队列中存储的元素总数为:"+mal.getsize());
    		for(int i=0;i<mal.getsize();i++){
    			Object stu=mal.getObject(i);
    			System.out.println(stu.toString());
    		}
    		System.out.println("newmal数组队列中存储的元素总数为:"+mal.getsize());
    		for(int i=0;i<newmal.getsize();i++){
    			Object stu=newmal.getObject(i);
    			System.out.println(stu.toString());
    		}
    		System.out.println("mal中从索引3插入NewStudent：");
    		Student NewStudent=new Student(10,'0',19,"www");
    		System.out.println("NewStudent:"+NewStudent.toString());
    		mal.add(3, NewStudent);
    		for (int i = 0; i < mal.getsize(); i++) {
    			Object s = mal.getObject(i);
    			System.out.println(s.toString());
    		}
    		System.out.println("mal替换索引5为NewStudent：");
    		mal.update(5, NewStudent);
    		for (int i = 0; i < mal.getsize(); i++) {
    			Object s = mal.getObject(i);
    			System.out.println(s.toString());
    		}
    		
    		System.out.println("mal中从索引3插入newmal：");
    		//Student NewStudent=new Student(10,'0',19,"www");
    		mal.addArray(3, newmal);
    		for (int i = 0; i < mal.getsize(); i++) {
    			Object s = mal.getObject(i);
    			System.out.println(s.toString());
    		}
    		System.out.println("移除数组队列中索引为5的数据");
    		Object stu = mal.remove(5);
    		System.out.println("要移除的数据是：" + stu.toString());
    
    		
    		System.out.println("数组队列中存储的元素总数为：" + mal.getsize());
    		for (int i = 0; i < mal.getsize(); i++) {
    			stu = mal.getObject(i);
    			System.out.println(stu.toString());
    		}
    		System.out.println("对mal学分降序排序：");
    		for(int i=0;i<mal.getsize();i++){
    			for(int j=i;j<mal.getsize();j++){
    				if(mal.getObject(i).getscore()<mal.getObject(j).getscore()){
    					mal.swap(i, j);
    				}
    			}
    		}
    		for (int i = 0; i < mal.getsize(); i++) {
    			Object s = mal.getObject(i);
    			System.out.println(s.toString());
    		}
    		
    		System.out.println("对mal年龄降序排序：");
    		for(int i=0;i<mal.getsize();i++){
    			for(int j=i;j<mal.getsize();j++){
    				if(mal.getObject(i).getage()<mal.getObject(j).getage()){
    					mal.swap(i, j);
    				}
    			}
    		}
    		for (int i = 0; i < mal.getsize(); i++) {
    			Object s = mal.getObject(i);
    			System.out.println(s.toString());
    		}
    		
    		System.out.println("mal全部替换为NewStudent：");
    		mal.updateall(NewStudent);
    		for (int i = 0; i < mal.getsize(); i++) {
    			Object s = mal.getObject(i);
    			System.out.println(s.toString());
    		}
    		mal.clear();
    		System.out.println("清除所有数据后的mal.size()="+mal.getsize());
    		
    	}
    }

为了方便debug就用简单的ABCD表示人名，mal数组取长度10，newmal取3，也可以用随机数来。

运行结果

newmal要添加的元素个数为：10
    newmal要添加的元素个数为：3
    mal数组队列中存储的元素总数为:10
    姓名：nameA	年龄：10	性别：男	r学分：0
    姓名：nameB	年龄：11	性别：女	r学分：3
    姓名：nameC	年龄：12	性别：男	r学分：6
    姓名：nameD	年龄：13	性别：女	r学分：9
    姓名：nameE	年龄：14	性别：男	r学分：2
    姓名：nameF	年龄：15	性别：女	r学分：5
    姓名：nameG	年龄：16	性别：男	r学分：8
    姓名：nameH	年龄：17	性别：女	r学分：1
    姓名：nameI	年龄：18	性别：男	r学分：4
    姓名：nameJ	年龄：19	性别：女	r学分：7
    newmal数组队列中存储的元素总数为:10
    姓名：namea	年龄：10	性别：男	r学分：0
    姓名：nameb	年龄：11	性别：女	r学分：3
    姓名：namec	年龄：12	性别：男	r学分：6
    mal中从索引3插入NewStudent：
    NewStudent:姓名：www	年龄：19	性别：0	r学分：10
    姓名：nameA	年龄：10	性别：男	r学分：0
    姓名：nameB	年龄：11	性别：女	r学分：3
    姓名：nameC	年龄：12	性别：男	r学分：6
    姓名：www	年龄：19	性别：0	r学分：10
    姓名：nameD	年龄：13	性别：女	r学分：9
    姓名：nameE	年龄：14	性别：男	r学分：2
    姓名：nameF	年龄：15	性别：女	r学分：5
    姓名：nameG	年龄：16	性别：男	r学分：8
    姓名：nameH	年龄：17	性别：女	r学分：1
    姓名：nameI	年龄：18	性别：男	r学分：4
    姓名：nameJ	年龄：19	性别：女	r学分：7
    mal替换索引5为NewStudent：
    姓名：nameA	年龄：10	性别：男	r学分：0
    姓名：nameB	年龄：11	性别：女	r学分：3
    姓名：nameC	年龄：12	性别：男	r学分：6
    姓名：www	年龄：19	性别：0	r学分：10
    姓名：nameD	年龄：13	性别：女	r学分：9
    姓名：www	年龄：19	性别：0	r学分：10
    姓名：nameF	年龄：15	性别：女	r学分：5
    姓名：nameG	年龄：16	性别：男	r学分：8
    姓名：nameH	年龄：17	性别：女	r学分：1
    姓名：nameI	年龄：18	性别：男	r学分：4
    姓名：nameJ	年龄：19	性别：女	r学分：7
    mal中从索引3插入newmal：
    姓名：nameA	年龄：10	性别：男	r学分：0
    姓名：nameB	年龄：11	性别：女	r学分：3
    姓名：nameC	年龄：12	性别：男	r学分：6
    姓名：namea	年龄：10	性别：男	r学分：0
    姓名：nameb	年龄：11	性别：女	r学分：3
    姓名：namec	年龄：12	性别：男	r学分：6
    姓名：nameF	年龄：15	性别：女	r学分：5
    姓名：nameD	年龄：13	性别：女	r学分：9
    姓名：www	年龄：19	性别：0	r学分：10
    姓名：nameF	年龄：15	性别：女	r学分：5
    姓名：nameG	年龄：16	性别：男	r学分：8
    姓名：nameH	年龄：17	性别：女	r学分：1
    姓名：nameI	年龄：18	性别：男	r学分：4
    姓名：nameJ	年龄：19	性别：女	r学分：7
    移除数组队列中索引为5的数据
    要移除的数据是：姓名：namec	年龄：12	性别：男	r学分：6
    数组队列中存储的元素总数为：13
    姓名：nameA	年龄：10	性别：男	r学分：0
    姓名：nameB	年龄：11	性别：女	r学分：3
    姓名：nameC	年龄：12	性别：男	r学分：6
    姓名：namea	年龄：10	性别：男	r学分：0
    姓名：nameb	年龄：11	性别：女	r学分：3
    姓名：nameF	年龄：15	性别：女	r学分：5
    姓名：nameD	年龄：13	性别：女	r学分：9
    姓名：www	年龄：19	性别：0	r学分：10
    姓名：nameF	年龄：15	性别：女	r学分：5
    姓名：nameG	年龄：16	性别：男	r学分：8
    姓名：nameH	年龄：17	性别：女	r学分：1
    姓名：nameI	年龄：18	性别：男	r学分：4
    姓名：nameJ	年龄：19	性别：女	r学分：7
    对mal学分降序排序：
    姓名：www	年龄：19	性别：0	r学分：10
    姓名：nameD	年龄：13	性别：女	r学分：9
    姓名：nameG	年龄：16	性别：男	r学分：8
    姓名：nameJ	年龄：19	性别：女	r学分：7
    姓名：nameC	年龄：12	性别：男	r学分：6
    姓名：nameF	年龄：15	性别：女	r学分：5
    姓名：nameF	年龄：15	性别：女	r学分：5
    姓名：nameI	年龄：18	性别：男	r学分：4
    姓名：nameb	年龄：11	性别：女	r学分：3
    姓名：nameB	年龄：11	性别：女	r学分：3
    姓名：nameH	年龄：17	性别：女	r学分：1
    姓名：namea	年龄：10	性别：男	r学分：0
    姓名：nameA	年龄：10	性别：男	r学分：0
    对mal年龄降序排序：
    姓名：www	年龄：19	性别：0	r学分：10
    姓名：nameJ	年龄：19	性别：女	r学分：7
    姓名：nameI	年龄：18	性别：男	r学分：4
    姓名：nameH	年龄：17	性别：女	r学分：1
    姓名：nameG	年龄：16	性别：男	r学分：8
    姓名：nameF	年龄：15	性别：女	r学分：5
    姓名：nameF	年龄：15	性别：女	r学分：5
    姓名：nameD	年龄：13	性别：女	r学分：9
    姓名：nameC	年龄：12	性别：男	r学分：6
    姓名：nameB	年龄：11	性别：女	r学分：3
    姓名：nameb	年龄：11	性别：女	r学分：3
    姓名：namea	年龄：10	性别：男	r学分：0
    姓名：nameA	年龄：10	性别：男	r学分：0
    mal全部替换为NewStudent：
    姓名：www	年龄：19	性别：0	r学分：10
    姓名：www	年龄：19	性别：0	r学分：10
    姓名：www	年龄：19	性别：0	r学分：10
    姓名：www	年龄：19	性别：0	r学分：10
    姓名：www	年龄：19	性别：0	r学分：10
    姓名：www	年龄：19	性别：0	r学分：10
    姓名：www	年龄：19	性别：0	r学分：10
    姓名：www	年龄：19	性别：0	r学分：10
    姓名：www	年龄：19	性别：0	r学分：10
    姓名：www	年龄：19	性别：0	r学分：10
    姓名：www	年龄：19	性别：0	r学分：10
    姓名：www	年龄：19	性别：0	r学分：10
    姓名：www	年龄：19	性别：0	r学分：10
    清楚所有数据后的mal.size()=0