Selection of a single contact list



  • No way to sort the list, tell me where the mistake is.

    I've set up two single lists. One empty list to which a separate list is to be placed and the other to a single reference list. With each loss, we remove the node from our primary list and put it in the right position of the disserted list. The grading is performed by two functions. The first function (SortedInsert) is looking for a space on a separate list where to insert the knot. The second function(InsertionSort) is directly the sorting in which the node is selected from the reference list, which should be added to the new list and placed under the first function. So in the second function, we're taking into account when we have to put the knot first on the list.

    Here's the algorithm of the boxing.

    PNode InsertionSort(PNode Head)
    {
        if(!Head || !Head->next)
            return Head;
    
    PNode ptr = Head->next;
    PNode result = Head;
    result->next = NULL;
    
    while(ptr)
    {
        PNode temp = ptr;
        ptr = ptr->next;
        result = SortedInsert(result, temp);
    }
    
    return result;
    

    }

    Through this function, there is a place where to insert a knot in a new set:

    PNode SortedInsert(PNode Head, PNode NewNode)
    {
    if(Head == NULL || Head->data >= NewNode->data)
    {
    NewNode->next = Head;
    Head = NewNode;
    return Head;
    }

    PNode ptr = Head;
    PNode prev = NULL;
    
    while(ptr != NULL && ptr->data < NewNode->data)
    {
        prev = ptr;
        ptr = ptr->next;
    }
    
    NewNode->next = ptr;
    prev->next = NewNode;
    
    return Head;
    

    }

    All code with the addition and display of the list:

    #include <iostream>

    using namespace std;
    
    struct Node
    {
        int data;
        Node *next;
    };
    
    typedef Node *PNode;
    
    void AddNode(PNode &amp;Head, int data);
    void ShowList(PNode &amp;Head);
    
    
    int main()
    {
        PNode Head = NULL;
        int node;
    
        cout &lt;&lt; "Enter 5 members of the linked list!" &lt;&lt; endl;
    
        for(int i = 0; i &lt; 5; i++)
        {
            cin &gt;&gt; node;
            AddNode(Head, node);
        }
    
        ShowList(Head);
    
        cout &lt;&lt; endl;
    
        InsertionSort(Head);
    
        ShowList(Head);
    
    
        return 0;
    }
    
    void AddNode(PNode &amp;Head, int data)
    {
        PNode NewNode = new Node;
        NewNode-&gt;data = data;
        NewNode-&gt;next = Head;
        Head = NewNode;
        cout &lt;&lt; "Done!" &lt;&lt; endl;
    }
    
    void ShowList(PNode &amp;Head)
    {
        PNode q = Head;
        while(q)
        {
            cout &lt;&lt; q-&gt;data &lt;&lt; " ";
            q = q-&gt;next;
        }
    }
    



  • You have to write at least main.

    head = InsertionSort(Head);
    

    Otherwise, you will not remove the sorted list because you do not retain the result of the method at any parent node declared in the main.

    There is also a side problem that the reference knot does not change. I mean, two lists point to the same original node.

    For the rest, in principle, the functions are correctly written.

    I would use the following approach to moving one list to another and sorting its elements.

    In the method of implementation, the indicator on the head knot is transmitted by reference. The other way is to transfer the index to the main knot into methods that can change the main knot.

    You can use this program as a model for your program.

    #include <iostream>
    #include <cstdlib>
    #include <ctime>
    

    typedef struct Node
    {
    int data;
    Node *next;
    } *PNode;

    void push_front( PNode &head, int data )
    {
    head = new Node { data, head };
    }

    std::ostream & display( const PNode &head, std::ostream &os = std::cout )
    {
    for ( PNode current = head; current; current = current->next )
    {
    os << current->data << ' ';
    }
    return os;
    }

    void SortedInsert( PNode &head, PNode node )
    {
    if ( !head || node->data < head->data )
    {
    node->next = head;
    head = node;
    }
    else
    {
    PNode current = head;
    while ( current->next && !( node->data < current->next->data ) )
    {
    current = current->next;
    }

        node-&gt;next = current-&gt;next;
        current-&gt;next = node;
    }
    

    }

    PNode InsertionSort( PNode &head )
    {
    PNode result = nullptr;

    while ( head )
    {
        PNode node = head;
        head = head-&gt;next;
        SortedInsert( result, node );
    }
    
    return result;
    

    }

    int main()
    {
    const size_t N = 10;
    PNode head = nullptr;

    std::srand( ( unsigned int )std::time( nullptr ) );
    
    for ( size_t i = 0; i &lt; N; i++ ) push_front( head, std::rand() % N );
    
    display( head ) &lt;&lt; std::endl;    
    
    PNode head2 = InsertionSort( head );
    
    display( head2 ) &lt;&lt; std::endl;    
    
    return 0;
    

    }

    The withdrawal to the console may be as follows:

    7 2 2 1 0 5 4 1 4 1
    0 1 1 1 2 2 4 4 5 7




Suggested Topics

  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2