电报压缩解压缩系统课程设计报告.doc

课程设计报告 ( 2012-- 2013年度第2学期) 实验名称： 数据结构与算法 题 目： 电报压缩/解压缩系统 院 系： -------------------------- 班 级： ------------------- 学 号： ---------------- 学生姓名： ------- 指导教师： -------- 设计周数： 1周 成 绩： 日期：2013年7月11日 一、课程设计的目的与要求 目的: 应用数据结构和算法来设计相应的程序，培养学生问题求解模块的框架设计和详细设计、相关程序实现和调试能力，完成创新能力和实践能力的训练。 要求: 用高级程序设计语言C编码，用VC++开发平台调试 二、设计正文 (一) 课程设计题目 电报压缩/解压缩系统 (二）需求分析 报文中含有中英文字符； 原始报文、压缩报文和解压报文都采用文件存储； (三) 概要设计 本程序包含9个函数： ① 主函数main(); ② 菜单函数menu（）; ③ 初始化链表函数initDLink(); ④ 查找及插入新的数据函数search(); ⑤ 数据处理及统计函数settle(); ⑥ 求哈夫曼编码函数huf_code(); ⑦ 创建哈夫曼树函数creatHufTree(); ⑧ 压缩函数compress(); ⑨ 解压函数uncompress(); 各函数间关系如下： main main compress uncompress menu creatHufTree huf_code initDLink search settle (四) 详细设计 (1) 系统功能结构框图 电报压缩/ 电报压缩/解压缩系统 输入要压缩的文档名字，对其压缩 输入压缩后要保存的文档名字，将压缩后的文档保存在这。 输入解压后要保存的文档名，解压后保存。 (2) 数据类型定义 1） typedef struct dataNode { char c[3]; //用来存储每个汉字字符或英文字符 int weight; //用来存储出现的权值 struct dataNode *next; //指向下一个的指针 }DNode,*DLink; //结点类型和指针类型 2）typedef struct hufm { char data[3]; //用来存储汉字字符或者英文字符 int weight; //用来存储字符出现的权值 int parent,lch,rch; //父亲节点及左孩子右孩子 }NodeHufm,*HufTree; //哈夫曼树类型及其指针类型 3）typedef struct HCodeNode { char bits[26]; //用来存储哈夫曼编码 }HCodeNode,*HufCode; //哈夫曼编码类型及其指针类型 (3) 基本操作 1）int menu（）; 功能：清空界面，显示选择操作界面； 参数：无。 2）int initDLink(DLink D); 功能：初始化链表，采用带头结点的； 参数：D:为带头结点的链表的头指针。 3）int search(char e[],DLink D,int n); 功能：查找是否存在传进来的字符串，若果有权值加1如果没有创建并使权值初值为1； 参数：e:为要查找的字符串首地址，D:为链表的头指针; n:链表上节点的个数也就是字符的个数。统计n的大小是为以后算法实现打基础 4）int settle(FILE *ifp,DLink D,int flength,int n); 功能：从文件中读取数据，统计字符种类及其出现的权值并完成文本大小及字符个数的统计； 参数：ifp:读入的文件指针；D:链表的头指针；flength:文件的大小；n:字符的个数。函数调用search函数统计出n,此函数中统计出flength,下面的算法需要n与flength，而在此函数中可以顺便得到它们。 5）void huf_code(HufCode hcd,HufTree ht,int n); 功能：根据传进来的哈夫曼树及字符个数求出对应的哈夫曼编码； 参数：hcd:动态申请空间存储哈夫曼编码的数组名，每一个元素为字符串数