大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > 算法技巧 > 数据结构与算法基本程序合集

数据结构与算法基本程序合集(5)

关键词:数据结构算法基本程序  阅读(2752) 赞(55)

[摘要]本文是数据结构与算法基本程序合集,与大家分享。
//哈夫曼编码
 
#include<stdio.h>
#include<malloc.h>
#include<math.h>
#define NULL 0
 
typedef struct huff_code_node    //存储编码的链表
{
    char ch;    //编码对应的字符
    char code[100];        //字符对应的哈夫曼码
    struct huff_code_node *next;    
}hnode,*huff;
 
typedef struct tree_Node    //二叉树结点
{
    char ch;    //字符内容
    int amount;    //字符在字符串中出现的次数
    struct tree_Node *left,*right;    //指向左子树与右子树
}tnode,*bt;
 
typedef struct list_node        //链表结点
{
    char ch;    //存储字符串中的字符
    int amount;    //字符在字符串中出现的次数
    tnode *son;    //链表结点带有二叉子树的根结点指针
    struct list_node *next;    //指向链表中下一个结点
}Node,*L;
 
typedef struct stack_node
{
    char ch;    //存储字符
    int amount;        //出现次数
    bt son;        //指向二叉树的某结点
    struct stack_node *next;
}snode,*stack;
 

char t[200],*str,*c;    //用于存储和处理输入的字符串
bt root=NULL;        //哈夫曼树
L l,p,q,new_node;    //链表结点
huff hlist;        //计算得到的编码表
int char_num;    //输入的不同字符数量
int char_amount;    //输入的所有字符数量
int code_sum;        //哈夫曼编码总长
 

void initial()        //初始化操作
{
    l=(Node*)malloc(sizeof(Node));        //建立空链表
    l->ch='\0';
    l->amount=0;
    l->son=NULL;
    l->next=NULL;
 
    str=t;    //将字符串指针指向字符串的第一个位置
    //键盘输入字符串
    printf("输入字符串进行哈夫曼编码:\n");
    scanf("%s",str);
    getchar();    
}
 
void pull_in_list()
{
    int exist;    //表示当前字符是否存在于链表中,0为不存在,1为已存在
    int n;    //计算输入不同字符的数量,计算后赋值给全局变量char_num
    int m;    //计算输入所有字符的数量,计算后赋值给全局变量char_amount
    
    c=str;    //c指向第一个字符
    
    while(*c!='\0')        //若字符串未读完
    {
        exist=0;
        p=l;    //p指向链表头结点
        //寻找该字符是否已经在链表中
        while(p->next!=NULL)    //若链表非空
        {
            p=p->next;
            if(p->ch==*c)    //若当前字符已经在链表中
            {
                exist=1;
                p->amount++;    //字符出现次数加1
                break;
            }
        }
 
        if(exist==0)    //若当前字符不存在于链表中,则分配一个结点入表
        {
            new_node=(Node*)malloc(sizeof(Node));
            new_node->ch=*c;
            new_node->amount=1;
            new_node->next=NULL;
            new_node->son=NULL;
            p->next=new_node;
            p=new_node;
        }
        c++;    //读下一个字符
    }
 
    printf("统计结果:\n");
    p=l;
    n=0;
    m=0;
    while(p->next!=NULL)
    {
        n++;
        p=p->next;
        m+=p->amount;
        printf("%c——%d\n",p->ch,p->amount);
    }
    char_num=n;
    char_amount=m;
    printf("一共有%d种字符输入,字符总数%d\n",char_num,char_amount);
}
 
int list_element_amount()        //计算链表中结点的数量(不包括头结点)
{
    L temp;        //定义临时指针
    int n=0;        //结点数量
    temp=l;
    while(temp->next!=NULL)    //后面还有结点
    {
        n++;
        temp=temp->next;
    }
    return n;
}
 
