作业题！有代价的。
QQ:627382551

//一下是编码程序///////////head01.h/////////////////
#ifndef    HEAD_FILE01
#define HEAD_FILE01
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<stdlib.h>
#include<windows.h>
#include"stack.h"
////////////////
typedef struct T{    //树结点定义
    char data;       //数据
    int cost;       //权
    int parent;       //父母
    int lchild;       //左孩子
    int rchild;       //右孩子
}TreeNode,*Huftree;

typedef struct C{
    char c;           //字符
    int cost;      //权重
}charlist,*pcharlist;

//////////////////////////////////// 主要函数
pcharlist change(char *str,int &longth);//由字符串生成带权的字符集表//longth:字符集表长度

void madetree(Huftree &tree,pcharlist l,int longth);//由带权的字符集表生成树~~~什么时候开花结果~~

void Select(Huftree ,int longth,int &s1,int &s2);//在带权的森林中找出权最小的两个树(s1<=s2)

char* changetocode(char *str,Huftree tree);//由树生成编码~~~~~~~~什么时候能做好~~~~~~

//////////////////////////////////////辅助函数

int Findchar(char *str,char c);//从字符串中查找字符  返回字符数量

void outputtree(Huftree); //输出树//

Stack  loadtree(Huftree tree,int n,char *str);//遍历树//返回树的结点//递归调用//未定义

int loadcode(Stack &st,Huftree tree,int n,char c);//在树中对查找C并将应的编码入栈

void outputstack(Stack st);//输出栈的信息

void treetext(Huftree tree);//将哈夫曼树生成文本文件并保存//用于解码用

void begin();//程序运行函数；



/////////////stack.h//////////////////////////////
#define HEAD01_FILE    
/////////////////////
#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
#define TEST printf("her is OK!!\n");
typedef struct N{
    int data;
    struct N *next;
    struct N*per;
}stacknode,*PN;//栈的结点
typedef struct S{  //栈的属性
    PN base;
    PN top;         //为栈顶元素//有数据
    int lenth;
    char *remark;//备注    
}Stack,*PS;

void  InitStack(Stack &st,char *str){
    st.base=st.top=(PN)malloc(sizeof(stacknode));
    st.lenth=0;
    st.remark=(char*)malloc(sizeof(char)*32);
    strcpy(st.remark,str);
}
int Pop(Stack &st)    //弹出元素
{     int d;
    if(st.lenth!=0){
        st.top=st.top->per;    
        free(st.top->next);
        d=st.top->data;            
        st.lenth-=1;
    }
    else d=-1; //表示空栈
    return d;
}
void  Push(Stack &st,int d)  //
{
    st.top->data=d;
    st.top->next=(PN)malloc(sizeof(stacknode));
    st.top->next->per=st.top;
    st.top=st.top->next;
    st.lenth+=1;
}

void outputstack(Stack st)
{
    PN p;
    p=st.base;
    for(int i=0;i<st.lenth;i++,p=p->next)
        printf("**%d** : [ %d ]\n",i+1,p->data);
}

#endif

                                   实习报告
一、程序简介

将任意长度的英语文本文件(不能含有换行)转化生成二进制的哈夫曼编码存放在指定的文本文件中,
并且生成treecode.txt文件,存放树的结构信息以便于解码时使用.

二、概要设计
数据类型定义极其用途
(1)struct C{////////用于构成链表,存放带权的字符
    char c;           //字符
    int cost;      //权重
}charlist,*pcharlist


(2):typedef struct T{    //生成哈夫曼树的结点单位,
    char data;       //数据
    int cost;       //权
    int parent;       //父母
    int lchild;       //左孩子
    int rchild;       //右孩子
}TreeNode,*Huftree;

(3):struct N{//栈的结点
    int data;
    struct N *next;
    struct N*per;
}stacknode,*PN;

(4):struct S{  //栈的属性
    PN base;
    PN top;         //为栈顶元素//有数据
    int lenth;
    char *remark;//备注    
}Stack,*PS;

