利用Java编写常用数据结构函数
常用数据结构函数是指在程序设计和开发中，使用频率较高的一些数据结构的操作函数。常用数据结构主要包括数组、链表、栈、队列、树等。下面将介绍Java中常用数据结构的相关函数。
1. 数组
数组是一种最基本的数据结构之一，它可以存储相同类型的一组元素。在Java中，数组的大小和类型一旦确定就无法修改，因此，我们需要使用一些基本的数组函数进行操作。常用的数组函数包括：
（1）数组的定义和初始化
int[] arr = new int[10]; //定义一个大小为10的整型数组
int[] arr = {1,2,3,4,5}; //定义一个已知元素的整型数组
（2）数组的遍历
int[] arr = {1,2,3,4,5};
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+" ");
}
（3）数组的复制
int[] arr1 = {1,2,3,4,5};
int[] arr2 = new int[arr1.length];
System.arraycopy(arr1,0,arr2,0,arr1.length); //将arr1复制到arr2中
（4）数组的排序
int[] arr = {5,4,3,2,1};
Arrays.sort(arr); //对数组进行升序排序
2. 链表
链表是一种常用的非连续存储结构，它将元素存储在一个个节点中，每个节点包含指向下一个节点的指针。链表可以分为单向链表、双向链表和循环链表。常用的链表函数包括：
（1）链表的定义和初始化
class Node{
int val;
Node next;
}
Node head = new Node(); //定义一个空的头节点
head.next = null; //头节点的下一个节点为null
（2）链表的遍历
Node p = head.next;
while(p!=null){
System.out.print(p.val+" ");
p = p.next;
}
（3）链表的插入和删除
Node p = head.next;
Node q = new Node();
q.val = 5;
while(p!=null){
if(p.val==3){
q.next = p.next;
p.next = q;
break;
}
p = p.next;
}
Node p = head.next;
while(p.next!=null){
if(p.next.val==3){
p.next = p.next.next;
break;
}
p = p.next;
}
3. 栈
栈是一种常用的数据结构，它采用后进先出的原则，即最后进栈的元素最先出栈。栈可以用数组或链表来实现。常用的栈函数包括：
（1）栈的定义和初始化
Stack<Integer> st = new Stack<Integer>(); //定义一个整型栈
（2）栈的入栈和出栈
st.push(1); //将1入栈
int top = st.pop(); //将栈顶元素出栈，并将其赋值给top变量
（3）栈的判空和取栈顶元素
boolean flag = st.empty(); //判断栈是否为空
int top = st.peek(); //返回栈顶元素，但是不出栈
4. 队列
队列是一种先进先出的数据结构，即 队列的元素最先出队列。队列可以用数组或链表来实现。常用的队列函数包括：
（1）队列的定义和初始化
Queue<Integer> q = new LinkedList<Integer>(); //定义一个整型队列
（2）队列的入队和出队
q.offer(1); //将1入队
int front = q.poll(); //将队首元素出队，并将其赋值给front变量
（3）队列的判空和取队首元素
boolean flag = q.isEmpty(); //判断队列是否为空
int front = q.peek(); //返回队首元素，但是不出队
5. 树
树是一种重要的数据结构，它分为二叉树、平衡树、二叉搜索树等。常用的树函数包括：
（1）二叉树的遍历
class TreeNode{
int val;
TreeNode left;
TreeNode right;
}
public void preOrder(TreeNode root){ //二叉树的先序遍历
if(root!=null){
System.out.print(root.val+" ");
preOrder(root.left);
preOrder(root.right);
}
}
public void inOrder(TreeNode root){ //二叉树的中序遍历
if(root!=null){
inOrder(root.left);
System.out.print(root.val+" ");
inOrder(root.right);
}
}
public void postOrder(TreeNode root){ //二叉树的后序遍历
if(root!=null){
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val+" ");
}
}
（2）平衡树和二叉搜索树的遍历和增删查改
平衡树和二叉搜索树是一种重要的树形数据结构，常用的函数包括：
public void insert(int val){ //二叉搜索树的插入操作
if(root==null){
root = new TreeNode(val);
}
else{
TreeNode p = root;
while(true){
if(val<p.val){
if(p.left==null){
p.left = new TreeNode(val);
break;
}
p = p.left;
}
else{
if(p.right==null){
p.right = new TreeNode(val);
break;
}
p = p.right;
}
}
}
}
public boolean find(int val){ //二叉搜索树的查找操作
TreeNode p = root;
while(p!=null){
if(val<p.val){
p = p.left;
}
else if(val>p.val){
p = p.right;
}
else{
return true;
}
}
return false;
}
public void delete(int val){ //二叉搜索树的删除操作
TreeNode p = root,pre=null;
while(p!=null){
if(val<p.val){
pre = p;
p = p.left;
}
else if(val>p.val){
pre = p;
p = p.right;
}
else{
if(p.left==null&&p.right==null){ //情况1：要删除的节点是叶子节点
if(pre==null){
root = null;
}
else if(p==pre.left){
pre.left = null;
}
else{
pre.right = null;
}
}
else if(p.left==null){ //情况2：要删除的节点只有右子树
if(pre==null){
root = p.right;
}
else if(p==pre.left){
pre.left = p.right;
}
else{
pre.right = p.right;
}
}
else if(p.right==null){ //情况3：要删除的节点只有左子树
if(pre==null){
root = p.left;
}
else if(p==pre.left){
pre.left = p.left;
}
else{
pre.right = p.left;
}
}
else{ //情况4：要删除的节点有左右子树
TreeNode q = p.right,preq = null;
while(q.left!=null){
preq = q;
q = q.left;
}
p.val = q.val;
if(preq==null){
p.right = q.right;
}
else{
preq.left = q.right;
}
}
break;
}
}
}
以上是Java中常用数据结构的相关函数，通过掌握这些函数，我们可以更好地对常用数据结构进行操作。