[C] Sortowanie w strukturze


(Mateusz Tyl) #1

Witam,

Mam problem otóż chciałbym posortować elementy w strukturze według nazwisk. Struktura zawiera Imie, Nazwisko, Date Urodzenia(rok, miesiac, dzien), Rok zatrudnienia oraz ostatni miesięczny zarobek. Chciałbym te dane posortować według nazwisk ale nie mam pojęcia jak zrobić to by reszta danych powędrowała razem z posortowanymi nazwiskami(czyli jak już nazwiska będą posortowane to żeby nadal Imie, data itd należało do tej samej osoby );

Wklejam swój kod:

MAIN

struct dane

{

    int id;

    char *nazwisko,*imie;

    struct dane *nastepny;

    struct dane *poprzedni;

};


int main()

{

    int wybor;

    puts("Witam w bazie danych");

    wczytaj();

    do

    {

        puts("Co chcesz zrobic?\n1 - Wyswietlic Liste\n2 - Dodac Osobe\0 - Zakonczyc");

        scanf("%d",&wybor);

        switch(wybor)

        {

            case 1:

            {

                wyswietl();

                break;

            }

            case 2:

            {

                dodaj();

                break;

            }

            case 3:

            {

                sortuj();

                break;

            }


        }

    }while(wybor!=0);


    return 0;

}

Funkcje

#include 

#include 

#include "/Users/Matek/Documents/Programowanie Proceduralne/StrukturaDanych/StrukturaDanych/Header.h"



struct dane

{

    int id,rokzatr,zarobki,roku,miesu,dzienu;

    char *nazwisko,*imie,*dataur;

    struct dane *nastepny;

    struct dane *poprzedni;

};


void dodaj()

{

    struct dane *nowy;


    nowy = (struct dane*)malloc(sizeof(struct dane));

    nowy->nazwisko = (char*)malloc(100*sizeof(char));

    nowy->imie = (char*)malloc(100*sizeof(char));

    while (nowy->id == 0)

    {


        printf("Podaj id: ");

        scanf("%d",&nowy->id);

        printf("Podaj imie: ");

        scanf("%s",nowy->imie);

        printf("Podaj naziwsko: ");

        scanf("%s",nowy->nazwisko);

        printf("Podaj date urodzenia:\n");

        printf("Podaj rok urodzenia: ");

        scanf("%d",&nowy->roku);

        printf("Podaj miesiac urodzenia: ");

        scanf("%d",&nowy->miesu);

        printf("Podaj dzien urodzenia: ");

        scanf("%d",&nowy->dzienu);

        printf("Podaj rok zatrudnienia: ");

        scanf("%d",&nowy->rokzatr);

        printf("Podaj zarobki za ostatni miesiac: ");

        scanf("%d",&nowy->zarobki);


        if(pierwszy==NULL)

        {

            nowy->nastepny = NULL;

            nowy->poprzedni = NULL;

            pierwszy = nowy;

            ostatni = nowy;

        }

        else

        {

            nowy->nastepny = NULL;

            nowy->poprzedni = ostatni;

            ostatni->nastepny = nowy;

            ostatni = nowy;

        }

    }

}


void wyswietl()

{

    struct dane *wyswietl;

    wyswietl = pierwszy;

    while(wyswietl != NULL)

    {

        printf("%d. %s %s %d.%d.%d %d %d\n",wyswietl->id,wyswietl->imie,wyswietl->nazwisko,wyswietl->roku,wyswietl->miesu,wyswietl->dzienu,wyswietl->rokzatr,wyswietl->zarobki);

        wyswietl=wyswietl->nastepny;

    }

    /* Wyswietlanie od tyłu

     wyswietl = ostatni;

     while(wyswietl !=NULL)

     {

     printf("%d %s %s\n",wyswietl->id,wyswietl->imie,wyswietl->nazwisko);

     wyswietl=wyswietl->poprzedni;


     }

     */


}


void zapisplik()

{

    FILE *dane;

    struct dane *zapis;

    zapis = pierwszy;

    dane = fopen("/Users/Matek/Documents/Programowanie/BazaDanych/baza.csv","w");

    while(zapis != NULL)

    {

        fprintf(dane,"%d. %s %s\n",zapis->id,zapis->imie,zapis->nazwisko);

        zapis=zapis->nastepny;

    }


}


void wczytaj()

