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

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个单词的英文文章，分析该文章中每一个字符的出现概率（包括标点符号，区分大小写），根据分析结果对文章中每一个字符进行赫夫曼编码，并将编码原则存储于一个独立的文本文件中。最后，根据这个编码原则，将英文文章转换为01串存储于一个文本文件中。如：英文文章为aaabbc则编码规则为a-0 b-10c-11英文文章将被转化为000101011 有能力的同学应该再编写一个解码程序，这个就不统一要求。二 概要设计1 系统运行时，将有ifstream fs("n.txt")句生成一文本文件，用于存放要编码的英文文章。2 然后，将有fs.get(c)语句从文章中逐个读入字符，其字符的ASCII码值将存入int w2128的对应下标中，且对应w2i的值加1。之后，将ASCII码值及对应字符出现次数记录于一动态分配的机构体tongji数组*w中。3 然后，将调用赫夫曼编码函数HuffmanCoding(HT,HC,w,n)对文章中出现的字符进行编码，并将结果存于数组HC中。4 有ofstream fp("code.txt")打开勇于存储编码后的文章。5 对01码的解码程序将有函数Decoding()执行。三 详细设计#include<iostream.h>#include<string.h>#include<stdlib.h>#define MAX_NUM 100000#include<fstream.h> typedef struct int index;/用于记录字符的ASCII码int frequent;/用于记录字符出现的次数 tongji;/该结构体用于对统计文章中字符出现的次数，及该字符对应的整数值（用于字符与编码的转换）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)/cout<<end<<endl; int i; int min1=MAX_NUM; int min2; for (i=1;i<=end;i+) if (HTi.parent=0&&HTi.weight<min1) *s1=i; min1=HTi.weight; min2=MAX_NUM; for(i=1;i<=end;i+) if(HTi.parent=0&&(*s1!=i)&&HTi.weight<min2) *s2=i; min2=HTi.weight; void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,tongji w,int n)/w存放n个字符的权值（均>0），构造赫夫曼树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;i<=n;+i,+t) pi.weight=t->frequent;pi.parent=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+HTs2.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 *)malloc(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)/向左 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=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;i<9;i+)cout<<HCi<<endl; ifstream fs("n.txt");/该语句将自动创建并打开一个“n.txt”文本文件，用于要翻译的英文文章 char c; int w2128;/对应128个ASCII码值 for(int i=1;i<128;i+)w2i=0; while(fs.get(c) int a=c;w2a+;/统计各个字符出现的次数 fs.close(); tongji *w; w=new tongji100;/用new动态分配空间 int k=0;cout<<"字符的存储位置，对应ASCCII码值及出现次数依次为："<<endl; for(i=0;i<128;i+) if(w2i>0) k+;wk.frequent=w2i;/wk.frequent存储字符出现次数wk.index=i;/存储字符的ASCII码值cout<<"k="<<k<<" "<<"i="<<i<<" "<<wk.frequent<<endl; n=k;/表明要对n=k个进行编码HuffmanCoding(HT,HC,w,n);/调用赫夫曼编码函数cout<<"各个字符对应编码(每行显示5个字符编码)依次为："<<endl; for( i=1;i<=k;i+)cout<<HCi<<" "if(i%5=0)cout<<endl;/显示各个字符的编码 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)fp<<HCi; fp.close();/main()四 调试分析1 本题是利用赫夫曼树对一篇英文文章进行编码，起初感到无从下手，通过老师的讲解及对课本相关内容的分析，了解了其一般的思路，掌握该设计的基本方法。经过小组的商讨及不断的调试，完成了该项设计。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(k<n) k+; if(strcmp(pstr,HCk )=0) t=wk.index; ch=char(t);/cout<<ch;fp.put(ch);*pstr=null;/清空*pstr中原有内容i=0; fs.close(); fp.close();指导教师评语： 成绩： 指导教师： 年 月 日-