ToB企服应用市场:ToB评测及商务社交产业平台

标题: 链表 [打印本页]
作者: 嚴華    时间: 2022-9-16 17:24
标题: 链表
链表

1 链表

2 单链表




  1. package com.acti.linkedList;
  3. /**
  4. * author hongyeci
  5. * date 20220722
  6. * version 1.0
  7. * remark 单链表--商品类
  8. */
  9. public class GoodsNode {
  10.     private int goodsId;
  11.     private String goodsName;
  12.     private double goodsPrice;
  13.     private GoodsNode next;
  15.     public GoodsNode() {
  16.     }
  18.     public GoodsNode(int goodsId, String goodsName, double goodsPrice) {
  19.         this.goodsId = goodsId;
  20.         this.goodsName = goodsName;
  21.         this.goodsPrice = goodsPrice;
  22.     }
  24.     public int getGoodsId() {
  25.         return goodsId;
  26.     }
  28.     public void setGoodsId(int goodsId) {
  29.         this.goodsId = goodsId;
  30.     }
  32.     public String getGoodsName() {
  33.         return goodsName;
  34.     }
  36.     public void setGoodsName(String goodsName) {
  37.         this.goodsName = goodsName;
  38.     }
  40.     public double getGoodsPrice() {
  41.         return goodsPrice;
  42.     }
  44.     public void setGoodsPrice(double goodsPrice) {
  45.         this.goodsPrice = goodsPrice;
  46.     }
  48.     public GoodsNode getNext() {
  49.         return next;
  50.     }
  52.     public void setNext(GoodsNode next) {
  53.         this.next = next;
  54.     }
  56.     @Override
  57.     public String toString() {
  58.         return "GoodsNode{" +
  59.                 "goodsId=" + goodsId +
  60.                 ", goodsName='" + goodsName + '\'' +
  61.                 ", goodsPrice=" + goodsPrice +
  62.                 ", next=" + next +
  63.                 '}';
  64.     }
  65. }
复制代码
  1. package com.acti.linkedList;
  4. /**
  5. * author hongyeci
  6. * date 20220722
  7. * version 1.0
  8. * remark 带有头结点的单链表
  9. */
  10. public class SingleLinkedList {
  11.     private GoodsNode node = new GoodsNode(0,"头结点",0.0);
  13.     /**
  14.      * 增加结点-添加到末尾结点
  15.      * @param goodsNode 商品结点
  16.      */
  17.     public void addNode(GoodsNode goodsNode){
  18.         GoodsNode temp = node;
  19.         while(true){
  20.             if (temp.getNext() == null){
  21.                 break;
  22.             }
  23.             temp=temp.getNext();
  24.         }
  25.         temp.setNext(goodsNode);
  26.     }
  28.     /**
  29.      * 指定位置插入值
  30.      * 按照商品id值顺序插入到链表中
  31.      * @param goodsNode
  32.      */
  33.     public void insertNode(GoodsNode goodsNode){
  34.         GoodsNode temp = node;
  35.         boolean flag = false;
  36.         while(true){
  37.             if (temp.getNext() == null){
  38.                 break;
  39.             }
  40.             if (temp.getNext().getGoodsId()>goodsNode.getGoodsId()){
  41.                 break;
  42.             }else if (temp.getNext().getGoodsId() == goodsNode.getGoodsId()){
  43.                 flag = true;
  44.                 break;
  45.             }
  46.             temp=temp.getNext();
  47.         }
  48.         if (flag){
  49.             throw new RuntimeException("不能插入重复的商品...");
  50.         }else {
  51.             goodsNode.setNext(temp.getNext());
  52.             temp.setNext(goodsNode);
  53.         }
  54.     }
  56.     /**
  57.      * 修改指定结点data域信息
  58.      * @param goodsNode
  59.      */
  60.     public void updateNode(GoodsNode goodsNode){
  61.         GoodsNode temp = node;
  62.         if (temp.getNext() == null){
  63.             throw new RuntimeException("该链表为空链表，不能进行修改操作...");
  64.         }
  65.         boolean flag = false;
  66.         while (true){
  67.             //1 直到最后一个结点
  68.             if (temp.getNext()==null){
  69.                 break;
  70.             }
  71.             //2 找到指定结点
  72.             if (temp.getNext().getGoodsId()==goodsNode.getGoodsId()){
  73.                 flag = true;
  74.                 break;
  75.             }
  76.             temp = temp.getNext();
  77.         }
  78.         if (flag){
  79.             //修改指定结点data域数据
  80.             temp.getNext().setGoodsName(goodsNode.getGoodsName());
  81.             temp.getNext().setGoodsPrice(goodsNode.getGoodsPrice());
  82.         }else {
  83.             throw new RuntimeException("未找到指定结点...");
  84.         }
  85.     }
  87.     /**
  88.      * 删除指定结点
  89.      * 根据结点ID删除指定结点
  90.      * @param goodsId
  91.      */
  92.     public void deleteNode(int goodsId){
  93.         //判断链表是否为空
  94.         if (node.getNext() == null){
  95.             throw new RuntimeException("该链表为空链表，不能进行删除操作...");
  96.         }
  97.         GoodsNode temp = node;  //头结点
  98.         boolean flag = false;   //是否做删除操作标识
  99.         //遍历链表结点 获取指定结点
  100.         while (true){
  101.             //遍历至最后一个结点 退出遍历
  102.             if (temp.getNext()==null){
  103.                 break;
  104.             }
  105.             //找到指定结点
  106.             if (temp.getNext().getGoodsId()==goodsId){
  107.                 flag = true;
  108.                 break;
  109.             }
  110.             temp = temp.getNext();
  111.         }
  112.         if (flag){
  113.             //删除操作
  114.             temp.setNext(temp.getNext().getNext());
  115.         }else {
  116.             throw new RuntimeException("未找到指定删除结点...");
  117.         }
  118.     }
  121.     /**
  122.      * 获取当前单链表的结点个数
  123.      * @return
  124.      */
  125.     public int lengthNode(){
  126.         int length = 0;
  127.         GoodsNode temp = node.getNext();
  128.         while (temp!=null){
  129.             length++;
  130.             temp = temp.getNext();
  131.         }
  132.         return length;
  133.     }
  135.     /**
  136.      * 查看链表元素
  137.      */
  138.     public void listNode(){
  139.         if (node.getNext()==null){
  140.             System.out.println("空链表...");
  141.         }else {
  142.             GoodsNode temp = node;
  143.             while (true){
  144.                 if (temp.getNext()==null){
  145.                     break;
  146.                 }
  147.                 temp = temp.getNext();
  148.                 System.out.println(temp);
  149.             }
  150.         }
  151.     }
  153. }
