数据结构课程设计(赫夫曼树的建立).doc

(完整word版)数据结构课程设计(赫夫曼树的建立)

哈夫曼树的建立

数据结构课程设计文档

班 级：
小组组长:
成 员：

指导老师：

第一章 前 言

数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。在当今信息时代，信息技术己成为当代知识经济的核心技术。我们时刻都在和数据打交道。比如人们在外出工作时找最短路径，在银行查询存款、通过互联网查新闻、以及远程教育报名等，所有这些都在与数据发生关系。实际上，现实世界中的实体经过抽象以后，就可以成为计算机上所处理的数据。数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。

通过此次课程设计主要达到以下目的：

一、 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；

二、 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；

三、 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；

四、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。

第二章 概要设计
一、 数据结构设计
使用树TREE的结构，编造最优二叉树（即哈夫曼树），涉及到主要函数有Inithuffmantree,Destoryhuffmantree,huffmancodeing,Visithuffmantree等，用于在一定时间复杂度内寻找到最佳（最短）路径，节约比较次数。
二、 层次调用关系
在main（）函数中调用哈夫曼树的各种操作函数
三、 ADT描述 
Huffman tree 
{
n 数据对象D: D为带有各自实数W(D)的数据元素的集合
数据关系：D=NULL 则huffmantree不存在D≠NULL R={H}.H为如下二元 关系： 
n  ①D中存在唯一根数据元素root,这个元素无前驱。 
n  ②D-{root} ≠NULL.则存在D-{root} ={D1，Dr}.且D1∧Dr=NULL 
n  ③若D1 ≠NULL ，则D1 中存在唯一元素xr,<root, xr>∈H n 
   且存在Dr上关系Hr∈H,H= {<root,x1>,<root,xr>,H1,Hr}; 
n  ④符合① ② ③的R的组合中，存在一个组合R’使D中所有结点到 root的长度与其权值W(Di)相乘的和最小，此时的<D/R>集合称为 huffmantree.
}

第三章 详细设计
编译环境：VC6.0

实现该该程序的主要算法是：
基本操作
1、 Init huffmantree(&T)
操作结果：构造一个已知节点和权值的哈夫曼树
2、 Destory huffmantree(&T)
条件：huffmantree 已存在
结果：销毁huffmantree
3、 huffman coding（&T）
条件：huffmantree 已经存在
结果：输出huffman code
4、 Visit huffmantree（&T)
条件：huffmantree 已经存在
结果：显示huffman tree

一、二叉树的设计
typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
} HTNode,*HuffmanTree;

typedef char **HuffmanCode;

typedef struct
{
unsigned int s1;
unsigned int s2;

}MinCode;
二、主要过程
int main()
{
int code=0;
HuffmanTree HT=NULL;
HuffmanCode HC=NULL;
unsigned int *w=NULL;
unsigned int i,n;
printf("Input   n:\n"); 
scanf("%d",&n);
w=(unsigned int*)malloc((n+1)*sizeof(unsigned int*));       w[0]=0;    
printf("Enter   weight:\n");      
for(i=1;i<=n;i++)
{    
  printf("w[%d]=",i);
scanf("%d",&w[i]);      
}    
HT=inithuffmantree(w,n);    
huffmantreecoding (HT,HC,n)    
outputhuffmantree (HT,n);   
destroyhuffmantree (HT);
}

三、结构流程图

四、 程序代码

#include<stdio.h>
#include<stdlib.h>
#include<cstring>
#include<conio.h>
#include<iostream>
#include<algorithm>

using namespace std;

typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
} HTNode,*HuffmanTree;

typedef char **HuffmanCode;

typedef struct
{
unsigned int s1;
unsigned int s2;

}MinCode;

void outputhuffmantree(HuffmanTree HT,unsigned int n);
HuffmanTree inithuffmantree(unsigned int *w,unsigned int n);
HuffmanCode huffmantreecoding(HuffmanTree HT,HuffmanCode HC,unsigned int n);
void Error(char *message);
MinCode Select(HuffmanTree HT,unsigned int n);
void destroyhuffmantree(HuffmanTree *ht);

void Error(char *message)
{
fprintf(stderr,"Error:%s\n",message);
exit(1);
}

void destroyhuffmantree(HuffmanTree ht)
{
cout<<"-------------------------------------------------------------------------------"<<endl;
free(ht);
printf("huffmantree destroied\n");
exit(1);
}

HuffmanCode huffmantreecoding(HuffmanTree HT,HuffmanCode HC,unsigned int n)
{
char *cd;
unsigned int i,start,c,f;
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=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 *));
strcpy(HC[i],&cd[start]);
}
free(cd);
cout<<"-------------------------------------------------------------------------------"<<endl;
printf("Number\t\tWeight\t\tCode\n");
for(i=1;i<=n;i++)
printf("%d\t\t%d\t\t%s\n",i,HT[i].weight,HC[i]);
return HC;
}

