数据结构与算法专业课程设计格式要求.doc

数据结构和算法 课程设计（/第二学期第20周）指导老师： 孙麒 郭奕亿班级： 09计算机科学和技术1班学号： E0968姓名：倪建鹤数据结构和算法课程设计任务书数据结构和算法是计算机专业关键关键课程之一，在计算机专业学习过程中占有很关键地位。数据结构和算法课程设计就是要利用本课程和到现在为止相关课程中知识和技术来处理实际问题。尤其是面临非数值计算类型应用问题时，需要选择合适数据结构，设计出满足一定时间和空间限制有效算法。本课程设计要求同学独立完成一个较为完整应用需求分析。并在设计和编写含有一定规模程序过程中，深化对数据结构和算法课程中基础概念、理论和方法了解；训练综合利用所学知识处理实际问题能力，强化面向对象程序设计理念；使自己程序设计和调试水平有一个显著提升。 赫夫曼编码/译码器1. 问题描述利用赫夫曼编码进行通信能够大大提升信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端经过一个编码系统对待传输数据预先编码，在接收端将传来数据进行译码（复原）。对于双工信道（即能够双向传输信息信道），每端全部需要一个完整编/译码系统。试为这么信息收发站编写一个赫夫曼码编/译码系统。2. 基础要求一个完整系统应含有以下功效：(1) I：初始化（Initialization）。从终端读入字符集大小n，和n个字符和n个权值，建立赫夫曼树，并将它存于文件hfmTree中。(2) E：编码（Encoding）。利用已建好赫夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中正文进行编码，然后将结果存入文件CodeFile中。(3) D：译码（Decoding）。利用已建好赫夫曼树将文件CodeFile中代码进行译码，结果存入文件Textfile中。以下为选做：(4) P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式编码文件写入文件CodePrin中。(5) T：印赫夫曼树（Tree printing）。将已在内存中赫夫曼树以直观方法（比如树）显示在终端上，同时将此字符形式赫夫曼树写入文件TreePrint 中。3. 测试要求(1) 已知某系统在通信联络中只可能出现八种字符，其频率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，试设计赫夫曼编码。(2) 用下表给出字符集和频度实际统计数据建立赫夫曼树，并实现以下报文编码和译码：“THIS PROGRAME IS MY FAVORITE”。字符ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度57631514851802381811614. 实现提醒(1) 编码结果以文本方法存放在文件Codefile中。(2) 用户界面能够设计为“菜单”方法：显示上述功效符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功效符。此功效实施完成后再显示此菜单，直至某次用户选择了“Q”为止。(3) 在程序一次实施过程中，第一次实施I，D或C命令以后，赫夫曼树已经在内存了，无须再读入。每次实施中不一定实施I命令，因为文件hfmTree可能早已建好。具体要求：课程设计结果内容必需由以下四个部分组成，缺一不可。(1) 上交源程序：学生根据试验题目标具体要求所开发全部源程序（应该放到一个文件夹中）；(2) 上交程序说明文件：（保留在.txt中）在说明文档中应该写明上交程序所在目录，上交程序主程序文件名，假如需要安装，要有程序安装使用说明；(3) 设计汇报：（保留在word 文档中，文件名要求： 根据“姓名_学号_设计题目”起名，如文件名为“ 张三_XXX_赫夫曼编码 ”.doc。打印稿用A4纸）。其中包含: 题目； 试验目标； 需求分析：在该部分中叙述实现功效要求； 概要设计：在此说明每个部分算法设计说明（能够是描述算法步骤图），每个程序中使用存放结构设计说明（假如指定存放结构请写出该存放结构定义）； 具体设计各个算法实现源程序，对每个题目要有对应源程序（能够是一组源程序，每个功效模块采取不一样函数实现）。源程序要根据写程序规则来编写。要结构清楚，关键函数关键变量，关键功效部分要加上清楚程序注释； 调试分析测试数据，测试输出结果，时间复杂度分析，和每个模块设计和调试时存在问题思索（问题是哪些？问题怎样处理？），算法改善设想； 总结： 总结能够包含 : 设计过程收获、碰到问题及处理问题过程思索、程序调试能力思索、对数据结构这门课程思索、在设计过程中对数据结构课程认识等内容。三、工作内容及工作计划：一周（20）时间地点工作内容指导老师7月 11日早晨10-414试验要求，需求分析； 孙麒、郭奕亿下午10-414查找资料，总体结构设计；孙麒、郭奕亿7月12日早晨10-414算法设计、用户界面设计孙麒、郭奕亿下午10-414算法设计、用户界面设计孙麒、郭奕亿7月13日早晨10-414具体设计孙麒、郭奕亿下午10-414具体设计孙麒、郭奕亿7月14日早晨10-414具体设计孙麒、郭奕亿下午10-414具体设计孙麒、郭奕亿7月15日早晨10-414上机检验、答辩孙麒、郭奕亿下午10-414上机检验、答辩孙麒、郭奕亿四、考评成绩评定标准：本课程设计评价由三部分组成，包含程序演示（50%），课程设计汇报（30%），回复老师提问（20%）。1程序演示： 优功效完善，全部测试正确，而且能够对局部进行完善。 良功效完善，但测试欠缺。 中功效基础完善，但程序还有部分错误。 及格完成内存中赫夫曼编码/译码，但不包含文件操作。 不及格功效不完善，且程序错误较多，无法运行。2课程设计汇报： 优包含设计内容，设计思想，已经完成任务及达成目标，设计思绪清楚、书写条理清楚，源程序结构合理、清楚，注释说明完整，有对此次课程设计心得体会。 良包含设计内容，设计思想，已经完成任务及达成目标，设计思绪基础清楚、书写条理基础清楚，源程序结构合理、清楚，注释说明基础完整，有对此次课程设计心得体会。 中课程设计汇报内容基础完整，思绪较清楚，书写基础清楚，源程序结构尚可，有注释说明但不完整。 及格课程设计汇报内容基础完整，思绪较差，书写尚清楚。 不及格课程设计汇报内容不完整，书写没有条理。3回复老师提问： 优能回复老师提出全部问题，并完全正确，思绪清楚 良基础能回复老师提出全部问题，有些小错误 中基础能回复老师提出问题，少数问题回复错误或不清楚 及格能回复老师提出问题，但较多问题回复错误或不能回复 不及格基础不能回复老师提出问题数据结构和算法课程设计目 录一、 题目二、 需求分析三、 概要设计四、 程序说明五、 具体设计六、 试验心得和体会赫夫曼编译码器一、题目问题描述利用赫夫曼编码进行通信能够大大提升信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端经过一个编码系统对待传输数据预先编码，在接收端将传来数据进行译码（复原）。对于双工信道（即能够双向传输信息信道），每端全部需要一个完整编/译码系统。试为这么信息收发站编写一个赫夫曼码编/译码系统。基础要求一个完整系统应含有以下功效：(1) I：初始化（Initialization）。从终端读入字符集大小n，和n个字符和n个权值，建立赫夫曼树，并将它存于文件hfmTree中。(2) E：编码（Encoding）。利用已建好赫夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中正文进行编码，然后将结果存入文件CodeFile中。(3) D：译码（Decoding）。利用已建好赫夫曼树将文件CodeFile中代码进行译码，结果存入文件Textfile中。（以下为选做：）(4) P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式编码文件写入文件CodePrin中。(5) T：印赫夫曼树（Tree printing）。将已在内存中赫夫曼树以直观方法（比如树）显示在终端上，同时将此字符形式赫夫曼树写入文件TreePrint 中。测试要求(1) 已知某系统在通信联络中只可能出现八种字符，其频率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，试设计赫夫曼编码。(2) 用下表给出字符集和频度实际统计数据建立赫夫曼树，并实现以下报文编码和译码：“THIS PROGRAME IS MY FAVORITE”。字符ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度5763151485180238181161二、需求分析（1）初始化哈夫曼数（2）输入字符保留至tobetran.txt中（3）对字符编码（4）编码结果以文本方法存放在文件Codefile中。（5）在对codefile中编码进行译码（6）打印编码和哈夫曼树用户界面能够设计为“菜单”方法：显示上述功效符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功效符。此功效实施完成后再显示此菜单，直至某次用户选择了“Q”为止。 在程序一次实施过程中，第一次实施I，D或C命令以后，赫夫曼树已经在内存了，无须再读入。每次实施中不一定实施I命令，因为文件hfmTree可能早已建好。三、概要设计函数间关系图3.1所表示：主函数显示表头初始化树输入字符编码译码打印编码打印赫夫曼树选最小两个权值Select()图3.1 函数间关系数据结构和算法设计赫夫曼编译码器关键功效是先建立赫夫曼树，然后利用建好赫夫曼树生成赫夫曼编码后进行译码 。在数据通信中，常常需要将传送文字转换成由二进制字符0、1组成二进制串，称之为编码。结构一棵赫夫曼树，要求赫夫曼树中左分之代表0，右分支代表1，则从根节点到每个叶子节点所经过路径分支组成0和1序列便为该节点对应字符编码，称之为赫夫曼编码。最简单二进制编码方法是等长编码。若采取不等长编码，让出现频率高字符含有较短编码，让出现频率低字符含有较长编码，这么可能缩短传送电文总长度。赫夫曼树课用于结构使电文编码总长最短编码方案。其关键步骤图图3.2所表示。开始结点数是否大于1将data和权值赋给ht输出根结点和权值调用SELECT函数计算根结点函数父结点为两子结点之和输出两子结点和已结构结点是否为根结点？左子是否为空？此时编码为0I2*N?I+编码为1结束否否否右子是否为空是是否否是是是四、程序说明1赫夫曼树抽象数据类型定义ADT HuffmanCoding数据对象T：含有相同特征数据元素集合数据关系R：满足最优二叉树关系基础操作P：Init（&t）操作结果：结构一个空赫夫曼树t。encode()操作结果：利用赫夫曼树进行编码Decode（）操作结果：利用赫夫曼树进行译码2. 主函数Void mian（）打印表头；While(选择项不为q)输入选择项；Switch(选择项)Case i： 初始化；break;Case w： 输入要编码字符； break；Case e： 编码字符； break；Case d； 译码操作；break；Case p； 打印代码；break；Case t； 打印赫夫曼树； break；Default：输入错误，重新选择；五、具体设计源程序：#include #include #include const int UINT_MAX=1000;typedef struct int weight; /权值 int parent,lchild,rchild; /父节点，左孩子结点，右孩子结点HTNode,* HuffmanTree;typedef char *HuffmanCode;/定义全局变量HuffmanTree HT; /代表赫夫曼树HuffmanCode HC; /代表赫夫曼编码int *w,i,j,n;char *z;int flag=0;int numb=0;int min(HuffmanTree t,int i)/选出叶子结点 int j,flag; int k=UINT_MAX; /取k为足够大值 for(j=1;j=i;j+) if(tj.weights2) / s1为最小两个值中序号小那个 j=s1; s1=s2; s2=j; void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)/w存放n个字符权值（均0），结构哈夫曼树HT并求出n个字符哈夫曼编码HC int m,i,s1,s2,start; int c,f; HuffmanTree p; char *cd; if(n=1) return; m=2*n-1; /结点数 HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); / 0号单元未用 for(p=HT+1,i=1;iweight=*w; p-parent=0; p-lchild=0; p-rchild=0; for(;iparent=0; for(i=n+1;i=m;+i) / 建赫夫曼树 select(HT,i-1,s1,s2); HTs1.parent=HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; HC=(HuffmanCode)malloc(n+1)*sizeof(char*); 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(HTf.lchild=c) cd-start=0; else cd-start=1; HCi=(char*)malloc(n-start)*sizeof(char); strcpy(HCi,&cdstart); /复制cd到HC free(cd);void InitHuffman() /初始化赫夫曼链表 flag=1; int num; int num2; cout赫夫曼链表初始化endlnum; n=num; w=(int*)malloc(n*sizeof(int);/分配权值空间 z=(char*)malloc(n*sizeof(char);/分配字符空间 coutn请依次输入n个字符endl; char temp2;for(i=0;in;i+)/输入字符 cout字符i+1:endl; gets(temp); *(z+i)=*temp; coutn请依次输入n个字符权endl;for(i=0;i=n-1;i+) /输入权 coutendli+1num2; *(w+i)=num2;/输入部分结束 编码 HuffmanCoding(HT,HC,w,n);cout字符对应编码为:endl; for(i=1;i=n;i+) cout字符*(z+i-1)编码为：; puts(HCi); /输出编码 /将赫夫曼编码写入文件cout赫夫曼编码写入文件htmTree.txt中endl; FILE *htmTree; char r= ,0; if(htmTree=fopen(htmTree.txt,w)=NULL)cout文件打开失败endl;return; fputs(z,htmTree); /文件中输入z字符串 coutendl;/不加这个代码文件输入有误 fputc(n,htmTree);/换行 for(i=0;in;i+) /文件中输入权 fprintf(htmTree,%d ,*(w+i); fputs(r,htmTree); fprintf(htmTree,n);/换行 for(i=1;i=n;i+) /文件中输入编码 fputs(HCi,htmTree); fputs(r,htmTree); fclose(htmTree);/init/获取字符并写入文件创建待编码文件 void inputcode() FILE *virttran,*tobetran; char str; if(tobetran=fopen(tobetran.txt,w)=NULL) cout不能打开文件endl; return; cout请输入你想要编码字符并以#号结束endl; str=getchar();/ 用来初始化 str=getchar();/此语句用来接收输入第一个字符 while(str!=#) fputc(str,tobetran); str=getchar(); cout写入成功！endl; fclose(tobetran);void encode() /完成编码功效 cout下面对目录下文件tobetran.txt中字符进行编码endl; FILE *tobetran,*codefile; if(tobetran=fopen(tobetran.txt,rb)=NULL) cout不能打开文件endl; return; if(codefile=fopen(codefile.txt,wb)=NULL) cout不能打开文件endl; return; char *tran; i=99; tran=(char*)malloc(100*sizeof(char); /为tran分配100个字节 while(i=99) if(fgets(tran,100,tobetran)=NULL) cout不能打开文件endl; break; for(i=0;*(tran+i)!=0;i+) /对tobetran文件中字符经过初始化哈夫曼编码进行编码 for(j=0;jn) cout字符错误，无法编码!endl; break; cout完成！endl编码已写入codefile.txt中endlendl; fclose(tobetran); fclose(codefile); free(tran);void decode() /完成译码功效 cout下面对根目录下文件codefile.txt中字符进行译码endl; FILE *codef,*txtfile; if(txtfile=fopen(Textfile.txt,w)=NULL) cout不能打开文件endl; return; if (codef=fopen(codefile.txt,r)=NULL) cout不能打开文件endl; return; char *tbdc,*outext,i2; int io=0,i,m; unsigned long length=10000; tbdc=(char*)malloc(length*sizeof(char); /分配空间 fgets(tbdc,length,codef); /codefile中提取编码 outext=(char*)malloc(length*sizeof(char); /分配空间 m=2*n-1; for(i=0;*(tbdc+i)!=0;i+) /进入循环依次译码 i2=*(tbdc+i); if(HTm.lchild=0) *(outext+io)=*(z+m-1); io+; m=2*n-1; i-; else if(i2=0) m=HTm.lchild; else if(i2=1) m=HTm.rchild; *(outext+io)=*(z+m-1); *(outext+io+1)=0; fputs(outext,txtfile);/译码完成将译码放入文件 cout完成！endl结果已写入txtfile.txt中endlendl; free(tbdc); free(outext); fclose(txtfile); fclose(codef);void printcode() /打印代码 cout下面打印根目录下文件CodePrin.txt中编码字符endl-n; FILE * CodePrin,* codefile; if(CodePrin=fopen(CodePrin.txt,w)=NULL) cout不能打开文件endl; return; if(codefile=fopen(codefile.txt,r)=NULL) cout不能打开文件endl; return; char *work3; work3=(char*)malloc(51*sizeof(char); do if(fgets(work3,51,codefile)=NULL) cout不能读取文件endl; break; fputs(work3,CodePrin);/放入 puts(work3); while(strlen(work3)=50); free(work3);cout打印完成！endlendl; fclose(CodePrin); fclose(codefile);/打印赫夫曼树函数void coprint(HuffmanTree start,HuffmanTree HT)char t= ; if(start!=HT) FILE * TreePrint; if(TreePrint=fopen(TreePrint.txt,a)=NULL) cout创建文件失败rchild,HT); if(start-lchild&start-rchild) t=; coutsetw(5*numb)weighttweight); coprint(HT+start-lchild,HT); numb-; fclose(TreePrint); void printree(HuffmanTree HT,int w) /打印赫夫曼树 HuffmanTree p; p=HT+w; cout打印赫夫曼树endl; / 输出打印赫夫曼树语句 coprint(p,HT); cout打印完成！endl; /输出打印工作结束void printhead() coutntt; cout 欢迎使用赫夫曼编码解码系统 ntt;cout=ntt;cout i.初始化赫夫曼链表 ntt;cout w.输入字符保留在对应文件中 ntt;cout e.编 码 ntt;cout d.译 码 ntt;cout p.打印编码 ntt;cout t.打印赫夫曼树 ntt; cout q.退 出 ntt; coutendl; if(flag=0)cout链表还未初始化,输入i进行初始化nttendl;coutchoice; switch(choice) case i: