# 数据结构与算法

**Repository Path**: new_boy_oss/data-structure-and-algorithm

## Basic Information

- **Project Name**: 数据结构与算法
- **Description**: 数据结构与算法课程设计
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-05-30
- **Last Updated**: 2022-08-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: Cpp, 算法

## README

# 数据结构与算法

## **总体要求**

1. 每道题目的程序代码有合理注释，功能正确、有一定实用性。

2. 课程设计报告正文字数**不少于8000字**，概念清楚、叙述正确、内容完整、书写规范。

3. 独立完成课程设计，不得抄袭他人。

4. 尽可能大量使用各种C或者C++语言程序设计技术，尤其在以下几个方面： 指针及其运算、结构、指针数组、数组指针、字符数组与字符串等，注意数据输入与数据格式检查、数据类型转换、错误处理等。**要求完成2种以上经典算法。**

5. 不允许使用现成的数据库如Access、SQL Server等。

6. 认真自觉以个人为单位完成任务，代码和课程设计报均严禁雷同，否则成绩为不及格。验收时查看代码，并提出跟代码有关的问题，并把问题回答情况计入总评成绩。

## 具体内容

### 哈夫曼编码/译码器

#### 【问题描述】

设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。

#### 【基本要求】

1)将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中) 

2)分别采用动态和静态存储结构

3)初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；

4)编码：利用建好的哈夫曼树生成哈夫曼编码；

5)输出编码；

6)设字符集及频度如下表：

 字符 空格 A B C D E F G H I J K L M

 频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20

 字符 N O P Q R S T U V W X Y Z 

 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 

####  【进一步完成内容】

1)译码功能；

2)显示哈夫曼树；

3)界面设计的优化。

## 需求分析

根据题目要求，哈夫曼编码/译码器问题应具有以下功能：

（1）用户输入：获取并保存用户从键盘上输入的字符集和相应字符出现的频率。

（2）文件存取：将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中) 中

（3）哈夫曼树构造：根据用户输入获取模块保存的字符数据，构造哈夫曼树。

（4）字符-哈夫曼码对照表：根据哈夫曼树构造模块构造的哈夫曼树，建立字符-哈夫曼编码对照表。

（5）编码：根据字符-哈夫曼编码对照表构造模块构造的字符-哈夫曼编码对照表，对用户提供的明文进行编码。

（6）译码：根据哈夫曼树构造模块构造的哈夫曼树，对用户提供的字符进行译码（需要涉及到文件操作）。

# 贪心法（哈夫曼编码算法）

每次将集合中两个权值最小的二叉树合并成一棵新二叉树，n-1次合并后，成为最终的一棵哈夫曼树。这既是贪心法的思想：从某一个最初状态出发，根据当前的局部最优策略，以满足约束方程为条件，以使目标函数最快（或最慢）为原则，在候选集合中进行一系列的选择，以便尽快构成问题的可行解。

# 说明

在哈夫曼树的构造过程中，当合并两棵二叉树时，将两个权值最小和次小的根结点作为左或右孩子均可以，这也构造出的哈夫曼树可能不唯一，因此产生的哈夫曼编码也不唯一，但都是正确的哈夫曼编码，但它们的WPL一定是唯一的。