1

我正在尝试在 Java 中使用内部列表构建一个数据结构，该内部列表由包含整数的单个链接列表组成。我的数据结构体系结构有问题。它需要有一个内部类，其函数可以合并、拆分和给出内部列表的大小。

假设内部列表的大小将发生变化，并且将删除大小和数据以巩固和优化数据结构。

我有一个驱动程序类来与数据结构交互。然后我有一个数据结构类，它将有内部类。

当单链表折叠并随我的数据展开时，我应该将添加/删除顶级列表的方法放在哪里？

我应该上几节课？驱动程序，数据结构（带有内部类）......更多？

我只需要一个强大的编码人员的一点指导，我在自上而下的设计上进行了多次尝试，并且我已经阅读和搜索过。我只是需要一些方向。我附上了数据结构外观的图像。

请注意：

内部列表必须实现为带有虚拟头和尾指针的单链表，并且我不能将 Java Collections API 中的任何数据结构用于内部列表。对于顶级列表，我必须使用 Java Collections API 中的通用 LinkedList 类。

4

2 回答 2

5

注意：这看起来像一个家庭作业，否则就没有必要重新发明轮子了。知道了这一点，我不会提供具体的代码，只是伪代码（除了一些关键字，如class,int和类似的），没有有用的方法，如 getter 或 setter，没有额外的字段等。生成所有必要的 Java 代码将是你的工作使这项工作。

我不知道从哪里开始，我是链表的新手

首先定义将进入列表的元素的结构。这该怎么做？查看要求（强调我的）：

在 Java 中使用内部列表构建数据结构，该内部列表由包含整数的单链表组成

您需要一个数据结构，它首先可以保存一个整数值并表现为单链表。从单链表的定义来看，结构包含两个元素：

  1. 要保存的整数数据
  2. 指向下一个相似数据结构的指针。

这可以这样解决：

class DataStructure {
    int data;
    DataStructure next;
}

现在你已经有了支持单链表的结构，你需要一个新的结构来作为单链表并定义它的行为。这可以按照您的要求中所述解决：

内部列表必须实现为具有虚拟头和尾指针的单链表

将其移动到伪代码中：

class SinglyLinkedList {
    DataStructure head;
    DataStructure tail;
}

就是这样。现在你有了你的SinglyLinkedList，你只需要定义行为。再次，审查要求：

它需要有一个带有 f̶u̶n̶c̶t̶i̶o̶n̶s̶ 方法的内部类，可以合并、拆分和给出内部列表的大小。

SinglyLinkedList从这里，我们可以为数据结构定义至少三个方法merge：split和size。从中改编最新课程：

class SinglyLinkedList {
    DataStructure head;
    DataStructure tail;
    //added this method just to know you need to add data to your singly linked list
    public void add(int data) {
    }
    //you merge a list with another list
    public void merge(SinglyLinkedList singlyLinkedList) {
    }
    //you split the list into two or more lists
    public SinglyLinkedList[] split() {
    }
    //the size of the list is a numeric positive value
    public int size() {
    }
}

编辑（根据您的编辑并查看图片）

需要定义另一个包含单链表列表的数据结构。按要求：

对于顶级列表，我必须使用 Java Collections API 中的通用 LinkedList 类。

然后，您只需要一个使用 a 的新结构，该结构LinkedList将包含您的单链表：

class SinglyLinkedListHolder {
    LinkedList<SinglyLinkedList> holder;

    public SinglyLinkedListHolder () {
        holder <- new LinkedList<SinglyLinkedList>();
    }
    //this holder should at least add new singlyLinkedList in the bigger list
    public void add(SinglyLinkedList singlyLinkedList) {
    }
}

注意：我注意到您尝试使用泛型定义结构：

private static class Node<T> {
}

我强烈建议您在真正掌握有关单链表如何工作的主要概念之前不要这样做。这可能需要一些时间，但最好循序渐进。在使这个结构工作之后，您可以轻松地（实际上，取决于您的实现）将该结构替换为：

class DataStructure<T> {
    T data;
    DataStructure next;
}
于 2013-09-24T21:50:14.820 回答
0 
public class LL {

    class Node
    {
        String data;
        Node next;
        
        Node(String data)
        {
            this.data=data;
            this.next=null;
        }
    }
    

    public  Node head;     
    
    
    public void add_first(String data)
    {
        Node NewNode=new Node(data);
        if(head == null)
        {
            head=NewNode;
            return;
        }
        NewNode.next=head;
        head=NewNode;
    }
    
    public void add_last(String data)
    {
        Node NewNode=new Node(data);
        if(head==null)
        {
            head=NewNode;
            return;
        }
        Node currentNode =head;
        
        while(currentNode.next !=null)
        {
            currentNode=currentNode.next;
        }
        currentNode.next=NewNode;
        
        
        
    }   
    
    
    public void insert_pos(String data,int pos)
    {

        Node NewNode=new Node(data);
        
        Node current=head;
        
        for(int i=0;i<pos-1;i++)
        {

            System.out.println("Current is"+current.data);
            current=current.next;
        }
      
        System.out.println(current.data);
        
        NewNode.next=current.next;
        current.next=NewNode;

        System.out.println("Delete  Element Successfuly at position"+pos);
        
           
        }
    
    
    int counter;
    public void size()
    {
        Node current=head;
        
        
        if(head==null)
        {
            System.out.println("Linked list is Empty.......");
        }
        
        while(current!=null)
        {
            current=current.next;
            counter+=1;
        }
        System.out.println("Linked list size is:"+counter);
        
    }
    public void display()
    {
        Node cur=head;
        
        
        while(cur!=null)
        {

              System.out.print(cur.data+"->");
              cur=cur.next;
        }
        System.out.println("null");
    }
    

    
    public void delete_first()
    {
        Node temp=head;
        head=temp.next;
        System.out.println("Delete First Element Successfuly");
        
    }
    
    
    public void delete_last()
    {
        Node current=head;
        Node lastnode=head.next;
        
        while(lastnode.next!=null)
        {
            current=current.next;
            lastnode=lastnode.next;
        }
        
        current.next=null;      

        System.out.println("Delete last  Element.");
    }
    


    public void delete_pos(int pos)
    {

        
        Node current=head;
        Node last=head.next;
        
        for(int i=0;i<pos-1;i++)
        {

            System.out.println("Current is"+current.data);
            current=current.next;
            last=last.next;
            
        }
      
        
        current.next=last.next; 
        
    }
    


    
    
    
    
 public static void main(String[] args)
 {
     LL list=new LL();
     
     list.add_last("A");
     list.add_last("B");
     list.add_last("C");
     list.add_last("d");
     list.add_last("e");
     
    // list.delete_pos(3);
     //list.delete_first();
     
     //list.delete_last();
     
    // list.insert_pos("nirav",4);
     list.size();

     list.display();
 }

}
于 2022-02-20T09:42:16.450 回答