bt create()    //建立最优二叉树
{
    //=========================================
    //这些变量用于寻找最小结点
    L min1_pos,min2_pos,t,min_pri;
    bt min1_son,min2_son;
    int min1,min2;
    char min1_c,min2_c;
    //=========================================
 
    //=========================================
    //这些变量用于构造二叉子树
    bt left,right,root;
    //==========================================
 
    //==========================================
    //这些变量用于将二叉子树信息插入链表
    L made,temp_p;
    //============================================
 
    while(list_element_amount()>=2)    //若表中还有两个或以上结点,则归并继续
    {
        //选择次数值最小的两个结点
 
        //============================================================================
        //先寻找第一个小结点
        t=l->next;
        min1=t->amount;        //将第一个结点的次数值赋给min1
        min1_pos=t;            //将第一个结点的位置指针赋给min1_pos
        min1_c=t->ch;        //将第一个结点的字符赋值给min1_c
        min1_son=t->son;    //将第一个结点的二叉指针赋值给min1_son
        min_pri=l;            //min_pri始终指向最小结点的前驱,以方便删除最小结点
 
        while(t->next!=NULL)
        {
            t=t->next;
            if(min1>t->amount)    //发现更小的结点
            {
                min1=t->amount;        //将当前结点的次数值赋给min1
                min1_pos=t;            //将当前结点的位置指针赋给min1_pos
                min1_c=t->ch;        //将当前结点的字符赋值给min1_c
                min1_son=t->son;    //将当前结点的二叉指针赋值给min1_son
            }
        }//退出本循环时,最小结点的信息找出,将该结点删除
 
        min_pri=l;
        while(min_pri->next!=min1_pos)
            min_pri=min_pri->next;
        //退出循环时min_pri指向min1_pos的前驱
        min_pri->next=min1_pos->next;        //删除结点min1_pos
        //寻找第一个小结点完成
        //=================================================================
 
        //=================================================================
        //先寻找第二个小结点
        t=l->next;
        min2=t->amount;        //将第二个结点的次数值赋给min2
        min2_pos=t;            //将第二个结点的位置指针赋给min2_pos
        min2_c=t->ch;
        min2_son=t->son;
        min_pri=l;        //min_pri始终指向最小结点的前驱,以方便删除最小结点
 
        while(t->next!=NULL)
        {
            t=t->next;
            if(min2>t->amount)    //发现更小的结点
            {
                min2=t->amount;        //将当前结点的次数值赋给min2
                min2_pos=t;            //将当前结点的位置指针赋给min2_pos
                min2_c=t->ch;
                min2_son=t->son;
            }
        }//退出本循环时,最小结点的信息找出,将该结点删除
 
        min_pri=l;
        while(min_pri->next!=min2_pos)
            min_pri=min_pri->next;
        //退出循环时min_pri指向min1_pos的前驱
        min_pri->next=min2_pos->next;        //删除结点min2_pos
        //寻找第二个小结点完成
        //=================================================================
 

        //==================================================================
        //两个最小结点找到,由这对结点级成一个二叉子树,将根结点插入链表中
        if(min1_son==NULL)    //该结点无二叉子树指针,则须新分配一个二叉树结点
        {
            left=(bt)malloc(sizeof(tnode));        //产生左孩子
            left->amount=min1;        //次数值复制
            left->ch=min1_c;        //字符复制
            left->left=NULL;
            left->right=NULL;
        }
        else    //该结点为计算产生的结点,它已指向一个二叉子树
            left=min1_son;    //left直接指向已经生成的二叉子树的根结点
 
        if(min2_son==NULL)    //该结点无二叉子树指针,则须新分配一个二叉树结点
        {
            right=(bt)malloc(sizeof(tnode));        //产生右孩子
            right->amount=min2;        //次数值复制
            right->ch=min2_c;        //字符复制
            right->left=NULL;
            right->right=NULL;
        }
        else
            right=min2_son;    //left直接指向已经生成的二叉子树的根结点
 
        root=(bt)malloc(sizeof(tnode));
        root->amount=min1+min2;
        root->ch='\0';        //对于计算产生的树结点,字符均为空
        root->left=left;
        root->right=right;
        //二叉子树完成
 
        //生成一个对应上面已产生二叉子树地址的链表结点
        made=(L)malloc(sizeof(Node));
        made->amount=root->amount;
        made->ch=root->ch;
        made->next=NULL;
        made->son=root;
 
        //将生成的链表结点插入链表中
        temp_p=l;
        while(temp_p->next!=NULL)
            temp_p=temp_p->next;
        //退出循环时temp_p指向链表最后一个结点
        temp_p->next=made;        //将生成的结点插入链表
    }
 
    temp_p=l->next;
    return temp_p->son;
}
 
