Sortowanie bąbelkowe listy dwukierunkowej

0

Witam wszystkich mam problem z posortowaniem listy dwukierunkowej za pomocą sortowania bąbelkowego. Mój kod wygląda tak:

struct node {
     int key;
     struct node *left;
     struct node *right;
}; 

void sort(int count, struct node *t_node)
{
    struct node *tmp,*nextnode, *node1, *node2;
	node2 = t_node;

	do{
		 while(node2->right){
			if (node2->key > node2->right->key) {
				// zamiana B z C w liście A<->B<->C<->D na listę A<->C<->B<->D
				// B = node2
				nextnode = node2->right; // C
				tmp = node2->left; // A 
	
				if (tmp) 
					tmp->right = nextnode; // A->right = C

				if (nextnode->right)
					nextnode->right->left = node2; //D->left = B
				node2->right = nextnode->right; //B->right = D
				node2->left = nextnode->left; //B->left = C
				nextnode->right = node2; //C->right = B
				nextnode->left = tmp; //C->left = A
			}
			node2 = node2->right;
		}
		 count = count -1;
	}while(count > 1);

   
}

Problem polega na tym, że dla przykładowych danych przed sortowaniem mam

Node value: 15
Node value: 3
Node value: 1
Node value: 10 

A po sortowaniu:

 
Node value: 15
Node value: 1
Node value: 10

Gdzie mam błąd w kodzie proszę o pomoc.

0

Debuger w dłoń i klikaj, nikt tego za ciebie nie zrobi.

0

Wersja na kompletnego lenia:
Lista dwukierunkowa posiadająca gałęzie prev i next, traktowana kodem z internetu jak lista jednokierunkowa.

0

Trochę stary temat ale pomyślałem sobie: "A napiszę sobie to!"

Do posortowania takiej listy jak napisał autor (z intem jako klucz) wcale nie jest potrzebny wskaźnik na poprzedni element.

#include <stdio.h>
#include <stdlib.h>

struct Liczba{
    int wartosc;
    struct Liczba *nastepny;
    struct Liczba *poprzedni;
    struct Liczba *ostatni;
};

void dodaj(struct Liczba **glowa, int wartosc){
    struct Liczba *element = (struct Liczba*)malloc(sizeof(struct Liczba));
    element->wartosc = wartosc;
    element->nastepny = element->poprzedni = element->ostatni = NULL;

    if((*glowa) == NULL){
        (*glowa) = element;
        (*glowa)->nastepny = (*glowa);
        (*glowa)->poprzedni = (*glowa);
        (*glowa)->ostatni = (*glowa);
    }
    else{
        (*glowa)->ostatni->nastepny = element;
        element->poprzedni = (*glowa)->ostatni;
        element->nastepny = (*glowa);
        (*glowa)->poprzedni = element;
        (*glowa)->ostatni = element;
    }
}

void wypisz(struct Liczba *glowa){
    struct Liczba *temp = glowa;
    while(temp != glowa->ostatni){
        printf("%d ", temp->wartosc);
        temp = temp->nastepny;
    }
    printf("%d ", temp->wartosc);
    printf("\n");
}

void sortuj(struct Liczba *glowa){
    struct Liczba *iter_1 = NULL;
    struct Liczba *iter_2 = NULL;
    int temp = 0;

    for(iter_1 = glowa; iter_1 != glowa->ostatni; iter_1 = iter_1->nastepny){
        for(iter_2 = glowa; iter_2 != glowa->ostatni; iter_2 = iter_2->nastepny){
            if(iter_1->wartosc > iter_2->wartosc){
                temp = iter_1->wartosc;
                iter_1->wartosc = iter_2->wartosc;
                iter_2->wartosc = temp;
            }
        }
    }
}


void zniszcz(struct Liczba **glowa){
    struct Liczba *temp = (*glowa);
    struct Liczba *doZniszczenia = NULL;
    while(temp != (*glowa)->ostatni){
        doZniszczenia = temp;
        temp = temp->nastepny;

        free(doZniszczenia);
        doZniszczenia = NULL;
    }
}

int main(void)
{
    struct Liczba *tab = NULL;
    dodaj(&tab, 10);
    dodaj(&tab, 2);
    dodaj(&tab, -3);
    dodaj(&tab, 41);
    dodaj(&tab, 98);
    dodaj(&tab, 3);
    dodaj(&tab, -11);
    printf("\nPrzed sortowaniem:\n");
    wypisz(tab);
    sortuj(tab);
    printf("\nPo posortowaniu:\n");
    wypisz(tab);
    zniszcz(&tab);
    return 0;
}

https://ideone.com/DB48Ks

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