// Huffman code using a preprocessing quicksort and two (conceptual) queues. // This is a prototype for demonstration purposes only. #include #include double *probLink; // For qsort int compare(const void *xin,const void *yin) { // Sorts a permutation array based on elements being subscripts // to indirect to an array of doubles. double work; int x,y; x= *((int*) xin); y= *((int*) yin); work=probLink[x] - probLink[y]; if (work==0.0) return 0; if (work<0) return -1; return 1; } int main() { int n,m,i,j,val; double *prob,probSum,expected; int *left,*right; // Links for Huffman code tree, root is subscript m-1 int *parent; // For printing the codes int *length; char *outString; int *orderedInput; // Permutation to reorder input probabilities int inputHead,mergedHead; printf("Enter alphabet size\n"); scanf("%d",&n); m=2*n-1; // Number of nodes in tree prob=(double*) malloc(m*sizeof(double)); orderedInput=(int*) malloc(n*sizeof(int)); left=(int*) malloc(m*sizeof(int)); right=(int*) malloc(m*sizeof(int)); parent=(int*) malloc(m*sizeof(int)); outString=(char*) malloc((n+1)*sizeof(char)); length=(int*) malloc(m*sizeof(int)); if (!prob || ! orderedInput || !left || !right || !parent || !outString || !length) { printf("malloc problem %d\n",__LINE__); exit(0); } // Read alphabet symbols' probabilities. probSum=0.0; for (i=0;i=m) printf("ctc bonk 200\n"); if (right[i]<0) printf("ctc bonk 300\n"); if (right[i]>=m) printf("ctc bonk 400\n"); parent[left[i]]=parent[right[i]]=i; prob[i]=prob[left[i]]+prob[right[i]]; } parent[m-1]=(-1); // Goes breadth-first from root to compute length of prefix bit codes. length[m-1]=0; for (i=m-1;i>=n;i--) length[left[i]]=length[right[i]]=length[i]+1; // Print the leaves, i.e. for the alphabet symbols printf(" i prob parent bits product code\n"); for (i=0;i