大家好 我是makasa
这个栏目呢，我会按照我之前通过视频学习的一个笔记来记录.
同时,通过写这几篇blog来巩固一下我的基础
数据结构与算法，顾名思义，分为两个部分：数据结构、算法。那它们各自具体概述是什么呢。让我们看以下两个图，简单明了。这里大概了解以下即可。
下面我们重点来讲以下线性结构。
首先线性结构分为：
1.以顺序存储方式存储的线性结构：
①数组(最大可取到长度-1、数组长度不可变)
如何解决数组长度不可变：创建一个新数组，长度为原数组+1(添加)或者-1(删除)
②栈：(先进后出)例：子弹夹
③队列(先进先出)例：排队买票
2.以链表存储方式存储的线性结构：
①单链表：
②循环链表
③双链表
然后，在这里呢，我们重点提一下数组里面的查找算法
查找算法包括：
①线性查找：即定义一个数组、进行遍历，查找元素和数组元素相等即可
②二分查找(效率高):应用面不广，因为要求目标数组有序.
下面贴一下数组的代码(增删改查)
package cn.makasa;
import java.util.Arrays;public class MyArray {//定义一个数组private int[] elements;//构造方法public MyArray(){elements = new int[0];}//返回数组的长度public int size(){return elements.length;}/*** 一、在数组末尾添加一个元素*/public void add(int element) {//1.定义一个新的数组：长度为原数组长度+1int[] newArray = new int[elements.length + 1];//2.遍历原数组，把原数组的值赋值给新数组for (int i = 0; i < elements.length; i++) {newArray[i] = elements[i];}//3.在数组末尾添加一个元素：添加元素的下标 等于 原数组的长度 即： newArray[elements.length] = element;//4.把新数组赋值给原数组elements = newArray;}/*** 二、打印所有元素显示在控制台*/public void show(){System.out.println(Arrays.toString(elements));}/*** 三、删除数组中的元素*/public void delete(int index){//1.判断下标是否越界if (index< 0 || index > elements.length-1){throw new RuntimeException("下标越界");}//2.定义一个新数组 长度为原数组的长度-1int[] newArray = new int[elements.length-1];//3。遍历新数组，如果在删除元素之前的元素 ：直接赋值 若在删除元素之后的元素：值加1for (int i = 0;i<newArray.length;i++){if(i<index){newArray[i] = elements[i];}else {newArray[i] = elements[i+1];}}//4.把新数组赋值给旧数组elements = newArray;}/*** 四、得到每一个元素*/public int get(int index){return elements[index];}/*** 五、插入一个元素到指定位置*/public void insert(int index,int element){//1.定义一个新数组 长度为原数组的长度+1int[] newArr = new int[elements.length+1];//2.遍历原数组，判断 如果i<index 直接赋值 如果新数组for(int i = 0;i<elements.length;i++){if (i<index){newArr[i] = elements[i];}else {newArr[i+1] = elements[i];}}newArr[index] = element;//替换原数组elements = newArr;}//替换指定位置的元素public void set(int index,int element){elements[index] = element;}/*** 六、线性查找*/public int search(int target) {for(int i =0;i<elements.length;i++){if(elements[i] == target){return i;}}return -1;}/*** 七、二分查找*/public int binarySearch(int target){int begin = 0;int end = elements.length-1;int mid = (begin+end)/2;int index = -1;while (true){//什么情况下没有这个元素?//如果开始在结束位置之后或者重合,没有这个元素if(begin>=end){return -1;}if(elements[mid] == target){return mid;}else {if (elements[mid]>target){end=mid-1;}else {begin = mid+1;}mid = (begin+end)/2;}}}
}
测试类：
package makasaTest;import cn.makasa.MyArray;public class testArray {public static void main(String[] args) {//创建数组对象MyArray ma = new MyArray();//获取数组长度int size = ma.size();System.out.println("原数组长度为"+size);//显示所有元素ma.show();//添加元素ma.add(9);ma.add(8);ma.add(7);ma.show();//删除某个元素ma.delete(1);ma.show();System.out.println(ma.get(1));System.out.println("==============");//插入一个元素ma.insert(0,100);ma.show();//修改元素ma.set(2,100);ma.show();}
}
输出结果：
原数组长度为0
[]
[9, 8, 7]
[9, 7]
7
============
[100, 9, 7]
[100, 9, 100]
