Elektroda.pl
Elektroda.pl
X
Proszę, dodaj wyjątek www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

[C]Sortowanie tablicy typu char

deveaux 07 Gru 2010 22:25 5874 14
  • #1 07 Gru 2010 22:25
    deveaux
    Poziom 7  

    Witam.

    Muszę posortować tablicę typu char, aby wykonać resztę zadania i niestety nie potrafię tego prawidłowo napisać. Poniżej daję część kodu:

    Code:

    for (i=1000;i>1;i--)
    {
        f=0;
        for (j=0;j<1000;j++)
        {
             if(anagram[j]>anagram[j+1])
             {
                 tmp=anagram[j];
                 anagram[j]=anagram[j+1];
                 anagram[j+1]=tmp;
                 f=1;
             }
        }
        if (f==0)
           break;
    }


    Proszę o pomoc.

    0 14
  • #3 07 Gru 2010 22:36
    deveaux
    Poziom 7  

    Dżyszla napisał:
    coś tu nie tak z wcięciami i nawiasami - nie sądzisz?


    Teraz może być? :P

    A i zapomniałam dodać, że tablica zapisuje nie więcej niż 1000 znaków i po tym sortowaniu, co wyżej widać, wyskakuje mi kupa krzaków.

    0
  • #4 08 Gru 2010 11:15
    sevare
    Poziom 13  

    Z tego co pamietam to C mialo wbudowaną funkcje zamiany char na kody ASCII(scanf(%i, &x) jak się nie myle) które w rzeczywistosci dla alfabetu przyjmują spojne wartosci liczbowe(65-90 dla duzych znakow i 97-122 dla malych). Moze odczytaj wartosci liter z tablicy ascii, zastosuj toUpper() lub w druga strone jak ci wygodniej, posortuj i wyswietl jako ciag char'ow

    0
  • #5 08 Gru 2010 13:08
    directx11
    Poziom 17  

    Code:
    #define SIZE    // twoj rozmiar
    

    f = 1;

    while( 0 != f )
    {
      f = 0;

      for( j = 0; j < SIZE - 1; j++ )
      {
        if( anagram[j] > anagram[j+1] )
        {
          tmp = anagram[j];
          anagram[j] = anagram[j+1];
          anagram[j+1] = tmp;
          f = 1;
        }
      }
    }


    Wyświetla Ci krzaki min. dlatego, ponieważ "mażesz" sobie po pamięci (wychodzisz poza zakres tablicy przy "anagram[j+1] = tmp;" w Twoim kodzie). Tablice indeksuje się od 0, więc maksymalny indeks w przypadku 1000 elementów to 999. Ty próbojesz indeksować 1000 a takiego elementu nie ma w tablicy. Żeby wyświetlić kod ascii lub znak z kodu wystarczy prosta konstrukcja:

    Code:
    printf( "\n%c", 100 );    // ASCII na char
    
    printf( "\n%d", 'C' );    // char na ASCII

    0
  • #6 08 Gru 2010 14:16
    deveaux
    Poziom 7  

    Nie wiem co jest nie tak, ale cały czas albo drukuje krzaki albo błędnie sortuje.
    Może wstawię całą treść zadania i część kodu która działa poprawnie.

    Treść:

    Code:

    Napisz program, który sprawdza, czy podane wyrazy są anagramami.
    Wejście

    Na wejście programu podana zostanie pewna ilość zestawów danych (co najwyżej 1000). Każdy zestaw będzie się składać z dwóch wyrazów (wyraz = ciąg złożony z liter) rozdzielonych spacją. Poszczególne zestawy zostaną rozdzielone znakiem nowej linii. Przyjmujemy, że żaden z wyrazów nie ma więcej niż 1000 znaków.
    Wyjście

    Dla każdego z wczytanych z wejścia zestawów należy sprawdzić, czy wchodzące w jego skład wyrazy są anagramami, tj. czy drugi powstaje z pierwszego poprzez przestawienie pewnej liczby znaków. Wynik, tj. napis "TAK" lub "NIE" należy wypisać na wyjście. Poszczególne wyniki należy rozdzielić znakiem nowej linii.
    Przykład

    Wejście:

        AlFa aalf
        raz dwa
        grrr rrg

    Wyjście:

        TAK
        NIE
        NIE

    Code:

    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    main()
    {
        char wyraz[1000];
        char anagram[1000];
        char tmp;
        int w=0, i=0, a=0, lw=0, la=0, n;

            while(scanf("%s %s",wyraz,anagram)==2)
            {
            // liczenie długości stringa
                 while(wyraz[w]!='\0')
                 {
                     w++;
                 }
                 while(anagram[a]!='\0')
                 {
                     a++;
                 }
                 // Tu powinno być sortowanie tablic albo zliczanie wystąpień znaków i wtedy warunki najwyżej bym zmieniła
                         if  (w!=a)
                             printf("NIE\n");
                                 else if ((strcmp(wyraz,anagram)==0) && (w=a))
                                      printf("TAK\n");
                                 else
                                      printf("NIE\n");
                                           
                a=0;
                i=0;
                lw=0;
                la=0;
                n=0;
            }
                 
                 
       


    return 0;
    }

    0
  • #7 08 Gru 2010 16:41
    sevare
    Poziom 13  

    Zacznijmy od poczatku. Moje 2 skromne uwagi do i tak juz dzialajacego kodu. Po co for'em sprawdzac dlugosc tablic - mozna skorzystac z wbudowanej funkcji sizeof() ktora dziala zdecydowanie szybciej. Druga rzecz to rozwazylbym uzycie funkcji gets() zamiast scanf(). Po przyjeciu stringa stworzy nam ona odrazu char array o odpowiedniej dlugosci (nie bedziemy deklarowac zbednej pamieci). Dodatkowo nie wiem na jakim etapie programowania jestes ale programowanie strukturalne spisuje sie troche lepiej niz "wszystko do maina". To takie techniczne uwagi a twoje sortowanie zaraz przejze

    0
  • Pomocny post
    #8 08 Gru 2010 17:56
    szelus
    Specjalista - Mikrokontrolery

    Chyba faktycznie powinno się dodać przycisk "wpuścił w maliny". ;)

    sevare napisał:
    Po co for'em sprawdzac dlugosc tablic - mozna skorzystac z wbudowanej funkcji sizeof() ktora dziala zdecydowanie szybciej.

    Jaki sizeof? sizeof() zwraca statyczny rozmiar tablicy, który jest zawsze większy, niż długość napisu - przynajmniej w poprawnie napisanym programie.
    Ręczne liczenie długości będzie często obecnie równie efektywne co wbudowana funkcja strlen() - z uwagi na zaawansowany poziom optymalizacji w kompilatorach.
    Cytat:

    Druga rzecz to rozwazylbym uzycie funkcji gets() zamiast scanf(). Po przyjeciu stringa stworzy nam ona odrazu char array o odpowiedniej dlugosci (nie bedziemy deklarowac zbednej pamieci).

    Najlepszy sposób uzyskania błędu ochrony pamięci itp. efektów. Czy gets/fgets, czy scanf nic same nie alokują, trzeba im przekazać wskaźnik do już utworzonej, odpowiednio dużej tablicy. Dodatkowo tak wczytany napis trzeba by ręcznie podzielić na dwa wyrazy, a scanf() to sam już załatwia.

    Teraz do autorki:
    Do przechowania 1000 literowego słowa potrzebna jest tablica 1001 elementowa - bo dochodzi '\0'.
    Dobrą praktyką jest zagwarantowanie, że wczytany napis nie przekroczy rozmiaru tablicy przez podanie w specyfikacji formatu maksymalnego rozmiaru pola.

    Poza tym, sortowanie bąbelkowe robisz prawie dobrze, tylko nie masz go robić po całej tablicy a tylko do długości napisu. A tak, to Ci śmieci z końca tablicy przenosi (potencjalnie) na początek.

    0
  • #9 08 Gru 2010 18:46
    sevare
    Poziom 13  

    Fakt sizeof() zwraca statyczny rozmiar tablicy i przez pospiech moj post ma troche pomieszana hierarhie. Myslac o gets/puts do ktorych wykorzystanie sizeof'a ma praktyczne zastosowanie. Skoro uwazasz ze gets powoduje bledy ochrony pamieci to jestem w szoku, programuje w C i jezeli zdazylo sie to tylko z wlasnej glupoty. Wybacz studiuje na kierunku na ktorym obsluga bledow, optymalizacja zlozonosci pamieciowej i obliczeniowej to podstawa, a odpowiednie wykorzystanie odpowiednich do danej sytuacji funkcji wbudowanych jest prostsze i "krotsze". Tak btw przymuje sie zlozonosc funkcji zwracajaca dlugosc tablicy n-elementowej na O(n) wiec nie wiem gdzie tu dluzsze dzialanie, ja widze tylko bardziej spojny zapis

    0
  • #10 08 Gru 2010 19:35
    szelus
    Specjalista - Mikrokontrolery

    @sevare
    Może to trochę OT i może trochę zbyt skrótowo napisałem - nie chodziło mi samo wykorzystanie gets() tylko Twoją sugestię, że gets() samo przydzieli pamięć na tablicę/łańcuch. Przynajmniej tak można było zrozumieć to, co napisałeś. Zadeklarowanie wskaźnika bez przydzielenia pamięci na wskazywaną zmienną to częsty błąd w programach osób początkujacych w C.
    O tym, że działa (funkcja wbudowana) szybciej też Ty pisałeś, ja się tylko do tego odniosłem. Oczywiście, że użycie funkcji standardowej jest czytelniejsze w zapisie. Ale programy "studenckie" mogą podlegać różnym, nietypowym ograniczeniom - np. zakaz korzystania z bibliotek itp.

    0
  • #11 08 Gru 2010 22:06
    deveaux
    Poziom 7  

    Teraz mam tak:

    Code:

    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    main()
    {
        char wyraz[1001];
        char anagram[1001];
        char tmp;
        int w=0, i=0, a=0, j, f=1;

            while(scanf("%s %s",wyraz,anagram)==2)
            {
            // liczenie długości stringa
                 while(wyraz[w]!='\0')
                 {
                     w++;
                 }
                 while(anagram[a]!='\0')
                 {
                     a++;
                 }
            //sortowanie
                 for (i=a;i>=0;i--)
                 {
                     f=0;
                     for (j=0;j<a;j++)
                     {
                         if(anagram[j]>anagram[j+1])
                         {
                         tmp=anagram[j];
                         anagram[j]=anagram[j+1];
                         anagram[j+1]=tmp;
                         f=1;
                         }
                     }
                     if (f==0)
                     break;
                 }
                     for (i=a;i>=0;i--)
                     {
                         f=0;
                         for (j=0;j<a;j++)
                         {




                         if(wyraz[j]>wyraz[j+1])
                         {
                             tmp=wyraz[j];
                             wyraz[j]=wyraz[j+1];
                             wyraz[j+1]=tmp;
                             f=1;
                         }
                     }   
                     if (f==0)
                     break;
                 }
     
                         if  (w!=a)
                             printf("NIE\n");
                                 else if ((strcmp(wyraz,anagram)==0) && (w=a))
                                      printf("TAK\n");
                                 else
                                     printf("NIE\n");
                                     
                                           
                a=0;
                w=0;
                i=0;
                j=0;
            }
                 
                 
       


    return 0;
    }


    I już jest coraz lepiej, ale nadal czasami drukuje mi błędne odpowiedzi i nie mam pojęcia co jest źle..

    0
  • #12 08 Gru 2010 22:51
    sevare
    Poziom 13  

    Sadzilem ze warto przytoczyc poczatkujacemu programiscie techniki sluzace ulepszeniu kodu pisanego przez niego no ale ok zmienie podejscie. Ale to bedzie zbyt dluga dyskusja wracajac do tematu.


    Code:
    else if ((strcmp(wyraz,anagram)==0) && (w=a)) 
    
                                      printf("TAK\n");

    Po 1. (w==a) chyba nie chcemy w warunku przypisywac dlugosci w dlugosci a. Druga rzecz strcmp() porownuje dlugosci i zwraca zero jesli dlugosci sa takie same. Akurat to warto porownac for'em tzn
    Code:

    int bool=1;
    for(i=0;i<w;i++)
        {
              if(wyraz[i]!=anagram[i]) bool=0;
              break;
        }
    //if(bool==0) printf("Nie");


    Dodatkowo nie wiem jakie jest zalozenie programu ale w kazdym if'ie mozesz dodac return, wtedy po wykonianiu jednorazowym programu (sprawdzenie 2 wyrazow) program sie zamknie

    A no i wtedy
    Code:

    if  (w!=a) printf("NIE\n");
                 else if(bool==0) printf("NIE\n");
                            else   printf("TAK\n");


    Do tego jedna rzecz... warto przed petla sprawdzajaco wyrazy tablic sprawdzic ich dlugosci i jezeli sa rozne to odrazu wywalic w jesli nie to petla + sprawdzenie bool i ostatni przypadek

    0
  • Pomocny post
    #13 09 Gru 2010 11:48
    szelus
    Specjalista - Mikrokontrolery

    sevare napisał:
    Druga rzecz strcmp() porownuje dlugosci i zwraca zero jesli dlugosci sa takie same. Akurat to warto porownac for'em [...]

    Ja się nie chcę czepiać, ale kolego, jeżeli słabo znasz C, to sprawdzaj wszystko dwa razy, zanim komuś podpowiesz. strcmp() służy właśnie do porównywania napisów, a nie długości, więc tu akurat jest dobrze.

    Jeżeli chodzi o techniki strukturalne itd. to ja się oczywiście zgadzam - tylko spokojnie i powoli, bo jak za dużo podpowiedzi w jednym poście, to łatwo się zgubić. ;)

    Do autorki:
    Sortowanie, a także liczenie długości jeżeli nie chcesz skorzystać z strlen(), wyłącz przed main() jako oddzielne funkcje, aby uniknąć powielania kodu.
    Teraz tak, jeżeli chodzi o sortowanie to poprzednio napisałem niedokładnie, przepraszam, ale mogłaś sama na to wpaść biorąc pod uwagę post directx11 - ostatnie elementy porównywane/przestawiane przy sortowaniu to powinny być np. wyraz[w-2] i wyraz[w-1], a 'for' jako zewnętrzna pętla sortująca jest bez sensu. Czyli powinnaś mieć coś takiego:
    Code:

    void sortuj( char *str, int len)
    {
        int f = 1;
        int i;

        while (f)
        {
            f = 0;
            for ( i = 0; i < (len - 1); ++i )
            {
                if ( str[i] > str[i+1] )
                {
                    char t = str[i];
                    str[i] = str[i+1];
                    str[i+1] = t;
                    f = 1;
                }
            }
        }
    }

    A w programie głównym coś w ten deseń:
    Code:

    int main(...)
    [...]
            w = strlen( wyraz );
            a = strlen( anagram );

            if ( a != w )
            {
                sortuj( wyraz, w );
                sortuj( anagram, a );
                if ( strcmp( wyraz, anagram ) == 0 )
                {
                     /* TAK */
                    [...]
                }
                else
                [...]
            }
            else
    [...]

    0
  • #14 09 Gru 2010 12:06
    sevare
    Poziom 13  

    Przyznaje ze sprawdzilem opis funkcji tylko w jednym zrodle... po sprawdzeniu kilku okazalo sie ze dokumentacje sa sprzeczne. Ksiazki do C aktualnie nie mam lecz nie bedac pewnym dzialania funkcji poprostu podalem kod ktory ja zastepuje. Moze wychodze ze zlego zalozenia ale nie jestem z ludzi ktorzy podsuwaja gotowce lecz tylko naprowadzaja na rozwiazanie, a nie oszukujmy sie, wlasnie napisales gotowca :)

    2
  • #15 09 Gru 2010 12:39
    directx11
    Poziom 17  

    Cytat:
    a 'for' jako zewnętrzna pętla sortująca jest bez sensu. Czyli powinnaś mieć coś takiego:

    Jak ktoś tak bardzo lubi for-a to przecież można sobie użyć :), np:
    Code:
    for( ; 0 != f ; ) albo for( ;f; )

    choć to już zaczyna trochę przypominać zabawę w IOCCC. Kolego sevare - może trochę staranności przy odpowiedziach, bo czasem można zrobić więcej krzywdy niż pożytku, zwłaszcza początkującym. Większość programistów wychowała się jednak na przykładach i analizie działającego kodu, choć oczywiście samodzielnego myślenia nic nie zastąpi. Ale dobry przykład zawsze się przyda, nawet jeśli nazwać go "gotowcem".

    0