最近遇到有人在問霍夫曼編碼

仔細想想，接觸演算法到現在，霍夫曼編碼也都只是紙上談兵

從來沒有自己 Implement 過...

 

當我準備開始寫時，想想...天呀，要設計個Queue來存放

而且最好是每次會挑出最小的....

那豈不是要用陣列做堆積

暈倒....

 

想想，算了，用Java的LinkedList做Queue就好了

因此，沒幾行就把Huffman tree 作好了....

結果問問題的人一定要用C

 

天呀，C++我又不熟，不想用C++的Class做...

只好，用陣列來放

每次將rate最小的節點swap到陣列底端

再做合併...So easy，然後遞迴走訪

把節點轉錄到Table中，以供查悅

 

 

#include<stdio.h>
#include<stdio.h>

unsigned int *HuT;
char *WT;

typedef struct node *ptr;
struct node{
    char w;
    float rate;
    ptr left,right;
};

void inorder(ptr tree,int *index,unsigned int addr){
    if(tree->left==NULL){
        HuT[*index]=addr;
        WT[*index]=tree->w;
        (*index)++;
    }
    else{
        inorder(tree->left,index,addr<<1);
        inorder(tree->right,index,(addr<<1)+1);
    }
}

int main(){
    int n,i,j,k,index=0;
    ptr *list,temp;
    char bc[33];
   
    printf("請輸入資料個數>");
    scanf("%d",&n);
   
    //動態產生Table & list(queue);
    list=(ptr*)malloc(sizeof(ptr)*n);
    HuT=(unsigned int*)malloc(sizeof(unsigned int)*n);
    WT=(char*)malloc(sizeof(char)*n);
   
    //儲存資料
    for(i=0;i<n;i++){
        list[i]=(ptr)malloc(sizeof(struct node));
        scanf(" %c",&(list[i]->w));
        scanf(" %f",&(list[i]->rate));
        list[i]->left=list[i]->right=NULL;
    }
   
    //建立Huffman tree
    printf("Building...\n");
    k=n;
    while(--k>0){
        //選出兩個最小的
        for(i=0;i<2;i++){
            for(j=0;j<k-i;j++){
                if(list[j]->rate<list[k-i]->rate){
                    temp=list[j];
                    list[j]=list[k-i];
                    list[k-i]=temp;
                }
            }
        }
        //合併 (產生新節點，設定rate，並建立為子樹，再加入list)
        temp=(ptr)malloc(sizeof(struct node));
        temp->rate=list[k]->rate+list[k-1]->rate;
        temp->left=list[k];
        temp->right=list[k-1];
        list[k-1]=temp;
    }
    //轉換到表格上
    inorder(list[0],&index,1);
    printf("Huffman code table\n");
    for(i=0;i<n;i++){
        for(j=0;(HuT[i]>>j)>0;j++);
        for(bc[--j]='\0',--j;j>=0;j--){
            bc[j]=(HuT[i]&1)+48;
            HuT[i]>>=1;
        }
        printf("%c %s\n",WT[i],bc);
    }
    system("pause");
    return 0;
}

Good~完成

第一次寫，對C的指標運用又進一層樓嚕...

解奇摩知識家，受益良多

增加了許多練習的機會，題目都不用自己想

前幾天在奇摩知識遇到這問題，2006/5/02，也就是昨天早上

我一大早不小心就睡過頭了，匆匆忙忙趕到教室去，老師開始發期中考卷

看到成績就暈倒了....我居然考50分，天呀，這是奇恥大辱

我再仔細看一下考卷，程式部分居然只有一題定義物件(class)結構的程式題對

其他程式題全軍覆沒>"<，老師等大家看過考卷後，就開始收考卷

我就開始問老師啦。

 

我：老師，這題 Sparse Matrix 的 陣列表示法為什麼錯？

 

老師：這樣當然不對啦，要用二維陣列 N*3陣列 或 3*N 陣列存放，這樣才能讀取呀

 

我：我這樣一次以三筆資料為一個單位抓取，不也一樣

 

老師：唉呀，我知道呀，但是你這樣就不知道陣列要宣告多大阿

 

我：跟二維陣列不是一樣，你要宣告多大，我就宣告多大呀....

 

老師：嗯，是這樣沒錯，這是如果每個人都說一套儲存格式，那不就天下大亂

　　　這樣就不知道要用哪一種格式。所以我們要統一格式呀！

 

我：.....(無言，沉默了一下)......，喔...

 

後面的問題我也不想再問了，因為後面的問題更誇張.....

前面簡單問題都這樣了，後面更不用說了....

或許看到的人可以評評理！(不懂程式的人就不用來評了，隔行如隔山)

 

 

因為課本是用C++，所以考卷裡也要求用C++寫

因為本身是用Dev C++ 編輯器，所以我就直接寫了....

 

那些題目都是一些 Array 或LinkedList 做 Stack 或 Queue

然後要我們寫出運作的程式(如，插入新資料，刪除資料....)

 

有寫過C與C++的人都知道，兩個語法幾乎一樣

尤其在這些宣告與簡單的運算、搬動、指標、宣告....

 

