数据结构设计大赛作品

} // HuffmanCoding
int Decode(HuffmanCode HC){//编码
int j,LL;
char str[4];
printf("请输入文本:\n");
scanf("%s",str);getchar();
LL=strlen(str);//求字符串的长度
printf("%d",LL);
printf("HT初态:\n结点weight parent lchild rchild");
for (i=1; i<=m; i++)
printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,
HT[i].parent,HT[i].lchild, HT[i].rchild);
80
23
8
18
1
16
1
设字符集及频度如下表：
二、设计思路【说明为了解决实际的问题，采用什么样的数据和算法】
采用什么样的数据和算法如下：
采用哈夫曼编码思想实现对字符串的编码，以及对编码的解码。
三、程序主要方法说明【说明主要方法的功能和实现细路以及技巧，只要方法的声明，不要贴实现代码】
#include <stdio.h>
{
for(int i=1;i<=5;i++)
if(file[i]=='0')
Coding(p->lchild);
else if(file[i]=='1')
Coding(p->rchild);
printf("%c",p->data);
}
return OK;
}
void main()
{
int m=1;
BiTree T;
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';
else cd[--start] = '1';
HC[i] = (char *)malloc((n-start)*sizeof(char));
printf("欢迎进入编码、译码系统\n");
printf("****************************\n");
printf(" 1.编码\n");
printf(" 2.译码\n");
printf(" 0.返回\n");
printf("****************************\n");
#include <malloc.h>
#include <string.h>
#define OK 1
#define ERROR 0
typedef int Status;
typedef struct{
int weight,parent,lchild,rchild;
}HTNode,*HuffmanTree;
printf("按回车键，继续...");
getchar();
for (i=n+1; i<=m; 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=0;
HT[i].rchild=0;
}
for (i=n+1; i<=m; i++) { //初始化
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
printf("\n哈夫曼树的构造过程如下所示：\n");
设计题目
问题描述
采用哈夫曼编码思想实现对字符串的编码，以及对编码的解码。字符串的长度不小于5000字节。
读取要编码的文本文件，将文件的内容进行编码，生成新的文件。对编码文件进行解码，获得文本文件。将译码的文本文件和原文件进行比较，恢复文件和原文件必须完全一致。
设字符集及频度如下表：
字符
空格
A
B
C
D
E
int c, f;
if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号单元未用
for (i=1; i<=n; i++) { //初始化
HT[i].weight=w[i-1];
HT[i].parent=0;
对编码文件进行解码，获得文本文件。
2.要求：
将译码的文本文件和原文件进行比较，恢复文件和原文件必须完全一致。
字符串的长度不小于5000字节。
3.条件：
字符
空格
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
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree CreateBiTree(BiTree &T) { //算法6.4
//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，
printf("请选择（1或2）:");
scanf("%d",&n);
getchar();
switch(n)
{
case 1: Decode(HC);break;
case 2:{
printf("构造二叉树:\n");
CreateBiTree(T);
Coding(T);
int file[5];
printf("请输入密码:\n");
//构造二叉链表表示的二叉树T。
char ch;
scanf("%c",&ch);
if (ch=='#') T = NULL;
else {
if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;
T->data = ch; //生成根结点
CreateBiTree(T->lchild); //构造左子树
数据结构设计大赛作品说明书
作品名称：译码器
院系：计算机科学与信息工程学院
学生姓名：李瑞琳
学号：200903060016
专业班级：09级网络工程（二）班
指导教师：闫怀平
2011年05月20日
一、作品的背景【说明设计该作品的目的，或者说作品能够解决什么实际问题】
1.解决的实际问题：
读取要编码的文本文件，将文件的内容进行编码，生成新的文件。
//为第i个字符编码分配空间
strcpy(HC[i], &cd[start]); //从cd复制编码(串)到HC
}
free(cd); //释放工作空间
//outputcoding
for(i=1;i<=n;i++)
printf("字符%c:%s\n",node[i-1],HC[i]);
printf("\n");
for (j=1; j<=i; j++)
printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,
HT[j].parent,HT[j].lchild, HT[j].rchild);
printf("按回车键，继续...");
getchar();
}
//---从叶子到根逆向求每个字符的哈夫曼编码---
for(j=0;j<LL;j++)
if(!((str[j]>='A'&&str[j]<='Z')||(str[j]==' ')))
{
printf("第%d个字符输入错误!请重新输入:",j+1);
str[j]=getchar();getchar();
printf("\n");
}
printf("文本的编码如下:\n");
for(int i=0;i<5;i++)
scanf("%d",&file[i]);
}break;
case 0:m=0;break;
default:printf("输入错误,请重新输入");break;
}
}
}
四、程序测试说明【为了验证程序满足设计要求，需要给出适当的测试数据。如输入什么数据，程序能够输出什么数据。要求至少给出3组以上测试数据，并说明每组测试数据能够测试作品的什么功能】
j=0;
while(str[j]!='\0')
{
printf("****");
for(int i=0;i<3;i++)
{
//printf("%c\n",str[j]);
//printf("%c\n",node[i]);
///while(HC[i]!=NULL)
//{
if(str[j]==node[i])
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) {
// w存放n个字符的权值(均>0)，构造哈夫曼树HT，
//并求出n个字符的哈夫曼编码HC
int i, j, m, s1, s2, start;
char *cd;
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、对编码文件进行译码，获得恢复文件
HT[i].lchild = s1; HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
printf("\nselect: s1=%d s2=%d\n", s1, s2);
printf("结点weight parent lchild rchild");
printf("%s",HC[i+1]);
//}
}
j++;
}
printf("\n");
return OK;
}ቤተ መጻሕፍቲ ባይዱ
int file[5];
BiTree p;
int Coding(BiTree T){//译码
p=T;
if(p==NULL)
return ERROR;
else
while(p->lchild!=NULL||p->rchild!=NULL)
HuffmanTree HT;
HuffmanCode HC;
//printf("%d",HC);
int w[]={1,2,3};
int n=3;
HuffmanCoding(HT,HC,w,n);
//for(int i=0;i<3;i++)
printf("%s",HC[1]);
while(m)
{
printf("\n");
typedef char **HuffmanCode;
/*typedef struct Node{//用来存储每个字符编码的表结点
int hm[20];
} Node;
typedef struct VNode{//存储哈弗曼编码的头结点
char data;
Node *next;
}VNode,HC[3];*/
CreateBiTree(T->rchild); //构造右子树
}
return T;
} // CreateBiTree
char node[4]="ABC";
void Select(HuffmanTree HT, int k, int &m1, int &m2)
{
int i,min1,min2;
min1=min2=10000;//首先给它们赋一个最大的值,这个值大于所有可能的权值
4、比较恢复文件和原文件是否相同。
计算机科学与信息工程学院制
提问人的追问 2011-04-29 20:14
这是我的代码···这可以输出吗
#include <iostream.h>
#include <fstream.h>
#include <malloc.h>
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;}
else if( HT[i].weight <min2 && HT[i].parent==0)
{ min2=HT[i].weight;m2=i;}
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
cd = (char *)malloc(n*sizeof(char)); //分配求编码的工作空间
cd[n-1] = '\0'; //编码结束符。
for (i=1; i<=n; ++i) { //逐个字符求哈夫曼编码