void encoding()        //根据建立的哈夫曼树编码
{
    stack code,top,temp,readcode;
    bt r;
    huff temp_huff,hp;
    char huff[100]="";        //用于存储当前字符的哈夫曼编码串
    int i,j,n=0;
 
    hlist=(hnode*)malloc(sizeof(hnode));
    hlist->ch='\0';
    for(i=0;i<100;i++)
        hlist->code[i]='\0';
    hlist->next=NULL;
    hp=hlist;    
 
    //建立空栈
    code=(stack)malloc(sizeof(snode));
    code->amount=0;
    code->ch='\0';
    code->next=NULL;
    code->son=NULL;        //栈的头结点指向树的根结点
    top=code;
 
    r=root;
    temp=(stack)malloc(sizeof(snode));    //给哈夫曼树的根结点分配栈结点
    temp->amount=r->amount;
    temp->ch='0';
    temp->next=top;
    temp->son=r;
    top=temp;
    
    while(r!=NULL)    //当前结点存在
    {
        if(r->left!=NULL&&r->left->amount!=-1)    //当前结点有左孩子
        {
            r=r->left;        //r转向左孩子
            r->amount=-1;
 
            temp=(stack)malloc(sizeof(snode));    //给左孩子分配栈结点
            temp->amount=r->amount;
            temp->ch='0';
            temp->next=top;
            temp->son=r;
            top=temp;
        }
        else if(r->right!=NULL&&r->right->amount!=-1)        //当前结点有右孩子
        {
            r=r->right;        //r转向右孩子
            r->amount=-1;
 
            temp=(stack)malloc(sizeof(snode));    //给右孩子分配栈结点
            temp->amount=r->amount;
            temp->ch='1';
            temp->next=top;
            temp->son=r;
            top=temp;
        }
        else    //无未访问的孩子结点
        {
            
            if(r->left==NULL&&r->right==NULL)    //当前结点为叶子结点
            {
                for(i=0;i<100;i++)    //对哈夫曼编码数组初始化
                    huff[i]='\0';
 
                //先输出该叶子结点的编码
                printf("字符%c,编码为:",r->ch);
                readcode=top;
                i=0;
 
                while(readcode!=code)
                {
                    huff[i++]=readcode->ch;        //将栈元素倒置入哈夫曼编码数组中
                    readcode=readcode->next;
                }
                
                temp_huff=(hnode*)malloc(sizeof(hnode));    //为当前字符及其编码创建结点
                temp_huff->ch=r->ch;        //存储编码的原字符
                for(j=0;j<100;j++)        //初始化编码串数组
                    temp_huff->code[j]='\0';
 
                j=0;
 
                for(i=i-2;i>=0;i--)                //依次读出哈夫曼编码数组中的编码串
                {
                    printf("%c",huff[i]);
                    temp_huff->code[j++]=huff[i];
                }
                temp_huff->next=NULL;
                hp->next=temp_huff;
                hp=temp_huff;
 
                printf("\t\t");
                if(++n%2==0)
                    printf("\n");
            }
 
            if(top->next!=code)        //若栈非空
            {
                top=top->next;
                r=top->son;
            }
            else
                break;
        }
    }
}


相关评论