数据结构课程设计-实例.doc

《数据结构课程设计-实例.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计-实例.doc（41页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date数据结构课程设计-实例数据结构课程设计-实例数据结构课 程 设 计 报 告 书题目：赫 夫 曼 编 码 系别：计算机科学与应用 学号： 051007222 学生姓名： 牛 志 远 指导教师： 王亚楠 完成日期：2007年2月1日 一需要分析赫夫曼编码自己找一篇不少于100个单词的英文文章，分析该文章中每一个字符的出现概率（包括标点符号，区分大小写），根据分析结果对文章

2、中每一个字符进行赫夫曼编码，并将编码原则存储于一个独立的文本文件中。最后，根据这个编码原则，将英文文章转换为01串存储于一个文本文件中。如：英文文章为aaabbc则编码规则为a-0 b-10c-11英文文章将被转化为000101011 有能力的同学应该再编写一个解码程序，这个就不统一要求。二 概要设计1 系统运行时，将有ifstream fs(n.txt)句生成一文本文件，用于存放要编码的英文文章。2 然后，将有fs.get(c)语句从文章中逐个读入字符，其字符的ASCII码值将存入int w2128的对应下标中，且对应w2i的值加1。之后，将ASCII码值及对应字符出现次数记录于一动态分配的

3、机构体tongji数组*w中。3 然后，将调用赫夫曼编码函数HuffmanCoding(HT,HC,w,n)对文章中出现的字符进行编码，并将结果存于数组HC中。4 有ofstream fp(code.txt)打开勇于存储编码后的文章。5 对01码的解码程序将有函数Decoding()执行。三 详细设计#include#include#include#define MAX_NUM 100000#include typedef struct int index;/用于记录字符的ASCII码int frequent;/用于记录字符出现的次数 tongji;/该结构体用于对统计文章中字符出现的次数，及

4、该字符对应的整数值（用于字符与编码的转换）typedef struct unsigned int weight; unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;/动态分配数组存储赫夫曼树typedef char *HuffmanCode;/动态分配数组存储赫夫曼编码表/Select()函数，用于选择两个weight最小的结点void Select(HuffmanTree HT,int end,int *s1,int *s2)/coutendendl; int i; int min1=MAX_NUM; int min2; for (i

5、=1;i=end;i+) if (HTi.parent=0&HTi.weightmin1) *s1=i; min1=HTi.weight; min2=MAX_NUM; for(i=1;i=end;i+) if(HTi.parent=0&(*s1!=i)&HTi.weight0），构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC if(n=1)return; tongji *t=w+1; int m=2*n-1; HuffmanTree p;int i; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); for(p=HT,i=1;ifrequent;pi.p

6、arent=0;pi.lchild=0;pi.rchild=0; /*p=*w,0,0,0; for(;i=m;+i)pi.weight=0;pi.parent=0;pi.lchild=0;pi.rchild=0;/*p=0,0,0,0; int s1,s2; for(i=n+1;i=m;+i) /在HT1.i-1选择parent为0且weight最小的两个结点，其序号分别为s1和s2。 Select(HT,i-1,&s1,&s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HT

7、s2.weight; /-从叶子到根逆向求每个字符的赫夫曼编码-/*int start,c,f;HC=(HuffmanCode)malloc(n+1)*sizeof(char *);char *cd; cd=(char *)malloc(n*sizeof(char); cdn-1=0; for(i=1;i=n;+i)/逐个字符求赫夫曼编码 start=n-1; for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)/从叶子到根逆向求编码 if(c=HTf.lchild) cd-start=0; else cd-start=1; HCi=(char *)mallo

8、c(n-start)*sizeof(char); strcpy(HCi,&cdstart); free(cd);/释放工作空间*/-从根到叶子求编码- HC=(HuffmanCode)malloc(n+1)*sizeof(char*);/分配n个字符编码的头指针向量 char *cd; cd=(char*)malloc(n*sizeof(char);/分配求编码的工作空间 cdn-1=0;/编码结束符 int q=m;int cdlen=0; for(i=1;i=m;+i) HTi.weight=0;/遍历赫夫曼树时用作结点状态标志 while (q) if(HTq.weight=0)/向左

9、HTq.weight=1;if(HTq.lchild!=0)q=HTq.lchild; cdcdlen+=0;else if(HTq.rchild=0)/登记叶子结点的字符的编码 HCq=(char*)malloc(cdlen+1)*sizeof(char);/为第i个字符编码分配空间 cdcdlen=0;strcpy(HCq,cd);/从cd复制编码（串）到HC else if(HTq.weight=1)/向右 HTq.weight=2;if(HTq.rchild!=0)q=HTq.rchild;cdcdlen+=1; else/HTq.weight=2,退回 HTq.weight=0;q=

10、HTq.parent;-cdlen;/退到父结点，编码长度减1 /else /while/主函数void main() HuffmanTree HT;HuffmanCode HC; int n=128; / int w20=0,5,29,7,8,14,23,3,11; /for(int i=1;i9;i+)coutHCiendl; ifstream fs(n.txt);/该语句将自动创建并打开一个“n.txt”文本文件，用于要翻译的英文文章 char c; int w2128;/对应128个ASCII码值 for(int i=1;i128;i+)w2i=0; while(fs.get(c) i

11、nt a=c;w2a+;/统计各个字符出现的次数 fs.close(); tongji *w; w=new tongji100;/用new动态分配空间 int k=0;cout字符的存储位置，对应ASCCII码值及出现次数依次为：endl; for(i=0;i0) k+;wk.frequent=w2i;/wk.frequent存储字符出现次数wk.index=i;/存储字符的ASCII码值coutk=k i=i wk.frequentendl; n=k;/表明要对n=k个进行编码HuffmanCoding(HT,HC,w,n);/调用赫夫曼编码函数cout各个字符对应编码(每行显示5个字符编码

12、)依次为：endl; for( i=1;i=k;i+)coutHCi ;if(i%5=0)coutendl;/显示各个字符的编码 fs.open(n.txt); char ch; tongji *ptr;ptr=w; /创建并打开“code.txt”文件，存储编码结果 ofstream fp(code.txt); while(fs.get(ch) int b=ch; for(i=1;i=k;i+) if(wi.index=b)fpHCi; fp.close();/main()四 调试分析1 本题是利用赫夫曼树对一篇英文文章进行编码，起初感到无从下手，通过老师的讲解及对课本相关内容的分析，了解了

13、其一般的思路，掌握该设计的基本方法。经过小组的商讨及不断的调试，完成了该项设计。2 对赫夫曼树的构造及其编码的详细过程不会程序化，经过仔细看书和同学交流，经过不断调试，最终实现。3 设计中用到文件的输入输出，其中对于文件中字符的提取及把字符读入到文件不清楚，通过对相关知识的了解及不断尝试最终得到了解决。五 测试结果要编码的英文文章及“n.txt”内容为：编码结果及“code.txt”为：屏幕显示结果为： 附加：该程序对应解码程序为：void Decoding(HuffmanCode HC,int n) int i=0,k,t; char c,ch; char *pstr; pstr=new charn; ifstream fs(code.txt);/打开含01码的文本 ofstream fp(decode.txt);/创建并打开一文本，用于存储解码后的内容 while(fs.get(c) *(pstr+i)=c;i+;k=0;while(kn) k+; if(strcmp(pstr,HCk )=0) t=wk.index; ch=char(t);/coutch;fp.put(ch);*pstr=null;/清空*pstr中原有内容i=0; fs.close(); fp.close();指导教师评语： 成绩： 指导教师： 年 月 日-