c++ urejevanje

char *temp;

Zato, ker polje ni tipa char*, ampak char**.

Hehe... si zvezdice še kar za rezervo nasipal po kodi.

Očitno ne razumeš kazalcev - popravi tako, kot sem ti napisal, prevedi, poskusi, potem pa še enkrat poglej v skripto/knjigo, da boš razumel kaj si naredil.

Potem se pa lahko lotiš tega, kaj je to BubbleSort...

Si popravil in poskusil prevesti tako, kot sem napisal v prvem odgovoru?

Ajajajaj... sedaj sem šele opazil, da uporabljaš statično MxN polje.
Tega ne boš mogel razrešiti s kazalci.

Katera varianta ti je bolj všeč: funkcija ostane enaka, spremeniš pa preostanek programa; ali pa spremeniš funkcijo, vendar pa potem ne prestavljaš kazalcev na posamezna polja.

Ti povej...

void urejanje(char polje[stevilo][dolzina_besede])
{
    char temp[dolzina_besede];
    bool swapped;

    do {
        swapped = false;
        for (int ii = 0; ii < (stevilo - 1); ii++) {
            if (strlen(polje[ii]) < strlen(polje[ii + 1])) {
                strcpy(temp, polje[ii]);
                strcpy(polje[ii], polje[ii + 1]);
                strcpy(polje[ii + 1], temp);
                swapped = true;
            }
        }
    } while (swapped);
}

Narobe si se lotil. Če hočeš, oziroma če imaš še kaj volje, ti lahko poskusim pokazati zakaj...

OK. Bistvena razlika je v strukturi, ki je shranjena v pomnilniku.

char polje[10][10];

To je polje 10x10 elementov tipa 'char'. Vseh 100 znakov je v enem bloku pomnilnika, en za drugim.

char* polje[10];

To je pa polje 10 elementov tipa 'char*'. Vsak element je potem kazalec na ločen kos pomnilnika, kjer je shranjena dejanska vsebina vrstice. 10 kazalcev je v enem bloku pomnilnika, eden za drugim. Vrstice na katere kažejo pa so razmetane drugje. Zato uporabljamo kazalce, da nam "pokažejo" kje se ti znaki dejansko nahajajo.

Bistvena razlika je v temu, da moraš po prvi varianti za zamenjavo dveh vrstic prenesti celotno vsebino teh vrstic (to je opletanje s strcpy). Po drugi varianti, pa moraš med seboj samo zamenjati kazalce na vsebino posameznih vrstic. S tem boš vsebino vrstic pustil tam kjer je, spremenil (uredil) pa boš samo vrstni red kazalcev in s tem tudi vrstni red izpisa.

Na takšnem primeru je ta razlika morda res nepomembna, vendar si sedaj predstavljaj, da imaš 10000 vrstic s po 10000 znaki. Po prvi varianti bo BubbleSort skopiral do cca. 10000 * 10000 * 3 bytov = 300.000.000 bytov. Po drugi varianti pa do cca. 10000 * 4 * 3 bytov = 120.000 bytov. Tako čez uč postanejo razlike zelo hitro zelo pomembne.

Se ti pa po drugi varianti zaplete zato, ker moraš začeti upravljati s pomnilnikom. To upravljanje s pomnilnikom pa je bistvena razlika med C++ in Java razvojem!

No... če grem sedaj na primer:

#define MAX_DOLZINA_VRSTICE 15
#define MAX_VRSTIC 10

void uredi(char* polje[], int vrstic);

int main(int argc, char **argv) {
    char vrstica[MAX_DOLZINA_VRSTICE];
    char* polje[MAX_VRSTIC];
    int ii;

    for (ii = 0; ii < MAX_VRSTIC; ii++) {
        cin >> niz;
        polje[ii] = strdup(vrstica);
    }

    uredi(polje, MAX_VRSTIC);

    for (ii = 0; ii < MAX_VRSTIC; ii++) {
        cout << polje[ii];
        free(polje[ii]);
    }

    return 0;
}

void uredi(char* polje[], int vrstic) {
    char *temp;
    bool swapped;

    do {
        swapped = false;
        for (int ii = 0; ii < (vrstic - 1); ii++) {
            if (strlen(polje[ii]) < strlen(polje[ii + 1])) {
                temp = polje[ii];
                polje[ii] = polje[ii + 1];
                polje[ii + 1] = temp;
                swapped = true;
            }
        }
    } while (swapped);
}

