数据结构教程-李春葆-七章习题答案

若发现答案有错处，请留言于下面空间万分感谢！！7.3/******************************************题目：设给定权集w={2,3,4,7,8,9}，设构成关于w的一颗哈夫曼树，并求其带权路径长度WPL设计;狼影时间：2012.10.5***************************************//******************************************************若发现错误请留言本空间，万分感谢！！/*******************/#includestdio.h#definesize100typedefstruct{intweight;intlchild;intrchild;intparent;}HTNODE;typedefstruct{inth[size];//存放当前节点的编码intlength;//存放节点编码的长度}HCNODE;//函数声明voidcreat_htree(HTNODE*ht,intn);voidout_htree(HTNODE*ht,intn);voidcreat_hcnode(HTNODE*ht,HCNODE*hc,intn);voidout_hctree(HTNODE*ht,HCNODE*hc,intn);main(){inti;intn;HTNODEht[size];HCNODEhc[size];printf(输入叶子节点的个数\n);scanf(%d,&n);printf(输入%d个叶子的权值\n,n);for(i=0;in;i++)scanf(%d,&ht[i].weight);//构建哈夫曼树creat_htree(ht,n);/*输出哈夫曼树；；如果只为做题下面的输出函数可以不要*/printf(哈夫曼树顺序存储如下\n);out_htree(ht,n);//求哈夫曼编码creat_hcnode(ht,hc,n);printf(各节点的编码以及带权路径长度如下\n);out_hctree(ht,hc,n);}//构建二叉树voidcreat_htree(HTNODE*ht,intn){inti,j;intmin1,min2;//用来暂时存放两个最小值intlnode,rnode;//存放两个最小值在数组中的下标，一个作为左孩子，一个为右孩子//初始化，把双亲域与左右孩子域设为-1for(i=0;i2*n-1;i++)//定理：具有n个叶子节点的哈夫曼树，共有2*n-1个节点ht[i].lchild=ht[i].parent=ht[i].rchild=-1;//将数组分为两部分for(i=n;i2*n-1;i++){min1=min2=8000;//此处的值尽可能的大（要大于节点中权值最大的值）lnode=rnode=-1;//在下标为i的前面的数组中寻找两个权值最小的节点，作为孩子节点for(j=0;ji;j++){if(-1==ht[j].parent){if(min1ht[j].weight){min2=min1;//至于为什么有这句和下面的一句，，大家依次将权值假设为213带入里面自己手工模仿运行lnode=rnode;//一下，感觉一下，有这两句和没这两句的区别（看是否两次得到的两个最小值结果一样）min1=ht[j].weight;rnode=j;}elseif(min2ht[j].weight){lnode=j;min2=ht[j].weight;}}}//下标为i处的节点作为父节点，下标lnode为左孩子节点，下标为rnode为有孩子节点ht[i].weight=ht[lnode].weight+ht[rnode].weight;ht[i].lchild=lnode;ht[i].rchild=rnode;//（lnodernode处）左右孩子的父节点同为i处的节点ht[lnode].parent=i;ht[rnode].parent=i;}}//输出哈夫曼树voidout_htree(HTNODE*ht,intn){inti;printf(\n-------------------------------------------------------------\n);printf(下标;);for(i=0;i2*n-1;i++)printf(%5d,i);printf(\n-------------------------------------------------------------\n左孩子:);for(i=0;i2*n-1;i++)printf(%5d,ht[i].lchild);printf(\n-------------------------------------------------------------\n权值:);for(i=0;i2*n-1;i++)printf(%5d,ht[i].weight);printf(\n-------------------------------------------------------------\n右孩子:);for(i=0;i2*n-1;i++)printf(%5d,ht[i].rchild);printf(\n-------------------------------------------------------------\n);}//求出哈夫曼编码voidcreat_hcnode(HTNODE*ht,HCNODE*hc,intn){HCNODEpNow;intchild,father;inti;//从各个叶子节点往上编码，for(i=0;in;i++){pNow.length=0;child=i;father=ht[child].parent;//当前叶子节点的父节点while(-1!=father){if(child==ht[father].lchild)//当前孩子节点为父节点的左孩子时，编码为0，否则为1{pNow.h[pNow.length]=0;pNow.length++;}else{pNow.h[pNow.length]=1;pNow.length++;}//接着往上编码，直到父根节点child=father;father=ht[child].parent;}hc[i]=pNow;//整体赋值，在这看出pNow的作用了吧}}//求带权路径长voidout_hctree(HTNODE*ht,HCNODE*hc,intn){intsum=0;inti,j,k;for(i=0;in;i++){k=0;printf(%d:,ht[i].weight);for(j=hc[i].length-1;j=0;j--){k++;printf(%d,hc[i].h[j]);}printf(\n);sum+=ht[i].weight*k;}printf(带权路径是长度%d\n,sum);}/*************************************************************输入叶子节点的个数6输入6个叶子的权值234789哈夫曼树顺序存储如下-------------------------------------------------------------下标;012345678910-------------------------------------------------------------左孩子:-1-1-1-1-1-116479-------------------------------------------------------------权值:23478959151833-------------------------------------------------------------右孩子:-1-1-1-1-1-102358-------------------------------------------------------------各节点的编码以及带权路径长度如下2:00013:00004:0017:118:109:01带权路径是长度80Pressanykeytocontinue7.4/************************************题目：一颗具有n个节点的完全二叉树以顺序方式存储在数组A中，设计一个算法构造二叉树的二叉链存储结构设计：狼影时间:2012.10.5********************************************************/#includestdio.h#includestdlib.h#includestring.h#definesize100typedefstructnode{charch;structnode*lchild;structnode*rchild;}BTNODE;//函数声明BTNODE*cerat_btree(char*st,intn,intk);voidout_btree(BTNODE*pHead);main(){charA[size];intn;BTNODE*pHead;//按照完全二叉树的的编号方式，输入相应的字符，空的话输入'#'(如对完全二叉树编号不明白，请参考本课本p160)printf(输入二叉树顺序存储的字符串\n);A[0]='#';//不用下标0gets(&A[1]);//从下标1开始存放有效数据n=strlen(A);//创建二叉树pHead=cerat_btree(A,n-1,1);//在这我采用层次遍历的方式输出，你也可以用其余的方式printf(层次遍历二叉树输出如下\n);out_btree(pHead);printf(\n);}//创建二叉树BTNODE*cerat_btree(char*st,intn,intk){BTNODE*pNew;if(kn)returnNULL;if('#'==st[k])returnNULL;pNew=(BTNODE*)malloc(sizeof(BTNODE));if(NULL==pNew){printf(内存分配错误\n);exit(-1);}pNew-ch=st[k];pNew-lchild=cerat_btree(st,n,2*k);pNew-rchild=cerat_btree(st,n,2*k+1);returnpNew;}//层次遍历输出二叉树内容voidout_btree(BTNODE*pHead){BTNODE*pNow;BTNODE*queue[size];intfront=-1;intrear=-1;if(pHead){rear=(rear+1)%size;queue[rear]=pHead;while(rear!=front){front=(front+1)%size;pNow=queue[front];printf(%c,pNow-ch);if(pNow-lchild){rear=(rear+1)%size;queue[rear]=pNow-lchild;}if(pNow-rchild){rear=(rear+1)%size;queue[rear]=pNow-rchild;}}}}/***************************************输入二叉树顺序存储的字符串ABCD#EF#G##H##L层次遍历二叉树输出如下ABCDEFGHLPressanykeytocontinue**************************************************************/7.5/**************************