1、Java实现链表的增、删、查、插入、修改操作
package cn.link;/*** 链表节点类*/public class ListNode {public int val; // 数据public ListNode next; // 下一个节点的数据// 构造方法 通过数据来创建节点public ListNode(int val){this.val = val;}}
package cn.link;/*** 自定义链表实现类*/public class MyLinkedList {// 固定头结点private ListNode head = null;/*** 链表头部插入新节点*/public void addFirst(int data){// 头插法 通过新节点的next 指向 headListNode node = new ListNode(data);node.next = this.head;// 将头结点 指向nodethis.head = node;}/*** 链表尾部插入新节点*/public void addLast(int data){// 尾插法 需要循环到尾部节点再将 curr.next = newNodeListNode node = new ListNode(data);// 定义节点来代替head 循环到最后一个节点ListNode curr = this.head;// 需要先判断该链表是否为空if (this.head == null){this.head = node;}else {// 找到最后节点while (curr.next != null){curr = curr.next;}// 将新节点插入到尾部curr.next = node;}}/*** 获取单链表的长度*/public int length(){int count = 0;ListNode curr = this.head;while (curr != null){curr = curr.next;count++;}return count;}/*** 查找index索引位置的前驱*/public ListNode findIndexPrevNode(int index){ListNode curr = this.head;// 这里 大于1是因为找前驱 并且是默认0开始while (index > 1){curr = curr.next;index--;}return curr;}/*** 通过索引插入节点，默认索引为0开始*/public void addIndex(int index, int data){/*** 通过索引插入到链表需要分以下几点情况* 1、index 位于 头节点* 2、index 位于链表中间* 3、index 位于 尾节点*/// 先判断是否再链表length范围之键if (index < 0 || index > length()){System.out.println("index不合法");return; // 结束方法执行}// 头插法if (index == 0) {this.addFirst(data);return;}// 尾插法if (index == length()){this.addLast(data);return;}// 剩下的就是插入到链表中间的咯，需要先找到index位置的前驱// 这里可以避免代码冗余，将寻找index 提取到一个方法中ListNode curr = findIndexPrevNode(index);ListNode node = new ListNode(data);node.next = curr.next;curr.next = node;}/*** 查找是否存在关键字key在单链表中*/public boolean contains(int key){ListNode curr = this.head;while (curr != null){if (curr.val == key){return true;}curr = curr.next;}return false;}/*** 工具方法 找到 需要删除节点关键字的前驱*/public ListNode findKeyPrev(int key){ListNode curr = this.head;while (curr.next != null){if (curr.next.val == key){return curr;}curr = curr.next;}return null;}/*** 删除第一次出现关键字key 的节点*/public void remove(int key){// 为头结点时if (this.head.val == key){this.head = this.head.next;return;}// 获取前驱ListNode prev = findKeyPrev(key);if (prev == null){System.out.println("链表中不存在"+key+"该数据");return;}//删除操作prev.next = prev.next.next;}/*** 删除所有关键字为key的节点*/public void removeAllByKey(int key){// 前驱ListNode prev = this.head;ListNode curr = this.head.next;while (curr != null) {if (curr.val == key) {// 删除当前节点prev.next = curr.next;}else {// 前驱向后移prev = curr;}curr = curr.next;}//判断第一个节点是否是要删除的节点 上面是双指针方法就会遗漏头结点没有判断if(this.head.val == key) {this.head = this.head.next;}}/*** 打印链表*/public void display(){ListNode curr = this.head;while (curr != null){System.out.print(curr.val+" ");curr = curr.next;}// 换行System.out.println();}/*** 删除链表*/public void clear(){ListNode curr = this.head;//一个个制空while (curr != null) {// 保存当前节点ListNode currNext = curr.next;// 将当前节点的断开curr.next = null;// 进行往下循环操作curr = currNext;}this.head = null;}}
package cn.link;
/**
* 链表测试类
*/
public class LinkedListTest {
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
// 插入值
for (int i = 0; i < 10; i++) {
myLinkedList.addLast(i);
}
myLinkedList.display();
myLinkedList.addFirst(15);
myLinkedList.display();
myLinkedList.addIndex(2,-5);
myLinkedList.display();
myLinkedList.remove(3);
myLinkedList.display();
myLinkedList.remove(18);
myLinkedList.display();
}
}
2、实现二叉树的前序、中序、后序遍历
package cn.tree;
/**
* 二叉树类的定义
*/
public class TreeNode {
TreeNode left; // 指向左孩子
TreeNode right; // 指向右孩子
int val; // 节点储存的数据
// 构造方法
public TreeNode(){}
public TreeNode(int val){
this.val = val;
}
}
package cn.tree;
import java.util.Stack;
/**
* 二叉树的实现
*/
public class MyTreeNode {
/**
* 二叉树的遍历有简单的 遍历方法
* 也可以用复杂一点的非递归方法
* 两种方法的底层都相差不大 都是进栈和出栈
*/
/**
* 递归方法来遍历
*
*/
// 递归调用的方法,需要将root传递进去
public void preOderByRecursion(TreeNode node) {
if (node == null)
return;
System.out.print(node.val+" ");
preOderByRecursion(node.left);
preOderByRecursion(node.right);
}
// 中序遍历
public void inOrderByRecursion(TreeNode root){
if(root==null){
return;
}
inOrderByRecursion(root.left);
System.out.print(root.val+" ");
inOrderByRecursion(root.right);
}
// 后序遍历
public void postOrderByRecursion(TreeNode root){
if(root==null){
return;
}
postOrderByRecursion(root.left);
postOrderByRecursion(root.right);
System.out.print(root.val+" ");
}
/**
* 迭代方法实现
*/
//前序遍历
public void preOrderIteration(TreeNode head) {
if (head == null) {
return;
}
// 使用栈存数据 和递归相似
Stack<TreeNode> stack = new Stack<>();
stack.push(head);
/**
* 前序遍历为 中 -> 左 -> 右
*/
while (!stack.isEmpty()) {
// 将当前节点出栈
TreeNode node = stack.pop();
System.out.print(node.val + " ");
// 若子代不为空就入栈循环输出
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}
// 中序遍历
public void inOrderIteration(TreeNode head) {
if (head == null) {
return;
}
// 定义代替循环指针
TreeNode cur = head;
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || cur != null) {
// 中序遍历为 左->中->右 所以这里需要先找到最左边的子节点
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
// 输出最左边的节点
TreeNode node = stack.pop();
System.out.print(node.val + " ");
// 当栈退到上一节点的root时，判断是否继续上退
if (node.right != null) {
cur = node.right;
}
}
}
// 后序遍历
public void postOrderIteration(TreeNode head) {
if (head == null) {
return;
}
/**
* 后序遍历的 左 -> 右 ->中
* 这里需要1个栈来实现后序的进栈和出栈，1个栈储存数据来输出
* 原因是 如果在stack2.push(node); 直接输出就是前序遍历 中 -> 左 ->右
* 现在需要将其逆转为 中 右 左 然后再出栈就是倒序的遍历，
* 这里的 逆转的中是先根节点到最低子节点的入栈（上到下的入栈，遍历经过就入栈）
* 而 前序的中是指直接从最低节点开始打印（下到上打印root）
*/
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
stack1.push(head);
while (!stack1.isEmpty()) {
TreeNode node = stack1.pop();
stack2.push(node);
if (node.left != null) {
stack1.push(node.left);
}
if (node.right != null) {
stack1.push(node.right);
}
}
while (!stack2.isEmpty()) {
System.out.print(stack2.pop().val + " ");
}
}
}
package cn.tree;
/**
* 二叉树的测试类
*/
public class TreeTest {
public static void main(String[] args) {
MyTreeNode myTreeNode = new MyTreeNode();
TreeNode tree = createTree();
System.out.println();
System.out.println("递归前序遍历--------------");
myTreeNode.preOderByRecursion(tree);
System.out.println();
System.out.println("迭代前序遍历--------------");
myTreeNode.preOrderIteration(tree);
System.out.println();
System.out.println("递归中序遍历--------------");
myTreeNode.inOrderByRecursion(tree);
System.out.println();
System.out.println("迭代中序遍历--------------");
myTreeNode.inOrderIteration(tree);
System.out.println();
System.out.println("递归后序遍历--------------");
myTreeNode.postOrderByRecursion(tree);
System.out.println();
System.out.println("迭代后序遍历--------------");
myTreeNode.postOrderIteration(tree);
}
public static TreeNode createTree(){
TreeNode A=new TreeNode(1);
TreeNode B=new TreeNode(2);
TreeNode C=new TreeNode(3);
TreeNode D=new TreeNode(4);
TreeNode E=new TreeNode(5);
TreeNode F=new TreeNode(6);
A.left=B;
A.right=C;
B.left=D;
B.right=E;
C.left=F;
return A;
}
}
3、给定单链表的头结点head，请反转链表，并返回反转后的链表的头结点
package cn.reverse;
import cn.link.ListNode;
/**
* 反转链表方法集合
*/
public class ReverseSolution {
// 双指针法
public static ListNode reverseListByPointer(ListNode head) {
//申请节点，pre和 curr，pre指向null,curr最为当前节点
// 保存3个结点的比较简单
// 1->2->3->4->5->5
/**
* 第一步 1 指向pre 就是指向null作为尾节点 null <-1 ->2->3->4->5->5
* 第二步 记录pre = 1，curr 为 2 tmp为 3 null <-1 <-2 -> 3->4->5->5
*/
ListNode pre = null;
ListNode curr = head;
//记录当前节点的下一个节点
ListNode tmp = null;
while(curr != null) {
tmp = curr.next;
//然后将当前节点指向pre
curr.next = pre;
//pre和cur节点都前进一位
pre = curr;
curr = tmp;
}
return pre;
}
/**
* 递归解法1
* 虽然是递归解法但是实际上是一个和上面那个解法很相似
*/
// 需要一个 保存上一的循环的pre 这个解法不太行 不靠谱
static ListNode pre = null, tmp = null;
public static ListNode reverseListByRecursion1(ListNode head) {
//递归终止条件是当前为空，或者下一个节点为空 就是找到最后一个节点然后 “归”
if(head == null) {
return pre;
}
// 保存当前节点的后驱节点
tmp = head.next;
// 将当前节点指向前一个节点
head.next = pre;
// 然后再将 前驱节点和当前节点后移
pre = head;
head = tmp;
// 再下一个循环
return reverseListByRecursion1(head);
}
/**
* 递归解法2
*/
public static ListNode reverseListByRecursion2(ListNode head) {
//递归终止条件是当前为空，或者下一个节点为空
if(head==null || head.next==null) {
return head;
}
//这里的cur就是最后一个节点
ListNode cur = reverseListByRecursion2(head.next);
//这里请配合动画演示理解
//如果链表是 1->2->3->4->5，那么此时的cur就是5
// 当 head 位于 4 的时候 4.next = 5 然后再next 就是表示5.next = head
// 而当前的head为4 所已还是逆转回来了
head.next.next = head;
//防止链表循环，需要将head.next设置为空
head.next = null;
//每层递归函数都返回cur，也就是最后一个节点
return cur;
}
public static void main(String[] args) {
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
ListNode node4 = new ListNode(4);
ListNode node5 = new ListNode(5);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = null;
// display(reverseListByPointer(node1));
// System.out.println();
display(reverseListByRecursion1(node1));
System.out.println();
// display(reverseListByRecursion2(node1));
// System.out.println();
}
public static void display(ListNode head){
while (head != null){
System.out.print(head.val+"->");
head = head.next;
}
}
}
4、Java实现文件夹遍历
package cn.file;
/**
* 保存文件信息
* 包括 文件名 文件类型 文件大小 文件后缀
*/
public class FileInfo {
private String fileName; // 文件名
private String fileType; // 文件类型
private int fileSize; // 文件大小
private String suffix; // 文件后缀
public FileInfo() {
}
public FileInfo(String fileName, String fileType, int fileSize, String suffix) {
this.fileName = fileName;
this.fileType = fileType;
this.fileSize = fileSize;
this.suffix = suffix;
}
public String getFileName() {
return fileName;
}
public void setFileName(String fileName) {
this.fileName = fileName;
}
public String getFileType() {
return fileType;
}
public void setFileType(String fileType) {
this.fileType = fileType;
}
public int getFileSize() {
return fileSize;
}
public void setFileSize(int fileSize) {
this.fileSize = fileSize;
}
public String getSuffix() {
return suffix;
}
public void setSuffix(String suffix) {
this.suffix = suffix;
}
@Override
public String toString() {
return "{ fileName='" + fileName + '\'' +
", fileType='" + fileType + '\'' +
", fileSize=" + fileSize +
", suffix='" + suffix + '\'' +
'}';
}
}
package cn.file;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.*;
/**
* 文件实现类 文件信息收集类
* 文件名 文件类型 文件大小 文件后缀的方法
*/
public class FileImpl {
// 保存文件及文件夹的对象信息
private List<FileInfo> fileList = new ArrayList<>();
/**
* 获取当前目录的文件
*/
public void myFileRecursive(String basePath){
// path为一个目录，记录当前访问目录
String path = null;
// 获取当前的目录下 的信息
File file = new File(basePath);
// 当前文件不可读
if (file == null) return;
// 判断当前路径的文件及文件夹列表
String[] listList = file.list();
for (String filePath : listList) {
// 实例化一个对象来储存数据
FileInfo fileInfo = new FileInfo();
// 拼装当前文件的路径
path = basePath + "//" + filePath;
File file1 = new File(path);
// 这里的文件名加了扩展名 也可以截取不加
String fileName = file1.getName();
// 这几行是截取主名
// int pos = fileName.lastIndexOf(".");
// if (pos >0){
// fileName = fileName.substring(0,pos);
// }
fileInfo.setFileName(fileName);
// 判断是否为文件夹 如果为文件夹就不存在文件后缀 和大小
if (file1.isDirectory()){
fileInfo.setFileType("文件夹");
}else {
fileInfo.setFileType("文件");
// 添加当前文件的大小
fileInfo.setFileSize((int) file1.length());
// 文件后缀
fileInfo.setSuffix(filePath.substring(filePath.lastIndexOf(".")));
}
// 保存到list
fileList.add(fileInfo);
// 判断当前file是否为文件夹 如果是则将子文件再次递归
if (file1.isDirectory()){
myFileRecursive(path);
}
}
}
/**
* 传入path
* 将文件列表存入txt文件中,只需要将上面的list存入即可
*/
public void saveFileInfoToTxt(String path){
// 判断是否存在该文件
File file = new File(path);
if (!file.exists()){
try {
file.createNewFile();
} catch (IOException e) {
e.printStackTrace();
}
}
// 这里我们只需要将 文件对象的字符串存入就行 通过字符流
FileWriter writer = null;
try {
// 这里是new 一个字符流 默认追加
writer = new FileWriter(file,true);
for (FileInfo fileInfo : fileList) {
writer.write(fileInfo.toString()+"\n");
// 刷新流 输入下一个字符
writer.flush();
}
} catch (IOException e) {
e.printStackTrace();
}finally {
// 关闭流
try {
writer.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
}
package cn.file;
import java.util.Scanner;
/**
* 文件的测试类
*/
public class FileInfoTest {
public static void main(String[] args) {
// 输入文件路径
String path =null;
//Scanner scanner = new Scanner(System.in);
//path = scanner.next();
path = "E:\\tmp";
FileImpl fileImpl = new FileImpl();
// 传入basePath
fileImpl.myFileRecursive(path);
// 再将文件list储存到txt 中
String savePath = "E:\\files.txt";
fileImpl.saveFileInfoToTxt(savePath);
}
}
最后大家需要注意自己的代码格式哦！可以去百度找找Java开发规范的代码格式，一些命名格式等等，尽量慢慢养成习惯。
若有收获，就点个赞吧
0 人点赞
