• Index
  •  » Tutorial
  •  » [C] Tablice jednowymiarowe i dynamiczna alokacja pamięci.

#1 04-07-2007 16:29:09

mieczyk

Member

3375619
Zarejestrowany: 03-08-2007
Posty: 24
Punktów :   
WWW

[C] Tablice jednowymiarowe i dynamiczna alokacja pamięci.

Proszę moderatora lub administratora o przeniesienie artykułu do działu "Tutorial". Z góry dziękuję.


Niniejszy artykuł jest kontynuacją tekstu "Wskaźniki - wprowadzenie" W dużej mierze pomogła mi ta publikacja:http://pl.wikibooks.org/wiki/Programowa … %C5%BAniki. Jeżeli ktoś znajdzie jakieś błędy, proszę o natychmiastowe sprostowanie.

W następnej części postaram się omówić tablice wielowymiarowe oraz przekazywanie tablic do funkcji. Tymczasem życzę miłej lektury .

Rzutowanie wskaźników c.d.

W poprzednim artykule pokazałem w jaki sposób rzutować typy wskaźników. Nie pokazałem jednak jak wyłuskać wartość z takiego wskaźnika. Oto przykładowy kod, który powinien to wyjaśnić:

Kod:

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

int main()
{
    int x = 5;
    void *wsk_x;

    wsk_x = (int*)&x;

    printf("Adres zmiennej x: %d\n", wsk_x);
    printf("Wartosc zmiennej x: %d\n", *(int*)wsk_x);

    getchar();
    return 0;
}

Tablice i wskaźniki

Każdy powinien zdawać sobie sprawę, że tablice w języku C to też pewien rodzaj zmiennej wskaźnikowej. Wskaźnik tego rodzaju wskazuje na miejsce w pamięci, gdzie przechowywany jest pierwszy element tablicy. Następne elementy znajdują się bezpośrednio w następnych komórkach pamięci, w odstępie zgodnym z wielkością odpowiedniego typu zmiennej.

W poprzednim artykule, przedstawiając pamięć graficznie, nie wspomniałem o jednej istotnej rzeczy. Otóż różne rodzaje zmiennych mogą zajmować różne ilości komórek pamięci. Np. Zmienna typu char zmieści się w jednej komórce, ale zmienna typu int może potrzebować już więcej komórek. W tym artykule, weźmiemy na to poprawkę.

Ilustruje to poniższy przykład:

Kod:

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

int main()
{
    int tab1[]={100, 200, 300};
    char tab2[] = {'a', 'b', 'c'};
    
    printf("&tab1[0] = %d\n", &tab1[0]);
    printf("&tab1[1] = %d\n", &tab1[1]);
    printf("&tab1[2] = %d\n", &tab1[2]);
    
    printf("\n");
    
    printf("&tab2[0] = %d\n", &tab2[0]);
    printf("&tab2[1] = %d\n", &tab2[1]);
    printf("&tab2[2] = %d\n", &tab2[2]);
    
    getchar();
    return 0;
}

Zadeklarowaliśmy dwie tablice. Jedną typu int, a drugą typu char. Następnie wyświetliliśmy adresy poszczególnych elementów obu tablic. Od razu widać, że różnica adresów elementów tablicy typu int jest większa niż różnica adresów elementów typu char.

Wiąże się to z tym, że różne typy danych (m.in. int i char) różnią się wielkością. Można to sprawdzić za pomocą operatora sizeof, który zwraca wielkość danego obiektu w bajtach.

    printf("%d\n", sizeof(int));
    printf("%d\n", sizeof(char));

Dobrze, ale co z tego, że tablice to zmienne wskaźnikowe? Spójrzmy na poniższy przykład:

Kod:

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

int main()
{
    int tab[5];
    int i;
    
    for(i=0; i<=4; i++)
       tab[i]=i;
       
    for(i=0; i<=4; i++)
       printf("tab[%d] = %d\n", i, i);
       
    printf("\n");
    
    /* Chcemy sie odniesc do 2-go elementu tablicy (z indeksem 1) */
    printf("%d\n", tab[1]);
    
    /* To samo co wyzej, metoda wskaznikowa */
    printf("%d\n", *(tab+1));  
    
    getchar();
    return 0;
}

Część kodu odpowiedzialna za utworzenie tablicy, wypełnienie jej oraz wyświetlenie jest chyba jasna. Bardziej interesujące są dwie ostatnie funkcje printf. Najpierw wyświetlamy drugi element tablicy (z indeksem 1, ponieważ numerowaliśmy od zera), następnie...zrobiliśmy to samo, tylko metodą wskaźnikową. Obie metody odwoływania się do elementów tablicy są równoważne z definicji.

