以前都是在一個文件里寫代碼的，第一次用了這么多文件（4個_!!），哈，很有成就感阿，還熟悉了linux下的編程環境，gcc,gdb都是很好好強大的東東，記得下次多用用：
有不足之處望各位高手指正阿！！！
huffman.h
1 /*最小堆操作方法get the data input*/
2
3 //#define MAXSIZE 100
4 #define DEFAULTSIZE 50
5 /*最小堆的節點結構*/
6 struct hnode
7 {
8 char ch;
9 int index; //索引對應于haffman數組的下標
10 int freq; //對該字段建立最小堆
11 };
12 typedef struct hnode *PHHead;
13 typedef struct hnode HNode;
14
15
16 int getdata(PHHead );
17
18 //make the data into min heap structure
19 void makeMinheap(PHHead , int);
20
21 int IsFull();
22 int IsEmpty();
23 void MoveUP(HNode *);
24 void MoveDown(HNode *);
25 int Insert(PHHead , HNode );
26 HNode DeleteMin(PHHead );
27
28
29
30
31 //哈夫漫操作方法func for construaction of HUFFMAN tree
32 /*this is a struct for the huffmancode when record*/
33 typedef char **HuffmanCode;
34
35
36
37 /*haffman struct*/
38 typedef struct HuffmanNode{
39 int freq;
40 char ch;
41 int parent, lchild,rchild;
42 } HTNode, *HuffmanTree;
43 void HuffmanCoding(HuffmanTree HT, HuffmanCode HC, PHHead, int); //PHHead is a point for input, int is number of element
Minheap.c最小堆實現
1 #include <stdio.h>
2 #include "huffman.h"
3
4
5
6 HNode heapData[DEFAULTSIZE+1]; //第一個節點不用
7 int currentSize = 0;//記錄當前堆的元素個數,currentSize位置當前數據的最后一個位置的下標
8 int totalNum = 0;//輸入的數據個數
9
10 int getdata(PHHead data) //從控制臺獲得輸入數據，存入最小堆數組
11 {
12 char c = 0; //the char
13 int freq = 0;
14 scanf("%c %d", &c, &freq);
15 while(c!='0' && freq != 0)
16 {
17 if(currentSize < DEFAULTSIZE)
18 {
19 currentSize++;//增加當前大小
20 heapData[currentSize].ch = c;
21 heapData[currentSize].freq = freq;
22 heapData[currentSize].index = currentSize;//放入輸入數據的先后索引
23
24 getchar(); //去除輸入的回車等其他無效字符
25 scanf("%c %d", &c, &freq);
26 }
27 else
28 {
29 fprintf(stderr, "too many input!!"); //提示：輸入數據太多了
30 return 0;
31 }
32 /* else//if input data number greater than defaultsize, then malloc more
33 {
34
35 }
36 */
37 }
38 totalNum = currentSize;
39 }
40 //對輸入的數據形成最小堆，從 元素個數/2的首個非葉子節點，迭代構建
41 void makeMinheap(PHHead data, int currentSize) //這里的currentSize不影響全局的該變量
42 {
43 HNode tempNode;
44
45 int i = 0;
46 int j= 0;
47 int tempi = 0;
48 for(i = currentSize/2; i>0; i--) //i表示循環個數
49 {
50 tempi = i; //單次循環變量
51 for(j= 2*tempi; j<=currentSize; j*=2) //假設除本節點外的子樹已是最小堆，考慮本節點后，重新形成最小堆
52 {
53 if( j<currentSize && data[j].freq > data[j+1].freq) j++;//找出i節點兩個子節點的較小者記為j
54 if(data[tempi].freq > data[j].freq)
55 {
56 tempNode.ch = data[tempi].ch;
57 tempNode.freq = data[tempi].freq;
58 tempNode.index = data[tempi].index;
59
60 data[tempi].ch = data[j].ch;
61 data[tempi].freq = data[j].freq;
62 data[tempi].index = data[j].index;
63
64 data[j].ch =tempNode.ch;
65 data[j].freq = tempNode.freq;
66 data[j].index =tempNode.index; //交換i,j節點的數據
67
68 tempi = j; //把還下來的數據一直放到合適的位置
69
70 }
71 else break;
72 }
73 }
74 }
75
76 int IsFull()
77 {
78 if(currentSize >= DEFAULTSIZE)
79 return 1;
80 else
81 return 0;
82 }
83 int IsEmpty()
84 {
85 if(currentSize == 0)
86 return 1;
87 else
88 return 0;
89 }
90 //把已經插入并放在最尾端的一個元素，重構最小堆
91 void MoveUP(HNode * heap)
92 {
93 HNode temp;
94 int i = currentSize;
95 for(; i >=1;i/=2)
96 {
97 if(heap[i].freq < heap[i/2].freq)
98 {
99 temp.ch = heap[i/2].ch;
100 temp.freq = heap[i/2].freq;
101 temp.index = heap[i/2].index;
102
103 heap[i/2].ch = heap[i].ch ;
104 heap[i/2].freq = heap[i].freq ;
105 heap[i/2].index = heap[i/2].index;
106
107 heap[i].ch =temp.ch;
108 heap[i].freq = temp.freq;
109 heap[i].index = temp.index;
110 }
111 else
112 break;
113
114 }
115
116 }
117 //當取走最小元素后，把最小堆的最后一個元素放在該位置，重構最小堆
118 void MoveDown(HNode *heap)
119 {
120 HNode temp;
121 int i=1 ;
122 int j=0;
123 for(j=2*i; j <= currentSize; j*=2)
124 {
125 if(j<currentSize && heap[j].freq> heap[j+1].freq) j++;
126 if(heap[i].freq < heap[j].freq) break;
127 temp.ch = heap[j].ch;
128 temp.freq = heap[j].freq;
129 temp.index = heap[j].index;
130
131 heap[j].ch = heap[i].ch;
132 heap[j].freq = heap[i].freq;
133 heap[j].index = heap[i].freq;
134
135 heap[i].ch = temp.ch;
136 heap[i].freq = temp.freq;
137 heap[i].index = temp.index;
138
139 i = j;
140 }
141 }
142 //完成插入新元素，并重構最小堆
143 int Insert(PHHead heap , HNode node)
144 {
145 heap[currentSize+1].ch = node.ch;
146 heap[currentSize+1].freq = node.freq;
147 heap[currentSize+1].index = node.index;
148 currentSize++;
149 MoveUP(heap);
150
151 }
152 //完成刪除最小元素，并重構最小堆
153 HNode DeleteMin(PHHead heap )
154 {
155 HNode node;
156 node.ch = heap[1].ch;
157 node.freq = heap[1].freq;
158 node.index = heap[1].index;
159
160 heap[1].ch = heap[currentSize].ch;
161 heap[1].freq = heap[currentSize].freq;
162 heap[1].index = heap[currentSize].index;
163
164 currentSize--;
165 MoveDown(heap);
166
167 return node;
168 }
169
haffman.c 哈夫曼實現
1 #include <stdio.h>
2 #include<stdlib.h>
3 #include <string.h>
4 #include "huffman.h"
5 extern HNode heapData[DEFAULTSIZE];
6 extern int currentSize;
7 extern int totalNum;
8 int currentSizeTree = 0;//樹結構的當前長度
9 HuffmanCode HC;
10
11 /*對n個元素，構建哈夫曼樹HT，輸出每個元素的哈夫曼編碼，在操作過程中，取最小權重元素的操作由最小堆完成*/
12 void HuffmanCoding(HuffmanTree HT, HuffmanCode HCtemp, PHHead heap , int n)
13 {
14 HNode hnode1; //從最小堆里面取出的兩個元素
15 HNode hnode2;
16 int m = n+1; // the index number that merged nodes starts
17 if(n <= 1) return;
18
19 while(!IsEmpty())
20 {
21
22 //從最小堆中取出兩個最小元素，并保存到huffman樹結構，并建立關聯
23 if(currentSize <=1)
24 {
25 break;//直接返回，輸入只有一個元素，一開始用return，錯誤阿！！
26 }
27 else //如果最小堆里有>=2個元素
28 {
29
30 hnode1 = DeleteMin(heapData );
31 hnode2= DeleteMin(heapData );
32 int i = hnode1.index;
33 int j = hnode2.index;
34
35 HT[i]. parent = currentSizeTree+1; //建立新節點
36 HT[j].parent = currentSizeTree+1;
37 currentSizeTree++; //樹結構元素個數增加一
38
39 HT[currentSizeTree].lchild = i;
40 HT[currentSizeTree].rchild = j;
41 HT[currentSizeTree].parent =0;//把默認父結點設為0,便于編碼判斷
42
43 HT[currentSizeTree].freq = hnode1.freq + hnode2.freq;
44 //創建最小堆節點（兩個最小元素的合并），并插入，重構最小堆
45 HNode hnode;
46 hnode.index =currentSizeTree;
47 hnode.freq =HT[currentSizeTree].freq;
48 Insert(heapData, hnode);
49 }
50
51 }
52
53 //以下求從葉子到根的huffman編碼
54 HCtemp = (HuffmanCode)malloc((totalNum+1)*sizeof(char*));
55 int length =totalNum;//編碼的最大長度,應該為輸入構建樹后，數目減去1，但'\0' +1
56 char *cd = (char *)malloc(length*sizeof(char));
57 cd[length-1] = '\0';
58 int i = 0;
59 int c;
60 int start;//編碼開始標號
61 int f; //父結點下標
62 for(i = 1; i <=totalNum;++i)
63 {
64 start = length-1;//編碼結束符
65 for(c=i, f=HT[i].parent; f!=0; c=f,f=HT[f].parent)
66 if(HT[f].lchild == c) cd[--start] = '0';
67 else cd[--start] = '1';
68
69
70
71 HCtemp[i] = (char *)malloc(length*sizeof(char)); //加上'\0' +1
72 strcpy(HCtemp[i], &cd[start]);
73
74 }
75 HC = HCtemp; //c語言沒有引用類型，所以最后要把指針傳回去阿！！！
76 free(cd);
77 }
最后main.c
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include "huffman.h"
4 extern HNode heapData[DEFAULTSIZE+1];
5 extern int currentSize;//堆的當前長度
6 extern int currentSizeTree;//樹的當前長度
7 extern int totalNum;//輸入的總個數
8 extern HuffmanCode HC;//哈夫曼編碼
9
10 void printCode(HuffmanCode HC,int n);
11 void dataCpy(HuffmanTree, HNode[]); //從堆結構的輸入數據中cpy數據到樹結構中
12 void printOutHeap(HNode* heapData, int size);//測試用：把推結構的數據打印出來
13 void printOutTree(HuffmanTree treeData, int size);//測試用：把樹結構的數據打印出來
14 int main()
15 {
16 currentSizeTree = 0;//樹長度初始化為0
17
18 int chNum;
19 getdata(heapData); // 為對結構輸入數據
20
21 int lengthOfFinalTree = currentSize *2-1;//
22 HuffmanTree HT = (HuffmanTree)malloc(sizeof(HTNode)*currentSize *2 ); //創建數組形式的樹，個數為樹節點的個數2*n-1,首節點不用+1
23 dataCpy(HT,heapData);//把數據復制到樹結構中
24
25 chNum = currentSize;
26 makeMinheap(heapData, chNum);
27
28 /*HNode a;
29 a.ch = 'k';
30 a.freq = 3;
31 Insert(heapData , a );
32 makeMinheap(heapData,currentSize);*/
33
34 // DeleteMin(heapData);
35
36 HuffmanCoding(HT, HC, heapData, chNum);
37 // printOutHeap(heapData, currentSize);
38 printOutTree(HT, lengthOfFinalTree);
39 printCode(HC,totalNum);
40 return 0;
41 }
42
43 void printCode(HuffmanCode HC,int n)//n是元素個數
44 {
45 int i;
46 char* t;
47 char c;
48 for(i =1; i <= n; i++)
49 {
50 t = HC[i];
51 for(; (c=*t) != '\0'; t++)
52 {
53 printf("%c", c);
54 }
55 printf("\n");
56 }
57 }
58 void dataCpy(HuffmanTree t, HNode s[])//從堆結構的輸入數據中cpy數據到樹結構中
59 {
60 int i = currentSize+1;//數據輸入的規模
61 while(--i>0)
62 {
63 t[i].freq = s[i].freq;
64 t[i].ch = s[i].ch;
65 currentSizeTree ++;//更新樹結構的長度
66
67 }
68 }
69
70 //打印出推結構的數據,測試用
71 void printOutHeap(HNode* heapData, int size)
72 {
73 int i = 1 ;
74 for(;i<=size; i++)
75 {
76 printf("%d %c\n", i, heapData[i].ch);
77 }
78 printf("\nthis is the end!! ");
79 }
80 //打印出樹結構的數據,測試用
81 void printOutTree(HuffmanTree treeData, int size)
82 {
83 int i;
84 for(i=1; i<=size;i++)
85 {
86 //printf("%d %c\n",i, treeData[i].ch);
87 printf("%d: %d\n",i, treeData[i].freq);
88 }
89 }
gcc下用如下命令
gcc -g -o main huffman.h Minheap.c huffman.c main.c
debug with
gdb main
感覺程序有點寫的太冗長了，不知道哪里可以精簡下？
posted on 2008-03-28 23:29
fullfocus 閱讀(2943)
評論(9) 編輯 收藏 所屬分類:
算法