《数据结构与算法》课程设计 |
您所在的位置：网站首页 › 新海诚角色 › 《数据结构与算法》课程设计 |
《数据结构与算法》课程设计
|
一、题目： 赫夫曼编码/译码器 利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。 二、实验目的： 本课程设计要求同学独立完成一个较为完整的应用需求分析。并在设计和编写具有一定规模程序的过程中，深化对《数据结构与算法》课程中基本概念、理论和方法的理解；训练综合运用所学知识处理实际问题的能力，强化面向对象的程序设计理念；使自己的程序设计与调试水平有一个明显的提高。 三、需求分析： 该程序包括以下功能： (1) 1：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树，并将它存于文件hfmTree中。 (2) 2：编码（Encoding）。利用已建好的赫夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 (3) 3：译码（Decoding）。利用已建好的赫夫曼树将文件CodeFile中的代码进行译码，结果存入文件Textfile中。 (4) 4：打印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。 (5) 0：退出。 四、 概要设计： 基于哈夫曼树的存储结构 typedef struct HaffmanTree { double weight; //权值 char data; int parent, lChild, rChild; //结点的双亲、左孩子、右孩子的下标 }HTNode, * HuffmanTree; //动态分配数组储存哈夫曼树 typedef char** HuffmanCode; //动态分配数组储存哈夫曼编码表有下图所示的大致设计 五、 程序说明： 本程序是一个赫夫曼编码/译码器，首先利用Initialization函数，初始化建立赫夫曼树，利用Coding函数进行赫夫曼编码，Deconding函数进行赫夫曼译码，Print函数进行打印CodeFile.txt文件中的内容。其中Initialization函数中创建哈夫曼树的时候涉及select函数，select函数的用途是寻找父母为0且权值最小的两个结点是s1,s2。Decongding函数主要是在赫夫曼树中寻找赫夫曼码所对应的字符，并写入到Textfile.txt中。 六、 详细设计： 课设.cpp #define _CRT_SECURE_NO_WARNINGS #include #include #include #define MAXSIZE 100 using namespace std; //哈夫曼树的存储结构 typedef struct HaffmanTree { double weight; //权值 char data; int parent, lChild, rChild; //结点的双亲、左孩子、右孩子的下标 }HTNode, * HuffmanTree; //动态分配数组储存哈夫曼树 typedef char** HuffmanCode; //动态分配数组储存哈夫曼编码表 //寻找最小的两个元素 void Select(HuffmanTree& HT, int n, int& s1, int& s2) { int i, flag = 0; for (i = 1; i s1 = i; flag = 1; } else if (HT[i].parent == 0 && flag == 1) { s2 = i; break; } } if (HT[s1].weight > HT[s2].weight) {//使s1 s2 = s1; s1 = i; } else if (HT[i].parent == 0 && HT[i].weight int m; if (n //将双亲、左孩子、右孩子的下标初始化为0 HT[i].parent = 0; HT[i].lChild = 0; HT[i].rChild = 0; } //初始化n个字符及其权值 for (int i = 1; i //通过n-1次的选择、删除、合并来创建哈夫曼树 Select(HT, i - 1, s1, s2); //找出权值最小的两个 HT[s1].parent = i; HT[s2].parent = i; //将双亲设为i HT[i].lChild = s1; HT[i].rChild = s2; //将其作为左右孩子 HT[i].weight = HT[s1].weight + HT[s2].weight; //双亲的权值为左右孩子权值之和 } //初始化保存至文件 ofstream out; out.open("hfmTree.txt", ios::out); int i = 1; for (i = 1; i out start = n - 1; //start开始指向最后，即编码结束符的位置 child = i; parent = HT[i].parent; //parent指向节点child的双亲节点 while (parent != 0) { --start; //回溯一次start向前指一个位置 if (HT[parent].lChild == child) cd[start] = '0'; //child为parent的左孩子，生成0 else cd[start] = '1'; //child为parent的右孩子，生成1 child = parent; parent = HT[parent].parent; //继续向上回溯 } HC[i] = new char[n - start]; //为第i个字符编码分配空间 strcpy(HC[i], &cd[start]); //将求得的编码从临时空间cd复制到HC的行列中 } delete cd; //释放临时空间 cout fout //判断文件是否打开 cout if (ch == HT[i].data) { fout //判断文件是否打开 cout //当前字段解码完毕 fout //判断文件是否打开 cout cout int choice, n; HuffmanTree Tree; HuffmanCode HC; while (1) { menu(); cout choice; switch (choice) { //初始化，并建立哈夫曼树 case 1: cout n; Initialization(Tree, n); break; //编码 case 2: if (Tree != NULL) { Encoding(Tree, HC, n); TextCode(Tree, HC, n); } else cout |
【本文地址】