Aby lepiej zrozumieć na czym to polega, przeanalizujmy poniższą tabelkę (odnosimy się do naszego ostatniego przykładu):

                          Instrukcja               |              Co wyświetli ?
----------------------------------------------------------------------------------------------------
          printf(„%d”, tab);                    |       Adres elementu tab[0]
----------------------------------------------------------------------------------------------------
          printf(“%d”, &tab[0]);              |       Adres elementu tab[0]
¬----------------------------------------------------------------------------------------------------
          printf(“%d”, tab[0]);                |                 0
----------------------------------------------------------------------------------------------------
          printf(“%d”, *tab);                  |                 0
----------------------------------------------------------------------------------------------------
          printf(“%d”, tab[2]);                |                 2
----------------------------------------------------------------------------------------------------
          printf(“%d, *(tab+2);              |                 2
----------------------------------------------------------------------------------------------------

Arytmetyka wskaźników

W języku C istnieje możliwość m.in. odejmowania wskaźników, aby sprawdzić jak daleko są od siebie położone. Możemy również dodawać do wskaźników liczby całkowite. Istotne jest jednak, że dodanie do wskaźnika liczby dwa nie spowoduje przesunięcia się w pamięci komputera o dwa bajty. Tak naprawdę przesuniemy się o 2*rozmiar zmiennej. Zerknijmy na poniższy przykład:

Kod:

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

int main()
{
    int tab[]={1,3,5,7,9};
    int *wsk_tab;
    
    wsk_tab=&tab[0];
    
    wsk_tab = wsk_tab + 4;
    
    printf("%d\n", *wsk_tab);  
    
    getchar();
    return 0;
}

Oczywiście cały czas pamiętamy, że tablice indeksujemy od 0. Na początku inicjujemy tablicę zawierajacą 5 elementów:

tab[0] = 1;
...
tab[4] = 9;

Następnie tworzymy zmienną wskaźnikową wsk_tab i przypisujemy jej adres pierwszego elemetu tablicy (należy zauważyć, że instrukcja wsk_tab = &tab; nie byłaby prawidłowa).

Teraz dodajemy do zmiennej wskaźnikowej liczbę 4. Powoduje to, że wskaźnik będzie wskazywał na piąty element tablicy (przypomnienie: tab[4] jest piątym elementem tablicy, ponieważ indeksujemy od 0 i co za tym idzie tab[0] jest elementem pierwszym).

Możemy teraz wyświetlić nasz „piąty element” poprzez operator wyłuskania.

Wskaźnik jako tablica.

Ciekawostką jest to, że wskaźniki możemy traktować jako tablice. Spójrzmy na poniższy kod:

Kod:

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

int main()
{
    int tab[]={1,3,5,7,9};
    int *wsk_tab;
    
    wsk_tab=&tab[0];
    
    printf("%d\n", wsk_tab[0]);  
    
    getchar();
    return 0;
}

W zasadzie, prawie nie różni się on od poprzedniego przykładu, poza jednym elementem. W funkcji printf użylimy zmiennej wskaźnikowej z indeksem 0 (wcześniej przypisując jej adres pierwszego elementu tablicy). Okazuje się, że taka operacja jest dozwolona. Program wyświetli wartość 1. Gdybyśmy w funkcji printf wstawili wsk_tab[1], program dałby nam na wyjściu 3 itd.

Dynamiczna alokacja pamięci.

Do tej pory, kiedy deklarowaliśmy tablicę znaliśmy jej rozmiar od początku (i deklarowaliśmy go od razu). Często jest tak, że nie wiemy na początku jak duża powinna być nasza tablica. Oczywiście możemy zadeklarować tablicę o bardzo dużym rozmiarze, ale okazuje się, że jest to ogromne marnotrawstwo pamięci, ponieważ pewnie i tak będziemy potrzebowali mniejszej liczby elementów. Na szczęście język C oferuje nam dynamiczną alokację pamięci.

Cytat z Wikipedii:

Czym jest dynamiczna alokacja pamięci? Normalnie zmienne programu przechowywane są na tzw. stosie (ang. stack) - powstają, gdy program wchodzi do bloku, w którym zmienne są zadeklarowane a zwalniane w momencie, kiedy program opuszcza ten blok. Jeśli deklarujemy tak tablice, to ich rozmiar musi być znany w momencie kompilacji - żeby kompilator wygenerował kod rezerwujący odpowiednią ilość pamięci. Dostępny jest jednak drugi rodzaj rezerwacji (czyli alokacji) pamięci. Jest to alokacja na stercie (ang. heap). Sterta to obszar pamięci wspólny dla całego programu, przechowywane są w nim zmienne, których czas życia nie jest związany z poszczególnymi blokami. Musimy sami rezerwować dla nich miejsce i to miejsce zwalniać, ale dzięki temu możemy to zrobić w dowolnym momencie działania programu.
Należy pamiętać, że rezerwowanie i zwalnianie pamięci na stercie zajmuje więcej czasu niż analogiczne działania na stosie.

Dodatkowo, zmienna zajmuje na stercie więcej miejsca niż na stosie - sterta utrzymuje specjalną strukturę, w której trzymane są wolne partie (może to być np. lista). Tak więc używajmy dynamicznej alokacji tam, gdzie jest potrzebna - dla danych, których rozmiaru nie jesteśmy w stanie przewidzieć na etapie kompilacji lub ich żywotność ma być niezwiązana z blokiem, w którym zostały zaalokowane.”

Jak zwykle posłużymy się prostym przykładem:

Kod:

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

int main()
{
    int *tab;
    int rozmiar;
    int i;
    
    printf("Podaj rozmiar tablicy: ");
    scanf("%d", &rozmiar);
    
    tab = (int*)malloc(rozmiar * sizeof(int));

    for(i=0; i<rozmiar; i++)
    {
        printf("tab[%d] = ", i);
        scanf("%d", &tab[i]);
    }
    
    printf("\n");
    
    for(i=0; i<rozmiar; i++)
         printf("tab[%d] = %d\n", i, tab[i]); 
    
    free(tab);
    
    
    getchar();
    getchar();
    return 0; 
}

Rozpocznijmy analizę naszego kodu od początku. Na starcie inicjujemy trzy zmienne:

int *tab – wskaźnik, który będzie wskazywał na miejsce w pamięci, gdzie będzie przyechowywana
            nasza tablica.

int rozmiar – rozmiar naszej tablicy, który wprowadzimy w trakcie wykonywania się programu.

int i – zmienna pomocnicza, służąca do indeksowania tablicy i iteracji.

Następnie, program prosi użytkownika o podanie rozmiaru tablicy i w końcu najciekawszy fragment kodu:
   
               tab = (int*)malloc(rozmiar * sizeof(int));

Jest to zarezerwowanie pewnego obszaru pamięci i przydzielenie wskaźnika do niego dla zmiennej tab. Przyjrzyjmy się na początku funkcji malloc. Oto jest jej prototyp:

            *void malloc( size_t size);

Jak widać funkcja malloc zwraca wskaźnik typu void*, a pobiera ona liczbę bajtów pamięci do zarezerwowania (parametr size). Mówiąc w skrócie, funkcja malloc przydziela pamięć o wielkości size bajtów.

Więcej informacji można znaleźć pod adresem http://pl.wikibooks.org/wiki/C/malloc.

Wróćmy jednak do naszego kodu. Jak widać, przed funkcją malloc znajduje się (int*). Jak wiemy malloc zwraca wskaźnik typu void*, dlatego przekonwertowaliśmy typ void* na int*. Pamiętajmy jednak, że takie rzutowanie jest konieczne tylko w C++, w czystym C nie jest wymagane.

   Zerknijmy na argument funkcji malloc, czyli rozmiar*sizeof(int). Operator sizeof zwróci nam rozmiar (podany w bajtach) zmiennej typu int. Następnie musimy to przemnożyć przez rozmiar naszej tablicy. Załóżmy , że chcemy mieć tablicę 3-elementową typu int. Załóżmy też, że zmienna typu int zajmuje 4 bajty. Nasza tablica potrzebuje więc 3*4=12 bajtów. Uzyskamy je (te 12 bajtów) właśnie dzięki funkcji malloc.

Reszta kodu jest chyba jasna – wypełniamy tablicę oraz ją wyświetlamy. Na uwagę zasługuje jedynie fragment
                                     free(tab);

Jest to funkcja, która zwalnia przydzieloną wcześniej pamięć. Należy o tym pamiętać, ponieważ kiedy będziemy alokować pamięć bez zwalniania jej, może dojść do sytuacji, kiedy nam jej zabraknie.

Ciekawostką jest to, że zamiast:

                             tab = (int*)malloc(rozmiar * sizeof(int));

Możemy napisać:

                             tab = (int*)malloc(rozmiar * sizeof(*tab));

Offline

 
  • Index
  •  » Tutorial
  •  » [C] Tablice jednowymiarowe i dynamiczna alokacja pamięci.

Stopka forum

RSS
Powered by PunBB 1.2.23
© Copyright 2002–2008 PunBB
Polityka cookies - Wersja Lo-Fi


Darmowe Forum | Ciekawe Fora | Darmowe Fora
www.timik2.pun.pl www.rebirth.pun.pl www.booking.pun.pl www.ekonom2010.pun.pl www.mbkserv.pun.pl