可排序的对象链表 [英] Sortable linked list of objects

问题描述

对于学校实验室，我必须列出消息的链接列表，然后按优先级对这些消息进行排序，首先是高"优先级，然后是中优先级，然后是低优先级.我已经尝试了好几天了，但我无法将精力集中在排序上.我一直在尝试使其排序，而不在ListofMessages类中添加除head和size字段以外的任何内容，但我似乎要做的就是添加垃圾代码.我想自己弄清楚这一点，但现在我很困惑.

For a school lab I have to make a linked list of messages and then sort those messages by priority, with "High" priority being pulled out first, then medium, then low. I've been trying to figure this out for days and I can't wrap my mind around the sorting. I've been trying to get it to sort without adding anything other than a head and a size field in my ListofMessages class but all I seem to do is add garbage code. I wanted to figure this out myself but right now I'm stumped.

这是我到目前为止所拥有的.希望您能理解它:

Here's what I have so far. Hopefully you can make sense of it:

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函数中.我真的只是在黑暗中绊倒.

My pop function to retrieve the messages might need some refining but most of the work right now lies in the Add function. I'm really just stumbling through the dark there.

有人知道我要问的简单方法吗?

Does anyone know of a simple way of doing what I'm asking?

推荐答案

最简单的解决方案是拥有三个单链接列表，每个优先级一个.

The easiest solution would be to have three singly-linked lists, one for each priority.

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

When you add, you add to the end of the correct list. When you remove, you first try to remove from the highest priority list. If that is empty, try the middle one. If even that is empty, use the lowest list.

如果优先级数量恒定，则两种情况下的时间复杂度均为O(1).

If you have constant number of priorities, the time complexities are O(1) in both cases.

这篇关于可排序的对象链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！