复制代码
3 双链表




  1. package com.acti.linkedList;
  3. /**
  4. * author hongyeci
  5. * date 20220725
  6. * version 1.0
  7. * remark 双链表--图书类
  8. */
  9. public class BooksNode {
  10.     private int id;
  11.     private String name;
  12.     private double price;
  13.     private BooksNode pre; //双链表前驱结点
  14.     private BooksNode next; //双链表后继结点
  16.     public BooksNode() {
  17.     }
  19.     public BooksNode(int id, String name, double price) {
  20.         this.id = id;
  21.         this.name = name;
  22.         this.price = price;
  23.     }
  25.     public int getId() {
  26.         return id;
  27.     }
  29.     public void setId(int id) {
  30.         this.id = id;
  31.     }
  33.     public String getName() {
  34.         return name;
  35.     }
  37.     public void setName(String name) {
  38.         this.name = name;
  39.     }
  41.     public double getPrice() {
  42.         return price;
  43.     }
  45.     public void setPrice(double price) {
  46.         this.price = price;
  47.     }
  49.     public BooksNode getPre() {
  50.         return pre;
  51.     }
  53.     public void setPre(BooksNode pre) {
  54.         this.pre = pre;
  55.     }
  57.     public BooksNode getNext() {
  58.         return next;
  59.     }
  61.     public void setNext(BooksNode next) {
  62.         this.next = next;
  63.     }
  65.     @Override
  66.     public String toString() {
  67.         return "BooksNode{" +
  68.                 "id=" + id +
  69.                 ", name='" + name + '\'' +
  70.                 ", price=" + price +
  71.                 '}';
  72.     }
  73. }
