课程设计（数据结构）课程设计任务书及成绩评定课题名称表达式求值哈夫曼树和哈夫曼编码Ⅰ、题目的目的和要求：巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。

（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。

（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。

Ⅱ、设计进度及完成情况Ⅲ、主要参考文献及资料[1] 严蔚敏数据结构（C语言版）清华大学出版社 1999[2] 严蔚敏数据结构题集（C语言版）清华大学出版社 1999[3] 谭浩强 C语言程序设计清华大学出版社[4] 与所用编程环境相配套的C语言或C++相关的资料目录第一章概述 (1)第二章系统分析 (2)第三章概要设计 (3)第四章详细设计及实现代码 (5)第五章调试过程中的问题及系统测试情况 (9)第六章结束语 (10)参考文献 (11)第一章概述课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。

课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。

《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。

数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。

同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

在这次的课程设计中我选择的题目是表达式求值和哈夫曼树及哈夫曼编码。

这里我们介绍一种简单直观、广为使用的算法，通常称为“算符优先法”。

哈夫曼树又称最优树，是一类带权路径长度最短的树，有着广泛的应用。

功能：表达式求值以栈为存储结构，实现输入的表达式的求值；哈夫曼树和哈夫曼编码是实现最优二叉树的构造，并能通过最优二叉树进行编码，应用到电文中，并以此来译码。

利用键盘，输入相应的数值，通过程序实现表达式的求值；再利用键盘，输入各个顶点，通过程序构造最优二叉树以及为此编码。

第二章系统分析一、表达式求值根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项；对于两个一元多项式所有指数不相同的项，则分别复抄到“和多项式”中去。

在此，安装上述抽象数据类型Polynomial中基本操作的定义，“和多项式”链表中的结点无需另生成，而应该从两个多项式的链表中摘取。

其运算规则如下：假设指着qa和qb分别指向多项式A和多项式B中当前进行比较的某个结点，则比较两个结点中的指数项，有下列3种情况：①指针qa所指结点的指数值<指针qb所指结点的指数值，则应摘取qa指针所指结点插入到“和多项式”链表中去；②指针qa所指结点的指数值>指针qb所指结点的指数值，则应摘取指针qb所指结点插入到“和多项式”链表中去；③指针qa所指结点的指数值=指针qb所指结点的指数值，则将两个结点中的系数相加，若和数不为零，则修改qa所指结点的系数值，同时释放qb所指结点；反之，从多项式A的链表中删除相应结点，并释放指针qa和qb所指结点。

二、哈夫曼树和哈夫曼编码建立哈夫曼树的算法思想是：1)根据给定的几个权值{w1，w2，……，w n}构成n颗二叉树的集合F={T1，T2，……，T n}，其中每颗二叉树T i中只有一个带权为w i的根结点，其左右子树均空。

2)在F中选取两棵根结点的权值最小作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。

3)在F中删除这两棵树，同时将新得到的二叉树加入F中。

4)重复（2）和（3），直到F只含一棵树为止。

这棵树便是哈夫曼树。

第三章概要设计一、表达式求值：ADT Polynomial{数据对象：D={a[i]|a[i]∈Elemset,i=1,2,…,n, n>=0TerSet中的咩歌元素包含一个表示系数的实数和表示指数的整数} 数据关系：R1={<a[i-1],a[i]>|a[i-1],a[i]∈D,i=2,…,n}基本操作：CreatPolyn（&P，m）操作结果：输入m项的系数和指数，建立一元多项式P。

Destroystack(&s)初始条件：一元多项式P已存在。

操作结果：销毁一元多项式P。

PrintPolyn（P）初始条件：一元多项式P已存在。

操作结果：打印输出一元多项式P。

PolynLength（P）初始条件：一元多项式P已存在。

操作结果：返回一元多项式P中的项数。

AddPolyn（&Pa，&Pb）初始条件：一元多项式Pa和Pb已存在。

操作结果：完成多项式相加运算，即：Pa=Pa+Pb，并销毁一元多项式Pb。

SubtrantPolyn（&Pa，&Pb）初始条件：一元多项式Pa和Pb已存在。

操作结果：完成多项式相减运算，即：Pa=Pa-Pb,并销毁一元多项式Pb。

MultiplyPolyn（&Pa，&Pb）初始条件：一元多项式Pa和Pb已存在。

操作结果：完成多项式相乘运算，即：Pa=Pa*Pb，并销毁一元多项式Pb。

}ADT Polynomial以下算法描述了这个求值过程。