Sicer ne vem, če se bo od prve prevedel (#include stavki manjkajo), ker sem ga kar iz glave napisal, ampak notri je vse, kar potrebuješ. Edini dve stvari, ki ju do sedaj v tej temi še nisi videl sta 'strdup' in 'free'. Z eno naredim kopijo niza, z drugo pa na koncu ta kos pomnilnika vrnem nazaj na kopico (recimo temu tako). Več o njih pa lahko prebereš v dokumentaciji.

Koda pa je napisana po naslednjih načelih:
1) Za #define konstante uporabljam SAMO VELIKE ZNAKE, da jih je lažje ločiti od ostalih spremenljivk.
2) Če že uporabljam konstante, sem pri njihovi uporabi dosleden. Nikjer nimam zapisanih številk.
3) Konstant ne uporabljam vsepovsod, ampak samo tam, kjer imajo res svoj pomen. Funkciji lahko posredujem število elementov kot parameter, s čemer jo naredim bolj univerzalno.
3) Števce poimenujem ii, jj, kk, ... namesto i, j, k. Če kdaj kaj iščem po kodi, je lažje najti ii, kot pa i.
4) Kar vzamem iz kopice (strdup), na kopico tudi vrnem (free).

Tip char je en sam znak. Tip char* je kazalec na en znak. Tip std::string je pa dejansko razred, ki ima svoje metode, ki ti omogočajo enostavno delo z zaporedji znakov (tipa char).

Do tukaj je vse še čisto enostavno, potem pa tudi jaz ne vem kako bi pomnilnik, kazalce in polja opisal razumljivo za začetnika. Ampak lahko pa poskusim...

Najprej pomnilnik. Tega si lahko predstavljaš kot zelooooooooo dolg trak na katerega vpisuješ podatke. Najmanjša enota podatka pa je (vsaj na tebi domačih arhitekturah) 8-biten byte. Naslov v pomnilniku pa je številka, ki pove koliko bytov daleč od začetka traku se nahajam. Pomnilnik je poenostavljeno gledano samo eno veliko polje, ki se začne na naslovu 0 in tako daleč, kolikor imaš RAM-a.

Potem kazalci. V pomnilnik lahko zapišem karkoli. Seveda pa to pomeni, da lahko v pomnilnik zapišem tudi številko, ki mi pove na katerem odmiku se nahaja podatek, ki ga iščem. Če v pomnilnik napišem številko 200 in rečem, da ta številka kaže na podatek tipa char, bo to pomenilo, da se lahko premaknem na 200. položaj na traku in od tam preberem char, ki je tam zapisan. Ta številka pa se ravno zaradi tega imenuje "kazalec".

Potem matematika s kazalci. To ni nekaj, kar je zapisano v pomnilniku, temveč je nekaj, kar naredi prevajalnik iz tvoje kode. Ko v kodi napišeš, char* pc je to drugače, kot pa če napišeš int* pi. Prvi kazalec kaže na podatek tipa char, drugi kazalec pa kaže na podatek tipa int. Ko boš napisal pc++, se bo to prevedlo v kodo, ki bo številko zapisano v pc povečala za 1. Ko pa boš napisal pi++, pa se bo to prevedlo v kodo, ki bo številko zapisano v pi povečala za 4. To pa zato, ker tip char v pomnilniku zaseda 1 byte, tip int pa zaseda 4 byte. Ta "matematika" s kazalci je včasih malo hecna, ampak čez nekaj časa se jo (v tem fohu) navadiš. Vse kar delaš s kazalci ni nič drugega, kot seštevanje, odštevanje in primerjanje teh številk.


Sedaj pa polja. Ko pogledaš kam kaže kazalec, si s tem prišel do enega podatka. Kazalec na char, ti bo dal char, kazalec na int ti bo dal int. Vendar pa ni ničesar, kar bi prepovedovalo prebrati dva zaporedna podatka namesto enega. Ali pa tri, štiri, pet, ... To pomeni, da nenadoma tisti kazalec več ne kaže na en char (int, float, ..., nek tip), temveč lahko kaže na celo zaporedje elementov. Če imam int* pi, to pomeni, da lahko z *(pi + 0) preberem tisto vrednost na katero kaže pi. Z *(pi + 1) preberem logično naslednjo vrednost. Z *(pi + 2) preberem še eno naprej. Čeprav je int dolg 4 byte, pa prevajalnik, s svojo "kazalčno matematiko" poskrbi, da se vrednost kazalca pravilno povečuje. Edino, kar moram še urediti je to, da skrajšam preveč dolgo zapisovanje tega dostopanja do zaporednih elementov. Zato C in C++ poznata sintakso pi[0], pi[1], pi[2], pi[nekaj], ... Pri čemer je pi[nekaj] isto, kot če bi zapisal *(pi + nekaj). Samo krajše. No, sedaj pa, ko že uporabljam operator [], pa lahko temu rečem tudi polje.

---

Kratek intermezzo na temo polj, ki so ali pa niso na kopici. Če bi imel CSS, bi bil to poseben okvirček float:right.