函数极其功能见head01.h 和stack.h

储存结构

(1):带权的字符链表由顺序表实现,其长度(len)由文本文件的字符集确定
它负责存放文本文件中不同的字符,权就是该字符在文本文件中出现的次数

(2):树的结构采用顺序的储存,储存空间的长度就是[带权的字符链表]的二倍,
空间的后半部分存放的是字符链表的所有字符极其权;前面的存放树枝;多了的
一个空间就是[0]的位置,可以将树的根结点(位置是树长度/2-1)作为[0]
的左孩子,这样会方便一点;[0]的权就是树的空间长度;

(3):栈的储存采用动态储存的方式,这样有利于节约空间和动态分配

重点函数简介(大概运行过程)

void begin();函数定义两个字符串,分别用于存放原文件位置和编码文件位置
其中调用了文件处理的函数fopen(),fgets(),…………还调用了程序中定义其他函数

pcharlist change(char *str,int &longth);该函数负责将字符串转化为带权的字符链表

void madetree(Huftree &tree,pcharlist l,int longth)//由带权的字符集表生成树;利用最小生成树
的原理,从树堆中找出权最小的;两个树构成新的树,加入到树堆中去

void Select(Huftree ,int longth,int &s1,int &s2);//在带权的森林中找出权最小的两个树(s1<=s2)

Stack  loadtree(Huftree tree,int n,char *str);//将文本文件字符串的每一个字符生成编码

int loadcode(Stack &st,Huftree tree,int n,char c);//在树中对查找C并将应的编码入栈//递归调用

最后由void begin()将生成的编码写入文件;

////////////////FUNCTION.CPP///////
#include"head01.h"
pcharlist change(char *str,int &longth)//由字符串生成带权的字符集表//longth:字符集表长度
{ 
    int i=0,j=0;
    char *s;
    pcharlist list1;    
    s=(char*)malloc(sizeof(char)*strlen(str));
    for(;i<strlen(str);i++) //遍历字符串//找出不相同的字符生成新串s
        if(!Findchar(s,str[i]))
        {
            s[j]=str[i];
            j++;
        }
        longth=j;
        list1=(pcharlist)malloc(sizeof(charlist)*(j));//这句为什么曾经错误 很严重耶        
        for(i=0;i<j;i++){                     
            (list1+i)->c=s[i];
            (list1+i)->cost=Findchar(str,s[i]);
        }        
        return list1;
}                       
/////////////////////////////                      
void madetree(Huftree &tree,pcharlist l,int longth)//由带权的字符集表生成树~~~什么时候开花结果~~
{
    int i,j=0;
    int s1,s2,len; 
    len=2*longth;    
    tree=(Huftree)malloc(sizeof(TreeNode)*(len));
    for(i=longth;i<len;i++){//将字符生成只有一个根的树放在longth-1 ~~~2*longth-1中
        //根的父母为[0] 孩子的父母是对tree的相对位移(整数)//刚好存放字符集表
        (tree+i)->cost=(l+j)->cost;
        (tree+i)->data=(l+j)->c;
        (tree+i)->lchild=0;
        (tree+i)->parent=0;
        (tree+i)->rchild=0;
        j++;     
    } //for
    for(i=1;i<longth;i++){     //longth-1个空间//刚好存放树枝
        Select(tree,len,s1,s2);    
        (tree+i)->lchild=s1;
        (tree+i)->rchild=s2;
        (tree+s1)->parent=i;
        (tree+s2)->parent=i;
        (tree+i)->parent=0;
        (tree+i)->cost=(tree+s1)->cost+(tree+s2)->cost;    
         //printf("我是：[ %d ] \n",i);printf("左孩子:[%d] 右孩子:[%d]\n",(tree+i)->lchild,(tree+i)->rchild);        
    }//哈夫曼树的根放在 len/2-1 位置//    for(i=9;i<5555;i++)            Sleep(11111);
    tree->lchild=longth-1;
    tree->rchild=0;
    tree->parent=0;
    tree->cost=len;//////////////////////        
} 

