• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Quicksort - sortowanie struktury

0 głosów
118 wizyt
pytanie zadane 24 czerwca 2018 w C i C++ przez siemasiema123.96 Początkujący (280 p.)

Musze wykonać sortowanie struktury za pomocą Quicksorta. Jest to struktura z książkami (tytuł, autor, rok wydania, cena). Wiem, że istnieje w C funkcja qsort, ale niestety nie mogę nią zrobić tego zadania, bo potrzebuje zliczyć liczbę porównań oraz zamian.

Na jakiej zasadzie powinienem podstawiać zmienną pivot? Teraz mam to zrobione tak i niestety wywala błędy w  kompilatorze

int partition(struct daneks X[], int low, int high)
{
    char pivot[MAX_TYTUL] = X[low];
    char tytul[MAX_TYTUL];
    int i = low-1, j = high+1;

    while(i<j) {
        while(X[--j]>pivot[MAX_TYTUL])
            ;
        while(X[++i]<pivot[MAX_TYTUL])
            ;
        if(i<j)
        {
           strcpy(tytul, X[i].tytul);
           strcpy(X[i].tytul, X[j].tytul);
           strcpy(X[j].tytul, tytul);
        }
    }
    return j;
}

void quicksort(struct daneks X[], int low, int high)
{
    if(low<high) {
        int partition_index = partition(X,low,high);
        quicksort(X, low, partition_index);
        quicksort(X, partition_index+1, high);
    }
}

 

komentarz 24 czerwca 2018 przez Secrus Nałogowiec (32,340 p.)
Wrzuć cały kod, bo nikt się nie będzie domyślał jak wygląda twoja struktura. Poza tym, błąd może być w zupełnie innym miejscu
komentarz 24 czerwca 2018 przez siemasiema123.96 Początkujący (280 p.)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define MAX_TYTUL 40
#define MAX_AUTOR 40
#define MAX_ksiazki 100

struct daneks {
    char tytul[MAX_TYTUL];
    char autor[MAX_AUTOR];
    int rok;
};

int odczyt_z_pliku(FILE *, struct daneks [], int rozmiar_pliku);
int zapis_do_pliku(FILE *fosoba, int licznik_osob, struct daneks [], int rozmiar_pliku);

int porownania, zamiany;

int main()
{
    int licznik_end, licznik_struktur, index;
    int rozmiar;
    struct daneks ksiazki[MAX_ksiazki];
    rozmiar = sizeof(struct daneks);

    FILE *book;
    if((book = fopen("dane.txt","a+")) == NULL)
    {
        fputs("Nie mozna otworzyc pliku.\n",stderr);
        exit(1);
    }
    rewind(book);

    licznik_struktur = odczyt_z_pliku(book,ksiazki,rozmiar);
    licznik_end = zapis_do_pliku(book,licznik_struktur,ksiazki,rozmiar);

    puts("Oto lista Twoich ksiazek: ");
    for(index = 0; index < licznik_end; index++)
        printf("%s, %s, %d \n",ksiazki[index].tytul,ksiazki[index].autor,ksiazki[index].rok);

    fwrite(&ksiazki[licznik_struktur],rozmiar,licznik_end-licznik_struktur,book);


    quicksort(ksiazki,0,licznik_struktur);

    puts("\n\nKsiazki po sortowaniu quicksort: ");
    for(index = 0; index < licznik_end; index++)
        printf("%s, %s, %d \n",ksiazki[index].tytul,ksiazki[index].autor,ksiazki[index].rok);


    return 0;
}

int odczyt_z_pliku(FILE *fosoba, struct daneks X[], int rozmiar)
{
    int licznik = 0;
    while(licznik < MAX_ksiazki && fread(&X[licznik],rozmiar,1,fosoba) == 1)
        licznik++;

    if(licznik == MAX_ksiazki)
    {
        fputs("Plik dane.txt jest pelny.",stderr);
        exit(2);
    }
    return licznik;
}

