以前都是在一个文件里写代码的，第一次用了这么多文件（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 阅读(2938)
评论(9) 编辑 收藏 所属分类:
算法