Java中的排序泛型

我必須實現一個通用的AVL樹作爲作業。它的定義如下：Java中的排序泛型

public class AVL<Key,Elem>;

的問題是，我認爲在某些時候，我不得不對鍵進行比較，以決定其中一個節點的身邊，我分配的元素。爲了這個作業的目的，Integers將被用作Keys。

由於沒有其他限制或有關信息，我首先想到的是，Key將始終是一個Integer。但是，這使得通用的「關鍵」變得多餘，我不認爲這就是教師所期望的。所以，我認爲最好的解決方案包括強制傳遞任何Key作爲Key實現的比較器，或類似的東西（我真的從來沒有用過Comparator，只是猜測），然後使用該比較器來比較Keys而不是使用==，<，>和！=運算符。但是，我不知道如何去做。任何提示？

在此先感謝。

來源

2011-04-16 bluehallu

嘗試public class AVL<Key extends Comparable<Key>,Elem>;並使用Comparable<T>接口所需的compareTo()方法，該方法由Integer執行。

來源

2011-04-16 15:31:37 Thomas

此解決方案和使用Comparator有什麼區別？有人告訴我他是用它做的。感謝您的解決方案。 – bluehallu 2011-04-16 15:36:27

我認爲你可以用Comparator來混合Comparable。比較器將是一個對象，它可以比較任何類型的對象而無需實現「可比較」。但是，您的密鑰不會實現「比較器」，但您可以將其作爲單獨的對象傳遞。另一方面，Comparable將對象標記爲具有自然順序（由'comparaTo（）'的實現定義，如果你的鍵實現了，它們可以直接進行比較，注意所有Number對象（'Integer'， 'Double'等）以及'String'實現'Comparable'。 – Thomas 2011-04-16 15:53:13

明白了，我將開始閱讀關於Comparable接口的Java文檔。謝謝。 – bluehallu 2011-04-16 15:58:33

的SortedMap和SortedSet實現標準Java API在任一使用Comparator<Key>並調用其compare(k1, k2)方法，或承擔鍵實現Comparable<Key>，並調用k1.compareTo(k2)。大多數都提供，這取決於使用哪個構造函數。（EnumMap/EnumSet不支持，因爲它們只支持通過聲明順序枚舉值的內置順序。）

Comparable方法要求按鍵始終按照相同的方式排序，並且將用於具有規範排序（如整數）的鍵，您要使用此排序的鍵。

Comparator方法更加靈活，因爲您可以對不同的地圖使用相同的關鍵對象，因爲它們的排列順序不同，您可以將它用於您無法控制的關鍵點，或者沒有規範的關鍵點排序（如列表，樹/圖等）。您還可以使用Collator（這是一個實現比較器的類）以除unicode值之外的其他標準（例如，基於區域的）對其排序字符串鍵進行排序。

兩者都需要您的密鑰的總訂單，但我想這也是您的AVL樹所必需的。

這是一個比較器實現，可用於任何可比較的對象，因此您可以你可以使用它（可能是內部的）作爲Comparable變體的適配器。

public static <X extends Comparable<X>> Comparator<X> makeComparator() { 
    return new Comparator<X>() { 
     public int compare(X left, X right) { 
      return left.compareTo(right); 
     } 
    }; 
}

來源

2011-04-16 16:06:30

事實上，我的Main類需要按不同的標準對項目進行排序，我需要爲每種排序實例化各種AVL，並針對每種情況使用最好的AVL。我想這可以通過每次使用對象的不同字段作爲Key和Comparable接口來完成，或者通過刪除通用的「Key」並每次傳遞不同的比較器來比較每個期望的字段，但是由於它們給出了我們用通用的「鑰匙」簽名，他們想迫使我們使用第一種方法。不是嗎？ – bluehallu 2011-04-16 16:19:23

你似乎有一個特殊情況，即關鍵是你提取的價值的一部分。在這種情況下，兩種方法都可用。你也可以實現'SortedSet '並使用一個合適的比較器（但如果任務需要''，則同時使用）。它並不重要，其基本機制幾乎相同。 – 2011-04-16 17:09:09

Java中的排序泛型

回答

相關問題