Kopica (heap) je pojem za neko strukturo, ki jo standardna knjižnica za C uporablja v pomnilniku. Služi predvsem temu, da (iz kopice) zahtevam kos pomnilnika točno določene velikosti (malloc ali new), na koncu pa ga vrnem (nazaj na kopico - free ali delete). To pa samo zato, da mi ni potrebno samemu razmišljati o naslovih v pomnilniku, ki jih že uprabljam, za razliko od tistih, ki jih še ne uporabljam.

Kazalci praviloma kažejo ravno na pomnilnik, ki sem si ga z malloc iz kopice rezerviral, na koncu pa se od mene pričakuje, da ga bom s free na kopico tudi vrnil. To so polja, ki jih deklariram z int* pi.

Potem pa obstajajo še polja, ki jih deklararam z int pi[]. Ta pa imajo malo drugačne lastnosti, saj jih prevajalnik ne gleda tako kot ostale kazalce, temveč jim določi natančno lokacijo kamor kažejo. To pomeni, da vrednosti tega kazalca pravilmo tudi ni možno (brez ogromno prepričevanja) spremeniti. Zaenkrat naj ostane pri temu, da to sicer so kazalci, ampak pomnilnik, na katerega kažejo, ne rabiš upravljati sam.

Konec medmeta.

---

Seveda pa temu takoj sledi vprašanje: kako vem kako dolgo je takšno dinamično polje? V bistvu ne vem. C in C++ sta jezika, ki teh "knjigovodskih" stvari ne skrivata, temveč programerja prisilita v veliko mero knjigovodenja. Če želim vedeti koliko znakov imam v polju, si moram to nekako zapisati. Po krajšem premisleku ugotovim, da imam dva načina zapisovanja dolžine polj: pred prvi element zapišem dolžino polja, ali pa polje zaključim z nekim dogovorjenim znakom. V enem primeru to pomeni, da moram vedeti, da moram najprej prebrati dolžino, nato pa šele prvi element. V drugem primeru pa to pomeni, da določene vrednosti v zaporedju ne morem uporabiti - marker konca podatkov.

In tukaj končno pridemo do famoznih nizov (angleško string-ov), ki to niso. Čeprav so, ampak ne takšni, kot bi jih želel ali pričakoval, če si kdaj videl kakšen drug programski jezik.

Dinamično polje char* se smatra, da vsebuje vse znake, razen znaka '\0' (ta znak je char z vrednostjo NUL po ASCII kodni tabeli znakov - ne sekiraj se za definicijo, samo zapomni si, da je to vrednost 0 in ne znak '0'). To pomeni, da je prvi znak niza na pc[0], drugi je na pc[1], ... in tako do zadnjega znaka pc[nevemkoliko], ki ima vrednost '\0'. Če želim izvedeti dolžino takšnega zaporedja, lahko to naredim tako:

int ii; for (ii=0; pc[ii] != '\0'; ii++); cout << ii;

Seveda, pa lahko napišem tudi strlen(pc), kar naredi isto in vrne enak rezultat. Zato je niz "123456" dolg 7 bytov (tistega '\0' na koncu doda prevajalnik sam), prvi znak je na odmiku 0, zadnji berljiv znak pa je na odmiku 5, strlen pa vrne 6 - število berljivih znakov. "123456" je v pomnilniku namreč zapisano kot: {49, 50, 51, 52, 53, 54, 0}.

In kaj vse to sedaj pomeni?

To pomeni, da če sešteješ dva kazalca, dejansko seštevaš njuni vrednosti, ne pa združuješ polj na katera kažejo. To pomeni, da dva niza v C-ju sešteješ tako, da:
- (iz kopice) vzameš kos pomnilnika, ki je dolg toliko, kolikor sta dolga oba posamična niza + 1 znak
- na začetek tega kosa pomnilnika preneseš vsebino prvega niza
- tam kjer si končal s prenosom prevega niza, nadaljuješ z dodajanjem znakov iz drugega niza
- na koncu dodaš še znak '\0', da označiš konec dinamičnega polja (to je tisti +1 znak, ki ga moraš prišteti)

V kodi to izgleda tako:

 - str_new = malloc(strlen(str1) + strlen(str2) + 1); // Rezerviram pomnilnik
 - strcpy(str_new, str1); // V ta kos pomnilnika prenesem vsebino prvega niza
 - strcat(str_new, str2); // Na njegov konec dodam vsebino drugega niza.
                          // Funkcija bo sama dodal tisti '\0'

Vendar pa imaš v C++ še cel kup razredov in eden izmed njih je std::string. Ta razred pa je napisan tako, da lahko vse zgoraj napisano znova pozabiš, saj vse to počne skrito pred tvojimi očmi. To pomeni, da lahko dva razreda std::string tudi "sešteješ" med seboj, saj je za njiju definirana čisto posebna verzija (overload) operatorja +. V ozadju pa se potem, ko napišeš str1 + str2 še vedno zgodi vse to, kar sem ti napisal.

...

Tako, za danes imam dovolj...