Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Insert-sort na liście dwukierunkowej

Ostatnio zmodyfikowano 2014-04-22 13:40
Autor Wiadomość
janiu
Temat założony przez niniejszego użytkownika
Insert-sort na liście dwukierunkowej
» 2014-04-22 13:40:06
Witam !
Chciałem napisać program który sortuje listę dwukierunkową. Mój kod działa poprawnie z wyjątkiem jednej sytuacji gdy pierwszy element jest największy i nie potrafię znaleźć błędu mógłby mi ktoś pomóc ?


C/C++
#include <iostream>

using namespace std;

struct node
{
    node * next;
    node * back;
    int value;
};

void add_start( node *& head, int x )
{
    node * temp = new node;
    temp->value = x;
    temp->next = head;
    head->back = temp;
    temp->back = NULL;
    head = temp;
   
}

void show_list( node * head )
{
    node * temp = head;
    while( temp )
    {
        cout << temp->value << "\t";
        temp = temp->next;
    }
   
}
void sort( node *& head )
{
    node * temp = head->next; //zapamietywany element
    node * pom = head; // poprzedni element
    node * wsk = head->next; //nastepny element
    while( wsk != NULL )
    {
        temp = wsk;
        pom = temp->back;
        wsk = temp->next;
       
        if( pom->value > temp->value ) // jezeli zapmaietany element jest mniejdzy niz poprzedni
        {
            if( wsk == NULL ) // jesli zapamietany element jest ostatni
            {
                pom->next = wsk;
            }
            else
            {
                pom->next = temp->next;
                wsk->back = pom;
            }
           
        }
       
        while( pom->value > temp->value ) // dopoki poprzednie elemnty sa wieksze
        {
            if( pom->back == NULL ) //jezeli przesuwany element jest pierwszy
            {
                if( pom->value > temp->value ) //jezeli pierwszy element jest wiekszy
                {
                    temp->next = pom;
                    pom->back = temp;
                    head = temp;
                    temp->back = NULL;
                }
            }
            else
            {
                pom = pom->back;
            }
           
            if( pom == temp )
            {
                break;
            }
           
        }
        if( pom->value <= temp->value && pom != temp ) // jesli poprzednik nie jest wiekszy
        {
            temp->next = pom->next;
            temp->back = pom;
            pom->next = temp;
           
        }
       
    }
   
}

int main()
{
    node * head = new node;
    head->next = NULL;
    head->value = 1;
    head->back = NULL;
    add_start( head, 1 );
    add_start( head, 2 );
    add_start( head, 3 );
    add_start( head, 1 );
    head->back = NULL;
   
    show_list( head );
    sort( head );
    cout << endl;
    show_list( head );
   
    cout << endl << endl;
    system( "PAUSE" );
}
P-108503
« 1 »
  Strona 1 z 1