Блог

Главная - Вопросы по программированию - Возможно ли использовать 2 типа данных в пользовательском ADT (отсортированном связанном списке)?

Возможно ли использовать 2 типа данных в пользовательском ADT (отсортированном связанном списке)?

#java #algorithm #data-structures #linked-list #sortedlist

#java #алгоритм #структуры данных #связанный список #сортированный список

Вопрос:

Я пытаюсь составить таблицу лидеров для игры, используя отсортированный связанный список. Я смог сделать это, отсортировав точки в порядке убывания, что означает переход от более высокой точки к более низкой. Кроме того, мне также нужно будет указать имя игрока вместе с точкой. Проблема возникает здесь. Реализованный мной SLL (отсортированный связанный список) представляет собой целочисленный тип данных, он отлично работает с целочисленным типом данных при сортировке чисел.

 SortedListInterface<Integer> Player = new LeaderboardSortedLinkedList<Integer>();

Но когда я пытаюсь ввести имя игрока, в котором использовалась строка, это не удастся сделать, потому что тип данных point должен будет соответствовать типу данных имени игрока.
Ниже приведены коды класса драйвера:

 public class testLeaderboard {

   
    public static void main(String[] args) {
        SortedListInterface<Integer> Player = new LeaderboardSortedLinkedList<Integer>();
        
            Player.add(1000000);
            Player.add(500000);
            Player.add(250000);
            Player.add(125000);
            Player.add(64000);
            Player.add(32000);
            Player.add(16000);
            Player.add(8000);
            Player.add(4000);
            Player.add(2000);
            Player.add(1000);
            Player.add(500);
            Player.add(300);
            Player.add(200);
            Player.add(100);
        
        
        System.out.printf("=================================n" 
                           "          Leaderboardn"
                          "=================================n");
        
        for(int i=0; i< Player.size();i  ){
            
            System.out.printf("=. %sn",(i 1), Player.get(i 1));
        }
        
    }
    
}

