stos na tablicy, alokacja i odkładanie elementow

Odpowiedz Nowy wątek
2011-10-05 18:55
0

Cześć szukałęm w necie odpowiedzi ale wszystkie sa z c++ a nie c (przynajmniej ja te tylko widziałem:)) a poniewaz jestem początkujacy to pisze tu.
pomózcie prosze rozwiazac mi ten program
Zaimplementować stos z użyciem tablic

* dane mają być przechowywane w tablicy w porządku LIFO
* zmienna będąca szczytem stosu wskazuje na ostatni element w tablicy
* po przepełnieniu tablicy należy utworzyć tablicę dwa razy większą, a następnie przepisać do niej wszystkie elementy
* do przydzielania, zwalniania i kopiowania tablicy należy użyć funkcji z instrukcji
* napisać funkcję do:
      o dodawania elementów,
      o zdejmowania elementów
      o czyszczenia stosu
#include <stdio.h>
int pop (int *a,int index)
    {
    int tmp;
     printf ("powiedz jaka liczbe chcesz dodac na stos\n");
     scanf ("%i",&tmp);
    a[index]=tmp;
    return(a);
    }

int push (int *a,int index)
    {free(int*a[index])
    }
int main()
    {
    int menu,show,index=-1;
    int *a=(int*)calloc(3,sizeof(int));
    do
        {   printf("liczba elementow stosu %i\n",index+1);
            printf ("\n");
            printf ("powiedz co chcesz zrobic\n0-zakonczyc\n1-dodac dana do tablicy\n2-zobaczyc wartosci stosu\n3- usunac ostatli element stosu\nwybieram: ");
            scanf ("%i",&menu);
            if (menu==1)
                {   index++;
                    pop (a,index);
                }
            if (menu==2)
                {   show=index;
                    printf ("znak w naszej tablicy to: ");
                    for (show=0;show<index+1;show++)
                    { printf ("%i, ",a[show]);
                    }
            if (menu==3)
                {
                    pop (a,index);
                    index--;
                }
                }
        }
    while (menu!=0);
    }

narazie napisałem tyle i się zaciąłem mam pytanie dlaczego mimo że alokuje oamięć na 3 elementy (calloc) to jak nawet dodam 4 to nie wychodzi z błedem tylko dzalej nie powinien chyba dodac? w takim razie jak mam zdjąc element ze stosu (nie wiem bo zwalnianie pamieci też źle robie (f.free) a co najgorsze skoro tablica sie ciagle rozszerza to jak ma się ona przepełnić by jej zawartość skopiować do drugiej większej??

Pozostało 580 znaków

2011-10-05 20:03
0

Nie bardzo rozumiem po co twoje funkcje pop() i push() mają takie a nie inne listy parametrów. Popatrz na np. http://www.cplusplus.com/reference/stl/stack/ - piękno i prostota interfejsu w jednym. Proponuję się na tym wzorować.

Odnośnie realokacji - domyślnie stos utworzysz w ten sposób, że zaalokujesz pamięć na np. 10 elementów. Gdy ktoś wywoła 10 razy funcję push(), to zapełni całą zaalokowaną pamięć. Jedenaste wywołanie push() powinno spowodować, że wewnętrznie zaalokujesz nową pamięć (na np. 20 elementów), przekopiujesz istniejące 10 elementów do nowego obszaru pamięci, a następnie dodasz jedenasty element.

edytowany 2x, ostatnio: Tomek2, 2011-10-05 20:22

Pozostało 580 znaków

2011-10-05 20:28
0

1) push powinno wkładać coś na stos a pop z niego zdejmować.
2) jeśli pop ma free to push powinno mieć wewnątrz malloc / calloc
3) nie mieszaj funkcji struktury z obsługą interfejsu użytkownika, czyli powinny być dodatkowo funkcje "testuj_push" i "testuj_pop" lub coś w tym rodzaju.
4) wywołanie free() nie wygląda dobrze.
5) nie masz wywołania push()


Szacuje się, że w Polsce brakuje 50 tys. programistów
edytowany 2x, ostatnio: vpiotr, 2011-10-05 20:31

Pozostało 580 znaków

2011-10-05 20:28
0

