指向结构 realloc() 错误的指针的 C 数组

Question

我正在尝试编写 Huffman 代码来练习 C 编码，但我总是遇到同样的错误。

让我解释一下代码。首先它创建下面的结构：

struct sNo {
    int valor;
    char letra;
    struct sNo *esq;
    struct sNo *dir;
};
typedef struct sNo sNo;

然后它创建一个结构数组 ('No'):

sNo *No;
No = calloc(qtd_no, sizeof(sNo));

它从键盘读取一个字符串，将字母和它出现的次数放在这个数组中。就像下面用单词 'abracadabra':

表示的

No:    a/5 b/2 r/2 c/1 d/1

现在，要生成霍夫曼树，我需要创建另一个数组 ('pNo')，并带有指向原始数组的指针：

int qtd_pno = qtd_no;
sNo **pNo;
pNo = calloc(qtd_pno, sizeof(sNo*));
for (i = 0; i < qtd_pno; i++){
    pNo[i] = &No[i];    
}

两个数组是这样的：

No:    a/5 b/2 r/2 c/1 d/1  
pNo:   a/5 b/2 r/2 c/1 d/1

之后它可以在不改变原来的指针数组的情况下像下面这样对指针数组进行排序：

No:    a/5 b/2 r/2 c/1 d/1  
pNo:   c/1 d/1 r/2 b/2 a/5

但是当它试图增加 'No' 数组的大小时...

qtd_no++;
No = realloc(No,(sizeof(sNo) * qtd_no));

...这就是数组发生的情况：

No:    a/5 b/2 r/2 c/1 d/1  /0
pNo:   c/1 d/1 r/2 b/2 /0

或类似的东西：

No:    a/5 b/2 r/2 c/1 d/1  /0
pNo:   c/1 d/1 r/2 b/2 �/1288268632

请注意，我没有更改 'pNo' 数组上的任何内容，但不知何故指向的值是。我认为这可能是动态内存分配的一些特定特征，但我不确定。

编辑
完整代码如下：

#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] != '[=19=]'; 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 = '[=19=]';
        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 (">");

}

Answer 1

您的方法存在的问题是 realloc 无法保证就地扩展数组。

to make a Huffman tree, it's needed that I create another array ('pNo'), with pointers to the original array

由于您在其他 struct sNo 对象中有指向 calloc-ed 数组的指针，因此在具有这些结构的块上调用 realloc 可能会使指向这些结构的所有外部指针无效。这就是为什么您的代码在调用 realloc.

后遇到未定义行为的原因

解决此问题的一种方法是存储索引而不是指针。只要您保留一个动态数组并向其添加新项目，但从不从中删除项目，这就有效。

指向结构 realloc() 错误的指针的 C 数组

C array of pointers to structs realloc() error

c

arrays

pointers

struct

dynamic-allocation