文档介绍：课程设计报告
( 2012-- 2013年度第2学期)
实验名称: 数据结构与算法
题目: 电报压缩/解压缩系统
院系: --------------------------
班级: -------------------
学号: ----------------
学生姓名: -------
指导教师: --------
设计周数: 1周
成绩:
日期:2013年7月11日
一、课程设计的目的与要求
目的: 应用数据结构和算法来设计相应的程序,培养学生问题求解模块的框架设计和详细设计、相关程序实现和调试能力,完成创新能力和实践能力的训练。
要求: 用高级程序设计语言C编码,用VC++开发平台调试
二、设计正文
(一) 课程设计题目
电报压缩/解压缩系统
(二)需求分析
报文中含有中英文字符;
原始报文、压缩报文和解压报文都采用文件存储;
(三) 概要设计
本程序包含9个函数:
①主函数main();
②菜单函数menu();
③初始化链表函数initDLink();
④查找及插入新的数据函数search();
⑤数据处理及统计函数settle();
⑥求哈夫曼编码函数huf_code();
⑦创建哈夫曼树函数creatHufTree();
⑧ press();
⑨ press();
各函数间关系如下:
main
compress
press
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:动态申请空间存储哈夫曼编码的数组名,每一个元素为字符串数据类型;ht:动态申请空间存储哈夫曼树的数组名,每个元素为一个结构体数据类型,元素包括数据,权值,父亲左孩子及右孩子;n:字符个数。根据是左孩子为0右孩子为1的规定得到哈夫曼编码。
6)void creatHufTree(HufTree &ht,FILE *ifp,int &n,int &flength);
功能:通过从文件中读取信息创建哈夫曼树,并给调用它的函数统计出n与flength;
参