老師居然直接劃掉，旁邊用紅筆補一句『請用C++寫』

而我很確定這些語法在Dev C++ 中，以.cpp格式撰寫，Compiler ok，結果正確

而且這語法在Visual C++ 中也一樣 ok ，我事後確認過.....

 

就這樣，第一頁寫這樣一句，後面所有程式題通通劃掉了.....

我想，理由只是跟課本中C++語法有些不同吧！

 

心情夠悶的了...課堂的東西太簡單.....

 

我趁資結老師都在講屁話時，拿出紙筆開始思考問題

 

我花了約10分鐘在思考 N^2log N 演算法複雜度的可能方法

以一般來說，a + b + c = d 以深度走訪+迴朔法，也要O(N^4)

 

以動態規劃來思考問題，若兩兩相加，我必須再擠出3維陣列

再加上二元搜尋也要花上O(N^3log N)

因為想先將動態規劃降到O(N^2)必先使動態規劃從3維空間降到2維空間....

所以，靈光一閃，跑出了：a + b + c = d→ a + b = d - c

搞定90%，只花10分鐘不到就想到了....我真是天才.....

因為 a b c d 都是 集合 s 中的元素，所以以一維陣列存放就ok了

再來是考慮到搜尋問題，因為我就先將集合 s 作排序。

 

接著畫一張表格，把 a+b 與 d-c 在表格上計算....

心中一閃，元素不重覆，所以對角線一定是空的

計算任兩個值之和與差也各僅要 ((n^2+n)/2)-n 的 空間/次數

所以....就直接將 n*n 矩陣規劃為 對角線為『空』，上三角計算兩數和

下三角計算兩數之差，因為恰上三角為 i < j ( i 表示列，j 表示行 )

下三角為 i > j。當我想到這，把資料算到紙上，思考一下

因為我的資料已排序過(小→大)，所以可以找到Ordered的加法順序

如 1 +3 + 6 = 10 (由小加到大)

以上面例子來解說

 

　　　１　２　３　５　　６　１０

 

　１　ｘ　３　４　６　　７　１１

 

　２　１　ｘ　５　７　　８　１２

 

　３　２　１　ｘ　８　　９　１３

 

　５　４　３　２　ｘ　１１　１５

 

　６　５　４　３　１　　ｘ　１６

 

１０　９　８　６　５　　４　　ｘ

 

當我產生表格後，因為在Order的次序中，不可能出現 上三角( i , j )算出的key值出現在

下三角的 < j 的左半矩陣，且，較大的數必由較小的數相加而成(正整數)

因此，我想到了一種演算法，以 j 為主， i 為次，j 由左往右掃....，i 由下往上掃

且剃除第一行與最後一行，因為這兩行都恰不同時存在上三角與下三角元素.....

以上三角當索引，計算後Hash到Hash Table，然後下三角計算後，就以key值去索引Hash Table

然後判斷裡面是否有資料，若沒有資料則跳過，若有就將資料還原，並印出，而整個LinkedList中

的資料都是吻合的，沒有例外....所以可以省略判斷...

以下是Code：

 

/*
輸入一個正整數集合S a,b,c,d 屬於S
去設計找出所有的 a+b+c=d 時間複雜度是O(n^2logn)的演算法
a,b,c,d皆不相等不是屬於同一元素
EX.
輸入S
S = {1,2,3,6,5,10}
輸出:
1+3+2=6
1+3+6=10
2+3+5=10
*/

#include<stdio.h>
#include<stdlib.h>

typedef struct node *ptr;
struct node{
 int x,y;
 ptr next;
};

ptr *list;
int size;

void creat(int s,int k){
 size=(s>k)?s+1:k+1;
 list=(ptr*)malloc(size*sizeof(ptr));
 for(s=0;s<size;s++)list[s]=NULL;
}

void Insert(int index,int i,int j){
 ptr temp=(ptr)malloc(sizeof(struct node));
 temp->x=i;
 temp->y=j;
 temp->next=list[index];
 list[index]=temp;
}

int compare(const void* x,const void* y){
 if((*(int*)x)>(*(int*)y))return 1;
 if((*(int*)x)<(*(int*)y))return -1;
 return 0;
}

int main(){
 int i,j,*s,n;
 printf("請輸入集合原素個數：\n");
 scanf("%d",&n);
 s=(int*)malloc(n*sizeof(int));
 for(i=0;i<n;i++)scanf("%d",&s[i]);
 qsort(s,n,sizeof(int),compare);
 creat(s[n-3]+s[n-2],s[n-1]-s[n-2]);
 for(j=1;j<n-1;j++){
  for(i=n-1;i>=0;i--){
   if(i<j)Insert(s[i]+s[j],i,j);
   else if(i>j){
    ptr pt=list[s[i]-s[j]];
    while(pt!=NULL){
     printf("%d+%d+%d=%d\n",s[pt->x],s[pt->y],s[j],s[i]);
     pt=pt->next;
    }
   }
  }
 }
 system("pause");
}

 

有版權的喔，連結或Copy去使用請先跟我說一聲，留個言也好

要詳細說明　你是誰，用途為何....用在哪.....之類的