第1页 / 共41页
第2页 / 共41页
第3页 / 共41页
第4页 / 共41页
第5页 / 共41页
第6页 / 共41页
第7页 / 共41页
第8页 / 共41页
数据结构课程设计报告.doc
一、线性表数据结构
(一)、需求分析
SqList L;
L.elem=(ElemType *)malloc(LIST_INIT_SIZE * sizeof
SqList L;
L=InitList_Sq();
L=ListInsert_Sq(L);
（1）构造链表；（2）数据输入；（3）执行删除；（4）输出要求数值
(二)、概要设计
(三)、详细设计
(四)．调试分析：
(五)、设计总结
(六)、附件
LNode* CREAT(int n) /* 创建循环链表 */
LNode *s,*q,*t;
DELETE (LNode* t,int m)/* 链表的删除 */
LNode *a;int i;
LNode *p;
}/* 通过数学思想求得实验要求情况下的数值 */
中南大学
数据结构课程设计报告
学 院：信息科学与工程学院
专 业：电子信息工程
班 级：0702 班
名 字：黄小明
学 号：0903070201
设计题目一
2009 年 7 月 5 日
哈夫曼编/译码器
一 需求分析
1. 本程序的目的是实现利用哈夫曼编码进行通信。因为利用哈夫曼编码进
行通信可以大大提高信道利用率，缩短信息传输时间，降低舆成本，这
使得哈夫曼编码译码器的用途大大增加。
2. 程序以用户和计算机对话的方式执行，即在计算机终端上显示“提示信
息”之后，由用户在键盘上输入程序中运行所需要的数据，比如选择要
执行的命令，输入要编译的英文句子，英文句子的字符等。
3. 程序执行的命令包括：
a）初始化
还可以加一些其它的命令项，如打印哈夫曼树等。
b）编码 c）译码 d）打印代码 q）退出
4. 测试数据:
（1） 利用教科书例 6-2 中的数据调试程序。
（2） 输入字符；a，b，c，d, 权值分别为：9，8，7，6
（3） 用《数据结构题集》P149 页的字符集和频度的实际统计数
据建立哈夫树，并实现以下报文的编码和译码：“THIS
PROGRAM IS MY FAVORITE”。
二 概要设计
1. 本程序用到的两个数据结构类型如下：
typedef struct
{
int
int
weight;
parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef struct
{
HuffmanTree HT;
char
*c;
int
longth;
HuffmanCode HC;
}Huffman;
它包含的函数如下：
A. Huffman HuffmanCoding(Huffman Hfm)//哈夫曼编码函数
B. Huffman InputHuffman(Huffman Hfm)//输入哈夫曼的编码值函数
C. Huffman InitHuffman(Huffman Hfm)//建立哈夫曼树函数
D. void Select(HuffmanTree HT,int end,int *s1,int *s2)// 查找权值最小
的两个字符序号的函数
2. 本程序包含五个模块：
1）主程序
Void main()
{
输出作者信息;
While(choice!='q')
｛
输出命令目录并接收选择的命令
处理命令并循环;
}
}
2）初始化功能
3）编码功能
4）译码功能
5）打印代码功能
3. 各模块调用关系为：
由主函数调用各个功能函数，而一般的程序使用顺序为从初始化
到编码再到译码最后打印代码。
三 详细设计
1. 数据类型和它的相关函数：
typedef struct
{
int
int
weight;
parent,lchild,rchild;
}HTNode,*HuffmanTree;
{
typedef struct
HuffmanTree HT;
*c;
char
int
longth;
HuffmanCode HC;
}Huffman;
void Select(HuffmanTree HT,int end,int *s1,int *s2)// 查找权值最小的
两个字符序号的函数
{
int i;
int min1=MAX_NUM;
int min2;
for (i=1;i<=end;i++)
{
if (HT[i].parent==0&&HT[i].weightHT[i].weight)
*s2=i;
min2=HT[i].weight;
{
}
}
{
}
}
Huffman HuffmanCoding(Huffman Hfm)//哈夫曼编码函数
{
int i,n,m,s1,s2,start;
int c,f;
char *cd;
n=Hfm.longth;
if(n<=1)
m=2*n-1;
return Hfm;
for(i=n+1;i<=m;++i)
{
Select(Hfm.HT,i-1,&s1,&s2);
Hfm.HT[s1].parent=i;
Hfm.HT[s2].parent=i;
Hfm.HT[i].lchild=s1;
Hfm.HT[i].rchild=s2;
Hfm.HT[i].weight=Hfm.HT[s1].weight+Hfm.HT[s2].weight;
}
Hfm.HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;++i)
{
start=n-1;
for(c=i,f=Hfm.HT[i].parent;f!=0;c=f,f=Hfm.HT[f].parent)
if(c==Hfm.HT[f].lchild)
else cd[--start]='1';
cd[--start]='0';
Hfm.HC[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(Hfm.HC[i],&cd[start]);
{
}
}
free(cd);
return Hfm;
}
Huffman InputHuffman(Huffman Hfm)//输入哈夫曼的编码值
{
int i,n;
printf("\n\n\n***初始化哈夫曼树***\n\n");
printf("字符和它的权值会被存入 \"hfmTree\"文件中\n");
printf("请输入将要输入的字符数目: ");
scanf("%d",&n);
Hfm.HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode));
Hfm.c=(char *)malloc((n+1)*sizeof(char));
for(i=1;i<=n;i++)
{
printf("\n\n 请输入字符: ");
scanf("%s",&Hfm.c[i]);
printf("请输入字符的权值: ");
scanf("%d",&Hfm.HT[i].weight);
Hfm.HT[i].parent=0;
Hfm.HT[i].lchild=0;
Hfm.HT[i].rchild=0;
}
for(;i<=2*n-1;++i)
{
Hfm.HT[i].weight=0;
Hfm.HT[i].parent=0;
Hfm.HT[i].lchild=0;
Hfm.HT[i].rchild=0;
}
Hfm.longth=n;
return Hfm;
}
Huffman InitHuffman(Huffman Hfm)//建立哈夫曼树
{
int n,i;
FILE *fp;
fp=fopen("hfmTree","rt");
if(fp==NULL)
{
Hfm=InputHuffman(Hfm);
fp=fopen("hfmTree","wt");
fprintf(fp,"%d\n",Hfm.longth);
for(i=1;i<=Hfm.longth;i++)
fprintf(fp,"%c %d",Hfm.c[i],Hfm.HT[i].weight);
rewind(fp);
fscanf(fp,"%d\n",&n);
Hfm.c=(char *)malloc((n+1)*sizeof(char));
Hfm.HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode));
for(i=1;i<=n;i++)
fscanf(fp,"%s %d",&Hfm.c[i],&Hfm.HT[i].weight);
for(i=1;i<=n;i++)
Hfm.HT[i].parent=0;
Hfm.HT[i].lchild=0;
Hfm.HT[i].rchild=0;
for(;i<=2*n-1;++i)
Hfm.HT[i].weight=0;
Hfm.HT[i].parent=0;
Hfm.HT[i].lchild=0;
Hfm.HT[i].rchild=0;
}
else
{
{
}
{
}
Hfm.longth=n;
}
fclose(fp);
Hfm=HuffmanCoding(Hfm);
return Hfm;
}
2. 实现各个功能的函数：
void Print(Huffman Hfm)//输出哈夫曼码
{
int i,n;
n=Hfm.longth;
printf("\n\n***输出字符编码***\n\n");
for(i=1;i<=n;i++)
{
}
}
printf("\n");
printf("字符: %c\t",Hfm.c[i]);
printf("权值: %d\t",Hfm.HT[i].weight);
printf("编码: ");
puts(Hfm.HC[i]);
void Encoding(Huffman Hfm)//实现编码功能
{
int i=0,j=0,n;
char ch[MAX];
FILE *fp,*ffp;
n=Hfm.longth;
printf("\n\n***编码***\n\n");
if((ffp=fopen("ToBeTran","rt"))==NULL)
{
}
{
}
{
}
}
printf("\n 请输入英文句子: ");
scanf("%s",&ch);
printf("\n");
fp=fopen("CodeFile","wt+");
else
fscanf(ffp,"%s",ch);
fclose(ffp);
while(ch[j])
for(i=1;i<=n;i++)
if(ch[j]==Hfm.c[i])
printf("%s",Hfm.HC[i]);
fprintf(fp,"%s",Hfm.HC[i]);
break;
j++;
{
}
rewind(fp);
fclose(fp);
void Decoding(Huffman Hfm)//实现译码功能
{
{
}
{
}
{
}
}
HuffmanTree p;
int i,n;
int j=0;
char d[50];
FILE *fp;
n=Hfm.longth;
printf("\n\n\n***译码***\n\n");
if((fp=fopen("CodeFile","rt"))==NULL)
printf("请输入编码:");
scanf("%s",&d);
else
fscanf(fp,"%s",d);
fclose(fp);
printf("\n 文件是: ");
fp=fopen("TextFile","wt+");
while(d[j])
{
}
p=&Hfm.HT[2*n-1];
while(p->lchild||p->rchild)
{
}
{
}
if(d[j]=='0')
i=p->lchild; p=&Hfm.HT[i];
else
i=p->rchild;
p=&Hfm.HT[i];
j++;
printf("%c",Hfm.c[i]);
fprintf(fp,"%c",Hfm.c[i]);
fclose(fp);
Huffman BuildHuffman(Huffman Hfm)//实现重建哈夫曼树
{
int i;
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