wiesz no przekazałęm wskaźnik na tabele, która (przynajmniej wg mnie) powninna mieć 3 miejsca wielkosci integer, dalej powinno nie wiem wyskoczyc blad pamieci albo co tym czasem wogóle olewa jakby to co zaalokowaałem chyba ze źle to robie, drugim parametrem jest index który mówi ile elementów jest na stosie(jaki to index tabeli)
wiec chyba mało ale jeszcze lookne na to co wysłałes tylko przeraza mnie juz sam adres c++:)

co do tej realokacji to rozumiem, zalokowałem callokiem 3 komórki a tym czasem nawet jak jest wiecej to nic nie wywala, to to jak ma dojść do przepełnienia?? jeśli to poprawie i sie stos zapełni to wtedy alokuje miejsce na nowa tablice (2x większa) kopiuje a potem uwalniam stara tablice

wiesz vpiotr 1 i 5 punt poprawiłem, dawno było bo az pół roku temu :P a pkt 2,3,4 jeszcze próbuje zrozumieć, możesz cośik więcej??

edytowany 1x, ostatnio: progma, 2011-10-05 20:48

Pozostało 580 znaków

2011-10-05 21:46
0
progma napisał(a)

wiesz vpiotr 1 i 5 punt poprawiłem, dawno było bo az pół roku temu :P a pkt 2,3,4 jeszcze próbuje zrozumieć, możesz cośik więcej??

Ad. 2
Funkcja pop() / tutaj push / zawiera wywołanie "free". Musisz się zdecydować - albo raz alokujesz i dealokujesz pamięć (odpowiednio na początku i na końcu programu), albo robisz to na początku, wewnątrz push/pop oraz na końcu. Wersja "tylko w pop" jest bez sensu.

Ad. 3

int pop (int *a,int *index)
    {
    int res;
    if (*index >= 0) {
      res = a[*index];
      (*index)--;
    } else {
      res = 0; // pusty stos
    }
    return res;
    }

void push (int *a,int *index, int value)
    {
    (*index)++;
    a[*index]=value;
    }

void testuj_push(int *a,int *index)
{
    int tmp;
    printf ("powiedz jaka liczbe chcesz dodac na stos\n");
    scanf ("%i",&tmp);
    push(a, index, tmp);
}

Ad. 4
Zwolnienie tablicy int (dodaj na końcu main):

free(a);

Szacuje się, że w Polsce brakuje 50 tys. programistów
edytowany 1x, ostatnio: vpiotr, 2011-10-05 21:50

Pozostało 580 znaków

2011-10-05 22:09
0
 #include <stdio.h>
int tabmax, *b;
int push (int *a,int index)
    {
    int tmp;
     if (index==-1)
        {
            int *a=(int*)calloc(2,sizeof(int));
        }
     if (tabmax==index)
        {
           printf("stos zapelniony! tworze dwa razy większa tabele");
           tabmax=tabmax*2; /*nowa maxymalna wielkosc tabeli*/
           int *b=(int*)calloc(tabmax,sizeof(int));/*to przydział na czas kopiowania potem usune stary stos i zamienie a=b*/
           memcpy(a,b, sizeof(int));
           printf("stworzono wiekszy stos oraz skopiowano do niego wartosci ze starego");
           b=a;

        }
     printf ("powiedz jaka liczbe chcesz dodac na stos\n");
     scanf ("%i",&tmp);
    a[index]=tmp;
    return(a);
    }

int pop (int *a,int index)
    {/*free(int*a[index])*/
        index--;

    }
int main()
    {
    int menu,show,index=-1;
    tabmax=2; /*maxymalna dlugosc tabeli*/
    do
        {   printf("liczba elementow stosu %i\n",index+1);
            printf ("\n");
            printf ("powiedz co chcesz zrobic\n0-zakonczyc\n1-dodac dana do tablicy\n2-zobaczyc wartosci stosu\n3- usunac ostatli element stosu\nwybieram: ");
            scanf ("%i",&menu);
            if (menu==1)
                {   index++;
                    push (a,index);
                }
            if (menu==2)
                {   show=index;
                    printf ("znak w naszej tablicy to: ");
                    for (show=0;show<index+1;show++)
                    { printf ("%i, ",a[show]);
                    }
            if (menu==3)
                {
                    pop (a,index);
                    index--;
                }
                }
        }
    while (menu!=0);
    }