int zapis_do_pliku(FILE *fosoba, int licznik_struktur, struct daneks X[], int rozmiar)
{
    puts("\nPodaj nowe ksiazki do zapisania. \n");
    puts("Podaj tytul.");
    puts("Jesli nie chcesz dodawac nowych ksiazek i zobaczyc aktualna liste nacisnij (ENTER)!");
    while(licznik_struktur < MAX_ksiazki && gets(X[licznik_struktur].tytul) != NULL && X[licznik_struktur].tytul[0] != '\0')
        {
            puts("Teraz podaj autora.");
            gets(X[licznik_struktur].autor);
            puts("Teraz podaj rok wydania.");
            scanf("%d",&X[licznik_struktur++].rok);
            while(getchar() != '\n')
                continue;
            if(licznik_struktur < MAX_ksiazki)
                puts("Podaj nastepny tytul.");
        }
    return licznik_struktur;
}

///QUICKSORT
int partition(struct daneks X[], int low, int high)
{
    char pivot[MAX_TYTUL];
    char tytul[MAX_TYTUL];

    strcpy(pivot[MAX_TYTUL], X[low].tytul);

    int i = low-1, j = high+1;

    while(i<j) {
        while(X[--j].tytul>pivot[MAX_TYTUL])
            ;
        while(X[++i].tytul<pivot[MAX_TYTUL])
            ;
        if(i<j)
        {
           strcpy(tytul, X[i].tytul);
           strcpy(X[i].tytul, X[j].tytul);
           strcpy(X[j].tytul, tytul);
        }
    }
    return j;
}

void quicksort(struct daneks X[], int low, int high)
{
    if(low<high) {
        int partition_index = partition(X,low,high);
        quicksort(X, low, partition_index);
        quicksort(X, partition_index+1, high);
    }
}



 

1 odpowiedź

0 głosów
odpowiedź 25 czerwca 2018 przez j23 VIP (106,360 p.)

Linia 100 i 102: do porównywania łańcuchów znakowych użyj funkcji strcmp.

komentarz 25 czerwca 2018 przez siemasiema123.96 Początkujący (280 p.)

Dalej nie działa :/


///QUICKSORT
int partition(struct daneks X[], int low, int high)
{
    char pivot[MAX_TYTUL];
    char tytul[MAX_TYTUL];

    strcpy(pivot[MAX_TYTUL], X[low].tytul);

    int i = low-1, j = high+1;

    while(i<j) {
        while(strcmp(X[--j].tytul, pivot[MAX_TYTUL]) > 0)
            ;
        while(strcmp(X[++i].tytul, pivot[MAX_TYTUL]) < 0)
            ;
        if(i<j)
        {
           strcpy(tytul, X[i].tytul);
           strcpy(X[i].tytul, X[j].tytul);
           strcpy(X[j].tytul, tytul);
        }
    }
    return j;
}

void quicksort(struct daneks X[], int low, int high)
{
    if(low<high) {
        int partition_index = partition(X,low,high);
        quicksort(X, low, partition_index);
        quicksort(X, partition_index+1, high);
    }
}

 

komentarz 25 czerwca 2018 przez j23 VIP (106,360 p.)
strcmp(X[--j].tytul, pivot)

strcmp(X[++i].tytul, pivot) 

 

Podobne pytania

0 głosów
1 odpowiedź 157 wizyt
pytanie zadane 29 maja 2015 w Algorytmy przez Kororo3 Nowicjusz (150 p.)
0 głosów
2 odpowiedzi 363 wizyt
pytanie zadane 7 kwietnia 2016 w C i C++ przez Jędrzej Dembowski Użytkownik (740 p.)
0 głosów
3 odpowiedzi 131 wizyt
pytanie zadane 2 czerwca 2015 w C i C++ przez Criss Mędrzec (171,380 p.)
Porady nie od parady
Możesz ukryć, zamknąć lub zmodyfikować swoje pytanie, za pomocą przycisków znajdujących się pod nim. Nie krępuj się poprawić pochopnie opublikowanego pytania czy zamknąć go po uzyskaniu satysfakcjonującej odpowiedzi. Umożliwi to zachowanie porządku na forum.Przyciski pytania

66,451 zapytań

113,207 odpowiedzi

239,680 komentarzy

46,704 pasjonatów

Przeglądających: 272
Pasjonatów: 11 Gości: 261

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...