【数据结构】用数据结构给水浒做了个英雄榜

简介: 【数据结构】用数据结构给水浒做了个英雄榜

链表

链表(Linked List)介绍 :

链表是有序的列表,但是它在内存中是存储如下

1.png



链表是以节点的方式来存储,是链式存储

每个节点包含 data 域, next 域:指向下一个节点.

如图:发现链表的各个节点不一定是连续存储.

链表分带头节点的链表和没有头节点的链表,根据实际的需求来确定


单向链表

单向链表存储节点思路图

2.png



单链表的应用实例

使用带 head 头的单向链表实现 –水浒英雄排行榜管理完成对英雄人物的增删改查操作

我们都知道 水浒传里有108位英雄吧

我们这里随便举例四个,我们想用链表的方式把他们放入我们的英雄榜里(单向链表)

新增,修改,删除的思路

添加英雄:


根据排名将英雄插入到指定位置(如果有这个排名,则添加失败,并给出提示) 思路的分析示意图:

3.png

修改节点功能


古时候,有武功的人士逗喜欢为了排名去争斗,所以我们制作英雄榜需要有更换排名的功能

排名是固定的,他的下一名也是固定的 我们要修改的只有当前占有排名的人和昵称即可

先找到该节点,通过遍历,

temp.name = newHeroNode.name ; temp.nickname= newHeroNode.nickname

4.png


删除节点

这个功能呢可以理解为,有英雄不想争夺排名了,退休回家种田耕地享受生活了,我们需要把不需要位置的英雄占有的位置腾出来。

5.png



单向链表的增删改查

/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.LinkedList
 * @className: LinkedlistDemo
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2021/12/17 16:24
 * @version: 1.0
 */
public class LinkedlistDemo {
    public static void main(String[] args) {
        // 设置一些英雄对象
        HeroNode heroNode = new HeroNode(1, "宋江", "及时雨");
        HeroNode heroNode1 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode heroNode2 = new HeroNode(3, "吴用", "智多星");
        HeroNode heroNode3 = new HeroNode(4, "林冲", "豹子头");
        // 声明单向链表
        SingleLinkedlist linkedlist = new SingleLinkedlist();
        //加入我们的英雄节点
        //linkedlist.add(heroNode);
        //linkedlist.add(heroNode1);
        //linkedlist.add(heroNode2);
        //linkedlist.add(heroNode3);
        //加入按照编号
        linkedlist.addByOrder(heroNode);
        linkedlist.addByOrder(heroNode3);
        linkedlist.addByOrder(heroNode2);
        linkedlist.addByOrder(heroNode1);
        //输出节点信息
        linkedlist.List();
        System.out.println("更新数据后");
        linkedlist.updateNode(new HeroNode(1, "冷环渊", "编码大师"));
        //输出节点信息
        linkedlist.List();
        System.out.println("删除数据后输出");
        linkedlist.DeleteNode(1);
        linkedlist.List();
    }
}
class SingleLinkedlist {
    //创建一个头结点
    HeroNode head = new HeroNode(0, "", "");
    //加入链表
    public void add(HeroNode node) {
        //头节点不能动 这里我们用一个临时指针来记录
        HeroNode temp = head;
        //遍历链表
        while (true) {
            //遍历为空就代表找了最后一个节点
            //不为空就后移一位继续找
            if (temp.next == null) {
                break;
            }
            //没有找到最后就后移 temp
            temp = temp.next;
        }
        //跳出while证明找到了最后的节点,将我们的新节点加入到最后的节点的next即可
        temp.next = node;
    }
    //添加节点 第二种方法
    public void addByOrder(HeroNode node) {
        /*
         * 因为头结点不能动,我们通过指针来记录头节点来帮助找到添加的位置
         *因为是单链表我们找的是 Temp是位于添加位置的前一个节点,否则插入不了
         * */
        //创建一个临时变量
        HeroNode temp = head;
        //用来标识 英雄是否存在 默认为不存在(false)
        boolean flag = false;
        while (true) {
            //找到最后为空的位置
            if (temp.next == null) {
                break;
            }
            //如果temp的下一个no 大于 我们加入的节点,就往temp加入
            if (temp.next.No > node.No) {
                break;
            }
            //如果下一个节点等于 加入节点的No 那么就代表已经存在了节点
            else if (temp.next.No == node.No) {
                //将flag 修改为 true 代表已经存在
                flag = true;
                break;
            }
            //如果上面的都没达成就代表当前节点位置不对,向后继续遍历
            temp = temp.next;
        }
        //    判断 flag的值
        if (flag) {
            //如果为 true 代表节点已经存在
            System.out.printf("当前节点%d已经存在了,不能加入\n", node.No);
        } else {
            //    如果为false 那代表符合插入条件并且不存在与当前链表
            node.next = temp.next;
            temp.next = node;
        }
    }
    //修改节点信息
    public void updateNode(HeroNode newHeroNode) {
        if (head.next == null) {
            System.out.println("链表是空的");
        }
        //这里是头节点不能修改,我用 temp 来指向头结点
        HeroNode temp = head.next;
        // 是否找到了no的标识
        boolean flag = false;
        while (true) {
            //找到最后一个
            if (temp == null) {
                break;
            }
            if (temp.No == newHeroNode.No) {
                //如果等于 那么代表可以修改
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            //  true 修改信息
            temp.NickName = newHeroNode.NickName;
            temp.Name = newHeroNode.Name;
        } else {
            System.out.printf("没有找到 %d 这个节点", newHeroNode.No);
        }
    }
    //删除节点信息
    public void DeleteNode(int no) {
        HeroNode temp = head;
        // 用来标注 是不是可以删除
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.No == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根据flag 删除Node
        if (flag) {
            //找到的话就删除,这里我们只需要指向空 GC会回收
            temp.next = temp.next.next;
        } else {
            System.out.printf("要删除的 %d 没有找到", no);
        }
    }
    //遍历链表
    public void List() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //头节点不能动 这里我们用一个临时指针来记录
        HeroNode temp = head.next;
        while (true) {
            //遍历为空就代表找了最后一个节点
            if (temp == null) {
                break;
            }
            //输出节点
            System.out.println(temp);
            //后移一位
            temp = temp.next;
        }
    }
}
/**
 * 编写 水浒传英雄 节点
 *  用于存放每个英雄的属性
 * */
