数据结构课程设计实验报告(赫夫曼编码)(共26页).doc

精选优质文档-倾情为你奉上+数据结构课程设计 题目：赫夫曼编码院、 系：计算机科学与工程学院学科专业：计算机科学与技术 学 生： 高经典 学 号： 指导教师： 梁晨 2010年12月22日专心-专注-专业目 录1课程设计的题目-02课程设计的目的（设计要解决的问题）-13概要设计（函数划分、总体设计）-14详细设计（算法、流程图、程序）-25调试结果- -326课程设计总结- -337心得体会-34二课程设计的目的<1>巩固构造赫夫曼树的算法。<2>设计实验用程序实现赫夫曼树的构造。<3>熟悉用先序、中序或后序的访问方法得到个叶子结点的赫夫曼编码。三概要设计（函数划分、总体设计）<一>总体设计（1） 输入一个字符串用结构体链表存储字符串中出现的不同字符及其出现的次数。（2） 定义赫夫曼数的结点结构体，把不同的字符及其在字符串中出现的次数作为叶子结点的元素及其权值，统计叶子结点的个数n，开辟可以存储2*n个结点的顺序表，来赫夫曼树的各个结点，然后按照一定的规则构造赫夫曼树。（3） 开辟一个可以存储叶子结点元素及指向存储其赫夫曼编码链表的指针的顺序表，然后从叶子结点开始向上访问，是左孩子的把“0”接进链表是右孩子的把“1”接进链表，直到根结点，然后把叶子结点的元素及存储其赫夫曼链表的头指针读入顺序表，直到把所有的叶子结点的元素及指向存储其赫夫曼编码链表的头指针读入顺序表，这样得到的赫夫曼编码是倒序的。（4） 从存储其叶子结点及指向存储其赫夫曼编码链表头指针的顺序表表头开始顺序访问各元素，在输出其赫夫曼编码之前，把链表中的编码顺序读入到等长的栈中，然后编码出栈就会得到顺序的赫夫曼编码，直到把所有的叶子结点都访问到。（5） 用一个字符型的指针指向字符串的第一个字符，从存储叶子结点元素及指向存储其赫夫曼编码链表的头指针的顺序表表头开始访问顺序表中的各元素，直到找到叶子结点的元素和当前字符相等就结束访输出赫夫曼编码，回到表头，指针后移，直到输出字符串的最后一个字符的赫夫曼编码，这样就得到输入字符串的赫夫曼编码。<二>函数划分 该程序有一个主函数和多个子函数，主函数完成对子函数的调用，各子函数实现相应的功能。子函数：（1） 结点的开辟。（2） 实现对输入字符串中出现的不同字符及其出现字数的信息记录。（3） 用叶子结点构造赫夫曼树。（4） 获得构造的赫夫曼树中所有叶子结点的元素及其赫夫曼编码。（5） 输出各叶子结点元素及其对应的赫夫曼编码。（6） 输出输入的字符串的赫夫曼编码。（7） 调用各子函数四详细设计（算法、流程图、程序）<一>算法<1>创建存储叶子结点元素及其权值的链表定义结构体node，其数据成员包括，字符型的元素a和整型元素b和指向node的next指针，来存储叶子结点的内容和权值。定义三个指向node的指针head、p1、p2和字符指针n、t、h，调用setnode()函数开辟一个结点让head指向该结点，p1=head,让n指向输入字符串的第一个元素，当n指向的内容不是0时，如果n指向字符串的第一个字符，则开辟一个结点，让p2指向该结点，让t指向字符串的第一个元素，当*t!=0并且*t=*n则r+（r为整型，初始值为0），把p2->a=*n,p2->b=r,p1->next=p2,p1=p2,n+,t回到字符串首；否则i+（i为整型，初始值为1）r=0，j=1；让t指向字符串第一个元素，当*t！=0，如果*t=*n，r+，t+；让h指向字符串的第一个元素，当h！=n时如果*h=*n就跳出此循环，否则，j+，h+如果i=j则开辟新的结点p2->a=*n,p2->b=r,p1->next=p2,p1=p2;n+,当把最后一个结点连入链表中，p1->next=NULL,然后把p1=head->next,当p!=NULL时输出结点中叶子结点的元素和对应的权值；最后返回head。/setnode()函数的算法：设指向node的指针p，用malloc开辟一个node结点并让p指向该结点，返回p。<2>构造赫夫曼树定义结构体node1，其数据项字符型a（存放叶子结点元素）、整型weight（存放对应权值）、整型sign（起标记作用）、和指向左、右孩子及父母结点的指针lchild、rchild和parent。定义指向node1的指针p0、p1、p2、p3、p4和整型的m、n、i、j、k1、k2，n=0、p=head->next，当p！=NULL，n+，p=p->next，开辟可以存储2*n个node1的顺序表，让p0指向表头，p1=p0,p=head->next,当p！=NULL时p1->a=p->a,p1->weight=p->bp1的指向左、右孩子及父母的指针指空，p=p->next，p1+；p1+,p=p->next;i=1,当i<=n-1,j=0,当j<2，如果j=0把1赋给k1；否则把1赋给k2；p2=p0，当p2！=p1时，如果p2->sign=NULL并且m=p2->weight用break结束循环否则p2+；p2=p0，当p2！=p时，如果m>=p2->weight并且p2->sign=NULL,把p2->weight赋给m，否则p2+；把p0赋给p2，当p2不等于p1时，如果m等于p2->weight并且p2->sign等于NULL，把1赋给p2->sign,如果j=0，把p2赋给p1->lchild,p2->weight赋给p1->weight,p1赋给p2->parent,用break结束循环；如果j=1，则把p2赋给p1->rchild,p1->weight加p2->weight赋给p1->weight,p1赋给p2->parent,用break结束循环；如果j等于0，k1+，p2+；如果j等于1，k2+，p2+；j+；如果k1大于k2把p1->lchild赋给p3，p1->rchild赋给p4，p4赋给p1->lchild,p3赋给p1->rchild,p1->sign=NULL,p1+,i+;然后p-，把p1->parent=NULL,p1+,把p0赋给p2，当p2不等于p时输出p2的各数据项，拍p2+；返回p0。<3>获得各叶子结点的赫夫曼编码定义只存储赫夫曼编码的结构体code，它的数据项有字符型的a（存储0、1编码）以及指向下一个结点的指针next。定义结构体huffmancode，它的数据项有字符型a(存储叶子结点元素)、指向结构体code的指针head。设指向node1的指针p1、p2、p4，指向huffmancode的指针l、l1和指向code的指针h、h1，把p（p为函数的形参）赋给p2，当p2->lchild和p2->rchild同时为NULL，n+，（n为整型，初始化为零），p2+；调用malloc函数开辟可以存储n+1个huffmancode结点的顺序表，让l指向该顺序表的表头，把l赋给l1，把p赋给p4，当p4->lchild和p4->rchild同时为NULL把p4赋给p1调用setcode（）函数开辟一个结点让h1指向该结点，把h1赋给l1->head,当p1->parent不等以NULL时，如果p1等于p1->parent->lchild，调用setcode()函数让h指向它，h->a=0，h1->next=h,h1=h;否则，调用setcode（）函数开辟一个结点让h指向它，h->a=1，h1->next=h,h1=h;然后，把p1->parent赋给p1，把NULL赋给h1->next,p4->a赋给l1->a,l+,当把所有的叶子结点元素及其赫夫曼编码读入顺序表后把NULL赋给l1->a;返回l。/setcode（）函数的算法：设指向code的指针p，调用malloc（）函数开辟一个code结点，让p指向该结点，返回p。<4>输出各叶子结点的赫夫曼编码设指向huffmancode的指针p，指向code的指针和指向字符型的指针base、top；把head1（函数的形参）赋给p，当p->a!=NULL时，把0赋给n，p->head->next赋给h，当h！=NULL时n+，h=h->next，开辟一个可以存储n+1个字符的栈，让base指向栈底，top=base,把h=p->head->next，当h！=NULL时，*top=h->a，top+，h=h->next；top-，当to不等于base时，输出*top，top- -;输出*top；p+。<5>输出字符串的赫夫曼编码设指向huffmancode的指针p1，指向code的指针h和指向字符型的指针base，top，p2，让p2指向字符串的第一个元素，当*p2！=0时，输出*p2，p2+；当*p！=0时（p为函数的形参），把0赋给n（n为整型）p1=p0（p0为形参）当p1->a!=NULL时，如果p1->a等于*p把p1->head->next赋给h，当h！=NULL时，h=h->next,base指向可以存储n+1个字符的栈底，top=base，把p1->head->next赋给h，当h！=NULL，*top=h->a,top+,h=h->next，top自减，当top！=base，输出*top，top-，输出*top，用break结束循环，p+。<6>control函数定义长度为20的字符数组a，指向node的指针p，整型n和指向node1的指针p1，输入a把a作为实参调用函数getdata（a），把返回值赋给p，把p作为实参调用coutdata（p）把返回值赋给n，如果n等于1，p=p->next,输出p->a和p->b,否则，以p为实参调用settree（p），将返回值赋给p1，以p1为实参调用gethuffmamcode（p1）函数，将返回值赋给p2（p2为指向huffmancode的指针），以p2为实参调用printhuffmancode（p1）函数，然后以a，p2为实参调用print（a，p2）函数。/coutdata()函数的算法：设指向node的指针p，把head->next赋给p，当p！=NULL时n+，p=p->next;返回n。<7>主函数调用control（）函数。<二>流程图创建存储叶子结点元素及其权值的链表开辟一个新的结点，让head指向它p1=headn=a *n！= 0 n=是=a?否开辟新的结点，让p1指向它 i+ r=0 t=n j=1 *t！= 0 t=a*t=是= 0 ？否 *t！= 0 *t=*n是？否r+r+ t+ t+p2->a=*n h=a p2->b=r h！=n p1->next=p2*h=是*n？ 否p1=p2 n+break j+ h+i=j？是 否开辟新结点，让p2指向它p2->a=*np2->b=rp1->next=p2p1=p2p1->next=NULL p1=head->nextp1!=NULL输出p1->a输出p1->a返回head/setnode函数开辟一个node结点，让p指向它返回p构造赫夫曼树 p=head->next p！=NULLn+p=p->nextp0=（listnode1）malloc（2*n*sizeof（node1）p1=p0p=head->nextp！=NULLp1->a=p->ap1->weight=p->bp1->lchild p1->rchild p1->parent p1->sign全置空p1+i=1i<=n-1j=0j<2是j=0?否k1=1k2=1p2=p0p2!=p1是P2->sign= =NULL?否m=p2->weightp2+breakp2=p0p2!=p1m>=p2->weight 是并且p2->sign= =NULL?否m=p2->weightp2+p2=p0p2!=p1m=p2->weight是并且p2->sign= =NULL?否 j=0?是 p2->sign j=0? =1? 是 否p1->lchild=p2 p1->rchild=p2p1->weight p1->weight+= k1+=p2->weight p2-weightk2+ p2->parent p2->parent =p1=p1breakp2+j+k1>k2是?否p3=p1->lchildp4=p1->rchildp1->lchild=p4p1->rchild=p3p1->sign=NULLp1+i+p1- -p1->parent=NULLp1+p2=p0p2!=p1输出p2->a p2->weightp2->lchild p2->parent p2->rchildp2+返回p0<3>获得各叶子结点的赫夫曼编码 p2=p p2=lchild= =NULL&&p2->rchild= =NULLn+p2+l=(listhuffmancode)malloc(n+1)*sizeof(huffmancode)p4=pp4->lchild= =NULL&&p4->rchild= =NULLp1=p4h1=setcode()l1->head=h1P1->parent！=NULL是 p1=p1->parent->lchild? 否开辟一个结点让h指向它 h->a= 0 h1->next=hh1=hh->a= 0 h1->next=hh1=hh1->next=NULLl1->a=p4->a l1+l1->a=NULL 返回l /setcode函数开辟一个code结点，让p指向该结点 返回p<4>输出各叶子结点的赫夫曼编码 p=head1p->a!=NULLh=h->head->nexth!=NULLn+h=h->nextbase=(char *)malloc(n+1)*sizeof(char)h=h->head->nexth!=NULL*top=h->atop+h=h->nexttop-top!=base输出*toptop-输出*top<5>输出字符串的赫夫曼编码p2=p*p2!= 0 *p2p2+*p!= 0 n=0p1=p0p1->a!=NULL p1->a= =*p? 是否h=p1->head->nextp1+h!=NULLn+h=h->nextbase=(char *)malloc(n+1)*sizeof(char)top=baseh=p1->head->nexth!=NULL*top=h->atop+h=h->next-toptop!=base输出*topbreakp+<6>control函数输入ap=getdata(a)n=coutdata(p)是n= =1?否p=p->nextp1=settree(p) 输出p->a和p->bp2=gethuffmancode(p1)printhuffmancode(p2)print(a,p2) /countdata()函数p=head-nextp!=NULLn+p=p->next返回n <7>主函数调用control()函数/程序的编译环境是Visual studio 2010/把统计叶子结点元素和权值的函数放在“计算权值.h”中#include<iostream>using namespace std;typedef struct node /存储叶子结点元素及其权值的结构体char a; /叶子结点的元素int b; /叶子结点的权值struct node *next; /指向下一个结点的指针*listnode;listnode setnode() /开辟结点的函数listnode p;p=(listnode)malloc(sizeof(node);return p;listnode getdata(char *a) /*统计输入字符串中的不同字符及其出现的次数的函并且把统计出的数据，作为叶子结点的元素和权值*/ listnode head,p1,p2; char *n,*t,*h; int i=1,j=1,r=0; head=setnode(); p1=head; for(n=a;*n!='0'n+) if(n=a) p2=setnode(); for(t=n;*t!='0't+) /统计相同的字符在字符串中出现的次数if(*t=*n) r+; p2->a=*n; p2->b=r; p1->next=p2; p1=p2; else i+; r=0; j=1; for(t=a;*t!='0't+) if(*t=*n) r+; for(h=a;h!=n;h+) if(*h=*n) break; else j+; if(i=j) p2=setnode(); /调用setnode（）函数开辟结点 p2->a=*n; p2->b=r; p1->next=p2; p1=p2; p1->next=NULL; cout<<"电文的长度为："<<i<<endl; cout<<"-"<<endl; p1=head; cout<<"叶子结点"<<"t"<<"权值"<<endl; for(p1=p1->next;p1!=NULL;p1=p1->next) cout<<p1->a<<"tt "<<p1->b<<endl; cout<<"-"<<endl;return head; int coutdata(listnode head) /统计叶子结点的个数 listnode p; int n=0; for(p=head->next;p!=NULL;p=p->next) n+; return n; /把构造赫夫曼树的函数放在头文件“构造赫夫曼树.h”中#include<iostream>#include"计算权值.h"using namespace std;typedef struct node1 /赫夫曼树的结点结构体 char a; /结点元素int weight,sign; /结点的权值和结点的标记struct node1 *parent,*lchild,*rchild; /指向父母结点和左、右孩子的指针*listnode1; /指向node1的指针listnode1 settree(listnode head) /构造赫夫曼树的函数 listnode p; listnode1 p0,p1,p2; int m,n,i,j,k1,k2; struct node1 *p3,*p4; n=0; for(p=head->next;p!=NULL;p=p->next) n+; p0=(listnode1)malloc(2*n*sizeof(node1); /开辟可以存储2n个赫夫曼树结点的顺序表 p1=p0; for(p=head->next;p!=NULL;p=p->next) /把叶子结点的信息读入到 顺序表中 p1->a=p->a; p1->weight=p->b; p1->lchild=NULL; p1->parent=NULL; p1->rchild=NULL; p1->sign=NULL; p1+; for(i=1;i<=n-1;i+) for(j=0;j<2;j+) if(j=0)k1=1; else if(j=1) k2=1; for(p2=p0;p2!=p1;p2+) if(p2->sign=NULL) m=p2->weight; break; for(p2=p0;p2!=p1;p2+) if(m>=p2->weight) if(p2->sign=NULL) m=p2->weight; for(p2=p0;p2!=p1;p2+) if(m=p2->weight) if(p2->sign=NULL) p2->sign=1; if(j=0) /把先找到的权值最小的作为左孩子 p1->lchild=p2; p1->weight=p2->weight; p2->parent=p1; else if(j=1) /把后找到的权值最小的最为右孩子 p1->rchild=p2; p1->weight=p1->weight+p2->weight; p2->parent=p1; break; if(j=0) k1+; /标记先找到的权值最小的结点在顺序表中的位置 else if(j=1) k2+; /标记后找到的权值最小的结点在顺序表中的位置 if(k1>k2) /*如果先找到的权值最小的结点在顺序表中的位置在后找到的后面 则他们父母结点的左右孩子指针交换*/ p3=p1->lchild; p4=p1->rchild; p1->lchild=p4; p1->rchild=p3; p1->sign=NULL; p1+; p1-; p1->parent=NULL; p1+; p2=p0; cout<<"叶子结点"<<"t"<<"权值"<<"t"<<"左孩子"<<"tt"<<"父母结点"<<"t"<<"右孩子"<<endl; /输出构造的赫夫曼树 while(p2!=p1) cout<<p2->a<<"tt "<<p2->weight<<"t"<<p2->lchild<<"t"<<p2->parent<<"t"<<p2->rchild<<endl; p2+; cout<<"-"<<endl; return p0; /把叶子结点赫夫曼编码的获取的函数放在头文件“获得赫夫曼编码.h”中#include<iostream>#include"构造赫夫曼树.h"using namespace std;typedef struct code /存储赫夫曼编码的结构体 char a; /存储0、1编码struct code *next; /指向链表下一个结点的指针*listcode; /指向该结构体的指针typedef struct huffmancode /存储叶子结点元素和赫夫曼编码链表的头指针的结构体char a; /叶子结点的元素listcode head; /指向存储赫夫曼编码链表的指针*listhuffmancode; listcode setcode() /开辟存储0、1编码结点的函数listcode p;p=(listcode)malloc(sizeof(code);return p;listhuffmancode gethuffmancode(listnode1 p) /把得到的叶子结点及其 赫夫曼编码存到顺序表中的函数listnode1 p1,p2,p4;int n=0;listhuffmancode l,l1;listcode h,h1;for(p2=p;p2->lchild=NULL&&p2->rchild=NULL;p2+)n+;l=(listhuffmancode)malloc(n+1)*sizeof(huffmancode); /开辟可以存储n+1个叶子结点信息的顺序表 l1=l;for(p4=p;p4->lchild=NULL&&p4->rchild=NULL;p4+)p1=p4;h1=setcode();l1->head=h1; for(;p1->parent!=NULL;p1=p1->parent)if(p1=p1->parent->lchild)h=setcode();h->a='0'h1->next=h;h1=h;else if(p1=p1->parent->rchild)h=setcode();h->a='1'h1->next=h;h1=h;h1->next=NULL;l1->a=p4->a;l1+;l1->a=NULL;return l;/把输出赫夫曼编码的函数放在头文件“输出赫夫曼编码.h”中#include<iostream>#include"获得赫夫曼编码.h"using namespace std;void printhuffmancode(listhuffmancode head1) /输出叶子结点及其赫夫曼编码 的函数listhuffmancode p; p=head1; listcode h;int n;char *base,*top;cout<<"叶子结点"<<"t"<<"权值"<<endl;for(p=head1;p->a!=NULL;p+)cout<<p->a<<"tt "n=0;h=p->head;for(h=h->next;h!=NULL;h=h->next)n+;base=(char *)malloc(n+1)*sizeof(char);top=base;h=p->head;for(h=h->next;h!=NULL;h=h->next)*top=h->a; top+;top-;for(;top!=base;top-)cout<<*top;cout<<*top;cout<<endl; cout<<"-"<<endl; void print(char *p,listhuffmancode p0) /输出输入字符串的赫夫曼编码listhuffmancode p1;listcode h;int n;char *base,*top,*p2;cout<<"电文内容："for(p2=p;*p2!='0'p2+)cout<<*p2;cout<<endl;cout<<"电文的赫夫曼编码："for(;*p!='0'p+)n=0;for(p1=p0;p1->a!=NULL;p1+)if(p1->a=*p)h=p1->head;for(h=h->next;h!=NULL;h=h->next)n+;base=(char *)malloc(n+1)*sizeof(char);top=base;h=p1->head;for(h=h->next;h!=NULL;h=h->next)*top=h->a;top+;for(-top;top!=base;top-)cout<<*top;cout<<*top;break;/把control函数放在头文件“控制函数.h”中#include<iostream>#include"输出赫夫曼编码.h"using namespace std;void control() /调用各个功能函数cout<<" 数据结构课程设计"<<endl;cout<<"-"<<endl;char a20;int n;cout<<"接受到的电文内容（不超过20个字符）：" cin>>a; listnode