数据结构实习报告12345

数据结构实习报告所在院系：班号：学号：专业：姓名：指导老师：二零一三年六月目录1一元多项式计算 21.1基本算法： 21.1.1输入输出 21.1.2多项式的加法 21.1.3多项式的减法 31.2程序： 41.3运行结果： 82设计一个模拟计算器的程序 82.1设计思路 82.2功能模块： 92.3程序： 92.4测试结果： 163学生成绩查询系统 163.1设计思路 163.2系统流程图： 173.3程序： 173.4测试结果： 204构造n个城市连接的最小生成树 204.1设计思路 214.2数据结构定义 214.3系统功能模块 224.4运行结果： 225哈夫曼编码的应用 235.1问题分析哈夫曼树的定义 235.2功能模块图 245.3程序： 245.4测试结果： 306实习总结： 301一元多项式计算

能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减和相乘，并将结果输出。1.1基本算法：1.1.1输入输出（1）功能：将要进行运算的多项式输入输出。（2）数据流入：要输入的多项式的系数与指数。（3）数据流出：合并同类项后的多项式。（4）程序流程图：多项式输入流程图如图1所示。（5）测试要点：输入的多项式是否正确，若输入错误则重新输入流程图：1.1.2多项式的加法（1）功能：将两多项式相加。（2）数据流入：输入函数。（3）数据流出：多项式相加后的结果。（4）程序流程图：多项式的加法流程图如图2所示。（5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算。流程图：1.1.3多项式的减法（1）功能：将两多项式相减。（2）数据流入：调用输入函数。（3）数据流出：多项式相减后的结果。（4）程序流程图：多项式的减法流程图如图3所示。（5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算。流程图：1.2程序：#include"stdafx.h"#include<stdio.h>#include<malloc.h>typedefstructPolynomial{floatcoef;intexpn;structPolynomial*next;}*Polyn,Polynomial;//Polyn为结点指针类型voidInsert(Polynp,Polynh){if(p->coef==0)free(p);//系数为0的话释放结点else{Polynq1,q2;q1=h;q2=h->next;while(q2&&p->expn<q2->expn){//查找插入位置q1=q2;q2=q2->next;}if(q2&&p->expn==q2->expn){//将指数相同相合并q2->coef+=p->coef;free(p);if(!q2->coef){//系数为0的话释放结点q1->next=q2->next;free(q2);}}else{//指数为新时将结点插入p->next=q2;q1->next=p;}}}//InsertPolynCreatePolyn(Polynhead,intm){//建立一个头指针为head、项数为m的一元多项式inti;Polynp;p=head=(Polyn)malloc(sizeof(structPolynomial));head->next=NULL;for(i=0;i<m;i++){p=(Polyn)malloc(sizeof(structPolynomial));//建立新结点以接收数据printf("请输入第%d项的系数与指数:",i+1);scanf("%f%d",&p->coef,&p->expn);Insert(p,head);//调用Insert函数插入结点}returnhead;}//CreatePolynvoidDestroyPolyn(Polynp){//销毁多项式pPolynq1,q2;q1=p->next;q2=q1->next;while(q1->next){free(q1);q1=q2;//指针后移q2=q2->next;}}voidPrintPolyn(PolynP){Polynq=P->next;intflag=1;//项数计数器if(!q){//若多项式为空，输出0putchar('0');printf("\n");return;}while(q){if(q->coef>0&&flag!=1)putchar('+');//系数大于0且不是第一项if(q->coef!=1&&q->coef!=-1){//系数非1或-1的普通情况printf("%g",q->coef);if(q->expn==1)putchar('X');elseif(q->expn)printf("X^%d",q->expn);}else{if(q->coef==1){if(!q->expn)putchar('1');elseif(q->expn==1)putchar('X');elseprintf("X^%d",q->expn);}if(q->coef==-1){if(!q->expn)printf("-1");elseif(q->expn==1)printf("-X");elseprintf("-X^%d",q->expn);}}q=q->next;flag++;}//whileprintf("\n");}//PrintPolynintcompare(Polyna,Polynb){if(a&&b){if(!b||a->expn>b->expn)return1;elseif(!a||a->expn<b->expn)return-1;elsereturn0;}elseif(!a&&b)return-1;//a多项式已空，但b多项式非空elsereturn1;//b多项式已空，但a多项式非空}//comparePolynAddPolyn(Polynpa,Polynpb){//求解并建立多项式a+b，返回其头指针Polynqa=pa->next;Polynqb=pb->next;Polynheadc,hc,qc;hc=(Polyn)malloc(sizeof(structPolynomial));//建立头结点hc->next=NULL;headc=hc;while(qa||qb){qc=(Polyn)malloc(sizeof(structPolynomial));switch(compare(qa,qb)){case1:{qc->coef=qa->coef;qc->expn=qa->expn;qa=qa->next;break;}case0:{qc->coef=qa->coef+qb->coef;qc->expn=qa->expn;qa=qa->next;qb=qb->next;break;}case-1:{qc->coef=qb->coef;qc->expn=qb->expn;qb=qb->next;break;}}//switchif(qc->coef!=0){qc->next=hc->next;hc->next=qc;hc=qc;}elsefree(qc);//当相加系数为0时，释放该结点}//whilereturnheadc;}//AddPolynPolynSubtractPolyn(Polynpa,Polynpb){//求解并建立多项式a+b，返回其头指针Polynh=pb;Polynp=pb->next;Polynpd;while(p){//将pb的系数取反p->coef*=-1;p=p->next;}pd=AddPolyn(pa,h);for(p=h->next;p;p=p->next)//恢复pb的系数p->coef*=-1;returnpd;}//SubtractPolynintmain(){intm,n,flag=0;floatx;Polynpa=0,pb=0,pc,pd,pe,pf;//定义各式的头指针，pa与pb在使用前付初值NULLprintf("请输入a的项数:");scanf("%d",&m);pa=CreatePolyn(pa,m);//建立多项式aprintf("请输入b的项数:");scanf("%d",&n);pb=CreatePolyn(pb,n);//建立多项式a//输出菜单printf("**********************************************\n");printf("操作提示：\n\t1.输出多项式a和b\n\t2.建立多项式a+b\n\t3.建立多项式a-b\n");printf("\t4.退出\n**********************************************\n");for(;;flag=0){printf("执行操作：");scanf("%d",&flag);if(flag==1){printf("多项式a：");PrintPolyn(pa);printf("多项式b：");PrintPolyn(pb);continue;}if(flag==2){pc=AddPolyn(pa,pb);printf("多项式a+b：");PrintPolyn(pc);DestroyPolyn(pc);continue;}if(flag==3){pd=SubtractPolyn(pa,pb);printf("多项式a-b：");PrintPolyn(pd);DestroyPolyn(pd);continue;}if(flag==4)break;if(flag<1||flag>4)printf("Error!!!\n");continue;}//forDestroyPolyn(pa);DestroyPolyn(pb);return0;}1.3运行结果：2设计一个模拟计算器的程序