to zmieniłem nazwy no czyli kosmetyczne błedy porawiłem
2) jeśli pop ma free to push powinno mieć wewnątrz malloc / calloc ==> no to też poprawiłem rozumeiem ze chodzi ci o to ze jak stos n ma już(index==tabmax)/ albo nie ma stosu jeszecze/ to wtedy calloc
4) free(a) mam wpisac tylko na końcu maina . ale to przecież przy każdym przejściu przez pętle w mainie mi sie będzie robił free, to może go tak dać do odzielnej procedury np if (menu==4) {free a}?

chyba go tez w fukcji push trzeba dodac na koniec if (tabmax==index) tylko że free(b) nie ??
nad ad 3 to jeszcze musze pomyśleć bo od wielu godzin siedze i sie zmeczyłem :) dzieki vpiotr :)

edytowany 2x, ostatnio: progma, 2011-10-05 22:19
pop() jest źle napisany, użyj debuggera, bo błądzisz po omacku - vpiotr 2011-10-06 09:53

Pozostało 580 znaków

2011-10-05 23:57
0

memcpy(a,b, sizeof(int));

powinno być raczej:
memcpy(a,b, sizeof(int) * stary_tabmax);

gdzie stary_tabmax to długość stosu przed jego pomnożeniem przez 2. Teraz kopiujesz tylko 4 bajty.

Pozostało 580 znaków

2011-10-07 14:04
0

no to rozwiazałem część min w memcpy trzeba zrobic przed tym #include <string.h> zostały mi 4 warningi ale zrobiłem #include <stdlib.h> został tylko 1 :/.... w 43 wierszu, odpala się ale nic sie do stosu nie dodaje :P nie wiem znowc co jest zle :(

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int tabmax,*a, *b;
int menu,show;
int push (int index)
    {
    int tmp;
        if (index==-1)
            {
            a= (int*)malloc(sizeof(int)*tabmax);
            index++;
            }
        if (index<tabmax)
            {
            printf ("powiedz jaka liczbe chcesz dodac na stos\n");
            scanf ("%i",&tmp);
            a[index]=tmp;
            index++;
            }
        else
       {
           printf("stos zapelniony! tworze dwa razy wiêksza tabele\n");
           tabmax=tabmax*2; /*nowa maxymalna wielkosc tabeli*/
           b=(int*)malloc(sizeof(int)*tabmax);/*to tablica tymbasowa na czas kopiowania potem usune stary stos i zamienie a=b*/
           memcpy(b,a, sizeof(a));/*kopiuje stara tablice do nowej*/
           printf("skopiowano stary stos do nowego, wiekszego\n");
           *a=*b;
           free(b);
           printf("uwolniono tabele tymczasowa\n");
        }

    }

int pop (int index)
    { if (index=-1)
        {    printf("no more elements\n");
        }
       else
    {
        a[index]=0;
        printf("element %d zamieniono na 0\n",a[index]);
        free(a[index]);
        index--;
    }

    }
int main()
    {
    tabmax=2; /*maxymalna dlugosc tabeli*/
    int index=-1;
    do
        {   printf("liczba elementow stosu %i\n",index+1);
            printf ("\n");
            printf ("powiedz co chcesz zrobic\n0-zakonczyc\n1-dodac dana do tablicy\n2-zobaczyc wartosci stosu\n3- usunac ostatli element stosu\nwybieram: ");
            scanf ("%i",&menu);
            if (menu==1)
                {  push (index);
                }
            if (menu==2)
                {   /*show=index;*/
                    printf ("znak w naszej tablicy to: ");
                    for (show=index;show>-1;show--)
                    { printf ("%i, ",a[show]);
                    }
            if (menu==3)
                {
                    pop (index);
                    index--;
                }
                }
        }
    while (menu!=0);
    }
