线性结构
知识点包括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
}
}