ecbtree.c

根据ascii码文件中各ascii字符出现的频率情况创建Haffman树

#include "ECBTree.h" 
#include "MyAssert.h" 
#include "ECStack.h" 
#include <stdio.h> 
#include <stdlib.h> 


PBinTree consBTree(EBTreeType* initList) 
{ 
       PBinTree pbtree; 
       pbtree=(PBinTree)malloc(sizeof(BinTree)); 


       if(pbtree!=NULL) 
            *pbtree=consRestBTree(initList); 

       gConsPos=0; 

       return pbtree; 
} 
PBinTreeNode consRestBTree(EBTreeType* initList) 
{ 
       PBinTreeNode pbnode; 


       if(initList[gConsPos]=='@') 
       { 
            gConsPos++; 
            pbnode=NULL; 
       } 
       else 
       { 
            pbnode=(PBinTreeNode)malloc(sizeof(struct BinTreeNode)); 


            assertF(pbnode!=NULL,"In consRestBTree,MEM APPLY FAILURE\n"); 


            pbnode->info=initList[gConsPos]; 


            gConsPos++; 


            pbnode->llink=consRestBTree(initList); 
            pbnode->rlink=consRestBTree(initList); 
       } 


       return pbnode; 
} 


void preOrder(PBinTreeNode inNode) 
{ 
       if(inNode==NULL) 
            return; 
       else 
       { 
            //preVisit(inNode->info); 
            printf("%c->",inNode->info); 
            preOrder(inNode->llink); 
            preOrder(inNode->rlink); 
       } 
} 


void preVisit(EBTreeType info) 
{ 
       printf("%c->",info); 
} 
//before it 
/* 
       findLen=0; 
       gFind=0; 
*/ 
void findPath(PBinTreeNode inNode,PBinTreeNode searchNode) 
{ 
       if(inNode==NULL) 
            return; 
       else 
       { 


            if(gFind) 
                    return; 


            prePanDuan(inNode,searchNode); 


            if(!gFind) 
            { 
                  findPath(inNode->llink,searchNode); 
                  findPath(inNode->rlink,searchNode); 
            } 
       } 
} 


void prePanDuan(PBinTreeNode inNode,PBinTreeNode searchNode) 
{ 
       if(inNode==searchNode) 
                  gFind=1; 


       gFindList[findLen]=inNode->info; 
       findLen++; 
} 


void    locateNode(PBinTreeNode inNode,EBTreeType inInfo,PBinTree targetNode) 
{ 
       if(inNode==NULL) 
            return ; 
       else 
       { 
            if(inNode->info==inInfo) 
            { 
                  *targetNode=inNode; 
                  gFind=1; 
                  return; 
            } 
            else 
            { 
                  locateNode(inNode->llink,inInfo,targetNode); 
                  locateNode(inNode->rlink,inInfo,targetNode); 
            } 
       } 


  } 


  int locateVisit(EBTreeType info) 
  { 
       return 0; 
  } 


  void preOrderUnStack(PBinTreeNode inNode) 
{ 


       PBinTreeNode p; 
       PSeqStack myStack; 
       int flag; 


       assertF(inNode!=NULL,"pass in node is null\n"); 


       myStack=createNullSeqStack(); 
       p=inNode; 


       preVisit(p->info);//visit 
       seqPush(myStack,p); 
       while(!isNullSeqStack(myStack)) 
       { 
            while(p->llink!=NULL) 
            { 
                  p=p->llink;//move to left child node 
                  preVisit(p->info);//visit 
                  seqPush(myStack,p);//push current node to the stack. 
            } 


            flag=0; 
            while(!flag&&!isNullSeqStack(myStack)) 
            { 
                  p=seqPop(myStack); 
                  if(p->rlink!=NULL) 
                  { 
                        p=p->rlink; 
                        preVisit(p->info);//visit 
                        seqPush(myStack,p); 
                        flag=1; 
                  } 
            } 
       } 
       printf("preOrder visit end\n"); 
} 