HuffmanTree inithuffmantree(unsigned int *w,unsigned int n)
{
unsigned int i,s1=0,s2=0;
HuffmanTree p,HT;
unsigned int m;
MinCode min;
if(n<=1) Error("节点数量太少，创建失败！\n");
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
if(!HT)
Error("无法创建哈夫曼树，请查看磁盘空间是否足够！");
for(p=HT,i=0;i<=n;i++,p++,w++)
{
p->weight=*w;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(;i<=m;i++,p++)
{
p->weight=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(i=n+1;i<=m;i++)
{
min=Select(HT,i-1);
s1=min.s1;
s2=min.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;
}
return HT;
}

MinCode Select(HuffmanTree HT,unsigned int n)
{
unsigned int min,secmin;
unsigned int temp;
unsigned int i,s1,s2,tempi;
MinCode code;
s1=1;
s2=1;
for(i=1;i<=n;i++)
if(HT[i].parent==0)
{
min=HT[i].weight;
s1=i;
break;
}
tempi=i++;
for(;i<=n;i++)
{
if(HT[i].weight<min&&HT[i].parent==0)
{
min=HT[i].weight;
s1=i;
}
}
for(i=tempi;i<=n;i++)
{
if(HT[i].parent==0&&i!=s1)
{
secmin=HT[i].weight;
s2=i;
break;
}
}
for(i=1;i<=n;i++)
{

if(HT[i].weight<secmin&&i!=s1&&HT[i].parent==0)
{
secmin=HT[i].weight;
s2=i;
}
}
if(s1>s2)
{
temp=s1;
s1=s2;
s2=temp;
}
code.s1=s1;
code.s2=s2;
return code;
}

void outputhuffmantree(HuffmanTree HT,unsigned int n)
{
unsigned int i;
printf("HT List:\n");
printf("Number\t\tweight\t\tparent\t\tlchild\t\trchild\n");
cout<<"********************************************************************************"<<endl;
for(i=n+1;i<=2*n-1;i++)
printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\n",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);

}

int main()
{
int code=0;
HuffmanTree HT=NULL;
HuffmanCode HC=NULL;
unsigned int *w=NULL;
unsigned int i,n;
P:
system("color A");
cout<<"※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※"<<endl;
cout<<"※ ※"<<endl;
cout<<"※ 哈夫曼树计算与编码程序 ※"<<endl;
cout<<"※ ※"<<endl;
cout<<"※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※"<<endl<<endl;
printf("请输入节点的数量(大于1个):\n");
scanf("%d",&n);
if(n==1)
{
system("CLS");
printf("节点数太少,请重新输入.....\n");
for(int j=1;j<600000000;j++){;}
system("CLS");

goto P;
}
w=(unsigned int *)malloc((n+1)*sizeof(unsigned int *));
w[0]=0;
printf("请输入它们对应的权值:\n");
for(i=1;i<=n;i++)
{
printf("w[%d]=",i);
scanf("%d",&w[i]);
}
sort(w+1,w+n+1);

HT=inithuffmantree(w,n);
GP:
system("CLS");
cout<<"*******************************************************************************"<<endl;
cout<<" 1.哈夫曼树编码 "<<endl;
cout<<" 2.哈弗曼树显示 "<<endl;
cout<<" 3.摧毁哈夫曼树并退出程序 "<<endl;
cout<<" "<<endl;
cout<<"*******************************************************************************"<<endl;
cout<<"请输入操作编码："<<endl;
cin>>code;
system("CLS");
switch(code)
{
case 1:
{
huffmantreecoding(HT,HC,n);
system("PAUSE");
cout<<endl<<endl;
goto GP;
break;
}
case 2:
{
outputhuffmantree(HT,n);
system("PAUSE");
cout<<endl<<endl;
goto GP;
break;
}
case 3:
{
destroyhuffmantree(HT);
system("PAUSE");
break;
}
default:
{
system("color A");
cout<<"非法字符，请重新输入"<<endl<<endl;
for(int j=0;j<700000000;j++){}
system("CLS");
goto GP;
break;
}
}
return 0;
}

第四章 测试显示结果

初始界面：

输入节点及权值：

选择界面：

哈夫曼树编码界面：

哈夫曼树显示：

退出界面：

第五章 总结

A：主要负责程序的设计和代码的编辑。根据《数据结构-C语言版》 作者严蔚敏、吴伟民著一书的理论知识，以及章节后的伪代码，我适合的更改，做出了课程设计中的作品。在打代码的过程中，出现好多次错误，在网上查找，得到解决。这次课程设计对数据结构有了更深的认识。

B：主要负责文档的编写。这次的课程设计中，与王文忠配合，把课程设计的文档写出来。为了更好地展现我们的成果以及代码，对于调试代码的界面，我们以截图的方式展现在文档中，让读者更好地查看。

C：主要负责文档的编写。在这次课程设计及中，学到了很多知识，还有很多知识还要现学。只要用心，就能学到自己想学的东西。

指导老师评语：

成绩评定：

指导老师签名：

基地指导老师签名：

年 月 日
教研室意见

教研室主任签章

年 月 日
学院意见

分管院长签章

年 月 日