按层次排序列表
本文关键字:列表 排序 层次 | 更新日期: 2023-09-27 18:13:43
我需要按层次结构排序列表,有人能帮我吗?列表如下所示:
// 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
- 父亲
我试图在我的类"Person"中实现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);
}
}
您需要计算层次结构中项目的深度,并按dept对列表进行排序:
如果下面是person类:
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
注意,在这个例子中,深度的计算效率不高,因为GetDept
方法会一次又一次地调用自己,而且它在列表上使用O(n)次查找。所有这些都可以通过对每个人只计算一次深度并存储它来改进,并结合像字典这样更有效的查找机制,以便在大型数据集上获得良好的性能。
您的问题是,如果值分布得太远,您没有办法确定哪个更大。你的祖父和子元素总是返回-1,因为字符串"父亲"总是小于字符串"祖父"。试着让你的person值变成常量int值,然后像这样比较:
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;
}
}
您必须根据您的排序逻辑修改您的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
这是一个数据问题。您正在尝试比较字符串值,但是数据中没有提供相对关系的固有内容。
我建议您将值转换为Enum,这样便于比较。下面是一些伪代码,我没有测试过,但应该给你一个想法:
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);
}
}