【蓝桥杯】必备的java数据结构和常⽤⽅法
⽂章⽬录
⼀.线性表
1.顺序表的实现
静态数组
java只有在为数组分配变量时，可以声明数组长度
java：int[]  a;
a = new int [3];//可以⽤变量
但是java的数组是⽐较特殊的对象，所以需要借助别的类来实现数组的⼀些
(1)取值 a[i][j]
(2)遍历可以采⽤foreach的形式for(int c : a){}
(3)增加(插⼊)，删除都需要根据数组的规律将后置位的元素移动；修改，直接修改
(4)查调⽤Arrays类的binarySearch ⽅法(⼆分查)
int a[]={1,2,3};
int x;
x= Arrays.binarySearch(a,2);
(5)排序 Arrays.sort⽅法
public static void sort(doule a[])
public static void sort(doule a[],int start,int end);
int[]a ={55,33,44,22,11};
int[]b = pyOfRange(a,1,4);
Arrays.sort(a,1,4);
(6)数组复制 pyOf
copyOf⽅法原型：public static float[] copyOf(float []original,int newLength)
从数组的第⼀个元素开始复制，复制长度为length，若长度超过数组原长，则超出元素为默认值0
int[]a ={11,22,33,44,55};
int[]b = pyOf(a,7);
copyOfRange⽅法原型：public static double[] copyOfRange(double []original,int from,int to)
从original下标为from的位置开始复制，到to-1的位置结束，返回⼀个长度为to-from的数组== 下标范围这种的基本都是从from到to-1所指的元素==
(7)数组转list
Arrays.asList(T… a) 或者Collections.addAll
因为前者返回的是list对象没有增删，只能查改
返回⼀个受指定数组⽀持的固定⼤⼩的列表。（对返回列表的更改会“直接写”到数组。）此⽅法同 Array() ⼀起，充当了基于数组的 API 与基于 collection 的 API 之间的桥梁。返回的列表是可序列化的，并且实现了 RandomAccess。
此⽅法还提供了⼀个创建固定长度的列表的便捷⽅法，该列表被初始化为包含多个元素：
//int[]不能直接转成integer的list
String[] strArray =new String[2];
ArrayList<String> list =new ArrayList<String>(Arrays.asList(strArray));
//或者⾥⾯直接是⼀个数组
String[] strArray =new String[2];
ArrayList< String> arrayList =new ArrayList<String>(strArray.length);
Collections.addAll(arrayList, strArray);
(8)初始化:Arrays.fill
（1）public static void fill(byte[] a, byte val)
将指定的 byte 值分配给指定 byte 节型数组的每个元素。
（2）public static void fill(byte[] a,int fromIndex,int toIndex,byte val)
将指定的 byte 值分配给指定 byte 型数组指定范围中的每个元素。填充的范围从索引 fromIndex（包括）⼀直到索引 toIndex（不包括）。（如果 fromIndex==toIndex，则填充范围为空。）
动态数组
ArrayList 继承了AbstractList，实现了List。它是⼀个数组队列，提供了相关的添加、删除、修改、遍历等功能
和Vector不同，ArrayList中的操作不是线程安全的！
(1)构造
// 默认构造函数
ArrayList()
// capacity是ArrayList的默认容量⼤⼩。当由于增加数据导致容量不⾜时，容量会添加上⼀次容量⼤⼩的⼀半。
ArrayList(int capacity)
// 创建⼀个包含collection的ArrayList
ArrayList(Collection<?extends E> collection)
(2)取值: get(int index)
(3)增删改查(⾃动移位)
boolean add(Element e)增加指定元素到链表尾部.
void add(int index, Element e)增加指定元素到链表指定位置.
void clear()从链表中删除所有元素.
E remove(int index)删除链表中指定位置的元素.
protected void removeRange(int start, int end)删除链表中从某⼀个位置开始到某⼀个位置结束的元素。
E set(int index, E element)将链表中指定位置上的元素替换成新元素。注意不能直接赋值
boolean contains(Object o)如果链表包含指定元素，返回true.
int indexOf(Object o)返回元素在链表中第⼀次出现的位置，如果返回-1，表⽰链表中没有这个元素。
int lastIndexOf(Object o)返回元素在链表中最后⼀次出现的位置，如果返回-1，表⽰链表中没有这个元素。
(4)逆置
(5)排序
Collections.sort()传⼊ArrayList，会采⽤默认的⽅式进⾏排序（字典序）
2.链表的实现
LinkedList和ArrayList⼀样是实现了List,API没太⼤区别，但是本质上还是有些区别
ArrayList底层是数组结构，LinkList底层是链表结构。
1.对于随机访问get和set，ArrayList优于LinkedList，因为LinkedList要移动指针。
对于新增和删除操作add和remove，LinedList⽐较占优势，因为ArrayList要移动数据。
⼆.栈
Stack来⾃于Vector，那么显然stack的底层实现是数组。
java中Stack只有⼀个⽆参构造函数。
属于stack⾃⼰的⽅法包括
push( num) //⼊栈
pop() //栈顶元素出栈
empty() //判定栈是否为空
peek() //获取栈顶元素
search(num) //判端元素num是否在栈中，如果在返回1，不在返回-1。
注意pop()和peek()的区别。pop()会弹出栈顶元素并返回栈顶的值，peek()只是获取栈顶的值，但是并不会把元素从栈顶弹出来。
Stack<Integer> st =new Stack<Integer>();
三.队列
队列是⼀种特殊的线性表，它只允许在表的前端进⾏删除操作，⽽在表的后端进⾏插⼊操作。
LinkedList类实现了Queue接⼝，因此我们可以把LinkedList当成Queue来⽤。虽然是线程不安全和⾮阻塞的，但是在⼀般的问题中⾜够了.        Queue<String> queue =new LinkedList<String>();
add()和remove()⽅法在失败的时候会抛出异常(不推荐)queue的增加元素⽅法add和offer的区别在于，add⽅法在队列满的情况下将选择抛异常的⽅法来表⽰队列已经满了，⽽offer⽅法通过返回false表⽰队列已经满了；在有限队列的情况，使⽤offer⽅法优于add⽅法
public boolean offer(E e)，向链表末尾添加元素，返回是否成功；
public boolean offerFirst(E e)，头部插⼊元素，返回是否成功；
public boolean offerLast(E e)，尾部插⼊元素，返回是否成功；
public void clear()，清空链表；
public E poll()，删除并返回第⼀个元素；
public E peek()，返回第⼀个元素；
public E peekFirst()，返回头部元素；
public E peekLast()，返回尾部元素；
public E set(int index, E element)，设置指定位置的元素；
四.串
String
注意
String 类是不可改变的，所以你⼀旦创建了 String 对象，那它的值就⽆法改变了(但是可以使引⽤类型变量指向另⼀个字符串对象)如果需要对字符串做很多修改，那么应该选择使⽤ StringBuffer & StringBuilder 类。
创建字符串常量时，JVM会⾸先检查字符串常量池，如果该字符串已经存在常量池中，那么就将此字符串对象的地址赋值给引⽤s（引⽤s在Java栈中）。如果字符串不存在常量池中，就会实例化该字符串并且将其放到常量池中，并将此字符串对象的地址赋值给引⽤s（引⽤s在Java栈中）。
关于equals和== ：
（1）对于==，如果作⽤于基本数据类型的变量则直接⽐较其存储的"值"是否相等；如果作⽤于引⽤类型的变量（String），则⽐较的是所指向的对象的地址（即是否指向同⼀个对象）。
（2）对于equals⽅法，注意：equals⽅法不能作⽤于基本数据类型的变量。如果没有对equals⽅法进⾏重写，则⽐较的是引⽤类型的变量所指向的对象的地址；⽽String类对equals⽅法进⾏了重写，⽤来⽐较指向的字符串对象所存储的字符串是否相等。其他的⼀些类诸如Double，Date，Integer等，都对equals⽅法进⾏了重写⽤来⽐较指向的对象所存储的内容是否相等。
常⽤⽅法
public char charAt (int index) ：返回指定索引处的 char值，不能直接说是修改
public int indexOf (String str) ：返回指定⼦字符串第⼀次出现在该字符串内的索引，没有返回-1
public String substring (int beginIndex) ：返回⼀个⼦字符串，从beginIndex开始截取字符串到字符串结尾。
public String substring (int beginIndex, int endIndex) ：返回⼀个⼦字符串，从beginIndex到endIndex截取字符串。含beginIndex，不含endIndex。
public char[] toCharArray () ：将此字符串转换为新的字符数组。
public String replace (CharSequence target, CharSequence replacement) ：将与target匹配的字符串使⽤replacement字符串替换。
public String[] split(String regex) ：将此字符串按照给定的regex（规则）拆分为字符串数组。
String StringBuffer 和 StringBuilder
StringBuilder 它和 StringBuffer 之间的最⼤不同在于 StringBuilder 的⽅法不是线程安全的（不能同步访问）。
由于 StringBuilder 相较于 StringBuffer 有速度优势，所以多数情况下建议使⽤ StringBuilder 类。
StringBuilder sb =new StringBuilder();//⽆参构造⽅法，默认容量是16
StringBuilder sb =new StringBuilder(int capacity);//指定容量的字符串缓冲区对象
StringBuilder sb =new StringBuilder(String string);//指定字符串内容的字符串缓冲区对象
StringBuilder和String的相互替换
String------->StringBuilder
（1）通过构造⽅法
（2）通过StringBuilder的append或者insert⽅法
StringBuilder------->String
（1）通过toString()⽅法
（2）通过substring(0,length)⽅法
⼤部分⽅法和String相同java replace方法
public StringBuffer append(String s)
将指定的字符串追加到此字符序列。
public StringBuffer reverse()
将此字符序列⽤其反转形式取代。
public delete(int start, int end)
移除此序列的⼦字符串中的字符。
public insert(int offset, int i)
将 int 参数的字符串表⽰形式插⼊此序列中。
replace(int start, int end, String str)
使⽤给定 String 中的字符替换此序列的⼦字符串中的字符。
public String substring(int start, int end) 截取从指定位置开始到结束位置，包括开始位置，不包括结束位置（注意：返回值不再是StringBuffer本⾝，⽽是String）
五.树和⼆叉树
/**
* TreeNode: 普通的树节点
*/
public class TreeNode<T>{
T value;
TreeNode<T> leftChild;
TreeNode<T> rightChild;
TreeNode(T value){
this.value = value;
}
TreeNode(){
}
/**  增加左⼦节点
* addLeft:
* @param value
* void  返回类型
*/
public void addLeft(T value){
TreeNode<T> leftChild =new TreeNode<T>(value);
this.leftChild = leftChild;
}
/**
* addRight: 增加右⼦节点
* @param value
* void  返回类型
*/
public void addRight(T value){
TreeNode<T> rightChild =new TreeNode<T>(value);
this.rightChild = rightChild;
}
/* (non-Javadoc)
* @see java.lang.Object#equals(java.lang.Object)
* 重载equal⽅法⽤来判断节点所对应的值是否相等
*/
@Override
public boolean equals(Object obj){
// TODO Auto-generated method stub
if(!(obj instanceof TreeNode)){
return false;
}
return this.value.equals(((TreeNode<?>)obj).value); }
/* (non-Javadoc)
* @see java.lang.Object#hashCode()
* 重载hashCode⽅法
*/
@Override
public int hashCode(){
// TODO Auto-generated method stub
return this.value.hashCode();
}
@Override
public String toString(){
return this.value==null?"":String();
}
}
⼀些⽅法
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。