哈夫曼树的应用及单链表的基本操作.doc

课程设计题目：哈夫曼树的应用及单链表的基本操作 一、课程设计目的 1、熟悉C语言程序的编辑、编译链接和运行的过程，至少能够用一种编译器较熟练地编辑、编译及调试程序。 2、综合应用所学的计算机基础知识和所掌握的程序设计语言。 3、学习并掌握程序设计语言中指针、链表的定义操作，构造哈夫曼树的相关操作。 4、自行设计并实现一个较为完整的对文本文件进行编码、解码的设计与开发。 5、通过系统分析、系统设计、编程实现，写实验报告等环节， 初步掌握软件系统的设计方法和步骤。 6、锻炼大家灵活运用程序语言进行软件开发的初步能力，提高分析问题和解决问能力。 7、综合应用程序设计语言的知识，实现一个完整的系统，提高编程能力，体会软件程序的开发过程。 8、培养学生独立完成程序课程设计的能力，提高程序设计水平。 二、课程设计内容 1、使用哈夫曼树和哈夫曼编码的有关知识设计一个哈夫曼编/译码器（附一单链表基本操作系统） （1）读取文本文件，并统计文件中字母个数。 （2）建立huffman树。 （3）对文件进行huffman编码：文本文件(统计字母个数(建立哈夫曼树(建立哈夫曼编码（利用已经建立好的哈夫曼树）( 读取文件，对文件进行哈夫曼编码，并将每个字母对应的哈夫曼编码写入到一个新文件。 （4）对文件进行huffman解码：读取存放哈夫曼编码的文件(解码(将解码后的字母存入新文件中。 （5）结果：比较源文件和解码后的文件是否一致。 2、采用线性表的链式存储结构,做一单链表基本操作系统，完成对信息的插入，删除、逆置的操作。 3、执行编译操作，并根据提示调试此程序，排除所有的错误和警告，直到编译成功为止。 4、执行运行操作，逐一对每个模块进行调试，直到全部程序运行成功为止。 5、请老师检查，向老师演练此程序，并能回答老师提出的相关问题。 三、需求分析 1、问题背景：哈夫曼树是一类带权路径长度最短的树，将其应用在信息编码中，权值可看作是某个符号出现的频率，出现频率大的字符其编码长度小，从而可缩短整个信息通信过程中的二进制编码长度，达到节省通信资源的目的。 对所开发系统功能的描述：利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。本次设计就是一个哈夫曼的编/译码器。可以将给定的文件编码成二进制文件，并能译码成原文，又能将二进制文件进行压缩，解压缩，并能成功的返回原文。 单链表基本操作系统：单链表基本操作系统系统是运行于windows系统下的应用软件，主要用于对信息进行增、删、等操作，并且还可对使用该系统的用户进行登录名和密码的管理。系统给用户提供了一个简单的人机界面，使用户可以根据提示输入操作项，调用系统提供的管理功能。 四、概要设计 1．系统结构图（功能模块图）和数据变量说明 （1）功能模块图 A、哈夫曼 B、单链表基本操作 （2）数据变量说明 A、哈夫曼 struct system { char user[5];/*验证身份的用户名*/ char mima[5];/*验证身份的密码*/ }SYS; typedef struct node { char data;/*存放各个字符*/ char code[20];/*存储哈夫曼编码*/ int weight; /* 用来存放各个结点的权值*/ int parent,lchild,rchild; /*指向双亲、孩子结点的指针*/ int length;/*存放编码长度*/ }HFNODE; typedef struct zipin { char data;/*存放各个字符*/ int count;/*存放各字符的出现频率*/ }character; B、单链表基本操作 struct system { char user[5];/*验证身份的用户名*/ char mima[5];/*验证身份的密码*/ }SYS; typedef struct node { int data; /*节点数据域*/ struct node *next;/*节点指针域*/ } NODE; 功能模块说明 A、哈夫曼 1）字符统计函数：通过读取文件，统计文件中的字符总个数，动态建立存储所有字符的数组。 2）读取函数：读取源文件，将源文件中的字符存入动态建立的数组中。