数据结构专业课程设计哈夫曼树.doc

课 程 设 计课程设计名称： 数据结构课程设计 专 业 班 级 ： 学 生 姓 名 ： 学 号 ： 指 导 教 师 ： 李磊 课程设计时间： .7.06.7.10 计算机类 专业课程设计任务书学生姓名专业班级学号题 目哈夫曼树编/译码系统课题性质A课题起源D指导老师李磊同组姓名无关键内容1. 学习掌握并熟练利用C语言进行程序设计,2.针对具体应用问题，选择、设计和实现适宜抽象数据类型；3.进行整体设计使各个函数之间紧密联络起来；任务要求1.综合利用和融化所学理论知识，提升分析和处理实际问题能力，达成培养良好程序设计能力和习惯目标，为开发满足问题要求小型应用软件奠定基础，达成软件工程综合性基础训练目标。,2.完成需求分析汇报，汇报中对关键部分给出图表说明。要求格式规范，工作量饱满。参考文件C语言程序设计（第三版）谭浩强 清华大学出版社C Primer Plus(第5版) Stephenprata 北京人民邮电出版社 审查意见指导老师签字：教研室主任签字： 年 月 日目录目录11需求分析21.1系统介绍21.2程序输入和输出21.3程序要达成功效21.4调试过程介绍22概要设计32.1数据结构设计32.2系统模块设计33具体设计44系统演示124.1主界面124.2数据录入124.3翻译短文134.4反译编码134.5打印文件编码144.6打印哈夫曼树145运行环境156课程心得总结16参考文件；161需求分析1.1系统介绍利用Huffman编码进行通信能够大大提升信道利用率缩短信息传输时间，降低传输成本，这要求在发送端经过一个编码系统对待传数据预先编码，在接收端将传来数据进行译码（复原）。对于双工信道（即能够双向传输信息信道），每端全部需要一个完整编译码系统。此程序就是为这么信息收发站写一个Huffman码编译码系统。1.2程序输入和输出从终端读入字符集大小n，和n个字符及各个字符权值，建立赫夫曼树，并将它存放到文件hfmTree中；利用已建好赫夫曼树将文件中字符编码，假如赫夫曼树不在内存中，则从文件hfmTree中读取到内存；将译得代码存到文件CodeFile中；利用已建好赫夫曼树对CodeFile中代码进行译码，将结果存入文件TextFile中；最终将已在内存中哈夫曼树以直观方法（树或凹入表形式）显示在终端上，同时将此字符形式哈夫曼树写入文件TreePrint中。1.3程序要达成功效用户能够利用菜单依据自己需要来选择要进行编码或是译码,并将转换好字符或编码以文件形式存到对应文件里面。1.4调试过程介绍（l）利用教材中数据调试程序。（2）用下表给出字符集和频度实际统计数据建立哈夫曼树，并实现以下报文编码和译码：THIS PROGRAM IS MY FAVORITE。字符 ABCDEFGHIJKLMNOPQRSTUVWXYZ频度18664132232103211547571532205763151485180238181161 选择2，输入THIS PROGRAM IS MY FAVORITE，屏幕上显示同时文件codefile里面也出现对应代码选择3，从codefile中调入代码，终端显示THIS PROGRAM IS MY FAVORITE，而且文件textfile中也对应存入了这段话。选择4，文件CodeFile以紧凑格式显示在终端上。选择5，将已在内存中哈夫曼树以直观方法（树或凹入表形式）显示在终端上，同时将此字符形式哈夫曼树写入文件TreePrint中。选择其它数字，将出现犯错提醒，并重新回到选择菜单。2概要设计 2.1数据结构设计 InitHuffman(Huffman Hfm)；/初始化哈夫曼树Encoding(Huffman Hfm)； /翻译短文Decoding(Huffman Hfm)； /反译编码Print1(Huffman Hfm)； /打印文件编码Print2(Huffman Hfm)； /打印哈夫曼树typedef char *HuffmanCode;/动态分配数组存放霍夫曼表码表typedef struct unsigned int weight; unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;/动态分配数组存放霍夫曼树typedef struct HuffmanTree HT; char *c; int length; HuffmanCode HC;Huffman;/分配数组存放字符串及其对应霍夫曼树Huffman Hfm;2.2系统模块设计哈夫曼树编/译码系统录入数据翻译短文反译编码打印文件编码打印哈夫曼树退出系统3具体设计#include #include #include #include#define NULL 0#define OK 1#define ERROR 0#define OVERFLOW -2#define MAX_NUM 32767#define MAX 60typedef char *HuffmanCode;/动态分配数组存放哈夫曼表码表typedef struct unsigned int weight; unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;/动态分配数组存放哈夫曼树typedef struct HuffmanTree HT; char *c; int length; HuffmanCode HC;Huffman;/全局结构体变量，来存放字符和代码/*-寻求权值最小两个节点-*/void Select(HuffmanTree HT,int end,int *s1,int *s2) int i; int min1=MAX_NUM; int min2; for (i=1;i=end;i+)/*遍历查找权值最小结点S1*/ if (HTi.parent=0&HTi.weightmin1) *s1=i; min1=HTi.weight; min2=MAX_NUM; for(i=1;iHTi.weight) *s2=i; min2=HTi.weight; /*-对哈夫曼树进行编码-*/Huffman HuffmanCoding(Huffman Hfm) int i,n,m,s1,s2,start; int c,f; char *cd; n=Hfm.length; if(n=1) return Hfm; m=2*n-1; for(i=n+1;i=m;+i) /*选择HT1.i-1中无双亲且权值最小两个节点，其序号为s1，s2*/ Select(Hfm.HT,i-1,&s1,&s2); Hfm.HTs1.parent=i; /*修改父亲位置*/ Hfm.HTs2.parent=i; Hfm.HTi.lchild=s1; /*修改孩子位置*/ Hfm.HTi.rchild=s2; Hfm.HTi.weight=Hfm.HTs1.weight+Hfm.HTs2.weight;/*父亲结点权值为左右孩子权值之和*/ /*从叶子结点到根逆向求每个字符哈夫曼编码*/ Hfm.HC=(HuffmanCode)malloc(n+1)*sizeof(char *);/*分配n个字符编码头指针向量*/ cd=(char *)malloc(n*sizeof(char);/*分配求编码工作空间*/ cdn-1=0;/*编码结束符*/ for(i=1;i=n;+i)/*逐一字符求哈夫曼编码*/ start=n-1;/*编码结束符位置*/ for(c=i,f=Hfm.HTi.parent;f!=0;c=f,f=Hfm.HTf.parent)/*从叶子到根逆向求编码*/ if(c=Hfm.HTf.lchild) cd-start=0; else cd-start=1; Hfm.HCi=(char *)malloc(n-start)*sizeof(char); strcpy(Hfm.HCi,&cdstart);/*从cd复制编码到Hfm.HC*/ free(cd); return Hfm;/*-录入数据函数-*/Huffman InputHuffman(Huffman Hfm) int i,n; printf(nn*录入数据*n); printf(录入字符及其权值将保留于:hfmTree n); printf(请输入录入字符个数: ); scanf(%d,&n); if(n=1) printf(只有一个字符无需编码); printf(n); printf(请输入录入字符个数: ); scanf(%d,&n); Hfm.HT=(HuffmanTree)malloc(2*n)*sizeof(HTNode); Hfm.c=(char *)malloc(n+1)*sizeof(char); for(i=1;i=n;i+) printf(请输入字符:); scanf(%s,&Hfm.ci); printf(请输入字符权值:); scanf(%d,&Hfm.HTi.weight); Hfm.HTi.parent=0; Hfm.HTi.lchild=0; Hfm.HTi.rchild=0; for(;i=2*n-1;+i) Hfm.HTi.weight=0; Hfm.HTi.parent=0; Hfm.HTi.lchild=0; Hfm.HTi.rchild=0; Hfm.length=n; return Hfm; /*-初始化哈夫曼树-*/Huffman InitHuffman(Huffman Hfm) int n,i; char x; FILE *fp; fp=fopen(hfmTree,rt);/*对文件hfmTree以读文本形式打开*/ if(fp=NULL) Hfm=InputHuffman(Hfm);/*调用InputHuffman函数，用户输入字符和对应权值存入哈夫曼数中*/ fp=fopen(hfmTree,wt); fprintf(fp,%dn,Hfm.length); for(i=1;i=Hfm.length;i+) fprintf(fp,%c %d ,Hfm.ci,Hfm.HTi.weight); rewind(fp); else printf(哈夫曼树已经存在!n你是否需要重新初始化哈夫曼树?(YorN)n);/*问询是否重新初始化*/ printf(请输入选择:); scanf(%s,&x); if(x=Y) Hfm=InputHuffman(Hfm);/*调用InputHuffman函数，用户输入字符和对应权值存入哈弗曼数中*/ fp=fopen(hfmTree,w+); fprintf(fp,%dn,Hfm.length); for(i=1;i=Hfm.length;i+) fprintf(fp,%c %d ,Hfm.ci,Hfm.HTi.weight); rewind(fp); else fscanf(fp,%dn,&n); Hfm.c=(char *)malloc(n+1)*sizeof(char); Hfm.HT=(HuffmanTree)malloc(2*n)*sizeof(HTNode); for(i=1;i=n;i+) fscanf(fp,%s %d ,&Hfm.ci,&Hfm.HTi.weight);/*将已经在文件中字符和其对应权重输入到Hfm.ci和&Hfm.HTi.weight中*/ for(i=1;i=n;i+)/*对每个节点初始化*/ Hfm.HTi.parent=0; Hfm.HTi.lchild=0; Hfm.HTi.rchild=0; for(;i=2*n-1;+i) Hfm.HTi.weight=0; Hfm.HTi.parent=0; Hfm.HTi.lchild=0; Hfm.HTi.rchild=0; Hfm.length=n; fclose(fp); Hfm=HuffmanCoding(Hfm); return Hfm;/*-翻译短文-*/void Encoding(Huffman Hfm)/*利用已建好Huffman树(如不在内存，则从文件hfmTree中读入)对文件ToBeTran中正文进行编码，然后将结果存入文件CodeFile中。*/ int i=0,j=0,n; char chMAX; FILE *fp,*fw; n=Hfm.length; printf(nn*翻译短文*nn); if(fw=fopen(ToBeTran,r+)=NULL)/*尝试打开ToBeTran*/ printf(n请输入需要翻译成编码短文: ); scanf(%s,ch); printf(n); fp=fopen(CodeFile,wt+); else fscanf(fw,%s,ch); fclose(fw); while(chj) for(i=1;ilchild|p-rchild) if(dj=0) i=p-lchild; p=&Hfm.HTi; else i=p-rchild; p=&Hfm.HTi; j+; printf(%c,Hfm.ci); fprintf(fp,%c,Hfm.ci); printf(n); fclose(fp);/*-打印文件编码-*/void Print1(Huffman Hfm) int i,n; int m=1; char ch; FILE* fprint; n=Hfm.length; printf(nn*打印文件编码*nn); fprint=fopen(CodeFile,rb); while ( feof(fprint)=0 ) ch=fgetc(fprint); printf(%c,ch); m+; if (m%50=0) printf(n); printf(n); fclose(fprint);/*-打印哈夫曼树-*/void Print2(Huffman Hfm) int i,n; n=Hfm.length; printf(nn*打印哈夫曼树*nn); for(i=1;i=n;i+) printf(n); printf(Char:%ct,Hfm.ci); printf(Weight:%dt,Hfm.HTi.weight); printf(parent:%dt,Hfm.HTi.parent); printf(lchild:%dt,Hfm.HTi.lchild); printf(rchild:%dt,Hfm.HTi.rchild); printf(Code:); puts(Hfm.HCi); printf(n);/*-主函数-*/void main() Huffman Hfm; char k; while(1) printf(n);printf( 欢迎进入哈夫曼编/译码系统:n);printf( welcomen);printf(t 【1】录入数据 n); printf(t 【2】翻译短文 n); printf(t 【3】反译编码 n); printf(t 【4】打印文件编码 n);printf(t 【5】打印哈夫曼树 n);printf(t 【0】退出系统 n);printf(n); printf(请输入你选择:); scanf(%c,&k);system(cls); switch(k) case 1: Hfm=InitHuffman(Hfm); getchar();break; case 2: Encoding(Hfm); getchar();break; case 3: Decoding(Hfm); getchar();break; case 4: Print1(Hfm); getchar();break; case 5: Print2(Hfm); getchar();break; case 0: exit(0); default: printf(无效选项!请重新输入n); 4系统演示4.1主界面4.2数据录入4.3翻译短文4.4反译编码4.5打印文件编码4.6打印哈夫曼树5运行环境1,软件环境：操作系统:Windows98/XP/Windows7以上版本2.硬件环境：1，处理器：Intel 166MX以上2，内存：32MB3：硬盘空间：2GB2，开发工具和编程语言Vc 6.0；用C语言编写；6课程心得总结 我学习数据结构时间也不短了，其中学习过程中或多或少有些遗漏知识点没有领悟透彻，经过这次做大程序机会，得以将过去学习部分知识点再次连贯起来，有了一次比较综合再学习，这次大程序也还有部分功效因为所学知识原因未能实现。这次大程序只是利用了数据结构中少部分知识，也使我认识到自己可能对其它知识点还没有完全掌握，这将会激励我以后努力学习，争取更上一层楼。参考文件；1 谭浩强 ，C语言程序设计，第2版.北京：高等教育出版社.2 Stephen C Prata,Primer Plus,第5版.北京：人民邮电出版社