课程设计说明书(**)
题目哈夫曼编码问题的设计和实现。
课程名称数据结构课程设计。
院（系、部、中心。
专业。班级。
学生姓名。学号。
设计地点。指导教师。
设计起止时间：2008 年6月 2日至 2008 年 6月 6 日。
目录。1 问题描述 2
1.1 题目内容 2
1.2 基本要求 2
1.3 测试数据 2
2 需求分析 2
2.1 程序的基本功能 2
2.2 输入值、输出值以及输入输出形式 2
2.3 各个模块的功能要求 3
3 概要设计 4
3.1 所需的adt，每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义） 4
3.2 主程序流程以及模块调用关系 4
3.3 各个模块的算法设计说明 4
4 详细设计 7
4.1 数据类型 7
4.2 函数调用 8
5 各个算法实现的源程序 8
6 调试分析 11
7 使用说明 12
8 测试结果 12
9 源程序 12
1 问题描述。
哈夫曼编码问题的设计和实现。
输入一个英文字符串，对该字符串中各字符个数进行统计取得各字符的出现次数；以其出现次数作为关键字建立哈夫曼树并进行编码，最后输出各个字符对应的码值。
要求：设计存储结构、基本算法（主要采用程序流程图体现）；完成基本算法的实现**；设计测试输入数据对程序进行测试，分析输出结果数据、算法的时间复杂度分析，如有改进算法则提出算法的改进方法。
测试数据三组：
aaaabbbccd(判断连续的字符串是否可行)
aabbaabcdc(判断间段的字符串是否可行)
aaaa bbbccd(判断含空格的字符串是否可行)
2 需求分析。
该程序大体上有两个功能：
1． 输入任何一个字符串后，该程序能统计不同字符串的个数，并以不同字符串的个数作为权值。
2． 已知不同字母的权值，以该权值作为叶结点，构造一棵带权路径最小的树，对该树从叶结点到根结点路径分支遍历，经过一个分支就得到一位夫曼编码值。（规定哈夫曼树中的左分支为0，右分支为1，则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码）
输入值 ：aaaabbbccd
输出值 ：w =4 c=0
w=3 c=10
w=2 c=111
w=1 c=110
输入值 ：aabbaabcdc
输出值 ：w=4 c=0
w=3 c=10
w=2 c=111
w=1 c=110
输入值 ：aaaa bbbccd
输出值 ：w=4 c=11
w=1 c=010
w=3 c=10
w=2 c=00
w=1 c=011
1． 统计模块。
任意输入一个字符串，不论字母是否相联，字符串中是否含空格都能统计出不同字母的个数。
2． 建立哈夫曼树模块。
以统计的字符串个数作为权值，利用**存储结构，建立带权路径最小的树。
其中对结点的存储需要六个域，分别是 weight 域，flag域， parent域，leftchild 域，rightchild域。weight 域是对权值的存放，flag 域是一个标志域，flag=0时表示该结点尚未加入到哈夫曼树中，flag=1时表示该结点已加入到哈夫曼树中。
3． 哈夫曼编码模块。
从哈夫曼树的叶结点到根结点路径分支逐步遍历，每经过一个分支就得到一位哈夫曼编码。哈夫曼编码也利用**存储结构。
4． 主函数模块。
从屏幕上输入字符串，调用函数，输出每个字母的权值与编码。
3 概要设计。
抽象数据类型集合：在该程序中未用到抽象数据类型，主要用到的数据类型为 ：int ,char 。
在哈夫曼树的建立与哈夫曼树的编码中用到**存储。
输入字符串——〉调用count 函数——〉申请内存空间——〉调用 haffman
—〉调用 haffmancode——〉输出权值与编码。
1． 主函数模块。ny
ynny
主函数中利用gets输入一个字符串，调用count 函数统计不同字母的个数，在调用。
haffman 函数建立哈夫曼树，然后调用haffmancode函数进行编码，如果成功，输出权。
值与编码，否则退出。
2． 统计函数。yn
yyny
统计函数在统计不同字符个数时先利用一个for循环遍历所有的字母，每遍历一个不同字母前令temp=1,然后用一个for循环将其后的字母与之比较，若相等则temp++,且将该字母从字符串中删除，否则从下一个字母遍历。如此循环直到字符串结束。
3． haffman 函数。ny n
ny ny
nyyhaffman函数主要以**结构存储信息，开始对每个域开始赋值，再根据不同的情况对每个域的值进行修改，如此循环下去，直到每个域的值修改完全。
4． hffmancode 函数。ny
nn n yy
数据结构课程设计
数据结构 课程设计。实验报告。学院 信息工程学院。班级 姓名 学号 指导老师 题目2 一元多项式的计算。1 实验目的。1 掌握链表的灵活运用 2 学习链表初始化和建立一个新的链表 3 知道怎样去实现链表删除结点操作与插入结点 4 理解链表的基本操作 包括数据域数据的相加 并能灵活运用。2 实验内容。...
数据结构课程设计
班级 信计 1102 姓名 李娜娜。学号 1108060209 设计日期 2013.07.15 西安科技大学计算机学院 1.实验题目 编制一个演绎扫雷游戏的程序。2.问题描述。做一个n x m的扫雷游戏，每个方格包含两种状态 关闭 closed 和打开 opened 初始化时每个方格都是关闭的，一个...
数据结构课程设计
数据结构 课程设计报告。安徽工业大学计算机学院。2014年6月。目录。一 迷宫问题求解 2 二 大数相乘 8 三 学生成绩查询系统 二叉排序树 10 一 问题描述 利用栈求解迷宫问题。二 设计思路 首先先定义栈，初始化，入栈，出栈，删除栈，判空等，然后再结合具体迷宫算法。三 数据结构定义。typed...