要求对包含加、减、乘、除、括号运算符的任意整型表达式进行求解。2.1设计思路表达式：任何表达式都是由操作数、运算符和界限符组成的有意义的式子。 表达式求值时一般有后缀表示、中缀表示、前缀表示。操作数：可以是常数、变量、常量。运算符：从运算对象上分有单目运算符、双目运算符、三目运算符。界限符：左右括号和表达式结束符。思路：我们平时用到的表达式即为我们所输入的表达式（以‘#’结束），此表达式为中缀表达式，只要将此表达式利用栈来进出运算的符号转换为后缀表达式，之后利用栈来进出运算的数字将后缀表达式的值求出即可。2.2功能模块：判断字符是否为操作数函数intisnum(char)

当输入表达式时要利用栈对表达式中的数字和符号进行进栈出栈，因此要判断表达式中的内容是操作数、运算符还是界限符，给出相关信息。求运算符优先级函数intpriority(char)

对输入的表达式中的内容，若为运算符和界限符则要判断其优先级已完成其计算的先后顺序。中缀表达式转换为后缀表达式函数intinfix_exp_value(char*,char*)

我们平时使用的为中缀表达式，但若利用栈则利用后缀表达式比较容易计算，因此要将中缀表达式转换为后缀表达式，具体算法步骤如下：