int cmp(term a, term b);//依a的指数值<(或=)(或>)b的指数值，分别返回-1、0、+1void CreatPolyn(polynomail&p,int m){//输入m项的系数和指数，建立表示一元多项式的有序链表pInitList(p); h =GetHead(p);e.coef =0.0; e.expn = -1; SetCurElem(h,e); //设置头结点的数据元素for (i=1; i<=m ; ++i){ //依次输入m个非零项scanf (e.coef, e.expn);if (!LocateElem(P,e,q(*cmp)())){ //当前链表中不存在该指数项if(MakeNode(s,e)) InsFirst(q,s); //生成结点并插入链表}} } //CreatPolynvoid AddPolyn(polynomai &Pa, polynomai &Pb){//多项式加法：Pa=Pa+Pb，利用两个多项式的结点构成“和多项式”。

ha =GetHead(Pa); hb =GetHead(Pb);//ha 和hb分别指向Pa和Pb中当前结点while(qa&&qb){//qa和qb均非空a=GetCurElem(qa); b=GetCurElem(qb);//a和b为两表中当前比较元素switch(*cmp(a,b)) {case -1://多项式PA中当前结点的指数值小ha=qa; qa=NextPos(pa,qa);break;case 0: //两者的指数值相等sum=a.coef+b.coef;if(sum!=0.0){//修改多项式PA中当前结点的系数值SetCurElem(qa,sum);ha=qa;}else{// 删除多项式PA中当前结点DelFirst(ha,qa); FreeNode(qa);}DelFirst(hb,qb); FreeNode(qb); qb=NextPos(Pb,hb);qa=NextPos(Pa,ha);break;case 1: //多项式PB中当前结点的指数值小DelFirst(hb,qb); InsFirst(ha,qb);qb=Nextpos(Pb,hb); ha=NextPos(Pa,ha);break;}//switch}//whileif(!ListEmpty(Pb)) Append(Pa,qb); //链接pb中剩余结点FreeNode(Pb): //释放Pb的头结点}//AddPolyn二、哈夫曼树及哈夫曼编码求哈夫曼树及编码的算法如下：Void HuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int *w,int n){//w存放n个字符的权值（均>0），构造哈夫曼树HT，并求n个字符的哈夫曼编码HC。

if(n<=1) return; m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用。

for(p=HT+1,i=1;i<=n,++i,++p,++w) *p={*w,0,0,0};for(;i<=m,++i,++p,) *p={0,0,0,0};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=s1; HT[i].rchild=s2;HT[i].weight= HT[s1].weight+ HT[s2].weight; }//从叶子到根逆向求每个字符的哈夫曼编码。

