班级网页设计专周报告.doc

《班级网页设计专周报告.doc》由会员分享，可在线阅读，更多相关《班级网页设计专周报告.doc（15页珍藏版）》请在沃文网上搜索。

1、成都电子机械高等专科学校专周报告课程名称数据结构设计题目哈夫曼树编码与译码班级10531学号02姓名宋美指导老师杨勇完成时间2011-5-30至2011-6-3 成都电子机械高等专科学校计算机工程系第 1 页 共 5 页目 录1. 专周题目与要求1专周要求.1编程要点.12. 设计与实现1内容包括.1设计思路.2关键技术和解决方案.23. 专周小结10设计结果.10问题分析.10心得体会.10不足之处.104. 参考文献11第 12 页报告正文注：以下所列内容报告中都应包括，可以根据实际情况扩充。二级及以上标题自己设计，标题最多列至4级1. 专周题目与要求专周题目：哈夫曼编码与译码专周要求：1

2、.由用户输入一段文章或从文件中读入（英文），计算机自动统计出文章中各单词出现的频率，以此为依据对该文章进行哈夫曼编码（即频率为权值）。2.对编码后的文章要输出到指定的文件，文件的开始位置给出编码表。第二行开始为编码的正文。3.对给定的编码文章进行译码，把译码后的结果显示出来，或输出到文本文件。编程要点：1）.有序表的建立与操作，二叉树森林是一有序表的形式存储的。2）.哈夫曼编码，见教材相关部分。3) 哈夫曼译码，把编码表提取出来创建一棵编码二叉树。2. 设计与实现内容包括：输入一篇英文文章，统计该文章中每个单词出现的次数，然后以它们作为权值，对每一个单词进行编码，编码完成后再对其编码进行译码，

3、提取创建一棵编码二叉树并以有序表的形式存储。1. 从键盘输入一段英语文章；2. 统计这篇文章中的每个单词出现的次数；3. 以单词出现次数作为权值，构建哈夫曼树，并创建一棵编码二叉树以二叉树的形式存储；4. 对每个单词进行编码并将编码进行破译。设计思路：1、创建一个工程Win32 Console Application，将函数体得实现存放于一个.c文件中，再创建一个.h文件用于存放所用的函数体以及一个总函数.c。 2、首先建立一个有序表，用于存放编码后的二叉树。 3、然后，将用户输入的英文文章的每个单词的频率计算出来作为权值。 4、编写哈夫曼树的初始化，建立，以及编码和译码。关键技术和解决方案（

4、关键代码，关键算法）1.OrderList.cinclude OrderList.h#include #include#include/*初始化有序表*/void InitiList(OrderList* list)list-ListLen = 0;list-Compare = NULL;list-Vist = NULL;/=/*添加一个元素*/int AddElement(OrderList* list, void* e)int j;if(list-ListLen=MAXSIZE)printf(表已满n);return 0 ;if(list-ListLen=0)list-data0=e;el

