c - 如何将排序链表传输到霍夫曼树？

Question

我使用列表来存储用户输入的字符串，并按降序排序，如下所示：Sorted Linked list

我的列表结构：

typedef struct list{
    char ch;
    int freq;
    struct list *next;
}LIST; //Linked list
LIST *L;

我的树结构：

typedef struct node{
    char ch;
    int freq;
    struct node *lc,*rc;
}TREE; //Tree
TREE *root;

我为霍夫曼树创建新节点的代码：

TREE *newNode(char ch,int freq){
    TREE *n = (TREE*)malloc(sizeof(TREE));

    n->ch = ch;
    n->freq = freq;
    n->rc = n->lc = root;

    return(n);
}

我的下一个计划是将排序的链表转移到霍夫曼树。

我在想这个函数会像这个过程一样传输链表：

1) head -> [a,6] -> [b,7] -> [c,8] -> [d,9] -> [e,10] -> null

2) head -> [n1,17] -> [c,8] -> [d,9] -> [e,10] -> null
           /\
          /  \
        [a,6] [b,7]

3) head -> [n2,25] -> [d,9] -> [e,10] -> null
           /\
          /  \
     [n1,17] [c,8]
       /\
      /  \
   [a,6] [b,7]

4) head-> [n3,34] -> [e,10] -> null
            / \
      [n2,25] [d,9]
           /\
          /  \
     [n1,17] [c,8]
       /\
      /  \
   [a,6] [b,7]

5) Final huffman tree
   
             [n4,44]
               /  \
          [n3,34] [e,10]
            / \
      [n2,25] [d,9]
           /\
          /  \
     [n1,17] [c,8]
       /\
      /  \
   [a,6] [b,7]

更新：我试图创建功能：

void huffman(){
    LIST *p = L;
    int total = 0;

    TREE *n=root,*q;

    if(p==NULL){
        root = NULL;
        return;
    }
    else{
        while(p!=NULL){
            total = 0;
            total = p->freq + p->next->freq;
            
            if(q==NULL){
                n = newNode(' ',total);
                n->lc = newNode(p->ch,p->freq);
                if(p->next!=NULL){
                    n->rc = newNode(p->next->ch,p->next->freq);
                    p->next->ch = ' ';
                    p->next->freq = total;
                    free(p);
                }
            }else{
                n = root;
                n->lc = q;
                if(p->next!=NULL){
                    n->rc = newNode(p->next->ch,p->next->freq);
                    p->next->ch = ' ';
                    p->next->freq = total;
                    free(p);
                }
            }

            q = n;
            p = p->next;
        }
    }
}

但它没有用。

我想我被这部分困住了：

       connecting this two nodes after connecting 
       first two nodes of linked list
              /        \
         [n1,17] -> [c,8] -> [d,9] -> [e,10] -> null
           /\
          /  \
        [a,6] [b,7]

更新：我决定创建一个节点数组并将其传输到根节点

TREE *a[15];
int i = 0;
void treeNodes(){
    LIST *p = L;
    int total = 0;

    if(p==NULL){
        root = NULL;
        return;
    }
    else{
        while(p!=NULL){
            total = 0;
            total = p->freq + p->next->freq;

            a[i] = newNode(' ',total);
            a[i]->lc = newNode(p->ch,p->freq);
            if(p->next!=NULL){
                a[i]->rc = newNode(p->next->ch,p->next->freq);
                p->next->ch = ' ';
                p->next->freq = total;
                free(p);
            }
            i++;
            p = p->next;
        }
    }
}

我想像这样连接节点数组：

        a[4]
       /    \
    a[3]  
    /   \ 
  a[2]
  /   \ 
a[1] 
/\

但我不知道我应该怎么做

标签： clisttreehuffman-code