void Select(Huftree tree,int len,int &s1,int &s2)//在带权的森林中找出权最小的两个树(s1<s2)
{    
    int i,k=0;
    s1=0;s2=0;
    for(i=1;i<len;i++){
        if(((tree+i)->parent==0)&&(tree+i)->cost>=k){
            s1=i;//s1记录大的
            k=(tree+s1)->cost;
        }
    }
    s2=s1;
    for(i=1;i<len;i++){
        if(((tree+i)->parent==0)&&(tree+i)->cost<=(tree+s1)->cost)
            s1=i;        
    }//for
    for(i=1;i<len;i++){
        if(((tree+i)->parent==0)&&(tree+i)->cost<=(tree+s2)->cost)
            if(s1!=i)    s2=i;        
    }//for    
}
int Findchar(char *str,char c)//从字符串中查找字符  返回字符数量
{
    int i,l,k=0;
    l=strlen(str);
    for(i=0;i<l;i++){
        if(str[i]==c) k++;
    }
    return k;
}

Stack  loadtree(Huftree tree,int n,char *str)//由字符串生成编码//放在栈中并返回//
{
    int i,len;
    len=strlen(str);
    Stack st;
    InitStack(st,"Haffcode");
    for(i=0;i<len;i++){
        //printf("%d]]字符:%c\n",i+1,str[i]);
        loadcode(st,tree,tree->lchild,str[i]);        
    }
    return st; 
}

int loadcode(Stack &st,Huftree tree,int n,char c)//在树中查找C并将对应的编码入栈//这个函数有点头大哦
{    
    if((tree+n)->data==c){
        //printf("已经找到\n");
        //outputstack(st);
        return 2;
    }
    if((tree+n)->lchild!=0){
        Push(st,0);    //printf("我左孩子是:%d\n",(tree+n)->lchild);
        if(loadcode(st,tree,(tree+n)->lchild,c)==2)
            return 2;
        else 
            Pop(st);     
                
    }
    if((tree+n)->rchild!=0){
        Push(st,1);//    printf("我右孩子是:%d\n",(tree+n)->rchild);
        if(loadcode(st,tree,(tree+n)->rchild,c)==2)
            return 2;
        else 
                Pop(st);
    }
    return 1;
}

void treetext(Huftree tree)//将哈夫曼树生成文本文件并保存//用于解码用
{
    int i,l;
    FILE* treefile;
    treefile=fopen("treecode.txt","wt");    
    fputc(tree->cost,treefile);//整数不用转化直接储存
    l=tree->cost;
    //因为一般树的储存长度小于122
    for(i=0;i<l;i++) //这里不关心权重
    {
        fputc((tree+i)->lchild+29,treefile);//顺序为左孩子
        fputc((tree+i)->rchild+29,treefile);//右孩子
        fputc((tree+i)->parent+29,treefile);//父母    
        fputc((tree+i)->data+29,treefile);//字符值
        //printf("%d  %d  %d  %c\n",(tree+i)->lchild+29,(tree+i)->rchild+29,(tree+i)->parent+29,(tree+i)->data+29);
    }
    fclose(treefile);
}



void begin()//程序运行函数
{
    printf("********************************************************************************");
    system("color 4a");
    Stack st;
    Huftree tree;
    pcharlist charlist;
    int listlong;
    char *str;
    char path[64],goodpath[64];
    int lenth;
    FILE *handle,*gfile;
    printf(" 请输入原文件路径: ");
    scanf("%s",path);    
    printf(" 输入目标文件路径: ");
    scanf("%s",goodpath);
    handle=fopen(path,"rt");      //打开文件
    gfile=fopen(goodpath,"wt");
    fseek(handle,0,SEEK_END);     //
    lenth=ftell(handle);         //取文件长度
    lenth+=1; 
    str=(char*)malloc(sizeof(char)*lenth);//多一个字节//存放'\0'
    rewind(handle);     //文件指针回打文件开始
    fgets(str,lenth,handle);      //将文件内容存入str     
    charlist=change(str,listlong); 
    madetree(tree,charlist,listlong); 
    st=loadtree(tree,0,str);
    //outputstack(st);//输出栈的信息//将栈中的每8个二进制数据转化为一个字符存放    
    ///////////////////////////////////////////////////
    int l,i;
    l=st.lenth;
    PN p;
    p=st.base; 
    for(i=0;i<l;i++){
        fputc(p->data+48,gfile);
        p=p->next;
    }
    fputc('\0',gfile);
    printf("\n\n");
    //outputstack(st);
    printf(" 编码完成 编码文件存放在 %s \n\n\n",goodpath);
    treetext(tree);
    printf("********************************************************************************\n\n\n");
}
void main()
{ 
    begin();
}


