Geek tričko zdarma Geek tričko zdarma
Tričko zdarma! Stačí před dobitím bodů použít kód TRIKO15. Více informací zde
Avatar
rosina.jakub
Člen
Avatar
rosina.jakub:3. ledna 23:34

Ahojte,
potrebujem pomôcť s uvoľnením pamäte.

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

typedef struct list {
        int hodnota;
        struct list *dalsi;
}LIST;

void uvolni(LIST *prvy) {
        LIST *tmp;
        while(prvy != NULL) {
                tmp = prvy->dalsi;
                free(prvy);
                prvy = tmp;
        }
}

LIST *vytvor(int cislo) {
        LIST *novy = (LIST*)malloc(sizeof(LIST));
        novy->hodnota = cislo;
        novy->dalsi = NULL;
        return novy;
}

LIST *pridanie(LIST *t, int n) {
        LIST *act = t, *pred = t;
        if (t==NULL) {
                return vytvor(n);
        }
        while(act!=NULL) {
                pred = act;
                act = act->dalsi;
        }
        pred->dalsi = vytvor(n);

        return t;
}

int has(LIST *t, int n) {
        LIST *act;

        if (t==NULL) {
                return 0;
        }
        for (act=t;act!=NULL;act=act->dalsi)
                if (act->hodnota == n) {
                        return 1;
                }
        return 0;
}

// vrati 1 ak 's' je podmnozina 't', inak vrati 0.
int is_subset(int s[], int n, int t[], int m)
{
        int i, j, k;
        LIST **pole = (LIST **)malloc(m*sizeof(LIST*)), *tmp;

        for (i=0;i<m;i++)
                pole[t[i] % m] = pridanie(pole[t[i] % m], t[i]);

        for (i=0;i<n;i++)
                if(!has(pole[s[i] % m], s[i])) {
                        return 0;
                }

        return 1;
}

// ukazkovy test
int main(void)
{
        int i, a[10], na, b[10], nb;
        scanf("%d", &na);
        for (i = 0; i < na; i++)
                scanf("%d", &a[i]);
        scanf("%d", &nb);
        for (i = 0; i < nb; i++)
                scanf("%d", &b[i]);
        if (is_subset(a, na, b, nb))
                printf("PODMNOZINA\n");
        else
                printf("NIE\n");
        return 0;
}

V tomto kóde potrebujem uvoľniť alokovanú štruktúru a potom pole.

Zkusil jsem: Skúšal som vo funkcii is_subset pred returnom dať free(pole), tiež som to skúšal cez funkciu uvolni().

 
Odpovědět 3. ledna 23:34
Avatar
Kenvil
Člen
Avatar
Odpovídá na rosina.jakub
Kenvil:5. ledna 2:18

Dle mě čistě jen free(pole) je špatně já se teda v C moc neorientují ale nemělo by to být něco jako free(pole[]); ?
A jinak před jaký return si dával to free(pole);

 
Nahoru Odpovědět  -1 5. ledna 2:18
Avatar
rosina.jakub
Člen
Avatar
Odpovídá na Kenvil
rosina.jakub:5. ledna 11:19

V Cečku sa to zapisuje free(pole).
Dával som to vo funkcii is_subset pred return 1 a return 0.

 
Nahoru Odpovědět 5. ledna 11:19
Avatar
Odpovídá na rosina.jakub
Matúš Olejník:5. ledna 17:21

Mne ten kód padne ešte pred tým než by sa mala uvoľniť pamäť, vo funkcii pridanie.

Nahoru Odpovědět 5. ledna 17:21
/* I am not sure why this works but it fixes the problem */
Avatar
rosina.jakub
Člen
Avatar
Odpovídá na Matúš Olejník
rosina.jakub:5. ledna 17:32

V Turingu ide v pohode, len veľký test neprejde kvôli pamäti

 
Nahoru Odpovědět 5. ledna 17:32
Avatar
Odpovídá na rosina.jakub
Matúš Olejník:5. ledna 18:16

Skús upraviť metódy takto

int is_subset(int s[], int n, int t[], int m) {
    int i, j, k;
    LIST **pole = (LIST**) malloc(m * sizeof(LIST*));

    for (i = 0; i < m; i++) {
        pole[i] = NULL;
    }

    for (i = 0; i < m; i++) {
        pole[t[i] % m] = pridanie(pole[t[i] % m], t[i]);
    }

    for (i = 0; i < n; i++) {
        if (!has(pole[s[i] % m], s[i])) {
            freePole(pole, m);
            return 0;
        }
    }
    freePole(pole, m);

    return 1;
}

void freePole(LIST **pole, int size) {
    int i;

    for (i = 0; i < size; i++) {
        free(pole[i]);
    }
    free(pole);
}
Nahoru Odpovědět 5. ledna 18:16
/* I am not sure why this works but it fixes the problem */
Avatar
rosina.jakub
Člen
Avatar
 