5、sefor(j=list-ListLen;j0;j-)int n;n=compareInt(list-dataj-1,e);if(ndataj=list-dataj-1;if(j-1=0)list-data0=e;if(n0)list-dataj=e;break;+list-ListLen;return 1;/=/*遍历有序表*/void Tranverse(OrderList* list)int i;if (!list-Vist) printf(请先设置Vist回调函数n);return;printf(各元素的权重：);for (i = 0; i ListLen; i+)list-Vist(

6、list-datai);printf(n);void strtolower(char *str)for (;*str;str+)if(*strZ) continue;*str+=0x20;/=/int Frequncy() /计算单词频率char wd20;int num=0;int i; char ch;while(1) scanf(%s,wd); /输入单词 /strtolower(wd); /把大写字母转化为小写 for(i=0;inum;i+) if(strcmp(wd,wci.word)=0) wci.count+; break; if(i=num) num+; strcpy(wcn

7、um-1.word,wd); wcnum-1.count=1; ch=getc(stdin); if(ch=10 | ch=13) /13表示回车的ASCMAbreak; return num;/=/*初始化Huffman树*/void InitiHuffman(HuffmanNode *ht,int n)int i;for(i=0;i2*n-1;i+) /n个叶子结点的Huffman树有n-1个结点hti.weight=0; / 初始值为hti.parent=0;hti.flag=0;hti.lchild=-1;hti.rchild=-1; /=/*构造Huffman树*/void Crea

8、tHuffman(HuffmanNode *ht,int n)int i,j,m1,m2,x1,x2; for(i=0;i2*n-1;i+) /n个叶子结点的Huffman树有n-1个结点hti.weight=0; / 初始值为hti.parent=0;hti.flag=0;hti.lchild=-1;hti.rchild=-1; for(i=0;in;i+)hti.weight=wci.count;for(i=0;in-1;i+) /构造Huffman树，每次循环构造一颗二叉树 m1=m2=1000; /设定初值，用于求最小权重结点x1=x2=0; /x1和x2是最小权重的两个结点的位置fo

9、r(j=0;jn+i;j+) /每次找出权重最小的两个结点if(htj.flag=0&htj.weightm1)m2=m1;x2=x1;m1=htj.weight;x1=j;else if(htj.weightm2&htj.flag=0)m2=htj.weight;x2=j;htx1.parent=n+i; /给双亲结点编号htx2.parent=n+i;htx1.flag=1;htx2.flag=1;htn+i.weight=htx1.weight+htx2.weight; /双亲结点的权重htn+i.lchild=x1; /左孩子为X1htn+i.rchild=x2;/右孩子为X2/=/*

10、根据Huffman求编码*/void Huffman(HuffmanNode *ht,HuffmanCode *hcd,HuffmanCode d,int n)int i,j,c,p;for (i=0;in;i+) /根据Huffman求编码d.start=n;c=i;p=htc.parent;while(p!=0) /由叶子结点向上直到根结点if(htp.lchild=c)d.cdd.start=0; /左孩子编码为elsed.cdd.start=1; /右孩子编码为d.start=d.start-1;c=p; p=htp.parent; d.start+;for( j=d.start;j=

11、n;j+)hcdi.cdj=d.cdj;hcdi.start=d.start; /=/打印Huffman树/void Print(HuffmanCode *hcd,int n)int i,j;printf(输出Huffman编码:n);for(i=0;in;i+) /输出Huffman树的叶子结点编码printf(%s,wci.word);printf( );for(j=hcdi.start;j=n;j+) printf(%d,hcdi.cdj); printf(n); /=/Huffman树的译码/void HuffmanDecoding(HuffmanNode *ht,HuffmanCod

12、e *hcd,int n) int i,j; HuffmanNode *p; p=ht; for(i=0;wci.word!=0;i+) for(i=0;in;i+) for(j=hcdi.start;jlchild) printf(%s ,wci.word); p=ht; elsep=p-lchild; else if(!p-rchild) printf(%s ,wci.word); p=ht; else p=p-rchild; printf(n);2.OrderList.h#ifndef ORDERLIST_H#define ORDERLIST_H#define Max 100#defin

13、e MAXSIZE 100/*最大表长*/*有序表，自动降序排列元素*/typedef structvoid* dataMAXSIZE;/*元素数组*/int ListLen;/*当前表长*/int (*Compare)(void*,void*);/*比较时回调函数（函数指针）*/void (*Vist)(void*);/*访问元素的回调元素*/OrderList;typedef struct int flag ;/ 结点标记 int weight; /权重 int parent; / 双亲结点下标 int lchild ; / 左孩子指针 int rchild ;/右孩子指针HuffmanN

14、ode;typedef struct /存放Huffman树编码的数组元素结构char cdMax; /数组int start; /编码的起始下标HuffmanCode;typedef struct WordCounter char word20; /装单词最大元素 int count; /计算单词个数WordCounter;WordCounter wcMAXSIZE;/*初始化有序表*/void InitiList(OrderList* list);/*添加一个元素*/int AddElement(OrderList* list,void* e);/*遍历有序表*/void Tranvers

15、e(OrderList* list);/*大小写字母转换*/void strtolower(char *str);/*初始化Huffman树*/void InitiHuffman(HuffmanNode *ht,int n);/*构造Huffman树*/void CreatHuffman(HuffmanCode *hcd,int n);/*编码*/void Huffman(HuffmanNode *ht,HuffmanCode *hcd,HuffmanCode d,int n);/*打印Huffman编码*/void Print(HuffmanCode *hcd);int Vist(Huffm

16、anNode *ht,int n); /void HuffmanDecoding(HuffmanNode *ht,HuffmanCode *hcd,int n);#endif3. main.c#include OrderList.h#include#include #include#includeint compareInt(void* e1,void* e2)return *(int*)e1-*(int*)e2;void printInt(void* e)printf(%d ,*(int*)e);void main()int a1000;int i,len; OrderList list;H

17、uffmanNode ht2*Max; HuffmanCode hcdMax, d;InitiList(&list); /初始化顺序表list.Compare=compareInt;/装载比较回调函数list.Vist=printInt;/装载访问回调函数printf(请输入一篇英文文章:n);len=Frequncy(); /返回单词频数for(i=0;ilen;i+) printf(%s %dn,wci.word,wci.count);for(i=0;ilen;i+)ai=wci.count;AddElement(&list,&ai); /向顺序表中添加元素Tranverse(&list)

18、;InitiHuffman(ht,len); /初始化Huffman树CreatHuffman(ht,len); /创建Huffman树Huffman(ht,hcd,d,len); /编码Huffman树 Print(hcd,len); /打印Huffman树 Vist(ht,len); HuffmanDecoding(ht,hcd,len);以下是代码的实现过程： 专周小结设计结果： 还算简单的编写出程序了，能够实现一些基本的哈夫曼编码和译码并正确。能够基本实现操作，达到实验的目的。问题分析： 编程的过程中，有遇到各种各样的问题，所幸都在同学的帮助和网络的协助下克服了难关。心得体会（遇到的问

19、题，解决方法，收获）：度过了一次艰难的数据专周，通过一周的课程设计使我对哈夫曼树以及哈夫曼编码有了更深的认识和理解，也使我更加明白哈夫曼编码译码在信息技术中的重要性和地位，让我知道哈夫曼树真的很重要也有点难。我谈谈我在编写我遇到的问题。做第一次的时候，编写出了很多错误。使得自己对自己失去了自信了，不过，后来还是坚持了下来。许多的错误让我明白了一个道理-细心是非常重要的。函数体的实现真的很重要。同时，对于编程者而言，事先画好流程图是很重要的，思路清晰也是相当重要的。在遇到问题的时候和同学一起交流探讨是一个十分好的学习机会，我们应该好好把握。请教老师也很重要，因为毕竟我们对于数据结构这门学科来说是

20、新手，对于一些问题很难弄明白。而且，某些错误对于我们来说有时候想半天都弄不来，思路简直就是混乱的，但老师就不一样了，几下下就搞定了，这样就更加有效地节约了时间和精力，让自己也有种恍然大悟的感觉。这次专周最大的挑战就是建立工程，毕竟以前都没有用过，有点丈二和尚摸不到头的感觉，不过，还好，在自己的努力下克服了种种困难。了解了工程的基本东西。能够准确的应用工程也算是这次专周学到的最好的东西。这次课程设计不但让我学得了一些编程知识，还学会了系统的做一份课程设计报告，明白了做事情只有认真，才能真正做得更好！通过这次课程设计，我看清楚了自己的编程功底和动手能力还不如人意，这主要是基本知识掌握不牢，平时实践太少的缘故。我想，在未来的暑假中，我会努力尝试编写一些程序，让自己从中获得更多的知识。设计不足之处，改进建议：在这个程序中，还有许多地方值得完善。比如：译码的编写中总是出现错误。还有很多地方需要学习和掌握的。致谢（老师，同学等的指导和帮助）4. 参考文献杨剑 数据结构清华大学出版社严蔚敏.数据结构(C语言版).清华大学出版社，2007苏仕华.数据结构课程设计.机械工业出版社，2007考核情况（由指导老师填写）项目考勤(20%)验收(40%)报告(20%)总分得分考勤记录考勤日期出勤记录验收情况