//附：将整数转化为字符串的函数：itoa(,,);
//字符转化为整数              : atoi(  );

以上是编码程序代码

//一以下是解码程序
/////////////head01.h////////////
#define HEAD01_FILE
////////////////////
#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
#define TEST printf("her is OK!!\n");
///////////////////////////////////////
typedef struct T{    //树结点定义
    char data;       //数据
    int parent;       //父母
    int lchild;       //左孩子
    int rchild;       //右孩子
}TreeNode,*Huftree;

Huftree madetree();//将树结构文件的的编码转化为树 存于内存中

void madefile(char *codefile,Huftree tree,char*goodfile);//由树和编码文件生成原文件

void begin();//程序运行函数

#endif

///////////////function01.cpp/////////////////
#include"head01.h"
#include<graphics.h>
Huftree madetree()//将树结构文件的的编码转化为树 存于内存中
{
    Huftree tree;
    FILE *file;
    int i,l;    
    file=fopen("treecode","r");
    l=(int)fgetc(file);
    tree=(Huftree)malloc(sizeof(TreeNode)*l);    
    for(i=0;i<l;i++)
    {
        (tree+i)->lchild=fgetc(file)-29;
        (tree+i)->rchild=fgetc(file)-29;
        (tree+i)->parent=fgetc(file)-29;
        (tree+i)->data=fgetc(file)-29;
        //printf("%d  %d  %d  %c\n",(tree+i)->lchild,(tree+i)->rchild,(tree+i)->parent,(tree+i)->data);
    }
    rewind(file);
    tree->data=getc(file);///树的长度存放在头结点的数据中
    fclose(file);
    return tree;
}
void madefile(char *codefile,Huftree tree,char*goodfile)
{  
    FILE* fcode,*gfile;
    int i,l,c,go,lenth;//go记录当前指针的方向
    fcode=fopen(codefile,"r"); //打开编码文件
    gfile=fopen(goodfile,"wt");//创建字符文件
    go=l=tree->lchild;    
    fseek(fcode,0,SEEK_END);     //
    lenth=ftell(fcode);         //取文件长度
    rewind(fcode);
    for(i=0;i<lenth;i++){
        c=fgetc(fcode);    
        if(c=='0')        go=(tree+go)->lchild;    
        else if(c=='1')    go=(tree+go)->rchild;
        if(go>l) {
            fputc((tree+go)->data,gfile);
            go=l;        
        }    
    }
    
}
void begin()//程序运行函数
{
    printf("********************************************************************************");
    system("color 4a");
    char *goodfile,*codefile;
    Huftree tree;
    goodfile=(char*)malloc(sizeof(char)*32);
    codefile=(char*)malloc(sizeof(char)*3);
    printf("编码文件位置:");
    scanf("%s",codefile);
    printf("输出文件位置:");
    scanf("%s",goodfile);
    tree=madetree();
    madefile(codefile,tree,goodfile);
    printf("\n\n");
    printf("文件%s已经生成\n\n\n\n",goodfile);
    printf("********************************************************************************\n\n\n");
}
void main()
{
    begin();
}

//声明：
//我的程序没有错误且很符合你的要求
//但是发给你时候就会有了几个错误
//如果你自己不能解决，请联系QQ271743617

谢谢，