52.【Java 数据结构——线性表】(三)

简介: 52.【Java 数据结构——线性表】

7.1练习:

类方法:

public class test{
   private class Node{
       Node next;  //指针
       int item;  //数据
       public Node(int item,Node next){
           this.next=next;
           this.item=item;
       }
   }//定义节点
    Node head;//定义头节点
    int size; //定义长度
    public test(){
        int size=0; //对长度进行初始化
    }
    public int getSize(){
        return size;
    }
    public Node getNode(int idex){
        Node target=this.head.next;
        for(int i=0;i<idex;i++){
            target=target.next;
        }
        return target;
    }//获得结点
    public int get(int idex){
        return getNode(idex).item;
    }//获得值
    public void add(int t){
        Node node=new Node(t,null);
        if(this.size==0){
            this.head.next=node;
        }else{
            getNode(this.size-1).next=node;
        }
        this.size++;
    }
    }

主方法:

import java.sql.SQLOutput;
import java.util.*;
import java.awt.*;
import java.lang.Math;
public class hello {
    public static void main(String []avgs) {
     LinkedList s=new LinkedList<>();
     Scanner sc=new Scanner(System.in);
        System.out.println("请输入您的数据");
        for(int i=0;i<100;i++){
            int m=sc.nextInt();
            s.add(m);
           if(s.get(i).equals(-1)){
               System.out.println("链表创建完毕!");
               break;
           }
        }
        System.out.println("链表的数据为:");
        for (int i=0;i<s.size();i++){
            System.out.print(s.get(i)+" ");
        }
    }
}

8.循环链表(双指针快慢)

循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。

8.1判断是否是循环链表

利用快慢指针判断是否这个链表是否为环形

基本思路:

因为快指针比慢指针走的快,慢指针比快指针走的慢。会有多次相遇的机会的

方法:

public boolean QuickSlowP(){
        //设置慢指针
        Node1 slow=this.head.next;
        //设置快指针
        Node1 quick=this.head.next;
        while(quick!=null&&quick.next!=null){
            //慢指针
            slow=slow.next;
            //快指针
            quick=quick.next;
            quick=quick.next;
            if(quick!=null&&quick.equals(slow)){
                return true;
            }
        }
        return false;
    }

//创建环形链表:

只需要把你想要的结点的指针指向你要循环的地方,就可以构成一个循环链表.

public void Recle(int start,int end){
        Node1 node=getNode(start);
        Node1 node1=getNode(end);
        node1.next=node;
    }

全部代码:

主方法:
import java.sql.SQLOutput;
import java.util.*;
import java.awt.*;
import java.lang.Math;
public class hello {
    public static void main(String []avgs) {
   LinkedList<String> s=new LinkedList<>();
   //构造一个单链表
   s.add("aa");
   s.add("cc");
   s.add("ee");
   s.add("zz");
   System.out.println(s.QuickSlowP());
   //构造一个环形链表
      s.Recle(2,s.size()-1);
        System.out.println(s.QuickSlowP());
    }
}
类方法
import org.jetbrains.annotations.NotNull;
public class LinkedList<T> {
    Node1 head;  //设置头节点
    int size;   //链表长度
    public LinkedList() { //初始化链表
        this.head=new Node1(null,null);
        this.size=0;
    }
    public void Recle(int start,int end){
        Node1 node=getNode(start);
        Node1 node1=getNode(end);
        node1.next=node;
    }
    //使用快慢指针寻找中间元素
    public boolean QuickSlowP(){
        //设置慢指针
        Node1 slow=this.head.next;
        //设置快指针
        Node1 quick=this.head.next;
        while(quick!=null&&quick.next!=null){
            //慢指针
            slow=slow.next;
            //快指针
            quick=quick.next;
            quick=quick.next;
            if(quick!=null&&quick.equals(slow)){
                return true;
            }
        }
        return false;
    }
    //获取当前链表的长度:
    public int size(){
        return this.size;
    }
    //获取指定位置的元素:
    public T get(int idex){
        Node1 target=this.head.next;  //获取0结点的指针,且目前表示的是第一个结点
            for(int i=0;i<idex;i++ ){   //移动指针
                target=target.next;
            }
            return target.item;
    }
    //获取指定位置的结点
    public Node1 getNode(int idex){
        if(idex==-1){   //目的是在指定位置0的时候的作用
            return head;
        }
        Node1 target=this.head.next;
        for(int i=0;i<idex;i++ ){   //移动指针
            target=target.next;
        }
        return target;
    }
    //在尾部添加数据
    public void add(T t){
    Node1 node=new Node1(t,null);
    if(this.size==0){   //假如说是0结点,那么就添加到零结点
        this.head.next=node;
    }else {  //找到最后一个结点
        this.getNode(this.size-1).next=node;
    }
    //链表长度++
        this.size++;
    }
    //在指定位置插入数据
    private class Node1 {   //调用结点类
    T item;    //数据域
    Node1 next;   //指针域
       public Node1(T item, Node1 next) {
           this.item = item;
           this.next = next;
       }
   }//调用节点类
}

8.2求循环链表的入口元素

基本思路:

首先我们要判断这个链表是否是一个循环链表,如果是循环链表的话那么我们就继续执行操作,不是循环链表的话返回一个NULL。判断是否是入口的关键就在于慢指针slow,和一个新的指针(从第一个元素开始)往后遍历,如果新的指针和指针slow相交的位置,就是元素的所在位置.

