Reputation: 33
I'm trying to make a Huffman code to practice C coding and I keep geting the same error.
Let me explain the code. First it creates the struct below:
struct sNo {
int valor;
char letra;
struct sNo *esq;
struct sNo *dir;
};
typedef struct sNo sNo;
Then it creates an array of structs ('No'):
sNo *No;
No = calloc(qtd_no, sizeof(sNo));
It reads a string from the keyboard placing in this array the letter and the ammount of times it appears. Like the representation below with the word 'abracadabra':
No: a/5 b/2 r/2 c/1 d/1
Now, to make a Huffman tree, it's needed that I create another array ('pNo'), with pointers to the original array:
int qtd_pno = qtd_no;
sNo **pNo;
pNo = calloc(qtd_pno, sizeof(sNo*));
for (i = 0; i < qtd_pno; i++){
pNo[i] = &No[i];
}
The two arrays appear like that:
No: a/5 b/2 r/2 c/1 d/1
pNo: a/5 b/2 r/2 c/1 d/1
After that it can sort the array of pointers like below without changing the original one:
No: a/5 b/2 r/2 c/1 d/1
pNo: c/1 d/1 r/2 b/2 a/5
But when it tries to increase the size of the 'No' array...
qtd_no++;
No = realloc(No,(sizeof(sNo) * qtd_no));
... this is what happens with the arrays:
No: a/5 b/2 r/2 c/1 d/1 /0
pNo: c/1 d/1 r/2 b/2 /0
or something like that:
No: a/5 b/2 r/2 c/1 d/1 /0
pNo: c/1 d/1 r/2 b/2 �/1288268632
Note that I'm not changing anything on the 'pNo' array, but somehow the value pointed is. I think it could be some specific characteristic of dynamic memory allocation, but I'm not sure.
EDIT
The complete code is below:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//Definicao do tipo struct No
struct sNo {
int valor;
char letra;
struct sNo *esq;
struct sNo *dir;
};
typedef struct sNo sNo;
//Funcoes
void SelectionSort(sNo *A[], int qtd_no);
void ImprimeArvore (sNo *a);
int main(){
//Variaveis auxiliares
int i, j;
//Leitura de texto do teclado
char texto[30];
printf("Digite frase \n");
setbuf(stdin, NULL);
fgets(texto, 30, stdin);
//Criacao dos nos
int qtd_no = 0;
sNo *No;
for(i = 0; i < strlen(texto) && texto[i] != '\0'; i++){
if(texto[i] >= 32){
if(i == 0){
qtd_no++;
No = calloc(qtd_no, sizeof(sNo));
if(No == NULL){
printf("Erro: memoria insuficiente\n");
exit(1);
}
No[i].letra = texto[i];
No[i].valor = 1;
No[i].esq = NULL;
No[i].dir = NULL;
printf("%d\t%c %c\t%d\n", i, texto[i], No[i].letra, No[i].valor);
}else{
for(j = 0; j <= qtd_no - 1; j++){
if(texto[i] == No[j].letra){
No[j].valor++;
printf("%d %d\t%c %c\t%d\n", i, j, texto[i], No[j].letra, No[j].valor);
break;
}
else if(j == qtd_no - 1){
qtd_no++;
No = realloc(No,(sizeof(sNo) * qtd_no));
if(No == NULL){
printf("Erro: memoria insuficiente\n");
exit(1);
}
No[j+1].letra = texto[i];
No[j+1].valor = 1;
No[j+1].esq = NULL;
No[j+1].dir = NULL;
printf("%d %d\t%c %c\t%d\n", i, j, texto[i], No[j+1].letra, No[j+1].valor);
break;
}
}
}
}
}
//Criacao de array com ponteiros para nos
int qtd_pno = qtd_no;
sNo **pNo;
pNo = calloc(qtd_pno, sizeof(sNo*));
if(pNo == NULL){
printf("Erro: memoria insuficiente\n");
exit(1);
}
for (i = 0; i < qtd_pno; i++){
pNo[i] = &No[i];
}
//Organizacao dos nos pelo valor
SelectionSort(pNo, qtd_pno);
//Criacao da arvore binaria
while(qtd_pno > 1){
qtd_no++;
No = realloc(No,(sizeof(sNo) * qtd_no));
if(No == NULL){
printf("Erro: memoria insuficiente\n");
exit(1);
}
No[qtd_no - 1].letra = '\0';
No[qtd_no - 1].valor = (pNo[0]->valor) + (pNo[1]->valor);
No[qtd_no - 1].esq = pNo[0];
No[qtd_no - 1].dir = pNo[1];
if(qtd_pno > 2){
for(i = 0; i <= qtd_pno-2; i++){
pNo[i] = pNo[i+2];
}
}
qtd_pno--;
pNo = realloc(pNo,(sizeof(sNo*) * qtd_pno));
pNo[qtd_pno - 1] = &No[qtd_no - 1];
if(qtd_pno > 1){
SelectionSort(pNo, qtd_pno);
}
}
sNo *raiz;
raiz = pNo[0];
free(pNo);
printf("\n%s\n", texto);
ImprimeArvore(raiz);
printf("\n");
}
//Funcao de organizacao por valor
void SelectionSort(sNo *A[], int qtd_pno){
sNo *temp;
int i, j, Imin;
for(i = 0; i < qtd_pno - 1; i++){
Imin = i;
for(j = i + 1; j < qtd_pno; j++){
if((A[j]->valor) < (A[Imin]->valor)){
Imin = j;
}
}
temp = A[Imin];
A[Imin] = A[i];
A[i] = temp;
}
}
void ImprimeArvore(sNo *a){
if(a->letra) printf ("<%c/%d", (a->letra), (a->valor));
else printf ("<_/%d", (a->valor));
if(a->esq != NULL) ImprimeArvore (a->esq);
if(a->dir != NULL) ImprimeArvore (a->dir);
printf (">");
}
Upvotes: 3
Views: 203
Reputation: 727137
The problem with your approach is that realloc
does not make any guarantees about expanding your array in place.
to make a Huffman tree, it's needed that I create another array ('pNo'), with pointers to the original array
Since you have pointers to calloc
-ed array inside other struct sNo
objects, calling realloc
on the block that has these structures may invalidate all external pointers to these structures. That is why your code runs into undefined behavior after a call to realloc
.
One approach to fixing this problem is to store indexes instead of pointers. This works, as long as you keep a single dynamic array to which you add new items, but never remove items from it.
Upvotes: 7