<1>count=0，初始化运算符栈s，将结束符‘#’加入运算符栈s中。

<2>读表达式字符=>w。

<3>当栈顶为‘#’并且w也是‘#’时结束；否则循环做下列步骤：

<3.1>如果w是操作数判断若count==0直接输出,读下一个字符=>w;转<3>。若count!=0追加字符’@’,读下一个字符=>w,转<3>。

<3.2>w若是运算符，则：count=1;

<3.2.1>如果栈顶为‘（’并且w为‘）’则‘（’出栈不输出，读下一个字

符=>w，转<3>。

<3.2.1>如果栈顶为‘（’或者栈顶优先级小于w优先级，则w入栈，读下

一个字符=>w，转<3>。否则：从运算符栈中出栈并输出，转<3>后缀表达式的求值函数doublepostfix_exp(char*)

使用一个操作数栈，当从左到右扫描表达式时，每遇到一个操作数就送入栈中保存，

如果操作数不止一位，则保存在operand中，遇到下一个操作数时，执行operand=operand*10+(ch-'0')，便可将操作数转化为数字。每遇到一个运算符就从栈中取出两个操作数进行当前的计算，然后把结果在入栈，直到整个表达式结束，这时送入栈顶的值就是结果。2.3程序：#include"stdafx.h"#include<stdio.h>#include<malloc.h>#include<conio.h>#definemaxsize100typedefdoubledatatype1;typedefchardatatype2;typedefstructstack1{datatype1data1[maxsize];inttop1; /*栈顶元素*/}seqstack1,*pseqstack1;/*顺序栈*/typedefstructstack2{datatype2data2[maxsize];inttop2; /*栈顶元素*/}seqstack2,*pseqstack2;/*顺序栈*//*栈的初始化*/pseqstack1init_seqstack1(void){pseqstack1S;S=(pseqstack1)malloc(sizeof(pseqstack1));if(S)S->top1=-1;returnS;}pseqstack2init_seqstack2(void){pseqstack2S;S=(pseqstack2)malloc(sizeof(pseqstack2));if(S)S->top2=-1;returnS;}/*判断栈空*/intempty_seqstack1(pseqstack1S){if(S->top1==-1)return1;elsereturn0;}intempty_seqstack2(pseqstack2S){if(S->top2==-1)return1;elsereturn0;}/*X入栈*/intpush_seqstack1(pseqstack1S,datatype1X){if(S->top1==maxsize-1){printf("栈满，无法入栈！\n");return0;}else{S->top1++;S->data1[S->top1]=X;return1; }}intpush_seqstack2(pseqstack2S,datatype2X){if(S->top2==maxsize-1){printf("栈满，无法入栈！\n");return0;}else{S->top2++;S->data2[S->top2]=X;return1; }}/*X出栈*/intpop_seqstack1(pseqstack1S,datatype1*X){if(empty_seqstack1(S))return0;else{*X=S->data1[S->top1];S->top1--;return1; }}intpop_seqstack2(pseqstack2S,datatype2*X){if(empty_seqstack2(S))return0;else{*X=S->data2[S->top2];S->top2--;return1; }}/*求栈顶元素*/intgettop_seqstack1(pseqstack1S,datatype1*X){if(empty_seqstack1(S))return0;else*X=S->data1[S->top1];return1; }intgettop_seqstack2(pseqstack2S,datatype2*X){if(empty_seqstack2(S))return0;else*X=S->data2[S->top2];return1; }/*判断字符是否为操作数。若是返回1，否则返回0*/intisnum(charc){if(c>='0'&&c<='9')return1;elsereturn0;}/*求后缀表达式的值*/doublepostfix_exp(char*A){pseqstack1S; /*定义栈S*/ doubleoperand=0;doubleresult; /*存放栈顶元素*/ doublea; /*运算符ch前的操作数出栈存入a*/ doubleb; /*运算符ch后的操作数出栈存入b*/ doublec; /*c==achb*/charch; /*存放读取到的表达式(A)的字符*/ch=*A++; /*读表达式字符=>A*/S=init_seqstack1(); /*初始化栈*/while(ch!='#')/*遇到元素!='#'时*/{if(isnum(ch))/*判断ch是否为数字字符,计算出操作数*/operand=operand*10+(ch-'0');else /*否则*/ { if(operand) { push_seqstack1(S,operand);/*当前字符不是数字,操作数结束,要入栈*/ operand=0; } if(ch!='@'&&ch!='') { pop_seqstack1(S,&b); /*运算符ch后的操作数出栈存入b*/ pop_seqstack1(S,&a); /*运算符ch前的操作数出栈存入a*/ switch(ch) /*求achb==?,将结果赋给c*/ { case'+': c=a+b; break; case'-': c=a-b; break; case'*': c=a*b; break; case'/': if(b!=0) c=a/b; else printf("分母为零!"); } push_seqstack1(S,c); /*将c压入栈中*/ } }ch=*A++; /*指针向下移动一位*/}/*遇到'#'循环结束*/gettop_seqstack1(S,&result);/*此时栈顶元素即为计算结果result*/returnresult;}/*优先级判断函数*/intpriority(charop){ switch(op) { case'#':return1; case')':return2; case'+': case'-':return3; case'*': case'/':return4; case'(':return5; default:return0; } }/*将指针infixexp指向的中缀表达式转换为指针postfixexp指向的后缀表达式*/intinfix_exp_value(char*infixexp,char*postfixexp){ pseqstack2S; /*定义栈S*/ intcount=0; charw; /*存放读取到的表达式(infixexp)的字符*/ charc; /*存放栈顶元素*/ chartopelement;/*存出栈元素*/ S=init_seqstack2(); /*初始化栈*/ if(!S) /*栈的初始化判断*/ { printf("栈初始化失败!"); return0; } push_seqstack2(S,'#'); /*将结束符'#'加入运算符栈S中*/ w=*infixexp; /*读表达式字符=>w*/ while((gettop_seqstack2(S,&c),c)!='#'||w!='#')/*<3>栈顶元素不等于'#'或w不等于'#'时循环*/ { if(isnum(w))/*判断w是否为操作数,若是直接输出,读下一个字符=>w,转<3>*/ { if(count) { *postfixexp='@'; postfixexp++; count=0; } *postfixexp=w; postfixexp++; w=*(++infixexp); } else /*w若是运算符分类如下*/ { count=1; if((gettop_seqstack2(S,&c),c)=='('&&w==')') {/*如果栈顶为'('并且w为')'则'('出栈不输出,读下一个字符=>w,转<3>*/ pop_seqstack2(S,&topelement);/*将'('出栈存入topelement*/ w=*(++infixexp); } else if((gettop_seqstack2(S,&c),c)=='('||priority((gettop_seqstack2(S,&c),c))<priority(w)) {/*如果栈顶为'('或者栈顶优先级小于w优先级,则w入栈,读下一个字符=>w，转<3>*/ push_seqstack2(S,w); w=*(++infixexp); } else/*否则*/ {/*从运算符栈中出栈并输出,转<3>*/ pop_seqstack2(S,&topelement); *postfixexp=topelement; postfixexp++; } } } *postfixexp='#';/*在指针postfixexp指向的后缀表达式结尾追加字符'#'*/ *(++postfixexp)='\0';/*在指针postfixexp指向的后缀表达式最后追加结束符'\0'*/ return1;}/*主函数*/intmain(){ inti=0; charA[maxsize]; charB[maxsize]; printf("请输入表达式,如:45+36#,必须以#号结尾!\n"); A[i]=getchar(); while(A[i++]!='#') { A[i]=getchar(); } A[i]='\0'; infix_exp_value(A,B); printf("A==%s\n",A); printf("B==%s\n",B); printf("上式的结果为:"); printf("%g\n",postfix_exp(B)); return0;getch();}2.4测试结果：1）输入11+（9-3）*（8/2）#2)输入3+(1/8)*(16-7)#3学生成绩查询系统

