数据结构设计说明和代码Word文件下载.docx
《数据结构设计说明和代码Word文件下载.docx》由会员分享，可在线阅读，更多相关《数据结构设计说明和代码Word文件下载.docx（26页珍藏版）》请在冰点文库上搜索。
13
22
32
103
21
15
47
57
1
5
20
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
63
48
51
80
23
8
18
16
2.采用算法如下：
采用Huffman编码思想实现对字符串的编码，以及对编码的解码。
⑴对上述表格中的27个字符分别编码（为便于输入，‘空格’在程序实现过程中用‘*’代替），其实现算法是建立赫夫曼树HC，对每一个字符进行编码，并将由赫夫曼树所得到的编码串存储在HC中。
⑵建立编码、译码函数，对输入的文件或密码进行转换，再通过main（）函数的调用,将其进行输出。
二、程序主要方法说明【说明主要方法的功能和实现细路以及技巧，只要方法的声明，不要贴实现代码】
㈠实现思路：
建立如图所示的赫夫曼树（赫弗曼树的形式不唯一），并编码
1000
603
397
211
355
248
182
173
128
120
108
78
102
95
53
43
35
49
17
31
28
9
4
2
HT初态：
HT终态：
HT
weight
parent
lchild
rchild
45
3
33
38
39
6
7
37
41
10
11
12
14
36
44
34
19
24
25
29
26
27
30
40
42
46
50
52
1001
110010
10111
11000011
1100001000
0111
1111011
111100
010
10110
111110
1111010
11010
1111110
1010
00
HC
1100001001
1100001010
0110
1110
110011
1100000
110001
1111111
1100001011
11011
㈡具体算法如下所示：
1.赫夫曼树和赫夫曼编码的存储结构表示
typedefstruct{
intweight,parent,lchild,rchild;
}HTNode,*HuffmanTree;
//动态分配数组存储赫夫曼树
typedefchar**HuffmanCode;
//动态分配数组存储赫夫曼编码表
2.⑴定义全局变量：
用于存储需要编码的字符集数组node[29]
用于存储需要编码的文件数组str[MAX1]
用于存储密码文件的数组Nfile[MAX2]
⑵建立相应的实现函数：
用于建立赫夫曼树函数HuffmanCoding（&
HT,&
HC,*w,n）
实现建立赫夫曼树的选择函数Select（HT,k,&
m1,&
m2）
实现对文件编码的编码函数Decode（HC）
实现对密码译码的译码函数Coding（HT,HC）
对以上函数进行调用的主函数main（）
⑶出错判断响应
A．当输入文本错误时，提出错误提醒printf（"
第%d个字符输入错误!
请重新输入:
"
j+1）;
B．当选择执行的选项出错时，提出错误提醒printf（"
输入错误,请重新输入"
）;
三、程序测试说明【为了验证程序满足设计要求，需要给出适当的测试数据。
如输入什么数据，程序能够输出什么数据。
要求至少给出3组以上测试数据，并说明每组测试数据能够测试作品的什么功能】
程序中输入及输出数据的运行步骤如下所示：
步骤一：
编译并运行程序，按提示运行（例如，“按回车键，继续…”）已验证所得赫弗曼树及27个字符的编码是否与分析的一致结果如下：
步骤二：
输入选择0-2以外的数，如3，以测试出错相应功能：
当选择执行的选项出错时，程序给出错误提醒。
得出如下结果：
步骤三：
输入文本文件“ROME*WAS*NOT*BUILT*IN*A*DAY”,并在程序执行前将存储密码文件的数组初始化如下：
Nfile[MAX2]={1,1,0,1,1,1,0,0,1,1,1,0,0,1,0,0,1,0,0,0,1,1,0,0,0,1,
1,0,1,0,0,1,1,0,0,0,1,0,0,0,1,0,0,1,1,1,1,0,0,0,1,1,1,1,0,1,0,
1,1,0,0,1,1,0,1,1,1,1,0,1,1,1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,0,0,
1,0,1,0,0,0,1,0,1,1,0,1,0,1,0,1,1,1,1,1,1,1}
测试译码的文本文件和原文件进行比较，恢复文件和原文件是否完全一致
步骤四：
输入文本文件“TiME*is*MonEY”,测试错误判断响应当输入文本错误时，提出错误提醒printf（"
步骤五：
输入正式文本文件“THANK*YOU*FOU*YOUR*LETTER*CONVEYING*ON*MY*APPOINTMENT*I*WISH*YOU*SUCCESS*AND*FULFILLMENT*THE*YEARS*AHEAD”得出相应密码文件：
步骤六：
选择“0”，返回，结束程序。
程序代码：
#include<
stdio.h>
malloc.h>
string.h>
#defineMAX13000
#defineMAX2110
#defineOK1
#defineERROR0
typedefintStatus;
charnode[29]="
*ABCDEFGHIGKLMNOPQRSTUVWXYZ"
;
//定义字符集
intn=27;
//需要编码的字符总数
intm=2*n-1;
//赫夫曼编码表HT的长度
intcount=0;
//记录输入的密码数字的个数
charstr[MAX1];
//定义存储需要编码的文件数组
intNfile[MAX2]={1,1,0,1,1,1,0,0,1,1,1,0,0,1,0,0,1,0,0,0,1,1,0,0,0,1,
1,0,1,0,0,1,1,0,0,0,1,0,0,0,1,0,0,1,1,1,1,0,0,0,1,1,1,1,0,1,0,
1,1,0,0,1,1,0,1,1,1,1,0,1,1,1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,0,0,
1,0,1,0,0,0,1,0,1,1,0,1,0,1,0,1,1,1,1,1,1,1};
//定义密码文件数组
voidSelect（HuffmanTreeHT,intk,int&
m1,int&
{
inti,min1,min2;
min1=min2=10000;
//首先给它们赋一个最大的值,这个值大于所有可能的权值
m1=1,m2=1;
for（i=1;
i<
=k;
i++）
if（HT[i].weight<
min1&
&
HT[i].parent==0）
{min1=HT[i].weight;
m2=m1;
m1=i;
}
elseif（HT[i].weight<
min2&
HT[i].parent==0）
{min2=HT[i].weight;
m2=i;
voidHuffmanCoding（HuffmanTree&
HT,HuffmanCode&
HC,int*w,intn）
{//w存放n个字符的权值（均>
0），构造赫夫曼树HT，
//并求出n个字符的赫夫曼编码HC
inti,j,s1,s2,start;
char*cd;
intc,f;
if（n<
=1）return;
HT=（HuffmanTree）malloc（（m+1）*sizeof（HTNode））;
//0号单元未用
for（i=1;
i<
=n;
i++）{//初始化
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for（i=n+1;
=m;
HT[i].weight=0;
printf（"
\n赫夫曼树的构造，初态如下所示：
\n"
HT初态:
\n结点weightparentlchildrchild"
i++）
\n%6d%10d%10d%10d%10d"
i,HT[i].weight,
HT[i].parent,HT[i].lchild,HT[i].rchild）;
按回车键，继续..."
getchar（）;
i++）{//建赫夫曼树
//在HT[1..i-1]中选择parent为0且weight最小的两个结点，
//其序号分别为s1和s2。
Select（HT,i-1,s1,s2）;
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
\n构造的赫夫曼树如下：
结点weightparentlchildrchild"
for（j=1;
j<
j++）
j,HT[j].weight,
HT[j].parent,HT[j].lchild,HT[j].rchild）;
//---从叶子到根逆向求每个字符的赫夫曼编码---
HC=（HuffmanCode）malloc（（n+1）*sizeof（char*））;
cd=（char*）malloc（n*sizeof（char））;
//分配求编码的工作空间
cd[n-1]='
\0'
//编码结束符。
++i）{//逐个字符求赫夫曼编码
start=n-1;
//编码结束符位置
for（c=i,f=HT[i].parent;
f!
=0;
c=f,f=HT[f].parent）
//从叶子到根逆向求编码
if（HT[f].lchild==c）cd[--start]='
0'
elsecd[--start]='
1'
HC[i]=（char*）malloc（（n-start）*sizeof（char））;
//为第i个字符编码分配空间
strcpy（HC[i],&
cd[start]）;
//从cd复制编码（串）到HC
free（cd）;
//释放工作空间
//outputcoding
字符%c:
%s\n"
node[i-1],HC[i]）;
}//HuffmanCoding
intDecode（HuffmanCodeHC）{//编码
intj,L;
请输入文本:
scanf（"
%s"
str）;
getchar（）;
L=strlen（str）;
//求字符串的长度
文本字符个数为:
%d"
L）;
for（j=0;
j<
L;
j++）
if（!
（（str[j]>
='
A'
str[j]<
Z'
）||（str[j]=='
*'
）））
{
printf（"
str[j]=getchar（）;
}
printf（"
文本的编码如下:
j=0;
while（str[j]!
）
{
for（inti=0;
27;
if（str[j]==node[i]）
HC[i+1]）;
j++;
returnOK;
voidCoding（HuffmanTreeHT,HuffmanCodeHC）{//译码
intj=0;
intt;
while（j<
count）
t=m;
while（HT[t].lchild!
=0||HT[t].rchild!
=0）
if（Nfile[j]==0）
t=HT[t].lchild;
else
t=HT[t].rchild;
j++;
printf（"
%c"
node[t-1]）;
}
voidmain（）
intk=1;
intn=27;
HuffmanTreeHT;
HuffmanCodeHC;
intw[]={186,64,13,22,32,103,21,15,47,57,1,5,32,20,
57,63,15,1,48,51,80,23,8,18,1,16,1};
//各个需要编码字符的频度，即赫弗曼树结点的权值
HuffmanCoding（HT,HC,w,n）;
while（k）
欢迎进入编码、译码系统\n"
****************************\n"
1.编码\n"
2.译码\n"
0.返回\n"
请选择（0-2）:
scanf（"
&
n）;
getchar（）;
switch（n）
case1:
Decode（HC）;
break;
case2:
{
printf（"
密码文件如下:
for（inti=0;
MAX2;
i++）//输出密码文件数组中的元素
{
printf（"
Nfile[i]）;
count++;
}
原文本如下:
Coding（HT,HC）;
}break;
case0:
m=0;
default:
升级会员 