首页 > 其他分享 >链表

链表

时间：2023-09-14 17:35:46浏览次数：23  
标签：node temp public 链表 GoodsNode next 节点

1、单向链表
//节点的定义
public class GoodsNode {
    public String name;
    public double price;

    //指向下一个节点的指针
    public GoodsNode next;

    //构造方法
    public GoodsNode() {
    }

    public GoodsNode(String name, double price) {
        this.name = name;
        this.price = price;
    }

}

//链表的常见操作
public class MyLinkList {
    //头结点
    private GoodsNode head = new GoodsNode("", 0);
    //链表的长度
    private int lenth = 0;

    //获取头结点
    public GoodsNode getHead() {
        return head;
    }

    //获取链表长度
    public int getLenth() {
        return lenth;
    }

    //添加添加节点的方法，使用尾插法
    public void add(GoodsNode node) {
        GoodsNode temp = this.head;
        //通过头结点找到最后一个节点
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = node;
        lenth++;
    }

    //插入节点，参数1表示要插入的节点，参数2表示要插入的索引位置
    public void insert(GoodsNode node, int index) {
        GoodsNode temp = this.head;
        //首先对错误索引进行处理
        if (index <= 0 || index > this.lenth) {
            throw new RuntimeException("索引有误!");
        } else if (index == lenth) {
            //通过头结点找到最后一个节点
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = node;
            lenth++;
        } else {
            while (index > 0) {
                temp = temp.next;
                index--;
            }
            //记录当前节点的下一个节点
            GoodsNode next = temp.next;
            //然后将当前节点的下一个节点指向新的节点
            temp.next = node;
            //然后将新节点的next域指向刚才记录的next值
            node.next = next;
            //长度自加
            lenth++;
        }
    }