public T QuickSlowP(){
        //设置慢指针
        Node1 slow=this.head.next;
        //设置快指针
        int length=-1;
        int a=0;
        Node1 quick=this.head.next;
        while(quick!=null&&quick.next!=null){
            //慢指针
            slow=slow.next;
            //快指针
            quick=quick.next;
            quick=quick.next;
            if(quick!=null&&quick.equals(slow)){   //假如环形
                Node1 entry=this.head.next;   //定义一个新的指针
                while(!entry.equals(slow)){
                    entry=entry.next;
                    slow=slow.next;
                }
                return entry.item;
            }
        }
        return null;
    }

8.3指定点循环链表的建立

public void Recle(int start,int end){
        Node1 node=getNode(start);  //开始点
        Node1 node1=getNode(end); //结束点
        node1.next=node;          //首尾相连接
    }

8.4不指定点循环链表建立

public void SolveYsf (int m,int n){  //m是元素的个数,n是间隔几个
        //建立一个链表
        for(int i=1;i<=m;i++){   //添加链表的元素
            add((T)(i+""));
        }
        //进行加环处理
        Node1 node=getNode(0);
        Node1 node1=getNode(this.size-1);
        node1.next=this.head.next;

8.5约瑟夫问题

进行自杀操作,一共m个人,没间隔n个,那么就第n个人进行自杀操作。

public void SolveYsf (int m,int n){
        //建立一个链表
        for(int i=1;i<=m;i++){   //添加链表的元素
            add((T)(i+""));
        }
        //进行加环处理
        Node1 node=getNode(0);
        Node1 node1=getNode(this.size-1);
        node1.next=this.head.next;
        //开始处理约瑟夫问题
        Node1 target=this.head.next;
        int cn=1;
        while(target!=target.next){
            //获取前一个元素
            Node1 prev=target;  //获取中间元素的前一个位置
            //游标进行后移
            target=target.next;  //获取中间元素
            //计算
            cn++;
            if(cn==n){  //假如说cn=指定的n,那么就自杀
                System.out.println("需要移除的元素是:"+target.item);
               prev.next=target.next;  //把中间元素的前一个元素指向中间元素后一个元素
                target=target.next;   //把中间元素指向中间元素的后一个元素.
                cn=1;
            }
        }
        System.out.println("保留的元素是:"+target.item);
    }

相关文章
|
24天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
61 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
14天前
|
存储 Java
Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。
【10月更文挑战第19天】本文详细介绍了Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。HashMap以其高效的插入、查找和删除操作著称,而TreeMap则擅长于保持元素的自然排序或自定义排序,两者各具优势,适用于不同的开发场景。
27 1
|
17天前
|
存储 Java
告别混乱!用Java Map优雅管理你的数据结构
【10月更文挑战第17天】在软件开发中,随着项目复杂度增加,数据结构的组织和管理至关重要。Java中的Map接口提供了一种优雅的解决方案,帮助我们高效、清晰地管理数据。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,有效提升了代码质量和维护性。
59 2
|
17天前
|
存储 Java 开发者
Java Map实战:用HashMap和TreeMap轻松解决复杂数据结构问题!
【10月更文挑战第17天】本文深入探讨了Java中HashMap和TreeMap两种Map类型的特性和应用场景。HashMap基于哈希表实现,支持高效的数据操作且允许键值为null;TreeMap基于红黑树实现,支持自然排序或自定义排序,确保元素有序。文章通过具体示例展示了两者的实战应用,帮助开发者根据实际需求选择合适的数据结构,提高开发效率。
48 2
|
5天前
|
存储 Java 索引
Java中的数据结构:ArrayList和LinkedList的比较
【10月更文挑战第28天】在Java编程世界中,数据结构是构建复杂程序的基石。本文将深入探讨两种常用的数据结构:ArrayList和LinkedList,通过直观的比喻和实例分析,揭示它们各自的优势与局限,帮助你在面对不同的编程挑战时做出明智的选择。
|
13天前
|
存储 算法 Java
Java 中常用的数据结构
【10月更文挑战第20天】这些数据结构在 Java 编程中都有着广泛的应用,掌握它们的特点和用法对于提高编程能力和解决实际问题非常重要。
19 6
|
14天前
|
存储 Java 开发者
Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效
【10月更文挑战第19天】在软件开发中,随着项目复杂度的增加,数据结构的组织和管理变得至关重要。Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,帮助开发者告别混乱,提升代码质量。
24 1
|
22天前
|
存储 算法 Java
Java常用的数据结构
【10月更文挑战第3天】 在 Java 中,常用的数据结构包括数组、链表、栈、队列、树、图、哈希表和集合。每种数据结构都有其特点和适用场景,如数组适用于快速访问,链表适合频繁插入和删除,栈用于实现后进先出,队列用于先进先出,树和图用于复杂关系的表示和查找,哈希表提供高效的查找性能,集合用于存储不重复的元素。合理选择和组合使用这些数据结构,可以显著提升程序的性能和效率。
|
29天前
|
存储 Java
数据结构第二篇【关于java线性表(顺序表)的基本操作】
数据结构第二篇【关于java线性表(顺序表)的基本操作】
29 6
|
8天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!