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

1、哈夫曼树的建立数据结构课程设计文档班 级： 小组组长: 成 员： 指导老师： 第一章 前 言 数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。在当今信息时代，信息技术己成为当代知识经济的核心技术。我们时刻都在和数据打交道。比如人们在外出工作时找最短路径，在银行查询存

2、款、通过互联网查新闻、以及远程教育报名等，所有这些都在与数据发生关系。实际上，现实世界中的实体经过抽象以后，就可以成为计算机上所处理的数据。数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要

3、达到以下目的：1、 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2、 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3、 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；四、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。第2章 概要设计1、 数据结构设计 使用树TREE的结构，编造最优二叉树（即哈夫曼树），涉及到主要函数有Inithuffmantree,Destoryhuffmantree,huffmancodeing,Visithuffmantree等，用于在一定时间复杂度内寻找到最佳

4、（最短）路径，节约比较次数。2、 层次调用关系 在main（）函数中调用哈夫曼树的各种操作函数3、 ADT描述 Huffman tree n 数据对象D: D为带有各自实数W(D)的数据元素的集合 数据关系：D=NULL 则huffmantree不存在DNULL R=H.H为如下二元 关系： n  D中存在唯一根数据元素root,这个元素无前驱。 n  D-root NULL.则存在D-root =D1，Dr.且D1Dr=NULL n  

5、;若D1 NULL ，则D1 中存在唯一元素xr,<root, xr>H n    且存在Dr上关系HrH,H= <root,x1>,<root,xr>,H1,Hr; n  符合  的R的组合中，存在一个组合R使D中所有结点到root的长度与其权值W(Di)相乘的和最小，此时的<D/R>集合称为huffmantree.第3章 详细设计编译环境：VC6.0实现该该程序的主要算法是：基本操作1、 Init huffmant

6、ree(&T) 操作结果：构造一个已知节点和权值的哈夫曼树2、 Destory huffmantree(&T) 条件：huffmantree 已存在结果：销毁huffmantree3、 huffman coding（&T）条件：huffmantree 已经存在结果：输出huffman code4、 Visit huffmantree（&T)条件：huffmantree 已经存在结果：显示huffman tree一、二叉树的设计typedef struct unsigned int weight; unsigned int parent,lchild,rchild

7、; 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=(un

8、signed int*)malloc(n+1)*sizeof(unsigned int*);       w0=0;    printf("Enter   weight:n");      for(i=1;i<=n;i+)      printf("w%d=",i);scanf(&q

9、uot;%d",&wi);          HT=inithuffmantree(w,n);    huffmantreecoding (HT,HC,n)    outputhuffmantree (HT,n);   destroyhuffmantree (HT);三、结构流程图4、 程序代码#include<stdio.h>

10、#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

11、 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(Hu

12、ffmanTree *ht);void Error(char *message) fprintf(stderr,"Error:%sn",message); exit(1);void destroyhuffmantree(HuffmanTree ht) cout<<"-"<<endl; free(ht); printf("huffmantree destroiedn"); exit(1);HuffmanCode huffmantreecoding(HuffmanTree HT,HuffmanCode HC,uns

13、igned int n) char *cd; unsigned int i,start,c,f; HC=(HuffmanCode)malloc(n+1)*sizeof(char *); cd=(char *)malloc(n*sizeof(char *); cdn-1='0' for(i=1;i<=n;i+) start=n-1; for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) if(HTf.lchild=c) cd-start='0' else cd-start='1' HCi=(char *)ma

14、lloc(n-start)*sizeof(char *); strcpy(HCi,&cdstart); free(cd); cout<<"-"<<endl; printf("NumberttWeightttCoden"); for(i=1;i<=n;i+) printf("%dtt%dtt%sn",i,HTi.weight,HCi); return HC;HuffmanTree inithuffmantree(unsigned int *w,unsigned int n) unsigned int

15、 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->rchi

16、ld=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; HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; return HT;MinCode Select(HuffmanTree HT,unsigned i

17、nt 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(HTi.parent=0) min=HTi.weight; s1=i; break; tempi=i+; for(;i<=n;i+) if(HTi.weight<min&&HTi.parent=0) min=HTi.weight; s1=i; for(i=tempi;i<=n;i+) if(HTi.parent

18、=0&&i!=s1) secmin=HTi.weight; s2=i; break; for(i=1;i<=n;i+) if(HTi.weight<secmin&&i!=s1&&HTi.parent=0) secmin=HTi.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

19、; printf("HT List:n"); printf("Numberttweightttparentttlchildttrchildn"); cout<<"*"<<endl; for(i=n+1;i<=2*n-1;i+) printf("%dtt%dtt%dtt%dtt%dn",i,HTi.weight,HTi.parent,HTi.lchild,HTi.rchild);int main() int code=0; HuffmanTree HT=NULL; HuffmanCode

20、 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; p

21、rintf("请输入节点的数量(大于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 *); w0=0; printf("请输入它们对应的权值:n"); for(i=

22、1;i<=n;i+) printf("w%d=",i); scanf("%d",&wi); sort(w+1,w+n+1); HT=inithuffmantree(w,n);GP: system("CLS"); cout<<"*"<<endl; cout<<" 1.哈夫曼树编码 "<<endl; cout<<" 2.哈弗曼树显示 "<<endl; cout<<" 3.摧

23、毁哈夫曼树并退出程序 "<<endl; cout<<" "<<endl; cout<<"*"<<endl; cout<<"请输入操作编码："<<endl; cin>>code; system("CLS"); switch(code) case 1: huffmantreecoding(HT,HC,n); system("PAUSE"); cout<<endl<<endl;