可排序的对象链表

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函数可能需要一些改进，但现在大部分工作都在Add函数中。我真的是在黑暗中跌跌撞撞。

有没有人知道一个简单的方法来做我所要求的?

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.
    }
}

如果您可以通过创建额外的内存来解决问题，例如:另一个链表。插入排序就可以了。为此，您还需要实现insert after功能。

我有一个LinkedList的实现，你可以看看。您只需要实现基于优先级的排序，您可以使用冒泡排序，插入排序或合并排序。

另外，您可能想要查看Heap，您可以使用它来实现优先级队列，它可以达到目的。我有一个堆数据结构实现，你可以看看

Answer 2

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

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

如果你有固定数量的优先级，在这两种情况下时间复杂度都是O(1)