Diskuze: Uvoľňovanie pamäti

rosina.jakub

Člen

rosina.jakub:3.1.2019 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.1.2019 23:34

Kenvil

Člen

Odpovídá na rosina.jakub
Kenvil:5.1.2019 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

5.1.2019 2:18

rosina.jakub

Člen

Odpovídá na Kenvil
rosina.jakub:5.1.2019 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.1.2019 11:19

Matúš Olejník

Člen

Odpovídá na rosina.jakub
Matúš Olejník:5.1.2019 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.1.2019 17:21

/* I am not sure why this works but it fixes the problem */

rosina.jakub

Člen

Odpovídá na Matúš Olejník
rosina.jakub:5.1.2019 17:32

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

Nahoru Odpovědět

5.1.2019 17:32

Matúš Olejník

Člen

Odpovídá na rosina.jakub
Matúš Olejník:5.1.2019 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.1.2019 18:16

/* I am not sure why this works but it fixes the problem */

rosina.jakub

Člen

Odpovídá na Matúš Olejník
rosina.jakub:6.1.2019 11:03

Stále nič.

Nahoru Odpovědět

6.1.2019 11:03

Matúš Olejník

Člen

Odpovídá na rosina.jakub
Matúš Olejník:6.1.2019 11:21

Tak asi to treba spraviť bez tej štruktúry 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.1.2019 11:21

/* I am not sure why this works but it fixes the problem */

rosina.jakub

Člen

Odpovídá na Matúš Olejník
rosina.jakub:6.1.2019 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.1.2019 11:24

DarkCoder

Člen

Odpovídá na rosina.jakub
DarkCoder:6.1.2019 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.1.2019 15:37

"I ta nejlepší poučka postrádá na významu, není-li patřičně předána." - DarkCoder

rosina.jakub

Člen

Odpovídá na DarkCoder
rosina.jakub:8.1.2019 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.1.2019 19:04

DarkCoder

Člen

Odpovídá na rosina.jakub
DarkCoder:8.1.2019 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.1.2019 19:44

"I ta nejlepší poučka postrádá na významu, není-li patřičně předána." - DarkCoder

rosina.jakub

Člen

Odpovídá na DarkCoder
rosina.jakub:8.1.2019 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.1.2019 20:03

rosina.jakub

Člen

rosina.jakub:8.1.2019 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.1.2019 20:04

DarkCoder

Člen

Odpovídá na rosina.jakub
DarkCoder:8.1.2019 23:42

void freePole (LIST **pole){
  while (pole) {
    LIST *p_tmp = *pole;
    *pole = (*pole)->dalsi;
    free(p_tmp);
  }
}

Nahoru Odpovědět

8.1.2019 23:42

"I ta nejlepší poučka postrádá na významu, není-li patřičně předána." - DarkCoder

rosina.jakub

Člen

Odpovídá na DarkCoder
rosina.jakub:8.1.2019 23:53

To už mi nejde vôbec

Nahoru Odpovědět

8.1.2019 23:53

DarkCoder

Člen

Odpovídá na rosina.jakub
DarkCoder:13.1.2019 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.1.2019 13:27

"I ta nejlepší poučka postrádá na významu, není-li patřičně předána." - DarkCoder