线性结构

知识点包括1.数组2.栈3.队列4.单链表5.循环链表6.双链表7.递归8.排序算法

1.数组

(1)数组的基本使用

public class Ex01 {
	public static void main(String[] args) {
		int[] arr1 = new int[3];		//动态初始化数组长度，长度一旦定义，不可变
		int length1 = arr1.length;	//获取数组的长度
		System.out.println(length1);	//输出数组长度：3
		
		//手动给数组的3个元素赋值
		arr1[0] = 0;	
		arr1[1] = 1;
		arr1[2] = 2;
		
		//获取数组的第0个元素，即索引为0
		int element0 = arr1[0];	
		System.out.println(element0);	//输出：0		
		
		//遍历数组，输出全部数组的元素，适用于有多个元素
		for(int i = 0;i < arr1.length;i++) {
			System.out.println(arr1[i]);
		}
		
		int[] arr2 = new int[] {0,1,2,3,4,};//静态初始化数组长度及元素，长度一旦定义，不可变
		System.out.println(arr2.length);	//输出：5
		
		//遍历数组，输出全部数组的元素，适用于有多个元素
		for(int i = 0;i < arr2.length;i++) {
			System.out.println(arr2[i]);
		}
		
	}
}

(2).数组元素的添加

解决数组长度一旦定义就不可变的方法：直接创建一个长度比原有数组大的新数组，获取原数组的元素

//想再添加一个元素:77，原有数组长度不够，增长数组长度
/*思路:原数组添加元素：创建比原数组长的新数组，
新数组获取原数组的元素，在新数组处添加新元素，
最后把新数组的内存地址赋给旧数组*/
import java.util.Arrays;
public class Ex01 {
	public static void main(String[] args) {	
		int[] arr = new int[3];		//动态初始化数组长度
		//手动给数组的3个元素赋值
		arr[0] = 0;	
		arr[1] = 1;
		arr[2] = 2;
		int newElement = 77;	//需要添加的目标新元素
		
		//创建一个比原有数组长度多一的新数组
		int[] newArr = new int[arr.length+1];	
		for(int i = 0;i < arr.length;i++) {	//遍历使新数组获取旧数组的元素
			newArr[i] = arr[i];	
		}
		
		//把目标元素放于新数组的最后一位
		newArr[arr.length] = newElement;
		System.out.println(Arrays.toString(newArr));	//方法Arrays.toString(数组),输出数组元素
		
		//newArr的内存地址赋值给arr
		System.out.println("arr增长前数组元素:" + Arrays.toString(arr));
		arr = newArr;	
		System.out.println("arr增长后数组元素:" +Arrays.toString(arr));
		
	}
}

(3)数组元素的删除

//删除数组指定元素
/*思路:原数组删除指定元素：创建长度比原数组短的新数组，
遍历给新数组赋值，除了旧数组的指定删除元素*/
import java.util.Arrays;
public class Ex01 {
	public static void main(String[] args) {
		//静态初始化原数组
		int[] arr = new int[] {11,22,33,44,55,66};
		int muBiao = 3;	//删除数组的第四个元素，即索引为3
		
		//创建一个长度小1的新数组来存储原数组指定元素被删后的所有元素
		int[] newArr = new int[arr.length - 1];
		//遍历给newArr赋值，除了目标删除元素
		for(int i = 0;i < newArr.length;i++) {
			//如果i小于目标索引，则newArr正常赋值
			if(i < muBiao)
				newArr[i] = arr[i];
			//否则newArr[i] = arr[i+1]这样赋值
			else
				newArr[i] = arr[i + 1];
		}
		System.out.println("删除元素前的arr数组:"+Arrays.toString(arr));
		arr = newArr;
		System.out.println("删除元素后的arr数组:"+Arrays.toString(arr) );
		
		
	}
}

(4)面向对象的数组

import java.util.Arrays;

//用面向对象的思想，自定方法，把获得数组长度、打印数组、增加、删除、插入、返回元素功能封装在一起
public class MyArr {
	private int[] arr;//用于存储数据的数组
	
	public MyArr() {//MyArr构造器
		arr = new int[0];
	}
	
	//自定义方法1:得到数组的长度
	public int size() {
		return arr.length;
	}
	
	//自定义方法2:打印数组
	public void show() {
		System.out.println("数组为:"+Arrays.toString(arr));
	}
	
	//自定义方法3:增加元素，往末尾添加一个元素
	public void add(int element) {
		//创建一个比原数组长度+1的新数组用于存储
		int[] newArr = new int[arr.length+1];
		for(int i = 0;i < arr.length;i++) {
			newArr[i] = arr[i];
		}
		//需要添加的元素赋值
		newArr[arr.length] = element;
		//新数组替换旧数组
		arr = newArr;
	}
	
	//自定义方法4:删除元素，删除数组指定元素
	public void delete(int index) {
		//创建一个比原数组长度-1的新数组用于存储
		int[] newArr = new int[arr.length-1];
		for(int i = 0;i < newArr.length;i++) {
			if(i < index)
				newArr[i] = arr[i];
			else
				newArr[i] = arr[i+1];
		}
		//新数组替换旧数组
		arr = newArr;
	}
	
