Сортируемый связанный список объектов

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

Моя поп-функция для извлечения сообщений, возможно, нуждается в доработке, но большая часть работы сейчас заключается в функции Add.Я действительно просто спотыкаюсь в темноте.

Кто-нибудь знает простой способ сделать то, что я прошу?

Answer 1

Самым простым решением было бы иметь три односвязных списка, по одному на каждый приоритет.

При добавлении вы добавляете в конец правильный список.При удалении вы сначала пытаетесь удалить из списка с самым высоким приоритетом.Если это пусто, попробуйте средний.Если даже это пусто, используйте самый низкий список.

Если у вас постоянное количество приоритетов, временные сложности в обоих случаях равны O (1).

Answer 2

Почему бы вам не написать собственный связанный список следующим образом:

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 , вы можете проверить это. Вам просто нужно реализовать сортировку по приоритету, вы можете использовать пузырьковую сортировку, сортировку вставкой или сортировку слиянием.

Кроме того, вы можете захотеть взглянуть на кучу, которую вы можете использовать для реализации приоритетной очереди, она служит цели. У меня есть Реализация структуры данных кучи Реализация, вы можете проверить ее.