개체의 정렬 가능한 연결 목록

Question

학교 실험실의 경우 연결된 메일 목록을 만든 다음 해당 메시지를 우선 순위별로 정렬해야합니다. 우선 순위가 "높음"우선 순위에서 먼저 추출한 다음 보통, 낮음 순으로 정렬해야합니다. 나는 이것을 며칠 동안 알아 내려고 노력해 왔으며 나는 그 소팅에 대해 내 마음을 감쌀 수 없다. 나는 그것을 ListofMessages 클래스의 head와 size 필드 이외의 것을 추가하지 않고서 정렬하려고 노력했지만, 쓰레기 코드를 추가하는 것으로 보인다. 나는 이것을 스스로 이해하고 싶었지만 지금 당황 스럽다.

여기까지 제가 지금까지 가지고 있습니다. 일부 정제 그러나 대부분의 작업은 현재 추가 기능에있다가 필요할 수 있습니다 메시지를 검색 할 수

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

내 팝업 기능 : 희망 당신은 그것을 이해 할 수 있습니다. 나는 정말로 거기서 어둠을 헤쳐 나가고있다.

누구든지 내가 원하는 것을하는 간단한 방법을 알고 있습니까? 다음과 같이

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 Data Structure 구현을 가지고, 당신은 그것을 확인할 수 있습니다.

Answer 2

가장 쉬운 해결책은 각 우선 순위에 하나씩 개의 3 개의 연결된 목록이있는 것입니다. 가장 쉬운 해결책은 개가있는 것입니다.

추가 할 때 올바른 목록의 끝에 추가하십시오. 제거 할 때 먼저 우선 순위가 가장 높은 목록에서 제거하려고합니다. 그게 비어 있다면, 가운데 하나를 시도하십시오. 그것도 비어 있다면, 가장 낮은 목록을 사용하십시오.

우선 순위가 일정한 경우 두 경우 모두 시간 복잡도는 O (1)입니다.