/*Start of Haffman Tree Ulti Function*/ 
/* 
       struct HtNode 
       { 
            EBTreeType type; 
            int parentIndex; 
            int llinkIndex; 
            int rlinkIndex; 
       }; 
*/ 
PHtTree consHtTree(EBTreeType* initList) 
{ 
       PHtTree pht; 
//     int i; 


       pht=(PHtTree)malloc(sizeof(struct HtTree)); 


       assertF(pht!=NULL,"in consHtTree,mem apply failure\n"); 


//     for(i=0;i<2*m-1;i++) 


       return NULL; 
} 


PHtTree haffmanAlgorithm(int m,EBTreeType* w) 
{ 
       PHtTree pht; 
       int i,j; 
       int firstMinIndex,secondMinIndex; 
       int firstMinW,secondMinW; 


       pht=(PHtTree)malloc(sizeof(struct HtTree)); 


       assertF(pht!=NULL,"in haffman algorithm,mem apply failure\n"); 


       /*Initialize the tree array*/ 
       for(i=0;i<2*m-1;i++) 
       { 
            pht->ht[i].llinkIndex=-1; 
            pht->ht[i].rlinkIndex=-1; 
            pht->ht[i].parentIndex=-1; 
            if(i<m) 
            { 
                  pht->ht[i].ww=w[i]; 
                  pht->ht[i].info=(char)i; 
            } 
            else 
                  pht->ht[i].ww=-1; 
       } 


       for(i=0;i<m-1;i++)//new Inner Node Num:m-1 
       { 
            firstMinW=MAXCHAR; 
            firstMinIndex=-1; 


            secondMinW=MAXCHAR; 
            secondMinIndex=-1; 


            for(j=0;j<m+i;j++) 
            { 
                  if(pht->ht[j].ww<firstMinW&&pht->ht[j].parentIndex==-1) 
                  { 
                       //trans minFirst info to minSecond info 
                       secondMinIndex=firstMinIndex; 
                       secondMinW=firstMinW; 


                       //set new first min node. 
                       firstMinIndex=j; 
                       firstMinW=pht->ht[j].ww; 
                  } 
                  else if(pht->ht[j].ww<secondMinW&&pht->ht[j].parentIndex==-1)/*update second 
node info*/ 
                  { 
                        secondMinW=pht->ht[j].ww; 
                        secondMinIndex=j; 
                  } 
            } 


            //Construct a new node. m+i is current new node's index 
                  pht->ht[firstMinIndex].parentIndex=m+i; 
                  pht->ht[secondMinIndex].parentIndex=m+i; 


                  pht->ht[m+i].ww=firstMinW+secondMinW; 
                  pht->ht[m+i].llinkIndex=firstMinIndex; 
                  pht->ht[m+i].rlinkIndex=secondMinIndex; 
                  pht->rootIndex=m+i; 
       } 


       return pht; 
} 


/*Invoke 
       preHtOrder(myHtTree,myHtTree->rootIndex) 
*/ 
void preHtOrder(PHtTree inTree,int rootIndex) 
{ 
       if(rootIndex==-1) 
            return; 
       else 
       { 
            preHtVisit(inTree->ht[rootIndex].info); 
            preHtOrder(inTree,inTree->ht[rootIndex].llinkIndex); 
            preHtOrder(inTree,inTree->ht[rootIndex].rlinkIndex); 
       } 
} 
/*Invoke: 
       preHaffListMake(myHtTree,myHtTree->rootIndex,0x00,0,myList) 
*/
void preHaffListMake(PHtTree inTree,int rootIndex,unsigned long youBiao,int sDepth,HaffCode* 
inList) 
{ 
       /* 
       typedef struct 
       { 
            char asciiCode; 
            unsigned haffCode; 
             int haffCodeLen; 
       }HaffCode; 
       */ 
       if(inTree->ht[rootIndex].llinkIndex==-1&&inTree->ht[rootIndex].rlinkIndex==-1) 
       { 
             inList[inTree->ht[rootIndex].info].haffCode=youBiao; 
             inList[inTree->ht[rootIndex].info].haffCodeLen=sDepth; 
       } 
       else 
       { 


       preHaffListMake(inTree,inTree->ht[rootIndex].llinkIndex,youBiao<<1,sDepth+1,inList); 


       preHaffListMake(inTree,inTree->ht[rootIndex].rlinkIndex,(youBiao<<1)|0x01,sDepth+1,inList); 
       } 
} 


void preHtVisit(InfoType info) 
{ 
       printf("%c->",info); 
}