linked list sort (swapping individual data is not an option)

[JAGgededgeOB172]

Hi all,

I'm just asking for help for my linked list sort function, I'm not including my entire program, as I'm sure my problem lies in my sort.

I need to sort the linked list by rearranging the pointers, I was fairly sure I got the function correct. When I test the sort function it isn't sorting properly. I can't see what exactly is wrong. If anyone can find anything I'd greatly appreciate it!

The list is to be in ascending order by 'frequency'.

//////////
struct huffman_data
{
    char letter;
    int frequency;
    //huffman_data *left;
    //huffman_data *right;
    huffman_data *linker;
};
/////////////
void sort_linker_list(huffman_data *head)
{
    huffman_data *temp, *temp1, *temp2;
    for(temp1 = head; temp1 != NULL; temp1 = temp1->linker)
    {
        for(temp2 = temp1->linker; temp2 != NULL; temp2 = temp2->linker)
        {
            if(temp1->frequency > temp2->frequency)
            {
                if(temp1 != head)
                {
                    temp = head;
                    while(temp->linker != temp1)
                    {
                        temp = temp->linker;
                    }
                    temp1->linker = temp2->linker;
                    temp2->linker = temp->linker;
                    temp->linker = temp2;
                }
                else
                {
                    head->linker = temp2->linker;
                    temp2->linker = head;
                    head = temp2;
                }
            }
        }
    }
    for(huffman_data *temp = head; temp != NULL; temp = temp->linker)
            cout << temp->letter << "   " << temp->frequency << endl;
    cout << endl;
    return;
}

[jencas]

Use std::list, the sort member function of std::list and write an appropriate binary predicate for sorting

[nucleon]

(Assuming you're not allowed to use std::list...)
It can be tricky swapping elements in a singly-liked list. Make diagrams so you can see what's needed. You'll probably need extra pointers to remember the previous elements of the two pointers with which you're traversing the list. Also, after you swap two elements, you will have to swap the contents of variables temp1 and temp2 to keep your loop on track.

[JAGgededgeOB172]

Thanks for your last tip from your input, nucleon. I redesigned the loops and got hung up, your hint about the swapping temp1/temp2 pointers got it done.

Thank you very much!

Here it is again in case of curiosity...

void sort_linker_list(huffman_data *head)
{
    huffman_data *temp, *temp1, *temp2, *pre_temp1, *pre_temp2, *post_temp1, *swap;
    for(temp1 = head; temp1 != NULL; temp1 = temp1->linker)
    {
        for(temp2 = temp1->linker; temp2 != NULL; temp2 = temp2->linker)
        {
            if(temp1->frequency > temp2->frequency)
            {
                if(temp1->linker == temp2)
                {
                    if(temp1 != head)
                    {
                        temp = head;
                        while(temp->linker != temp1)
                        {
                            temp = temp->linker;
                        }
                        temp1->linker = temp2->linker;
                        temp2->linker = temp->linker;
                        temp->linker = temp2;
                    }
                    else
                    {
                        head->linker = temp2->linker;
                        temp2->linker = head;
                        head = temp2;
                    }
                }
                else
                {
                    if(temp1 != head)
                    {
                        pre_temp1 = head;
                        while(pre_temp1->linker != temp1)
                        {
                            pre_temp1 = pre_temp1->linker;
                        }
                        pre_temp2 = head;
                        while(pre_temp2->linker != temp2)
                        {
                            pre_temp2 = pre_temp2->linker;
                        }
                        post_temp1 = head;
                        while(post_temp1 != temp1->linker)
                        {
                            post_temp1 = post_temp1->linker;
                        }
                        temp1->linker = temp2->linker;
                        temp2->linker = post_temp1;
                        pre_temp1->linker = temp2;
                        pre_temp2->linker = temp1;
                    }
                    else
                    {
                        post_temp1 = head;
                        while(post_temp1 != temp1->linker)
                        {
                            post_temp1 = post_temp1->linker;
                        }
                        pre_temp2 = head;
                        while(pre_temp2->linker != temp2)
                        {
                            pre_temp2 = pre_temp2->linker;
                        }
                        temp1->linker = temp2->linker;
                        temp2->linker = post_temp1;
                        head = temp2;
                        pre_temp2->linker = temp1;
                    }
                }
                swap = temp1;
                temp1 = temp2;
                temp2 = swap;
            }
        }
    }
        for(huffman_data *temp = head; temp != NULL; temp = temp->linker)
            cout << temp->letter << "   " << temp->frequency << endl;
        cout << endl;
        return;
}