复制代码
  1. package com.acti.linkedList;
  3. /**
  4. * author hongyeci
  5. * date 20220725
  6. * version 1.0
  7. * remark 带有头结点的双链表
  8. */
  9. public class DoubleLinkedList {
  10.     private BooksNode head = new BooksNode(0,"头结点",0.0);
  12.     /**
  13.      * 增加结点-添加到末尾结点
  14.      * @param booksNode 图书结点
  15.      */
  16.     public void addNode(BooksNode booksNode){
  17.         BooksNode temp = head;
  18.         while(true){
  19.             if (temp.getNext() == null){
  20.                 break;
  21.             }
  22.             temp=temp.getNext();
  23.         }
  24.         temp.setNext(booksNode);
  25.         booksNode.setPre(temp);
  26.     }
  28.     /**
  29.      * 指定位置插入值
  30.      * 按照商品id值顺序插入到链表中
  31.      * @param booksNode
  32.      */
  33.     public void insertNode(BooksNode booksNode){
  34.         BooksNode temp = head;
  35.         boolean flag = false;
  36.         while(true){
  37.             if (temp.getNext() == null){
  38.                 break;
  39.             }
  40.             if (temp.getNext().getId()>booksNode.getId()){
  41.                 break;
  42.             }else if (temp.getId() == booksNode.getId()){
  43.                 flag = true;
  44.                 break;
  45.             }
  46.             temp=temp.getNext();
  47.         }
  48.         if (flag){
  49.             throw new RuntimeException("不能插入重复的商品...");
  50.         }else {
  51.             if (temp.getNext()==null){
  52.                 temp.setNext(booksNode);
  53.                 booksNode.setPre(temp);
  54.             }else {
  55.                 //1、当前结点的后继结点后继节点前驱指向新结点
  56.                 temp.getNext().setPre(booksNode);
  57.                 //2、新结点后继结点指向当前结点后继结点
  58.                 booksNode.setNext(temp.getNext());
  59.                 //3、新结点前驱结点指向当前结点
  60.                 booksNode.setPre(temp);
  61.                 //4、当前结点后继结点指向新结点
  62.                 temp.setNext(booksNode);
  63.             }
  65.         }
  66.     }
  68.     /**
  69.      * 修改指定结点data域信息
  70.      * @param booksNode
  71.      */
  72.     public void updateNode(BooksNode booksNode){
  73.         BooksNode temp = head;
  74.         if (temp.getNext() == null){
  75.             throw new RuntimeException("该双向链表为空链表，不能进行修改操作...");
  76.         }
  77.         boolean flag = false;
  78.         while (true){
  79.             //1 直到最后一个结点
  80.             if (temp.getNext()==null){
  81.                 break;
  82.             }
  83.             //2 找到指定结点
  84.             if (temp.getId()==booksNode.getId()){
  85.                 flag = true;
  86.                 break;
  87.             }
  88.             temp = temp.getNext();
  89.         }
  90.         if (flag){
  91.             //修改指定结点data域数据
  92.             temp.setName(booksNode.getName());
  93.             temp.setPrice(booksNode.getPrice());
  94.         }else {
  95.             throw new RuntimeException("未找到指定结点...");
  96.         }
  97.     }
  99.     /**
  100.      * 删除指定结点
  101.      * 根据结点ID删除指定结点
  102.      * @param id
  103.      */
  104.     public void deleteNode(int id){
  105.         BooksNode temp = head;  //头结点
  106.         //判断链表是否为空
  107.         if (temp.getNext() == null){
  108.             throw new RuntimeException("该链表为空链表，不能进行删除操作...");
  109.         }
  110.         boolean flag = false;   //是否做删除操作标识
  111.         //遍历链表结点 获取指定结点
  112.         while (true){
  113.             //遍历至最后一个结点 退出遍历
  114.             if (temp.getNext()==null){
  115.                 break;
  116.             }
  117.             //找到指定结点
  118.             if (temp.getId()==id){
  119.                 flag = true;
  120.                 break;
  121.             }
  122.             temp = temp.getNext();
  123.         }
  124.         if (flag){
  125.             //1、当前结点前驱结点的后继指向当前结点的后继结点
  126.             temp.getPre().setNext(temp.getNext());
  127.             //2、当前结点的后继结点前驱指向当前结点的前驱结点
  128.             if (temp.getNext()!=null){
  129.                 temp.getNext().setPre(temp.getPre());
  130.             }
  131.         }else {
  132.             throw new RuntimeException("未找到指定删除结点...");
  133.         }
  134.     }
  137.     /**
  138.      * 获取当前单链表的结点个数
  139.      * @return
  140.      */
  141.     public int lengthNode(){
  142.         int length = 0;
  143.         BooksNode temp = head.getNext();
  144.         while (temp!=null){
  145.             length++;
  146.             temp = temp.getNext();
  147.         }
  148.         return length;
  149.     }
  151.     /**
  152.      * 查看链表元素
  153.      */
  154.     public void listNode(){
  155.         if (head.getNext()==null){
  156.             System.out.println("空链表...");
  157.         }else {
  158.             BooksNode temp = head;
  159.             while (true){
  160.                 if (temp.getNext()==null){
  161.                     break;
  162.                 }
  163.                 temp = temp.getNext();
  164.                 System.out.println(temp);
  165.             }
  166.         }
  167.     }
  169. }
复制代码
4 单向环形链表-约瑟夫环

<ul>设编号为1,2,...,n的n个人围坐成一圈，约定编号为k(1=



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4