sortowanie listy dwukierunkowej

Odpowiedz Nowy wątek
2016-11-10 16:41
0

Witam, mam problem z posortowaniem listy dwukierunkowej metodą quicksort. Problem polega na tym, że funkcja usuwa mi elementy mniejsze od pierwszego elementu listy, reszte natomiast normalnie sortuje i nie mogę dojść w czym problem. Zamieszczam kod funkcji do sortowania, partycjonowania i usuwania elementów:

void Sort(lista *head)
{
    lista *Lw = new lista, *Pw = new lista;

    Lw->Value = NULL;
    Lw->prev = NULL;
    Lw->next = head;

    if (Lw->next)
        Lw->next->prev = Lw;

    Pw->Value = NULL;
    Pw->next = NULL;
    Pw->prev = GetTail(head);

    if (Pw->prev)
        Pw->prev->next = Pw;

    Partition(Lw, Pw);

    Delete(Lw, Lw);
    Delete(head, Pw);
}

void Partition(lista *Lw, lista *Pw)
{
    lista *pivot, *i, *j;

    pivot = Lw->next;
    i = pivot->next;

    if (i != Pw)
    {
        do
        {
            j = i;
            i = i->next;
            if (j->Value < pivot->Value)
            {
                j->prev->next = j->next;
                j->next->prev = j->prev;
                j->next = pivot;
                j->prev = pivot->prev;
                pivot->prev = j;
                j->prev->next = j;
            }
        } while (i != Pw);

        if (Lw->next != pivot)
            Partition(Lw, pivot);
        if (pivot->next != Pw)
            Partition(pivot, Pw);
    }
}

lista *Delete(lista *head, lista *to_delete)
{
    if (to_delete->prev)
        to_delete->prev->next = to_delete->next;
    else 
        head = to_delete->next;

    if (to_delete->next)
        to_delete->next->prev = to_delete->prev;
    else
    {
        if (to_delete->prev == NULL)
            head = NULL;
        else
            to_delete->prev->next = NULL;
    }

    delete to_delete;

    return head;
}

Pozostało 580 znaków

2016-11-10 21:40
1

Ten kod jest dla mnie masakrycznie nieczytelny (albo czegoś nie wiem i kurna nie wiem czym jest lista dwukierunkowa).
E.g. jaki to ma sens?

Lw->next->prev = ...
j->next->prev = ...

Jeśli masz element E1 pokazujesz element następny E2 i poprzedni dla E2 to znów jesteś na E1.

Więc po co pisać E1->next->prev skoro to nadal E1?

+naprawdę bym pomógł ale nie mam zamiaru tego debugować w głowie.

Pozostało 580 znaków

2016-11-10 21:50
0

to może pokaże jesszcze jak wygląda struktura ...

struct lista
{
    int Value;
    lista *next, *prev;
}; 
Ale ja wiem jak wygląda lista dwukierunkowa, bo to niemalże jest implementacja uniwersalna ;) Nie odpowiedziałeś mi na zastosowane next,prev. - xfin 2016-11-10 21:57
ten łancuszek jest po to, że to nie E1 ma wskazywać na coś, tylko poprzednik jego następnika - thekross 2016-11-10 22:00
Ale poprzednik następnika E1 to dalej jest E1. - xfin 2016-11-10 22:01

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0