按層次結構排序列表

Question

我需要按層次結構對列表進行排序，有人可以幫我一把嗎？名單如下：

 // create your list 
     List<Person> persons = new List<Person>(); 

     // populate it 
     persons.Add(new Person("child", "father")); 
     persons.Add(new Person("father", "grandfather")); 
     persons.Add(new Person("grandfather", "grandgrandfather")); 
     persons.Add(new Person("grandgrandfather", null)); 

我想是這樣的：

• grandgrandfather
• 爺爺
• 父親
• 孩子

我tryed來實現IComparable在我的類「人」中，像這樣：

public class Person : IComparable<Person> 
{ 
    public String ID { get; set; } 
    public String ParentID { get; set; } 

    public Person(String id, String pid) 
    { 
     this.ID = id; 
     this.ParentID = pid; 
    } 

    public Int32 CompareTo(Person right) 
    { 


     if (this.ID.Equals(right.ID)) 
      return 0; 

     if (this.ParentID == null) return -1; 
     if (right.ParentID == null) return 1; 


     return this.ParentID.CompareTo(right.ID); 
    } 

}

但沒有做的事...

Answer 1

你需要計算層次結構中的項目的部門，並通過部門列表進行排序：

如果下面是人類：

class Person 
{ 
    public string Name {get; private set;} 
    public string Parent {get; private set;} 

    public Person(string name, string parent) 
    { 
     this.Name = name; 
     this.Parent = parent; 
    } 
} 

這是計算層次結構中人員部門的方法示例。

int GetDept(List<Person> list, Person person) 
{ 
    if (person.Parent == null) return 0; 
    return GetDept(list, list.First(p => p.Name == person.Parent)) + 1; 
} 

然後可使用該方法通過部門

List<Person> persons = new List<Person>(); 

// populate it 
persons.Add(new Person("child", "father")); 
persons.Add(new Person("father", "grandfather")); 
persons.Add(new Person("grandfather", "grandgrandfather")); 
persons.Add(new Person("grandgrandfather", null)); 

var sorted = persons.OrderBy(p => GetDept(persons, p)); 

foreach(var person in sorded) 
    Console.WriteLine("{0} {1} {2}", person.Name, person.Parent, GetDept(persons, p)) 

對列表進行排序這將打印：

grandgrandfather null    0 
grandfather  grandgrandfather 1 
father   grandfather   2 
child   father    3 

注意，在這個例子中，部門沒有被有效地計算爲方法將自動調用它自己的方法，並且它使用列表中的O（n）查找。所有這些都可以通過爲每個人計算一次部門並存儲它來改進，並結合更高效的查找機制（如字典）來獲得大數據集的良好性能。

Answer 2

您可以根據自己的排序邏輯修改public int CompareTo(Person right)方法的邏輯。

例如

if (this.ID == grandgrandfather && 
     right.ID == grandfather) return 1; 


if (this.ID == grandgrandfather && 
     right.ID == child) return 1; 

....... a lot more 

Answer 3

這是一個數據的問題。您正在嘗試比較字符串值，但您的數據中並沒有提供任何相關關係。

我建議你將你的值轉換爲一個枚舉，然後可以很容易地進行比較。下面是我沒有測試過一些僞代碼，但它應該給你一個想法：

public class Person : IComparable<Person> 
{ 
     public enum Types: int { 
      None, 
      Child, 
      Father, 
      Grandfather, 
      GrandGrandFather 
     } 
    public Types ID { get; set; } 
    public Types ParentID { get; set; } 

    public Person(Types id, Types pid) 
    { 
     this.ID = id; 
     this.ParentID = pid; 
    } 

    public Int32 CompareTo(Person right) 
    { 
     return this.ParentID.CompareTo(right.ID); 
    } 

} 

Answer 4

你的問題是，你沒有辦法判斷哪一個更大，如果值太大流傳至今分開。例如：您的祖父和子元素將始終返回-1，因爲字符串「父親」始終小於字符串「祖父」。試着讓你的個人價值觀到的整型值，然後這樣的比較：

const int child = 0; 
const int father = 1; 
const int grandfather = 2; 
const int greatgrandfather = 3; 

// create your list 
List<Person> persons = new List<Person>(); 

// populate it 
persons.Add(new Person(child)); 
persons.Add(new Person(father)); 
persons.Add(new Person(grandfather)); 
persons.Add(new Person(grandgrandfather)); 

public class Person : IComparable<Person> 
{ 
    public int ID { get; set; } 

    public Person(int id) 
    { 
     this.ID = id; 
    } 

    public Int32 CompareTo(Person right) 
    { 
     if (this.ID == right.ID) 
      return 0; 

     if (this.ID > right.ID) return -1; 
     else return 1; 
    } 
}