Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.
Pouze tento týden sleva až 80 % na e-learning týkající se Swiftu. Zároveň využij výhodnou slevovou akci až 30 % zdarma při nákupu e-learningu - více informací.
discount 30 + hiring
Avatar
rosina.jakub
Člen
Avatar
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
Avatar
Kenvil
Člen
Avatar
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
Avatar
rosina.jakub
Člen
Avatar
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
Avatar
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 */
Avatar
rosina.jakub
Člen
Avatar
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
Avatar
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 */
Avatar
rosina.jakub
Člen
Avatar
 
Nahoru Odpovědět
6.1.2019 11:03
Avatar
Odpovídá na rosina.jakub
Matúš Olejník:6.1.2019 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.1.2019 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.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
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.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
"Chceš-li předávat své znalosti, měj kvalitní podklady."
Avatar
rosina.jakub
Člen
Avatar
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
Avatar
DarkCoder
Člen
Avatar
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
"Chceš-li předávat své znalosti, měj kvalitní podklady."
Avatar
rosina.jakub
Člen
Avatar
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
Avatar
rosina.jakub
Člen
Avatar
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
Avatar
DarkCoder
Člen
Avatar
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
"Chceš-li předávat své znalosti, měj kvalitní podklady."
Avatar
rosina.jakub
Člen
Avatar
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
Avatar
DarkCoder
Člen
Avatar
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
"Chceš-li předávat své znalosti, měj kvalitní podklady."
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.