Nahoru Odpovědět 6. ledna 11:03
Avatar
Odpovídá na rosina.jakub
Matúš Olejník:6. ledna 11:21

Tak asi to treba spraviť bez tej štruktúry :D alebo akú chybu ti to vypíše?

Merge sortom zosorti obe polia a potom v jednom while cykle ľahko zistíš či jedna množina je podmnožinou tej druhej.

Nahoru Odpovědět 6. ledna 11:21
/* I am not sure why this works but it fixes the problem */
Avatar
rosina.jakub
Člen
Avatar
Odpovídá na Matúš Olejník
rosina.jakub:6. ledna 11:24

Keď som to mal bez uvoľňovania tak nevypíše nič, iba neprebehne posledny test v Turingu, resp. prebehne ten, ktorý je tam s Extra pamäťou.
Teraz mi neprebehol ani druhý test, dá mi Segmentation Fault.

 
Nahoru Odpovědět 6. ledna 11:24
Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!
Avatar
DarkCoder
Člen
Avatar
Odpovídá na rosina.jakub
DarkCoder:6. ledna 15:37

Pro zjištění, zda-li je druhé pole podmnožinou prvního pole není třeba vytvářet strukturu ani nic řadit. Dále pole, jehož velikost určujeme za běhu je dobré vytvářet dynamicky (od C99 lze vytvářet pole s proměnnou délkou) nebo kontrolovat povolený rozsah. Nezapomínat na kontrolu úspěšnosti přidělené paměti. Zde je řešení:

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

// Debug mod, 0 - bez vypisu, 1 - s vypisem
#define DEBUG 0

int is_subset(int *p1, int n1, int *p2, int n2);

int main(void) {
        int *dp1 = NULL, ndp1;
        int *dp2 = NULL, ndp2;
        int i;

        printf("Zadej velikost 1. pole: ");
        scanf("%d", &ndp1);

        // alokace pameti pro 1. pole
        dp1 = (int *)malloc(ndp1 * sizeof(int));
        if (dp1 == NULL) {
                fprintf(stderr, "Chyba alokace pole. (dp1)\n");
                exit(1);
        }

        // nacteni hodnot do 1. pole
        for (i = 0; i < ndp1; i++) {
                printf("%d. cislo: ", i + 1);
                scanf("%d", dp1 + i);
        }

        // kontrolni vypis obsahu 1. pole
#if (DEBUG)
        printf("\n%d\n", ndp1);
        for (i = 0; i < ndp1; i++) printf("%d ", *(dp1+i));
        putchar('\n');
#endif

        printf("\nZadej velikost 2. pole: ");
        scanf("%d", &ndp2);

        // alokace pameti pro 2. pole
        dp2 = (int *)malloc(ndp2 * sizeof(int));
        if (dp2 == NULL) {
                fprintf(stderr, "Chyba alokace pole. (dp2)\n");
                exit(1);
        }

        // nacteni hodnot do 2. pole
        for (i = 0; i < ndp2; i++) {
                printf("%d. cislo: ", i + 1);
                scanf("%d", dp2 + i);
        }

        // kontrolni vypis obsahu 2. pole
#if (DEBUG)
        printf("\n%d\n", ndp2);
        for (i = 0; i < ndp2; i++) printf("%d ", *(dp2 + i));
        putchar('\n');
#endif

        // vypis, zda-li je 2. pole podmozinou 1. pole
        (is_subset(dp1, ndp1, dp2, ndp2)) ? printf("\nPODMNOZINA\n") : printf("\nNE\n");

        // uvolneni pameti 1. pole
        free(dp1);
        dp1 = NULL;

        // uvolneni pameti 2. pole
        free(dp2);
        dp2 = NULL;

        return 0;
}

// Zjisteni, zda-li je 2. pole podmozinou 1. pole (bez opakovani prvku)
int is_subset(int *p1, int n1, int *p2, int n2){
        int *dcheck = NULL;
        int i, j, count = 0;

        // vetsi pole nemuze byt podmnozinou mensiho pole
        if (n2 > n1) return 0;

        // alokace pole pro oznaceni pouzitych prvku
        dcheck = (int *)calloc(n1, sizeof(int));
        if (dcheck == NULL) {
                fprintf(stderr, "Chyba alokace pole. (dtest)\n");
                exit(1);
        }

        // prochazeni a porovnavani prvku poli s predbeznym ukoncenim
        for (i = 0; i < n2; i++) {
                for (j = 0; j < n1; j++) {
                        if ((*(p2 + i) == *(p1 + j)) && (*(dcheck + j) == 0)) {
                                count++;
                                *(dcheck + j) = 1;
                                break;
                        }
                }
                if (count < i + 1) break;
        }

        // kontrolni vypis prvku který neni prvkem 1. pole
#if (DEBUG)
        if(count != n2) printf("\n%d. prvek neni prvkem 1. pole.\n", i + 1);
#endif

        // uvolneni pameti check pole
        free(dcheck);
        dcheck = NULL;

        return (count == n2) ? (1) : (0);
}
Nahoru Odpovědět 6. ledna 15:37
"„Učíš-li se proto, aby sis zapamatoval, zapomeneš. Učíš-li se proto, abys porozuměl, zapamatuješ si."
Avatar
rosina.jakub
Člen
Avatar
Odpovídá na DarkCoder
rosina.jakub:8. ledna 19:04