Вот класс сущности

 public class Player {
    private String name;
    private int prize;

    public Player(String name, int prize) {
        this.name = name;
        this.prize = prize;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getPrize() {
        return prize;
    }

    public void setPrize(int prize) {
        this.prize = prize;
    }

    @Override
    public String toString() {
        return "Player{"   "name="   name   ", prize="   prize   '}';
    }
}

Вот пользовательский отсортированный линейный список

 public class LeaderboardSortedLinkedList<T extends Comparable<T>> implements SortedListInterface<T> {

    private Node firstNode;
    private int length;

    public LeaderboardSortedLinkedList() {
        firstNode = null;
        length = 0;
    }

    public boolean add(T newEntry) {
        Node newNode = new Node(newEntry);

        Node nodeBefore = null; 
        Node currentNode = firstNode;   
        while (currentNode != null amp;amp; newEntry.compareTo(currentNode.data) < 0) {
            nodeBefore = currentNode;
            currentNode = currentNode.next;
        }

        if (isEmpty() || (nodeBefore == null)) { // CASE 1: add at beginning
            newNode.next = firstNode;
            firstNode = newNode;
        } else {    // CASE 2: add in the middle or at the end, i.e. after nodeBefore
            newNode.next = currentNode;
            nodeBefore.next = newNode;
        }
        length  ;
        return true;
    }

    public boolean contains(T anEntry) {
        boolean found = false;
        Node tempNode = firstNode;
        int pos = 1;

        while (!found amp;amp; (tempNode != null)) {
            if (anEntry.compareTo(tempNode.data) <= 0) {
                found = true;
            } else {
                tempNode = tempNode.next;
                pos  ;
            }
        }
        if (tempNode != null amp;amp; tempNode.data.equals(anEntry)) {
            return true;
        } else {
            return false;
        }
    }

    public int size(){
         int count = 0;    
        //Node current will point to head    
        Node current = firstNode;    
            
        while(current != null) {    
            //Increment the count by 1 for each node    
            count  ;    
            current = current.next;    
        }    
        return count;   
    }
    
     public T get(int position){
        T result = null;

    if ((position >= 1) amp;amp; (position <= length)) {
      Node currentNode = firstNode;
      for (int i = 0; i < position - 1;   i) {
        currentNode = currentNode.next;     // advance currentNode to next node
      }
      result = currentNode.data;    // currentNode is pointing to the node at givenPosition
    }

    return resu<
    }
    
    
    public final void clear() {
        firstNode = null;
        length = 0;
    }

    public int getLength() {
        return length;
    }

    public boolean isEmpty() {
        return (length == 0);
    }

    
    public String toString() {
        String outputStr = "";
        Node currentNode = firstNode;
        while (currentNode != null) {
            outputStr  = currentNode.data   "n";;
            currentNode = currentNode.next;
        }
        return outputStr;
    }

    private class Node {

        private T data;
        private Node next;

        private Node(T data) {
            this.data = data;
            next = null;
        }

        private Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }
}

And the results is here

 =================================
          Leaderboard
=================================
  1. 1000000
  2. 500000
  3. 250000
  4. 125000
  5. 64000
  6. 32000
  7. 16000
  8. 8000
  9. 4000
 10. 2000
 11. 1000
 12. 500
 13. 300
 14. 200
 15. 100

Вот мое тестирование точки с типом данных string, потому что я не могу придумать способ использовать имя игрока и точку с двумя разными типами данных одновременно в моем пользовательском ADT.

 public class testLeaderboard {

   
    public static void main(String[] args) {
        SortedListInterface<String> Player = new LeaderboardSortedLinkedList<String>()
      
            Player.add("1000000");
            Player.add("500000");
            Player.add("250000");
            Player.add("125000");
            Player.add("64000");
            Player.add("32000");
            Player.add("16000");
            Player.add("8000");
            Player.add("4000");
            Player.add("2000");
            Player.add("1000");
            Player.add("500");
            Player.add("300");
            Player.add("200");
            Player.add("100");
            

    System.out.println(Player);
    }

И вот результат, в котором сравнивается первая буква строки.

 8000
64000
500000
500
4000
32000
300
250000
2000
200
16000
125000
1000000
1000
100

Можно ли в любом случае использовать как String, так и Integer в одном ADT, потому что, если я не смогу этого сделать, я не смогу отсортировать точку. Прошу прощения за длинный вопрос. Я очень новичок в структурах данных и алгоритмах, поэтому мне действительно нужна помощь в этом. Большое спасибо.

Комментарии:

1. Итак, что вы ожидаете SortedListInterface<Player> player ?

Ответ №1:

Чтобы сохранить точки и имена вместе, вам нужно добавить объекты Player в список такими, какие они есть, а не только их точки или их имена:

 SortedListInterface<Player> players = new LeaderboardSortedLinkedList<>();

players.add(new Player("Alpha", 1000000));
players.add(new Player("Beta", 500000));
players.add(new Player("Gamma", 250000));

Чтобы это сработало, вам нужно будет иметь возможность сравнивать объекты Player по их номерам точек. Вы делаете это, реализуя Comparable интерфейс и добавляя compareTo метод.

Вы также захотите добавить toString() метод, чтобы можно было печатать объект Player.

 public class Player implements Comparable<Player> {
    private String name;
    private int prize;

    @Override
    public int compareTo(Player other) {
        return Integer.compare(this.prize, other.prize);
    }

    @Override
    public String toString() {
        return String.format("name='%s' prize=%d", name, prize);
    }
}

Ответ №2:

Спасибо, что помогли мне, я успешно получаю желаемый результат. Но возникла небольшая проблема, которая заключается в следующем

 =================================
           Leaderboard
=================================
  1. name='Alpha' prize=1000000
  2. name='Beta' prize=500000
  3. name='Gamma' prize=250000
BUILD SUCCESSFUL (total time: 1 second)

Он выводит выходные данные таким образом [name=»Alpha»]. Я не уверен, в чем проблема, но я предполагаю, что это мой System.out.print код.

 System.out.printf("=. %sn",(i 1), players.get(i 1));

и вот моя функция .get().

   public T get(int position){
        T result = null;

    if ((position >= 1) amp;amp; (position <= length)) {
      Node currentNode = firstNode;
      for (int i = 0; i < position - 1;   i) {
        currentNode = currentNode.next;     // advance currentNode to next node
      }
      result = currentNode.data;    // currentNode is pointing to the node at givenPosition
    }

    return resu<
    }