Po co aktualizujesz dwa razy index podczas wywołania pop() ? Dlaczego pop() zwalnia pojedynczy element tablicy? sizeof(a) nie policzy Ci tego o czym myślisz. "a=b" nie kopiuje wskaźników tylko pierwszy element struktury, powinno być "a = b"... DE-BUG-ER - vpiotr 2011-10-07 14:49

Pozostało 580 znaków

2011-10-07 22:48
0

No to kolejna porcja uwag :)

  1. memcpy(b,a, sizeof(a));/kopiuje stara tablice do nowej/ - tak naprawdę to kopiujesz 4 bajty, bo sizeof(a) zwróci wielkość wskaźnika, a nie twojej tablicy.

  2. free(a[index]); - jak już vpiotr wspomniał - jest to błąd. Zwolnić możesz blok pamięci zaalokowany przez malloc, a więc wskaźniki a i b, a nie jeden z elementów tablicy.

  3. proponuję przeorganizowanie programu odnośnie push i pop. Wyobraź sobie, że chcesz otworzyć plik funkcją fopen() i funkcja ta nie pobiera żadnego parametru, tylko wyświetla ci w konsoli pytanie o podanie nazwy pliku. Byłoby to totalnie bez sensu. Dziala to tak, że gdzieś pobierasz nazwę pliku wcześniej (z konsoli, w pola EDIT w oknie, z parametrów startowych programu, zmiennej środowiskowej, rejestru, z czego tylko sobie zapragniesz), a do funkcji fopen() podajesz już przygotowaną nazwę pliku. Podobnie powinno byc w twoim programie. Najpierw w menu sprawdź co użytkownik chce zrobić, jeśli chce wrzucić liczbę na stos, to niech ją poda, a funkcja push pobiera samą liczbę i jest na tyle inteligentna, że sama wie jak to zrobić. Czyli:

  4. deklaracja push powinna wyglądać:
    void push(int val);

  5. deklaracja pop powinna wyglądać:
    int pop();

  6. jeśli nie chcesz tworzyć struktury opisującej twój stos (co pozwoliłoby komuś utworzyć w programie kilka stosów), a operujesz na zmiennych globalnych (czyli cały twój program jest jedną wielką implementacją stosu - w cudzysłowiu oczywiście), to myślę, że powinieneś pozmieniać trochę nazwy zmiennych i ja proponowałbym coś w stylu:
    int* stack_data - wskaźnik do zaalokowanej pamięci na nasz stos
    int stack_capacity - wielkość zaalokowanej pamięci, a w zasadzie ilość elementów, które można wstawić bez alokowania nowej pamięci
    int stack_size - wielkość stosu - czyli ile liczb zostało wrzuconych na stos

  7. funkcja push() wyglądałaby mniej więcej tak (piszę z glowy, więc przepraszam za ewentualne błędy):
    void push(int val)
    {
    if(stack_data != 0)
    {
    if(stack_size < stack_capacity)
    {
    stack_data[stack_size++] = val;
    }
    else
    {
    //cały stos jest zajęty i musimy zaalokować nową pamięć
    int new_capacity = stack_capacity 2;
    int
    stack_tmp = (int) malloc(new_capacity sizeof(int));
    memcpy(stack_tmp, stack_data, stack_capacitysizeof(int));
    free(stack_data);
    stack_data = stack_tmp;
    stack_capacity = new_capacity;
    stack_data[stack_size++] = val;
    }
    }
    else
    {
    //stos jest niezainicjwany, więc go inicjujemy i wstawiamy liczbę
    stack_capacity = 10; //jakaś domyślna wartość
    stack_size = 0;
    stack_data = (int
    ) malloc(stack_capacity * sizeof(int));
    stack_data[stack_size++] = val;
    }
    }

edytowany 4x, ostatnio: Tomek2, 2011-10-07 23:03
Po namyśle może lepiej nie wynajdywac koła na nowo i zastosować interfejs klasy std::stack z linka, który już podalem wcześniej. Czyli pop() zwraca void i służy tylko do usunięcia danej ze stosu, top() zwraca referencję do szczytu stosu i wystarczy dopisać funkcje empty() i size(). Dodatkowo naszło mnie później to, że w funkcji push() można użyć realloc() do alokowania większego obszaru pamięci. - Tomek2 2011-10-08 12:31

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0