{

    FILE *dane;

    /*

    char nazwapliku[110], sciezka[110];

    do{

    printf("Wprowadz nazwe bazy do wczytania: ");

    scanf("%s",&*nazwapliku);

    //Dodanie sciezki do nazwy

    strcpy (sciezka,"/Users/Matek/Documents/Programowanie/BazaDanych/");

    strncat (sciezka,nazwapliku, 70);

    dane = fopen(sciezka,"r");

    }while(dane == NULL);

    */

    dane = fopen("/Users/Matek/Documents/Programowanie/BazaDanych/BazaMoja.csv","r");

    struct dane *nowy;

    while (!feof (dane))

    {

    nowy = (struct dane*)malloc(sizeof(struct dane));

    nowy->nazwisko = (char*)malloc(100*sizeof(char));

    nowy->imie = (char*)malloc(100*sizeof(char));



        fscanf(dane,"%d %s %s %d.%d.%d %d %d\n",&nowy->id,nowy->imie,nowy->nazwisko,&nowy->roku,&nowy->miesu,&nowy->dzienu,&nowy->rokzatr,&nowy->zarobki);

        //printf("Dane: %d. %s %s\n",nowy->id,nowy->imie,nowy->nazwisko);


        if(pierwszy==NULL)

        {

            nowy->nastepny = NULL;

            nowy->poprzedni = NULL;

            pierwszy = nowy;

            ostatni = nowy;

        }

        else

        {

            nowy->nastepny = NULL;

            nowy->poprzedni = ostatni;

            ostatni->nastepny = nowy;

            ostatni = nowy;

        }

    }


}


void sortuj()

{


}

Prosiłbym o jakieś wskazówki gdyż samo sortowanie to jeszcze dam rade - strcmp ale już zeby reszta się trzymała to nie, można to zrobić bardzo na około czyli po prostu jakoś pododawać resztę danych do tego ale to ogromne ilości linijek kodu zajmie, czy jest jakiś sposób by złączyć te dane i się o to nie martwić?

Korzystam z kompilatora XCode na Mac'u.

Z góry dziękuję za odpowiedź!


(B.Andy) #2

Po co ręcznie chcesz wiersze przenosić? Istnieje funkcja qsort, która wszystko (no dobra, nie tak wszystko - trzeba jeszcze napisać funkcję porównującą) robi za programistę.

http://stackoverflow.com/questions/2908 ... bute-value


(Mateusz Tyl) #3

Dzięki za wskazówkę ale nadal mam problem w wykorzystaniem tej funkcji. Mógłbyś mnie nakierować jak ją zaimplementować do mojego kodu? (czy muszę coś zmieniać w strukturze by to działało czy tutaj jest kopiuj - wklej, bo coś nie mogę zmusić tego do działania.)


(Grzelix) #4

To co kolega @B.Andy podał jest przydatne ale potrzebujesz paru zmian.

Po pierwsze w podanym linku opisane jest sortowanie tablicy danych "obiektów" jakieś zdefiniowanej struktury, natomiast ty posiadasz coś w rodzaju kolejki - dany item wie kto jego poprzednikiem i następnikiem.

Moja propozycja wygląda tak:

sort(){

array = prepare_array();

qsort(array, 25, sizeof(data), compareUsername);

correct_queue();

}

metoda prepare_array() zwraca tablicę danych "obiektów", znajduję pierwszy i przechodzi przez kolejkę wypełniając tablicę. metoda correct_queue() tworzy poprawną strukturę kolejki. Zaczyna od pierwszego "obiektu" i ustawia poprzedniki i następniki. do tego metoda compareUsername ale to już analogicznie jak podanym linku. ====================================== Po krótkim namyśle widzę jeszcze jedno rozwiązanie (nie wiem czy łatwiejsze, sam zdecyduj). Zaimplementowanie sortowania bąbelkowego dla tej struktury. Pseudokod:

sortuj(){

dane a = pierwszy;

dane n = ostatni;

bool koniec = false;

while(koniec){

  while (a != ostatni){

    dane b = a->następny;

    if(porównaj(a, b)){ //jeśli a jest większe od b zamień miejscami

       b->poprzedni = a->poprzedni;

       a->następny = b->następny;

       a->poprzedni = b;

       b->następny = a;

    }

    else{

       a= a->następny;

    }

  }//koniec pierwszego while'a, na końcu mamy największy element, teraz wystarczy posortować n-1 elementów więc zmniejszamy

  ostatni = a->poprzedni;

  a = pierwszy;

  if (ostatni == pierwszy); //jeśli ostatni równy pierwszemu to koniec

    koniec = true;

}

pisałem z palca ale mam nadzieje że idea została zrozumiana