HC=(HaffmanCode)malloc((n+1)*sizeof(char *));//分配n个字符编码的头指针向量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”;eles cd[--start]=”1”;HC[i]=(char *)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间strcpy(HC[i],&cd[start]); //从cd复制编码（串）到HC }}free(cd); //释放工作空间}//HuffmanCoding第四章详细设计及实现代码表达式求值的源代码：#include "stdio.h"#include "stdlib.h"typedef struct polynode{int cofe;int exp;struct polynode *next;}PNode;PNode *Creat_Linkst(int n){PNode *head,*p,*s;int i;head=(PNode*)malloc(sizeof(PNode));head->next=NULL;p=head;printf("enter cofe,exp:\n");for(i=1;i<=n;++i){s=(PNode *)malloc(sizeof(PNode));scanf("%d,%d",&s->cofe,&s->exp);s->next=NULL;p->next=s;p=s;}return(head);}void polyADD(PNode *pa,PNode *pb){PNode *pre,*qa,*qb,*q;int sum;pre=pa;qa=pa->next;qb=pb->next;while(qa&&qb){if(qa->exp==qb->exp){sum=qa->cofe+qb->cofe;if(sum){qa->cofe=sum;pre=qa;}else{pre->next=qa->next;free(qa);}qa=pre->next;q=qb;qb=qb->next;free(q);}else{if(qa->exp>qb->exp){pre=qa;qa=qa->next;}else{pre->next=qb;pre=qb;qb=qb->next;pre->next=qa;}}}if(qb)pre->next=qb;free(pb);}void print_Linkst(PNode *H){PNode *p;p=H->next;while(p){printf("%dx^%d+",p->cofe,p->exp);p=p->next;} if(p->exp)printf("%dx^%d\n",p->cofe,p->exp);else printf("%d\n",p->cofe);}main(){PNode *HA,*HB;int la,lb;printf("enter la,lb:");scanf("%d,%d",&la,&lb);printf("\ncreat HA\n");HA=Creat_Linkst(la);printf("A(x)=");print_Linkst(HA);printf("\ncreat HB\n");HB=Creat_Linkst(lb);printf("B(x)=");print_Linkst(HB);polyADD(HA,HB);printf("\nA(x)=");}哈夫曼树和哈夫曼编码的程序：#define maxvalue 10000#define maxnodenumber 100#define maxbit 10typedef struct{int weight;int parent,lchild,rchild;}htnode;typedef struct{int bit[maxbit];int start;}hcodetype;typedef htnode *huffmantree;htnode ht[maxnodenumber];hcodetype cd[maxnodenumber];void crthuffmantree(int n){int i,j,m1,m2,k1,k2;for(i=0;i<2*n-1;i++){ht[i].weight=0;ht[i].parent=1;ht[i].lchild=1;ht[i].rchild=1;}printf("shuruyizuweight:\n");for(i=0;i<n;i++)scanf("%d",&ht[i].weight);printf("i weight parent lchild rchild\n");for(i=0;i<n-1;i++){m1=maxvalue;m2=maxvalue;k1=0;k2=0;for(j=0;j<n+i;j++)if(ht[j].parent==-1&&ht[j].weight<m1){m2=m1;k2=k1;m1=ht[j].weight;k1=j;}if(ht[j].parent==-1&&ht[j].weight<m2){m2=ht[j].weight;k2=j;}ht[k1].parent=n+i;ht[k2].parent=n+i;ht[n+i].weight=ht[k1].weight+ht[k2].weight;ht[n+i].lchild=k1;ht[n+i].rchild=k2;}for(i=0;i<2*n-1;i++){printf("%d %5d %5d %5d %5d\n",i,ht[i].weight,ht[i].parent,ht[i].l child,ht[i].rchild);printf("\n");}}/*crthuffmantree*/void gethuffmancode(htnode ht[],int n){int i,j,c,p;printf("code:%d\n",n);for(i=0;i<n;i++){c=i;j=maxbit;do{j--;p=ht[c].parent;if(ht[p].lchild==c)cd[i].bit[j]=0;elsecd[i].bit[j]=1;c=p;}while(p!=1);cd[i].start=j+1;/*根也置1，所以编码从下一位置始*/ }for(i=0;i<n;i++){printf("%d:",ht[i].weight);{for(j=cd[i].start;j<maxbit;j++)printf("%d",cd[i].bit[j]);printf("------i:%d,start:%d",i,cd[i].start);printf("\n");}}}/*gethuffmancode*/main(){int n;printf("shuru n:\n");scanf("%d",&n);crthuffmantree(n);printf("hufmancode:\n");gethuffmancode(ht,n);}第五章调试过程中的问题及系统测试情况在输入过程中，一定要细心。