Java数据结构和算法之应用单链表解决实际问题

题目： 使用带head头的单向链表实现 –水浒英雄排行榜管理

1. 完成对英雄人物的增删改查操作， 注: 删除和修改,查找可以考虑学员独立完成，也可带学员完成
2. 第一种方法在添加英雄时，直接添加到链表的尾部
3. 第二种方式在添加英雄时，根据排名将英雄插入到指定位置(如果有这个排名，则添加失败，并给出提示)

单链表原理：

代码如下：

package com.guigu.LinkedListDemo;

public class SingleLinkedListDemo {

	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 linkList = new SingleLinkedList();
		
//		linkList.add(hero1);
//		linkList.add(hero2);
//		linkList.add(hero3);
//		linkList.add(hero4);
		
//		linkList.showSingleLinkedList();
		
		System.out.println("测试有序插入节点：");
		linkList.addByOrder(hero1);
		linkList.addByOrder(hero4);
		linkList.addByOrder(hero2);
		linkList.addByOrder(hero3);
		
		linkList.showSingleLinkedList();
		
		linkList.del(2);
		System.out.println("删除后的链表：");
		linkList.showSingleLinkedList();
		
		HeroNode newHeroNode = new HeroNode(3, "公孙胜", "入云龙");
		linkList.update(newHeroNode);
		System.out.println("修改后的链表：");
		linkList.showSingleLinkedList();
	}
	
}

//创建一个类用来管理英雄，其实就是创建一个个单链表，对节点进行管理操作
class SingleLinkedList{
	private HeroNode head = new HeroNode(0, "", ""); //初始化一个头结点，头结点不能动，不存放具体数据
	
	//添加节点
	public void add(HeroNode newHeroNode) {
		//定义一个辅助指针，来查找链表的最后一个节点
		HeroNode temp = head;
		while(true) {
			if(temp.next == null) { //说明到走到了最后一个节点 
				break;
			}
			temp = temp.next; //如果不是最后一个节点，temp往后移
		}
		//退出while是，temp就指向了最后一个节点，此时将最后节点的next指向新的节点
		temp.next = newHeroNode;
	}
	
	//第二种方式在添加英雄时，根据排名将英雄插入到指定位置
	//(如果有这个排名，则添加失败，并给出提示)
	//按编号来插入节点
	public void addByOrder(HeroNode newHeroNode) {
		//因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
		//因为是单链表，因为我们找的temp 是位于 添加位置的前一个节点，否则插入不了
		HeroNode temp = head;
		boolean isFlag = false; //表示要查入的节点是否已存在
		while(true) {
			if(temp.next == null) { //到最后一个节点了
				break;
			}
			if(temp.next.no > newHeroNode.no) { //找到了插入位置
				break;
			}else if(temp.next.no == newHeroNode.no){ //要插入的节点已经存在了，不能重复插入
				isFlag = true;
				break;
			}
			temp = temp.next;
		}
		if(isFlag) {
			System.out.println("节点已经存在了~~");
		}else {
			//插入到链表中, temp的后面
			newHeroNode.next = temp.next;
			temp.next = newHeroNode;
		}
	}
	
	//删除节点，按照英雄的序号来删除节点
	public void del(int no) {
		if(isEmpty()) {
			System.out.println("链表为空，没有可删除的节点~~");
			return;
		}
		boolean isFlag = false; //表示是否找到要删除的元素
		HeroNode temp = head; //头结点不能动，借助辅助节点来找要删除节点的前一个位置
		while(true) {
			if(temp.next == null) { //说明到头了
				break;
			}
			if(temp.next.no == no) { //说明找到了
				isFlag = true; //置为true
				break;
			}
			temp = temp.next; //temp往后移
		}
		if(isFlag) {
			temp.next = temp.next.next;
		}else {
			System.out.println("未找到要删除的节点~~");
		}
	}
	
	//根据 newHeroNode 的 no 来修改即可
	public void update(HeroNode newHeroNode) {
		//判断是否空
		if(head.next == null) {
			System.out.println("链表为空~");
			return;
		}
		//找到需要修改的节点, 根据no编号
		//定义一个辅助变量
		HeroNode temp = head.next;
		boolean flag = false; //表示是否找到该节点
		while(true) {
			if (temp == null) {
				break; //已经遍历完链表
			}
			if(temp.no == newHeroNode.no) {
				//找到
				flag = true;
				break;
			}
			temp = temp.next;
		}
		//根据flag 判断是否找到要修改的节点
		if(flag) {
			temp.name = newHeroNode.name;
			temp.nickName = newHeroNode.nickName;
		} else { //没有找到
			System.out.printf("没有找到 编号 %d 的节点，不能修改n", newHeroNode.no);
		}
	}
	
	//遍历链表
	public void showSingleLinkedList() {
		if(isEmpty()) {
			System.out.println("链表为空~~");
			return;
		}
		HeroNode cur = head.next; //定义个游标
		while(true) {
			if(cur == null) { //遍历完了
				break; 
			}
			System.out.println(cur); //输出节点信息
			cur = cur.next; //游标往后移
		}
	}
	
	//判断链表是否为空
	public boolean isEmpty() {
		return head.next == null;
	}
}

//创建一个英雄类，每个实例化对象就是一个节点
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;
	} 
	//为了方便显示，我们重写toString()
	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + ", nickName=" + nickName + "]";
	}
}

运行结果：（按照无序插入节点的运行方式没有列出）

测试有序插入节点：
HeroNode [no=1, name=宋江, nickName=及时雨]
HeroNode [no=2, name=卢俊义, nickName=玉麒麟]
HeroNode [no=3, name=吴用, nickName=智多星]
HeroNode [no=4, name=林冲, nickName=豹子头]
删除后的链表：
HeroNode [no=1, name=宋江, nickName=及时雨]
HeroNode [no=3, name=吴用, nickName=智多星]
HeroNode [no=4, name=林冲, nickName=豹子头]
修改后的链表：
HeroNode [no=1, name=宋江, nickName=及时雨]
HeroNode [no=3, name=公孙胜, nickName=入云龙]
HeroNode [no=4, name=林冲, nickName=豹子头]

总结： 这不仅仅是单链表的实现，而是应用单链表去解决实际问题。注意的是，当插入数据时，要是按照英雄序号插入的话，你要先找到他的位置。根据就是：当下一个节点的序号大于要插入节点的序号是，就找到了插入位置，但是如果下一个节点的序号等于要插入节点的序号，就说明这个节点已经插入 了，不能再重复插入。

最后

以上就是背后奇迹为你收集整理的Java数据结构和算法之应用单链表解决实际问题的全部内容，希望文章能够帮你解决Java数据结构和算法之应用单链表解决实际问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。