按学号排序后对学号进行折半查找。随机输入以学号为关键字的学生信息并构建二叉排序树，对学号进行二叉排序树查找。3.1设计思路这个程序主要是实现按学号对8名学生的信息进行查找，其中查找方式分为三种：顺序查找、折半查找、二叉排序树查找。由于顺序查找、折半查找很容易实现，而二叉排序树查找需要构建二叉排序树，再进行二叉排序树查找，所以在这一步骤上有点难度。学生信息包括序号、姓名、成绩，其中学号和姓名都是由字符实现，成绩由整形实现。在输入学生信息时直接按学号顺序输入，这样便省去了在程序中对学生的学号从新进行排序，在二叉排序树的查找过程中，只能查找那些参与构建二叉排序树的学号，二叉排序树是以第一个输入的学生学号为根结点构造二叉排序树的。3.2系统流程图：3.3程序：#include"stdafx.h"#include<stdio.h>#include<string.h>#include<stdlib.h>typedefstruct{ charsno[11]; //学号 charname[16]; //姓名 intscore; //成绩}student;typedefstructBinSTreeNode{ charhao[11]; charming[16]; intfen; structBinSTreeNode*lchild; structBinSTreeNode*rchild;}*BTree;intshun_search(studentstu[],intn,charx[]){ inti,j; for(i=0;i<n;i++) if(strcmp(stu[i].sno,x)==0) { printf("所查找的学生信息如下：\n学号\t姓名\t成绩\n"); printf("%s%s%d",stu[i].sno,stu[i].name,stu[i].score); return0; } }intzhe_search(studentstu[],intn,charx[]){ intlow,mid,high; low=0;high=n-1; while(low<=high) { mid=(low+high)/2; if(strcmp(stu[mid].sno,x)==0) { printf("所查找的学生信息如下：\n学号\t姓名\t成绩\n"); printf("%s%s%d",stu[mid].sno,stu[mid].name,stu[mid].score); return0; } elseif(strcmp(stu[mid].sno,x)>0)high=mid-1; elselow=mid+1; } return0;}voidBSTree(BTree*t,studentk){ BTreer; if(*t==NULL) { r=(BTree)malloc(sizeof(structBinSTreeNode)); strcpy(r->hao,k.sno); strcpy(r->ming,); r->fen=k.score; r->lchild=r->rchild=NULL; *t=r; return; }else if(strcmp(k.sno,((*t)->ming))<=0) BSTree(&((*t)->lchild),k); else BSTree(&((*t)->rchild),k);}BTreeBSTreeSearch(BTreet,charx[]){ if(t==NULL)returnNULL; if(strcmp(t->hao,x)==0)returnt; if(strcmp(t->hao,x)>=0) returnBSTreeSearch(t->lchild,x); else returnBSTreeSearch(t->rchild,x);}main(){ studentstu[40]; inti,j,k,n,b; charx[12]; printf("\n\t学生成绩查询系统\n\n"); printf("请输入本次统计的学生数："); scanf("%d",&n); printf("\n请输入这些学生的信息：\n"); printf("\t学号\t姓名成绩\n"); for(i=0;i<n;i++) { printf("学生%d",i+1); scanf("%s%s%d",&stu[i].sno,&stu[i].name,&stu[i].score); } printf("信息输入完毕...\n\n"); printf("请输入你需要查找的学生号："); scanf("%s",x); printf("\n下面进行顺序查找:\n"); shun_search(stu,n,x); printf("\n\n下面进行折半查找:\n"); zhe_search(stu,n,x); printf("\n\n下面进行二叉排序树的查找"); printf("\n输入构造二叉树学号的个数："); scanf("%d",&b); BTreeT; T=(BTree)malloc(sizeof(structBinSTreeNode)); T=NULL; for(i=0;i<b;i++) { printf("输入你的第%i学号：",i+1); scanf("%s",x); for(j=0;j<n;j++) if(strcmp(stu[j].sno,x)==0) k=j; BSTree(&T,stu[k]); } printf("信息输入完毕...\n"); printf("二叉排序树构建成功...\n"); printf("\n输入你想要在此二叉排序树中查找的学号："); scanf("%s",x); BTrees; s=(BTree)malloc(sizeof(structBinSTreeNode)); s=BSTreeSearch(T,x); printf("所查找的学生信息如下：\n学号\t姓名\t成绩\n"); printf("%s%s%d\n\n",s->hao,s->ming,s->fen); }3.4测试结果：4构造n个城市连接的最小生成树