Bohužiaľ týmto spôsobom to riešiť nemôžem pretože v testovačí mi to nesplní časový limit, ktorý je myslím, že 300ms. Preto sa to musí riešiť cez Hash tabuľku.

 
Nahoru Odpovědět 8. ledna 19:04
Avatar
DarkCoder
Člen
Avatar
Odpovídá na rosina.jakub
DarkCoder:8. ledna 19:44

V čem je to pomalé? Časová náročnost funkce is_subset() pro 10 a 10 prvků nepřesahuje při plném průchodu na průměrném počítači času 1ms.

Nahoru Odpovědět 8. ledna 19:44
"„Učíš-li se proto, aby sis zapamatoval, zapomeneš. Učíš-li se proto, abys porozuměl, zapamatuješ si."
Avatar
rosina.jakub
Člen
Avatar
Odpovídá na DarkCoder
rosina.jakub:8. ledna 20:03

Neber to čo je v maine. Main sa mi mení. V testovači je veľký test (tajný) neviem koľko tam je prvkov.

 
Nahoru Odpovědět 8. ledna 20:03
Avatar
rosina.jakub
Člen
Avatar
rosina.jakub:8. ledna 20:04

Už som to skúšal dealokovať aj takto. Do tej funkcie som cez cyklus vkladal pole[j] a tiež som skúšal aj *pole. Stále mi to musí zle uvoľňovať.

void freePole(LIST *pole) {
        LIST *p_act = pole, *p_tmp;

        while(p_act != NULL) {
                p_tmp = p_act->p_next;
                p_act->val = NULL;
                p_act->p_next = NULL;
                free(p_act);
                p_act = p_tmp;
        }
}
 
Nahoru Odpovědět 8. ledna 20:04
Avatar
DarkCoder
Člen
Avatar
Odpovídá na rosina.jakub
DarkCoder:8. ledna 23:42
void freePole (LIST **pole){
  while (pole) {
    LIST *p_tmp = *pole;
    *pole = (*pole)->dalsi;
    free(p_tmp);
  }
}
Nahoru Odpovědět 8. ledna 23:42
"„Učíš-li se proto, aby sis zapamatoval, zapomeneš. Učíš-li se proto, abys porozuměl, zapamatuješ si."
Avatar
rosina.jakub
Člen
Avatar
Odpovídá na DarkCoder
rosina.jakub:8. ledna 23:53

To už mi nejde vôbec :)

 
Nahoru Odpovědět 8. ledna 23:53
Avatar
DarkCoder
Člen
Avatar
Odpovídá na rosina.jakub
DarkCoder:13. ledna 13:27

Zde máš ukázku jednosměrného spojového seznamu (vkládání, výpis, mazání).

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

typedef struct node {
        int val;
        struct node *next;
} node_t;

void delete_list(node_t *head);
void print_list(node_t *head);
void push(node_t **head, int val);

int main(void) {
        node_t *test_list = NULL;

        push(&test_list, 1);
        push(&test_list, 2);
        push(&test_list, 3);

        print_list(test_list);
        delete_list(test_list);

        return EXIT_SUCCESS;
}

void delete_list(node_t *head) {
        node_t  *current = head,
                        *next = head;

        while (current) {
                next = current->next;
                free(current);
                current = next;
        }
}

void print_list(node_t * head) {
        node_t *current = head;

        while (current) {
                printf("%d\n", current->val);
                current = current->next;
        }
}

void push(node_t **head, int val) {
        node_t *current = *head;

        if (!current) {
                current = (node_t *)malloc(sizeof(node_t));
                current->val = val;
                current->next = NULL;
                *head = current;
        }
        else {
                while (current->next != NULL) current = current->next;
                current->next = (node_t *)malloc(sizeof(node_t));
                current->next->val = val;
                current->next->next = NULL;
        }
}
Nahoru Odpovědět 13. ledna 13:27
"„Učíš-li se proto, aby sis zapamatoval, zapomeneš. Učíš-li se proto, abys porozuměl, zapamatuješ si."
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 17 zpráv z 17.