可排序的对象链表对象

Question

对于学校实验室，我必须创建一个链接的消息列表，然后按优先顺序对这些消息进行排序，首先将“高”优先级拉出，然后再拉出中等，然后低。我一直试图弄清楚这几天，我无法围绕排序。我一直试图让它排序，而不是在我的ListofMessages类中添加除头和大小字段之外的任何内容，但我似乎要做的就是添加垃圾代码。我想自己弄清楚，但现在我很难过。

这是我到目前为止。希望你能理解它：

class ListOfMessages 
{ 
    private int m_nSize; 
    public Message m_cListStart; 
    //public Message m_cNextItem; 
    public Message m_cLastItem; 

    public ListOfMessages() 
    { 
     m_nSize = 0; 
     m_cListStart = null; 
     //m_cNextItem = null; 
    } 

    public int Count 
    { 
     get { return m_nSize; } 
    }  

    public string Display(Message cMessage) 
    { 
     return "Message: " + cMessage.m_strMessage + "\nPriority: " + cMessage.m_strPriority; 
    } 

    //list additions 
    public int Add(Message newMessage) 
    { 
     Message nextMessage = new Message(); 
     //inserts objects at the end of the list 
     if (m_nSize == 0) 
     { 
      m_cListStart = newMessage; 
       //m_cLastItem = newMessage; 
     } 
     else 
     { 
      Message CurrentMessage = m_cListStart; 

      if (newMessage.m_strPriority == "High") 
      { 

        if (m_cListStart.m_strPriority != "High") 
        { 
         //Make the object at the start of the list point to itself 
         CurrentMessage.m_cNext = m_cListStart; 
         //Replace the object at the start of the list with the new message 
         m_cListStart = newMessage; 

        } 
       else 
       { 
        Message LastMessage = null; 

        for (int iii = 0; iii < m_nSize; iii++)//(newmessage.m_strpriority == iii.m_strpriority) 
        //&& (iii.m_cnext == null);) 
        { 
         if (m_cListStart.m_strPriority != "High") 
         { 
          nextMessage = newMessage; 
          nextMessage.m_cNext = 
          CurrentMessage = nextMessage; 
          //LastMessage.m_cNext = CurrentMessage; 
         } 
         LastMessage = CurrentMessage; 

         if (m_cListStart.m_cNext != null) 
          m_cListStart = m_cListStart.m_cNext; 
        } 
       } 
       //iii = iii.m_cnext; 
      } 
        // for (int iii = m_cListStart; ; iii = iii.m_cNext)//(newMessage.m_strPriority == iii.m_strPriority) 
        // //&& (iii.m_cNext == null);) 
        //{ 
        // //Message lastMessage = iii; 
        // if (iii.m_strPriority != iii.m_strPriority) 
        // { 
        //  //iii.m_cNext = newMessage; 
        //  newMessage.m_cNext = iii.m_cNext; 
        //  iii.m_cNext = newMessage; 
        // } 


        //m_cLastItem.m_cNext = newMessage; 
     } 
      //m_cLastItem = newMessage; 
      return m_nSize++; 
    } 

    public Message Pop() 
    { 
     //Message Current = m_cListStart; 
     //if the object at the start of the list has another object after it, make that object the start of the list 
     //and decrease the size by 1 after popping an object off if there is more than 1 object after the start of the list 
     if (m_cListStart.m_cNext != null) 
     { 
      m_cListStart = m_cListStart.m_cNext; 
     } 
     if (m_nSize > 0) 
      m_nSize--; 
     else 
      m_cListStart = null; 
     return m_cListStart; 
     //if (m_cListStart.m_cNext != null) 
     // m_cListStart = m_cListStart.m_cNext; 
     //if (m_nSize > 1) 
     // m_nSize--; 
     //return m_cListStart; 
    } 

我的pop功能来检索消息可能需要一些改进，但现在大部分工作在于添加功能。我真的只是在那里黑暗中磕磕绊绊。

有没有人知道一个简单的方法来做我在问什么？

Answer 1

你为什么不写一个自定义链接列表如下：

class Node<T> : IComparable<T> 
{ 
    public int Priority {set;get;} 
    public T Data {set;get;} 
    public Node<T> Next {set;get;} 
    public Node<T> Previous {set;get;} 

    // you need to implement IComparable here for sorting. 
} 

这是您的节点定义。现在我们需要实现一个LinkedList类。

您的链接列表类可以是双向链表，因为您没有任何规格。而双链表则更容易。

这里的定义是：

class LinkedList<T> : IEnumerable<T> where T: IComparable 
{ 
    public Node<T> Head {set;get;} 
    public Node<T> Tail {set;get;} 

    // set of constructors 
    //..... 

    public void Insert(Node<T> node) 
    { 
     // you can do recursive or iterative impl. very easy. 
    } 

    // other public methods such as remove, insertAfter, insert before, insert last etc. 

    public void Sort() 
    { 
     // easiest solution is to use insertion sort based on priority. 
    } 

} 

如果你可以通过创建额外的内存，即闪避：另一个链接列表。插入排序会很好。为此，您还需要在功能之后实现插入。

我有一个LinkedList执行，你可以检查出来。您只需根据优先级实施排序，您可以使用冒泡排序，插入排序或合并排序。另外，你可能想看看你可以用来实现优先队列的Heap，它可以达到目的。我有一个Heap Data Structure执行，你可以检查出来。

Answer 2

最简单的解决方案是将三个单链表，每个优先级一个。

当您添加时，您将添加到正确列表的末尾。删除时，首先尝试从最高优先级列表中删除。如果这是空的，尝试中间的一个。如果即使是空的，使用最低的列表。

如果您的优先级数量不变，则在这两种情况下的时间复杂度都是O（1）。