class HeroNode {
    //排名
    public int No;
    // 姓名
    public String Name;
    //昵称
    public String NickName;
    // 下一个是哪位好汉
    public HeroNode next;
    public HeroNode(int hNo, String hName, String hNickName) {
        this.No = hNo;
        this.Name = hName;
        this.NickName = hNickName;
    }
    //方便输出语句输出
    @Override
    public String toString() {
        return "HeroNode{" +
                "No=" + No +
                ", Name='" + Name + '\'' +
                ", NickName='" + NickName + '\'' +
                '}';
    }
}

链表使用效果

6.png

总结

我们这次制作了属于自己的英雄榜(单向链表),我们收货了什么呢?

节点之间联系的思路

逐渐适应数据结构的一些思想

动手实


相关文章
|
存储 算法 前端开发
常见数据结构
常见数据结构
64 0
|
2月前
|
消息中间件 缓存 调度
常见的8种数据结构
常见的数据结构包括数组、链表、队列、栈、树、堆、哈希表和图。
66 4
|
4月前
|
存储 JavaScript 前端开发
复杂数据结构
【8月更文挑战第25天】
37 0
|
5月前
|
存储 算法 索引
|
7月前
|
存储 算法 索引
数据结构每日回顾
数据结构每日回顾
44 1
|
7月前
|
存储 算法
数据结构
数据结构
52 2
|
7月前
|
算法
数据结构22
数据结构22
29 0
|
存储 算法 容器
数据结构 > 什么是数据结构?
数据结构 > 什么是数据结构?
|
存储 算法 搜索推荐
【BaseArray 数据结构】
【BaseArray 数据结构】
数据结构94-深入链地址法
数据结构94-深入链地址法
66 0
数据结构94-深入链地址法