hsp 单链表增删改查 16-20
作者:
等一下
,
2022-01-27 11:18:34
,
所有人可见
,
阅读 198
hsp 单链表增删改查 16-23
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main{
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 linkedlist = new SingleLinkedList();
linkedlist.add(hero1);
linkedlist.add(hero2);
linkedlist.add(hero3);
linkedlist.add(hero4);
// linkedlist.addByOrder(hero1);
// linkedlist.addByOrder(hero4);
// linkedlist.addByOrder(hero3);
// linkedlist.addByOrder(hero2);
// linkedlist.addByOrder(hero4);
linkedlist.list();
System.out.println("逆序打印,没有改变单链表的结构~~");
linkedlist.reversePrint();
// System.out.println("反转链表后~~");
// linkedlist.reverseList();
// linkedlist.list();
}
}
class SingleLinkedList {
private HeroNode head = new HeroNode(0, "", "");
public void add(HeroNode hero) {
HeroNode tmp = head;
while(true) {
if(tmp.next == null) {
break;
}
tmp = tmp.next;
}
tmp.next = hero;
}
//根据no将英雄插入到指定位置(如果该no已存在,则添加失败,并给出提示)
public void addByOrder(HeroNode hero) {
//由于是单链表,所以我们要找的节点是插入位置的前一个节点,否则插入不了,
//所以我们要让tmp的下一个节点和新节点比较,这样当tmp的下一个节点的no大于新节点时,
//tmp指向插入位置的前一个节点,就能成功插入
HeroNode tmp = head;
boolean flag = false; //标志待添加的英雄的no是否存在,默认为不存在
while(true) {
if(tmp.next == null) {
break;
}
if(tmp.next.no > hero.no) {
break;
} else if(tmp.next.no == hero.no) {
flag = true;
break;
}
tmp = tmp.next;
}
if(flag) {
System.out.printf("待插入的英雄的编号%d已存在,插入失败\n", hero.no);
} else {
hero.next = tmp.next;
tmp.next = hero;
}
}
//删除节点
//思路:
//从单链表中删除一个节点,必须先找到它的前一个节点,所以在遍历的时候,
//是用tmp.next.no和待删除的no进行比较
public void delete(int no) {
if(head.next == null) {
System.out.println("链表为空");
return;
}
HeroNode tmp = head;
boolean flag = false; //标志是否找到待删除节点
while(true) {
if(tmp.next == null) {
break;
}
if(tmp.next.no == no) {
flag = true;
break;
}
tmp = tmp.next;
}
if(flag) {
tmp.next = tmp.next.next;
} else {
System.out.printf("待删除编号为%d的节点不存在,删除失败\n", no);
}
}
//修改编号和newHero.no相同的节点的信息,no不能改
public void update(HeroNode newHero) {
if(head.next == null) {
System.out.println("链表为空");
return;
}
HeroNode tmp = head.next;
boolean flag = false; //标志是否找到待修改节点
while(true) {
if(tmp == null) {
break;
}
if(tmp.no == newHero.no) {
flag = true;
break;
}
tmp = tmp.next;
}
if(flag) {
tmp.name = newHero.name;
tmp.nickname = newHero.nickname;
} else {
System.out.printf("编号为%d的节点不存在,修改失败\n", newHero.no);
}
}
public void list() {
//判断链表是否为空
if(head.next == null) {
System.out.println("链表为空");
return;
}
HeroNode tmp = head.next;
while(true) {
if(tmp == null) {
break;
}
System.out.println(tmp);
tmp = tmp.next;
}
}
//反转单链表
public void reverseList() {
//如果当前链表为空,或者只有一个节点,则无需反转,直接返回
if(head.next == null || head.next.next == null) {
return;
}
HeroNode reverseHead = new HeroNode(0, "", "");
HeroNode tmp = head.next;
HeroNode target;
//遍历原来的链表,每遍历一个节点,就将其取出并放在新的链表reverseHead的最前端
while(tmp != null) {
target = tmp;
tmp = tmp.next;
target.next = reverseHead.next;
reverseHead.next = target;
}
head = reverseHead;
}
//逆序打印单链表
//方式1:先反转单链表,再遍历即可,但这种方式的缺点是会破坏单链表的结构,有没有不改变单链表的结构,
//又能逆序打印的方法呢?见方式2
//方式2:可以利用栈这个数据结构,利用栈先进后出的特点,将单链表的各个节点压入到栈中,然后逆序出栈,
//就实现了逆序打印的效果
public void reversePrint() {
if(head.next == null) {
System.out.println("链表为空");
return;
}
Stack<HeroNode> stack = new Stack();
HeroNode cur = head.next;
//将单链表的各个节点压入栈中
while(cur != null) {
stack.push(cur);
cur = cur.next;
}
//逆序出栈
while(stack.size() > 0) {
System.out.println(stack.pop());
}
}
}
class HeroNode {
public int no;
public String name;
public String nickname;
public HeroNode next;
public HeroNode(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}
public String toString() {
return "HeroNode =" + "[no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
}
}