	//自定义方法5:插入元素,在指定位置插入元素
	public void insert(int index,int element) {
		//创建长度+1的新数组存储旧数组
		int[] newArr = new int[arr.length+1];
		//判定条件
		for(int i = 0;i < newArr.length;i++) {
			if(i < index) {
				newArr[i] = arr[i];
			}else if(i == index) {
				newArr[i] = element;
			}else {
				newArr[i] = arr[i-1];
			}
		}
		//新数组替换旧数组
		arr = newArr;
	}
	
	//自定义方法6:返回指定索引的数组元素
	public int getElement(int index) {
		return arr[index];
	}

	//自定义方法7:替换指定位置的元素
	public void set(int index,int element) {
		arr[index] = element;
	}
}

import java.util.Arrays;

public class Test {
	public static void main(String[] args) {
		MyArr myArr = new MyArr();
		//调用size()方法,输出数组长度
		System.out.println("数组长度为:"+myArr.size());//输出结果:数组长度为:0
		
		//测试增加元素是否成功
		myArr.add(1);
		myArr.add(2);
		//调用size()方法,输出调用add()方法增加元素后的数组长度
		System.out.println("数组长度为:"+myArr.size());	//输出结果:数组长度为:2
		
		//输出未删除时数组元素情况
		myArr.show();	//输出结果:数组为:[1, 2]
		myArr.delete(0);//删除数组索引为0的元素
		//输出删除后数组元素情况
		myArr.show();	//输出结果:数组为:[2]
		
		//测试插入元素方法insert(),在索引0的地方插入77
		myArr.insert(0, 77);
		myArr.show();	//输出结果:数组为:[77, 2]
		//在索引1的地方插入88
		myArr.insert(1, 88);
		myArr.show();	//输出结果:数组为:[77, 88, 2]
		//在索引3的地方插入99
		myArr.insert(3, 99);
		myArr.show();//输出结果:数组为:[77, 88, 2, 99]
		//测试getElement方法,返回索引为3的数组元素
		System.out.println(myArr.getElement(3));//输出结果:99
		//测试set()方法,替换指定元素
		myArr.set(3, 98);
		System.out.println(myArr.getElement(3));//输出结果:98
	}
	
}

(5).查找算法-线性查找

//线性查找的方法，返回所需要搜索的元素下下标
//思路:一个一个顺序地查就是线性查找
public class Test {
	public static void main(String[] args) {
//		静态初始化数组
		int[] arr = new int[] {11,22,33,44,55,66,77};
//		假定搜索目标元素为33
		int target = 33;
//		假定没有目标元素则返回索引-1
		int index = -1;
//		循环一个一个元素地去判断
		for(int i = 0;i < arr.length;i++) {
			if(arr[i] == target)
				index = i;
		}
		System.out.println("目标索引为:"+index);
	}	
}

(6).查找算法-二分法查找

//用二分法查找指定数组元素，返回该元素的索引(前提是数组元素小到大有序排序)
/*思路：对半对半的判断，先用一个int middle变量来划分，判断arr[middle]和目标元素target的大小关系
	(1).若arr[middle] > target，则说明target在arr[middle]的左方,向左对半对半找
	(2).若arr[middle] < target，则说明target在arr[middle]的右方,向右对半对半找
	(3).若arr[middle] == target，则说明target就是arr[middle],放回middle就是该元素的索引
	注意middle可以动态变化跟着变化着的begin和end，具体思路看代码
	实现方法如下:
*/
public class Test {
	public static void main(String[] args) {
		//静态初始化数组
		int[] arr = new int[] {11,22,33,44,55,66,77,88};
		//假定需要找的目标元素为33
		int target = 33;
		//存储目标元素的索引,默认为未找到,返回值为-1
		int index = -1;
		//初始化定义变量begin,end,middle的关系,进而middle=(begin+end)/2
		int begin = 0,end = arr.length - 1,middle = (begin+end)/2;
		//弄一个while(true)的循环来实现不断地对半搜索判断
		while(true) {
			//判断找不到的条件,begin>end的时候不能取=，因为begi =end的时候有可能就是目标索引
			if(begin > end) {
				break;
			}
			
			//说明target就是arr[middle],放回middle就是该元素的索引
			if(arr[middle] == target) {
				index = middle;
				break;//跳出循环
			}
			if(arr[middle] > target) {
				//target在arr[middle]的左方,向左对半对半找,此时end的值要改为middle-1的值
				//因为arr[middle] 不等于 target,所以排除middle这个索引,改成middle - 1
				end = middle - 1;
				//新的middle值
				middle = (begin+end)/2;
			}
			if(arr[middle] < target) {
				//target在arr[middle]的右方,向右对半对半找,此时begin的值要改为middle的值
				//此时同理 begin = middle + 1
				begin = middle + 1;
				//新的middle值
				middle = (begin+end)/2;
			}		
		}
		System.out.println("所查找的元素索引为:"+index);	//输出结果:所查找的元素索引为:2
		
	}
}