数据结构实习报告12345

5.2 功能模块图

5.3 程序：

#include \#include #include #include #include #include

typedef struct{ //赫夫曼树的结构体 char ch; int weight; //权值 int parent,lchild,rchild; }htnode,*hfmtree;

typedef char **hfmcode;

void Select(hfmtree &HT,int a,int *p1,int *p2) //Select函数，选出HT树到a为止，权值最小且parent为0的2个节点 { int i,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

24

} } for(i=j+1;i<=a;++i) { if(HT[i].weighty){ *p1=y; *p2=x; } else { *p1=x; *p2=y; } }

void hfmcoding(hfmtree &HT,hfmcode &HC,int n) //构建赫夫曼树HT，并求出n个字符的赫夫曼编码HC { int i,start,c,f,m,w; int p1,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字符信息和权值：\scanf(\while(getchar()!='\\n') { continue; }

HT[i].ch=z;

HT[i].weight=w; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0;

25

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); }

int main(){

26

char code[100],h[100],hl[100]; int n,i,j,k,l;

ifstream input_file; //文件输入输出流 ofstream output_file; char choice,str[100]; hfmtree HT; hfmcode HC; cout<<\

cout<<\ \ \ \ \ \ \\n\

while(choice!='Q'&&choice!='q') //当choice的值不为q且不为Q时循环 { cout<<\ \赫夫曼编码/译码器*************************\\n\ cout<<\ \ \ \ \

cout<<\请输入您要操作的步骤：\ cin>>choice;

if(choice=='I'||choice=='i') //初始化赫夫曼树 {

cout<<\请输入字符个数：\ cin>>n; hfmcoding(HT,HC,n); for(i=1;i<=n;++i) { cout<

27