    //通过商品的价值从小往后增加，
    public void addOrder(GoodsNode node) {
        GoodsNode temp = this.head;
        while (true) {
            //如果传入节点的价格大于当前索引下节点的价格，那么则结束循环
            if (node.price >= temp.price || temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        //如果索引到了最后一个节点，则直接将最后一个节点的next域设置为新加入的节点
        if (temp.next == null) {
            //必须要比最后一个节点的价格高才可以添加到链表中
            if(node.price >= temp.price){
                temp.next = node;
                //长度自增
                lenth++;
            }
        } else {
            //如果不是最后一个节点，那么就需要首先记录当前节点的next域中的值
            GoodsNode next = temp.next;
            //然后将当前节点的下一个节点指向新的节点
            temp.next = node;
            //然后将新节点的next域指向刚才记录的next值
            node.next = next;
            //长度自加
            lenth++;
        }
    }

    //输出列表的方法
    public void showLinkList(){
        GoodsNode node = head.next;
        while (node != null){
            System.out.println("商品名称为:" + node.name + "\t商品价格为:" + node.price);
            node = node.next;
        }
    }

}

//测试类
public class Test1 {
    public static void main(String[] args) {
        MyLinkList list = new MyLinkList();
        //创建三个节点
        GoodsNode node1 = new GoodsNode("华为",4399);
        GoodsNode node2 = new GoodsNode("一加",5999);
        GoodsNode node3 = new GoodsNode("步步高",5399);

        //调用添加节点的方法
        list.add(node1);
        list.add(node2);
        list.add(node3);

        //输出信息
        list.showLinkList();

    }
}

输出结果：

商品名称为:华为 商品价格为:4399.0 商品名称为:一加 商品价格为:5999.0 商品名称为:步步高 商品价格为:5399.0

2、双向链表
//节点的定义
public class DoubleGoodsNode {
    public int id;
    public String name;
    public double price;

    //指向下一个节点
    public DoubleGoodsNode next;
    //指向下一个节点
    public DoubleGoodsNode previous;

    public DoubleGoodsNode() {
    }

    public DoubleGoodsNode(int id, String name, double price) {
        this.id = id;
        this.name = name;
        this.price = price;
    }

}

//对链表的操作
/**
 * 双向链表
 */

public class DoubleLinkList {
    private DoubleGoodsNode head = new DoubleGoodsNode(0, "", 0.0);
    //双向链表的长度
    private int lenth;

    //获取链表长度
    public int getLenth() {
        return lenth;
    }

    //尾插法
    public void addLast(DoubleGoodsNode node) {
        //获取头结点
        DoubleGoodsNode temp = this.head;
        //遍历到最后一个节点
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = node;
        node.previous = temp;
        lenth++;
    }

    //任意索引位置插入节点
    public void insertData(DoubleGoodsNode node, int index) {
        //获取头结点
        DoubleGoodsNode temp = this.head;
        //首先对错误索引进行处理
        if (index <= 0 || index > this.lenth) {
            throw new RuntimeException("索引有误!");
        }else if(index == lenth){   //相当于直接插在末尾
            addLast(node);
        }else {
            while (index > 0) {
                temp = temp.next;
                index--;
            }
            //记录当前节点的下一个值
            DoubleGoodsNode next = temp.next;
            temp.next = node;
            node.previous = temp;
            node.next = next;
            next.previous = node;
            lenth++;
        }
    }

    //遍历链表
    public void showDoubleList() {
        //获取头节点
        DoubleGoodsNode node = head.next;
        while (node != null) {
            System.out.println("商品ID为:" + node.id + "\t商品名称为:" + node.name + "\t\t商品价格为:" + node.price);
            node = node.next;
        }
    }

}

//测试类
public class Test2 {
    public static void main(String[] args) {
        //创建几个节点
        DoubleGoodsNode node1 = new DoubleGoodsNode(1,"Huawei",6499);
        DoubleGoodsNode node2 = new DoubleGoodsNode(2,"Sanxing",6899);
        DoubleGoodsNode node3 = new DoubleGoodsNode(3,"Honor",6499);
        //创建双向链表
        DoubleLinkList list = new DoubleLinkList();

        //插入节点
        list.addLast(node1);
        list.addLast(node2);
        list.addLast(node3);

        //输出链表
        list.showDoubleList();
        System.out.println("--------------------------");
        //利用索引插入节点
        DoubleGoodsNode node4 = new DoubleGoodsNode(3,"Leshi",6899);
        list.insertData(node4,3);
        list.showDoubleList();
    }
}

输出结果：

商品ID为:1	商品名称为:Huawei		商品价格为:6499.0
商品ID为:2	商品名称为:Sanxing		商品价格为:6899.0
商品ID为:3	商品名称为:Honor		商品价格为:6499.0
--------------------------
商品ID为:1	商品名称为:Huawei		商品价格为:6499.0
商品ID为:2	商品名称为:Sanxing		商品价格为:6899.0
商品ID为:3	商品名称为:Honor		商品价格为:6499.0
商品ID为:3	商品名称为:Leshi		商品价格为:6899.0

进程已结束,退出代码0
3、利用循环链表解决约瑟夫问题

约瑟夫问题：设编号为1,2…，n的n个人围坐一圈，约定编号为k(1<=k<=n)的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

//定义节点类
public class Boy {
    private int id;

    private Boy next;


    public Boy() {
    }

    public Boy(int age) {
        this.id = age;
    }

    /**
     * 获取
     * @return age
     */
    public int getId() {
        return id;
    }

    /**
     * 设置
     * @param age
     */
    public void setId(int age) {
        this.id = age;
    }

    /**
     * 获取
     * @return next
     */
    public Boy getNext() {
        return next;
    }

    /**
     * 设置
     * @param next
     */
    public void setNext(Boy next) {
        this.next = next;
    }

}

//定义双向链表并且解决约瑟夫问题的类
public class RingList {
    private Boy first = new Boy(-1);
    //环形链表的长度
    private int lenth = 0;

    //设置指定长度的环形链表
    public void addBoy(int num) {
        if (num < 1) {
            System.out.println("数量有误！");
            return;
        }
        Boy temp = null;
        for (int i = 1; i <= num; i++) {
            Boy boy = new Boy(i);
            if (i == 1) {
                first = boy;
                first.setNext(first);
                temp = first;
                lenth++;
            } else {
                temp.setNext(boy);
                boy.setNext(first);
                temp = boy;
                lenth++;
            }
        }
    }

    //查看环形链表中的数据
    public void showRingList() {
        if (first == null) {
            System.out.println("链表为空!");
            return;
        }
        Boy boy = first;
        while (boy.getNext() != first) {
            System.out.println("boy的ID为:" + boy.getId());
            boy = boy.getNext();
        }
    }

    //解决约瑟夫问题
    public void yueSeFu(int k, int m) {
        if (first == null || k < 1 || m > lenth) {
            System.out.println("输出数据有误或者链表数据为空!");
            return;
        }

        //最后一个节点
        Boy end = first;
        while (true) {
            end = end.getNext();
            if (end.getNext() == first) {
                break;
            }
        }

        //根据k值重新确定循环链表的起始位置
        for (int i = 0; i < k - 1; i++) {
            first = first.getNext();
            end = end.getNext();
        }

        //找到出列的孩子
        while (true) {
            if (end == first) {    //表示只剩下了最后一个元素
                System.out.println("小孩" + first.getId() + "出列！");
                break;
            } else {
                for (int i = 0; i < m - 1; i++) {
                    first = first.getNext();        //遍历结束后first指向的值就是需要出列的数据
                    end = end.getNext();
                }
            }
            System.out.println("小孩" + first.getId() + "出列！");
            first = first.getNext();
            end.setNext(first);
        }

    }
    
}

标签：node,temp,public,链表,GoodsNode,next,节点
From： https://blog.51cto.com/u_15433911/7472037

相关文章

  • 数据结构之链表
    说明链表是数据结构中的线性结构，用于存储一系列元素（节点），其中每个元素都包含一个指向下一个元素的引用。链表由一组节点组成，每个节点包含两个部分：数据和指向下一个节点的指针（或引用）。线性结构中对比数组/列表的优势：插入和删除性能较好涉及的概念：1.节点：节点包括2个域,元素域、......
  • day03 - 链表part01
    力扣203.移除链表元素没有难度，只需掌握一个思路，即因为每次删除元素时，我们需要该元素的前一个元素的指针来操作，那么如果删除第一个元素呢？他的前一个元素无法获取因此需要进行特殊处理，而我们可以设置一个虚拟节点作为头结点，这样链表的每个元素的处理方式就统一了。代码如下ListN......
  • Java有关链表的基本操作
    上一篇发表的数组的基本操作,但是数组有优势也有劣势:·具体的优势是:拥有高效的随机访问能力·劣势是:由于排列紧密相连，插入和删除元素都会导致大量元素被迫移动，影响效率。接下来要阐述的数据结构是链表:·先看看单向链表的结构:单向链表的每一个节点又包含两个部分，一部分......
  • 重排链表
     解题思路：采用快慢指针的方法将单链表分成两半，再对两部分的链表进行合并voidreorderList(structListNode*head){  if(head==NULL||head->next==NULL){    return;  }    //找到链表中间节点  structListNode*slow=head; ......
  • 138. 复制带随机指针的链表
    给你一个长度为n的链表，每个节点包含一个额外增加的随机指针random，该指针可以指向链表中的任何节点或空节点。构造这个链表的深拷贝。深拷贝应该正好由n个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的next指针和random指针也都应指向复制链表......
  • 例2.9 建立一个带头结点的线性链表，用以存放输人的二进制数，链表中每个结点的data域存放
    1.题目例2.9建立一个带头结点的线性链表，用以存放输人的二进制数，链表中每个结点的data域存放一个二进制位。并在此链表上实现对二进制数加1的运算。2.算法分析3.代码/*二进制加1*/voidBinAdd(LinkListl){inttemp;Node*pa=l->next,*pb,*s;while(pa......
  • 例2.7 算法实现带头结点单链表的就地逆置问题。
    1.题目例2.7算法实现带头结点单链表的就地逆置问题。2.算法思想3.代码//就地逆置voidReverseList(LinkListL){Node*p,*q;p=L->next;L->next=NULL;while(p){q=p->next;p->next=L->next;L->next=p;......
  • Icoding 链表 删除范围内结点
    题目：已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度。链表结点定义如下：struct_lnklist{ElemTypedata;struct_lnklist*next;};typedefstruct......
  • 链表
            ......
  • java版本剑指offer：链表中倒数最后k个结点
    java版本剑指offer：链表中倒数最后k个结点描述输入一个链表，输出一个链表，该输出链表包含原链表中从倒数第k个结点至尾节点的全部节点。如果该链表长度小于k，请返回一个长度为0的链表。最简单的方式就是使用两个指针，第一个指针先移动k步，然后第二个指针再从头开始，这个时候这两个指针......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99