Java数据结构与算法 Java学习资料

package com.bing.Data_Structures_and_Algorithms.Datastructure.linkedList; import java.util.Stack; public class SingleLinkedListDome { public static void main(String[] args) { //测试 //先创建几个节点 HeroNode hero1 = new HeroNode(1, "松江", "呼保义"); HeroNode hero2 = new HeroNode(2, "无用", "智多星"); HeroNode hero3 = new HeroNode(3, "卢俊义", "玉麒麟"); HeroNode hero4 = new HeroNode(4, "林冲", "豹子头"); SingleLinkedList singleLinkedList = new SingleLinkedList(); // singleLinkedList.add(hero1); // singleLinkedList.add(hero4); // singleLinkedList.add(hero2); // singleLinkedList.add(hero3); //按照编号加入 singleLinkedList.addByOrder(hero1); singleLinkedList.addByOrder(hero4); singleLinkedList.addByOrder(hero2); singleLinkedList.addByOrder(hero3); //singleLinkedList.addByOrder(hero3); singleLinkedList.show(); System.out.println("修改后"); //修改 HeroNode heroNode = new HeroNode(2, "无用2", "智多星2"); singleLinkedList.update(heroNode); singleLinkedList.show(); HeroNode heroNode2 = new HeroNode(4, "无用2", "智多星2"); // System.out.println("开始删除"); // singleLinkedList.delete(1); // singleLinkedList.delete(2); // singleLinkedList.delete(3); // singleLinkedList.delete(4); singleLinkedList.show(); System.out.println(singleLinkedList.length()); System.out.println(singleLinkedList.getK(3)); } } //定义一个SingleLinkedList 管理我们的英雄 class SingleLinkedList { //初始化一个头结点，头结点不要动 不存放具体的数据 private HeroNode head = new HeroNode(0, "", ""); //返回头节点 public HeroNode getHead() { return head; } //反转链表 public void reverese() { //如果当前链表为空,或者只有一个节点,就无需反转直接返回 if (head.next == null || head.next.next == null) { return; } //定义一个辅助指针, HeroNode cur = head.next; HeroNode next = null; //指向当前[cur]节点的下一个节点 HeroNode reve = new HeroNode(0, "", ""); //遍历原来的链表,并从头到尾遍历每一个节点,j就将其取出,并放在新的链表reverseHead 的最前端 //动脑筋 while (cur != null) { //先保存当前节点的下一个节点,因为后面要用 next = cur.next; cur.next = reve.next; //将cur的下一个节点指向新的链表的头部 reve.next = cur; cur = next;//让cur后移 } //将head.next 指向reve.next,实现反转 head.next = reve.next; } //获取倒数第k个 public HeroNode getK(Integer k) { int length = length(); Integer i = length - k; if (i < 0 || k > length) { System.out.println("链表没有那么多元素"); return null; } HeroNode temp = head; for (int j = 1; j <= k; j++) { temp = temp.next; } return temp; } //获取有效节点 public int length() { if (head.next == null) { //空 return 0; } int length = 0; //这里我们没有统计头节点 //定义一个辅助变量 HeroNode cur = head.next; while (cur != null) { length++; cur = cur.next; } return length; } //添加节点到单项列表 //当不考虑编号的顺序时 // 找到当前链表的最后节点 // 将最后节点的next域指向新的节点 public void delete(Integer i) { HeroNode temp = head; boolean flag = false; if (temp.next == null) { System.out.println("链表为空"); return; } while (true) { if (temp.next == null) { System.out.println("该节点不存在"); break; } if (temp.next.no == i) { flag = true; break; } temp = temp.next; } if (flag) { temp.next = temp.next.next; } else { System.out.printf("没有找到编号%d的节点,不能删除\n", i); } } public void add(HeroNode hero) { // 因为head节点不能动，因此我们需要的一个辅助节点遍历 temp HeroNode temp = head; //遍历链表，找到最后 while (true) { // if (temp.next == null) { break; } //如果没有找到就将temp后移 temp = temp.next; } temp.next = hero; //当退出while循环时，temp就指向了 最后 } //第二种添加英雄的方式,根据英雄排名讲英雄插入到指定位置如果有这个排名,则添加失败 public void addByOrder(HeroNode hero) { //因为头节点不能动,使用辅助指针帮助找到添加的位置 //因为是单链表,因为我们找的temp是位于,添加位置的前一个结点,否则插入不了 HeroNode temp = head; boolean flag = false;//标识添加的的编号是否存在默认为false while (true) { if (temp.next == null) {//说明链表为空,头节点后面没有节点 break; } if (temp.next.no > hero.no) {//位置找到,就在temp后面插入 break; } else if (temp.next.no == hero.no) { flag = true;//说明编号存在 break; } temp = temp.next; //后移,遍历当前链表 } if (flag) { System.out.printf("当前便后存在不能添加,该英雄编号为 %d \n", hero.no); } else { //插入到链表中 temp后面 hero.next = temp.next; temp.next = hero; } } //修改节点的信息, //根据新节点的编号来修改 public void update(HeroNode hero) { if (head.next == null) { System.out.println("链表为空"); return; } //找到修改的节点 //创建辅助节点 HeroNode temp = head.next; boolean flag = false; while (true) { if (temp == null) { break;//已经遍历完 } if (temp.no == hero.no) { //找到了 flag = true; break; } temp = temp.next; } //根据falg判断是否找到 if (flag) { temp.name = hero.name; temp.nickname = hero.nickname; } else { System.out.printf("没有找到编号%d的节点,不能修改\n", hero.no); } } //显示链表 public void show() { if (head.next == null) { System.out.println("链表为空"); return; } //因为头结点不能动 HeroNode temp = head.next; while (true) { //判断是否到最后 if (temp == null) { break; } //输出节点信息 System.out.println(temp); //讲next后移 temp = temp.next; } } } //定义一个HeroNode ，每一个HeroNode就是一个节点 class HeroNode { public int no; public String name; public String nickname; public HeroNode next;//指向下一个节点 public HeroNode() { } public HeroNode(int no, String name, String nickname) { this.no = no; this.name = name; this.nickname = nickname; } //为了显示方