一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。基本要求：

1)城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。2)表示城市间距离网的邻接矩阵(要求至少6个城市，10条边)4.1设计思路本程序需要实现在一个具有权值的n个城市间的有向距离网中，通过调用函数建立最小生成树，并通过计算求得各个城市之间最小的权值。在设计程序时通过gnodevalue数组直接对各个城市之间的信息进行设置，而不是手动输入。城市的个数也默认设置为6个，路的个数也只设置成十个，所以在程序运行时不需要输入城市的相关信息。由于能力不足，在最后打印两个城市之间最短路径时，只显示路径所经过的顶点，而不是一次经过的顶点。4.2数据结构定义本程序的主要内容是通过函数调用构建最小生成树，实现求的两个城市之间的最短路径，并通过函数调用打印出来最短路径所经过的顶点，所有本程序便定义了三个结构体，每个结构体的作用如下所示。以及这六个城市和十条边的图也在下面显示出来：typedefcharvertextype[7];typedefcharinfoptr;typedefintvrtype;typedefenum{DG,DN,UG,UN}graphkind;typedefstruct{ vrtypeadj; //对于无权图，用1表示相邻，0表示不相邻，对于带权图，存储权值 infoptr*info; //与弧或边的相关信息}arcnode,adjmatrix[max][max];typedefstruct //图的类型定义{ vertextypevex[max]; //用于存储顶点 adjmatrixarc; //邻接矩阵、存储边或弧的信息 intvexnum,arcnum; //顶点数和边（弧）的数目 graphkindkind; //图的类型}mgraph;typedefstruct{ //添加一个存储网的行、列和权值的类型定义 introw; intcol; intweight;}gnode;4.3系统功能模块4.4运行结果：5哈夫曼编码的应用（1）哈夫曼树的建立哈夫曼编码的生成编码文件的译码5.1问题分析哈夫曼树的定义1.哈夫曼树节点的数据类型定义为：typedefstruct{//赫夫曼树的结构体 charch; intweight;//权值 intparent,lchild,rchild;}htnode,*hfmtree;2）所实现的功能函数如下1、voidhfmcoding(hfmtree&HT,hfmcode&HC,intn)初始化哈夫曼树，处理InputHuffman(HuffmanHfm)函数得到的数据，按照哈夫曼规则建立2叉树。此函数块调用了Select（）函数。voidSelect(hfmtree&HT,inta,int*p1,int*p2)//Select函数，选出HT树到a为止，权值最小且parent为0的2个节点2、intmain()主函数：利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.txt中读入）对文件中的正文进行编码，然后将结果存入文件codefile.txt中。如果正文中没有要编码的字符，则键盘读入并存储到ToBeTran文件中。读入ToBeTran中将要编码的内容，将编码好的哈夫曼编码存储到CodeFile中。3、Encoding编码功能：对输入字符进行编码4、Decoding译码功能：利用已建好的哈夫曼树将文件codefile.txt中的代码进行译码，结果存入文件textfile.dat中。Print()打印功能函数：输出哈夫曼树，字符，权值，以及它对应的编码。5.主函数的简要说明，主函数主要设计的是一个分支语句，让用户挑选所实现的功能。使用链树存储，然后分别调用统计频数函数，排序函数，建立哈夫曼函数，编码函数，译码函数来实现功能。5.2功能模块图5.3程序：#include"stdafx.h"#include<iostream.h>#include<stdio.h>#include<stdlib.h>#include<string.h>#include<fstream.h>typedefstruct{//赫夫曼树的结构体 charch; intweight;//权值 intparent,lchild,rchild;}htnode,*hfmtree;typedefchar**hfmcode;voidSelect(hfmtree&HT,inta,int*p1,int*p2)//Select函数，选出HT树到a为止，权值最小且parent为0的2个节点{ inti,j,x,y; for(j=1;j<=a;++j){ if(HT[j].parent==0){ x=j; break; } } for(i=j+1;i<=a;++i){ if(HT[i].weight<HT[x].weight&&HT[i].parent==0){ x=i;//选出最小的节点 } } for(j=1;j<=a;++j) { if(HT[j].parent==0&&x!=j) { y=j; break; } } for(i=j+1;i<=a;++i) { if(HT[i].weight<HT[y].weight&&HT[i].parent==0&&x!=i) { y=i;//选出次小的节点 } } if(x>y){ *p1=y; *p2=x; } else { *p1=x; *p2=y; }}voidhfmcoding(hfmtree&HT,hfmcode&HC,intn)//构建赫夫曼树HT，并求出n个字符的赫夫曼编码HC{ inti,start,c,f,m,w; intp1,p2; char*cd,z; if(n<=1){ return; } m=2*n-1; HT=(hfmtree)malloc((m+1)*sizeof(htnode)); for(i=1;i<=n;++i)//初始化n个叶子结点 { printf("请输入第%d字符信息和权值：",i); scanf("%c%d",&z,&w); while(getchar()!='\n') { continue; } HT[i].ch=z; HT[i].weight=w; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } for(;i<=m;++i)//初始化其余的结点 { HT[i].ch='0'; HT[i].weight=0; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } for(i=n+1;i<=m;++i)//建立赫夫曼树 { Select(HT,i-1,&p1,&p2); HT[p1].parent=i;HT[p2].parent=i; HT[i].lchild=p1;HT[i].rchild=p2; HT[i].weight=HT[p1].weight+HT[p2].weight; } HC=(hfmcode)malloc((n+1)*sizeof(char*)); cd=(char*)malloc(n*sizeof(char)); cd[n-1]='\0'; for(i=1;i<=n;++i)//给n个字符编码 { 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);}intmain(){ charcode[100],h[100],hl[100]; intn,i,j,k,l; ifstreaminput_file;//文件输入输出流 ofstreamoutput_file; charchoice,str[100]; hfmtreeHT; hfmcodeHC; cout<<"\n"; cout<<""<<""<<""<<""<<""<<"\n"; while(choice!='Q'&&choice!='q')//当choice的值不为q且不为Q时循环 { cout<<""<<"*************************赫夫曼编码/译码器*************************\n"; cout<<""<<"I.Init"<<""<<"E.Encoding"<<""<<"D.Decoding"<<""<<"Q.Exit\n"; cout<<"请输入您要操作的步骤："; cin>>choice; if(choice=='I'||choice=='i')//初始化赫夫曼树 { cout<<"请输入字符个数："; cin>>n; hfmcoding(HT,HC,n); for(i=1;i<=n;++i) { cout<<HT[i].ch<<":"<<HC[i]<<endl; } output_file.open("hfmTree.txt"); if(!output_file){ cout<<"can'toenfile!"<<endl; return1; } for(i=1;i<=n;i++) { output_file<<"("<<HT[i].ch<<HC[i]<<")"; } output_file.close(); cout<<"赫夫曼树已经创建完毕