Diskuze: Uvoľňovanie pamäti
V předchozím kvízu, Online test znalostí C++, jsme si ověřili nabyté zkušenosti z kurzu.

Člen

Zobrazeno 17 zpráv z 17.
//= Settings::TRACKING_CODE_B ?> //= Settings::TRACKING_CODE ?>
V předchozím kvízu, Online test znalostí C++, jsme si ověřili nabyté zkušenosti z kurzu.
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);
V Cečku sa to zapisuje free(pole).
Dával som to vo funkcii is_subset pred return 1 a return 0.
Mne ten kód padne ešte pred tým než by sa mala uvoľniť pamäť, vo funkcii pridanie.
V Turingu ide v pohode, len veľký test neprejde kvôli pamäti
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);
}
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.
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.
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);
}
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.
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.
Neber to čo je v maine. Main sa mi mení. V testovači je veľký test (tajný) neviem koľko tam je prvkov.
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;
}
}
void freePole (LIST **pole){
while (pole) {
LIST *p_tmp = *pole;
*pole = (*pole)->dalsi;
free(p_tmp);
}
}
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;
}
}
Zobrazeno 17 zpráv z 17.