随笔-28  评论-51  文章-10  trackbacks-0
以前都是在一个文件里写代码的,第一次用了这么多文件(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 <= 1return;
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 阅读(2926) 评论(9)  编辑  收藏 所属分类: 算法

评论:
# re: 第一次写这么多代码_!!--纯c哈夫曼代码实现(用了最小堆) 2008-03-29 15:28 | ZelluX
函数命名方法不统一阿
  回复  更多评论
  
# re: 第一次写这么多代码_!!--纯c哈夫曼代码实现(用了最小堆) 2008-03-29 15:55 | fullfocus
@ZelluX
你好,一般在c程序里面,函数命名方式是什么样的呢?
第一个单词小写后面每个单词首字母大写吗? 恳请指教!  回复  更多评论
  
# re: 第一次写这么多代码_!!--纯c哈夫曼代码实现(用了最小堆) 2008-03-29 18:31 | raof01
同学,你这练习——全局变量满天飞  回复  更多评论
  
# re: 第一次写这么多代码_!!--纯c哈夫曼代码实现(用了最小堆) 2008-03-29 18:33 | raof01
算法不错  回复  更多评论
  
# re: 第一次写这么多代码_!!--纯c哈夫曼代码实现(用了最小堆) 2008-03-29 20:18 | fullfocus
@raof01
因为文件之间要传递变量,没办法只能设这么多全局的了,您有其他建议吗?谢谢:)  回复  更多评论
  
# re: 第一次写这么多代码_!!--纯c哈夫曼代码实现(用了最小堆) 2008-03-29 20:53 | ZelluX
@fullfocus
怎么命名都可以,关键是要统一。  回复  更多评论
  
# re: 第一次写这么多代码_!!--纯c哈夫曼代码实现(用了最小堆) 2008-03-29 22:23 | raof01
@fullfocus
可以说,这个问题更多的是与封装(C语言提供了某种程度的封装)相关。也许是java对你的影响,因此你对C/C++将声明和定义分开的方式还不是很习惯。要消除全局变量,可以将其封装到struct/class中,就像你在java中做的一样。如:
// heap.h
class HeapData; //前向声明
class Heap
{
public:
// Public methods go here
private:
HeapData * m_Data;
};
有了这个声明,就可以在main()中这样使用:
Heap aHeap;
// ...
也许对于习惯于java思维的人来说,这样很难理解。不过你已经注意到了C/C++的声明与定义分开。思考一下,到底为什么要这么做——相信很快你就会知道如何eliminate这些global variables。  回复  更多评论
  
# re: 第一次写这么多代码_!!--纯c哈夫曼代码实现(用了最小堆) 2008-04-02 00:12 | billjeff
嘿嘿,作为练习是值得肯定的。练习了多文件组织、GDB、算法学习和实现。建议再试试写个Makefile、做成一个lib。想想用C写链表是怎么写的,节点用struct,相关的变量封装到struct,你这儿也可以多用struct封装,然后相关函数只需传入一些结构即可,减少全局变量。我也习惯C++思维,看到最小堆就会想到用模板来做~不过满足需要就行。  回复  更多评论
  
# re: 第一次写这么多代码_!!--纯c哈夫曼代码实现(用了最小堆) 2012-03-21 04:31 | kenan
1.结构体交换数据不用把所有成员都拿出来交换
2.没有考虑到频数相同的情况

  回复  更多评论
  

只有注册用户登录后才能发表评论。


网站导航: