This is my first post on this website.
I'm currently doing my assignment on reading a text file and create a Huffman code for each alphabet.
I'm still on the step to create the tree by picking every 2 smallest weight, and I'm encountering 2 problems
here is the code:I've set some printf to see where is my mistake but here the problem is :Code:#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct node { char letter; int weight; int PA, left, right; } BT; typedef struct { char letter; int weight; char *code; } Huff; void find2Lowest(BT * huffTable, int size, int *leftIndex, int *rightIndex) { while (huffTable[*leftIndex].PA != -1 || huffTable[*leftIndex].weight == 0) { *leftIndex++; } *rightIndex = *leftIndex; //printf("left index=%d\n",*leftIndex); for (int i = 0; i < size; ++i) { //finding first smallest element if (huffTable.weight == 0 || huffTable.PA != -1) // skip if node weight is zero or has been used continue; if (huffTable.weight < huffTable[*leftIndex].weight) *leftIndex = i; } //if first element is still same as second smallest element, increment right index while (*leftIndex == *rightIndex || huffTable[*rightIndex].PA != -1 || huffTable[*rightIndex].weight == 0) *rightIndex++; for (int i = 0; i < size; i++) { //finding second smallest element if (huffTable.weight == 0 || huffTable.PA != -1 || i == *leftIndex) // skip if node weight is zero or has been used continue; if (huffTable.weight < huffTable[*rightIndex].weight) *rightIndex = i; } printf("left=%d\tright=%d\n", *leftIndex, *rightIndex); } BT *generateHuffmanTreeTable(Huff * alphabet) { BT huffTable[51]; for (int i = 0; i < 51; i++) { //input the weight into the table if (i < 26) { huffTable.letter = alphabet.letter; huffTable.weight = alphabet.weight; huffTable.PA = -1; //mark non used node huffTable.left = -1; huffTable.right = -1; } else { huffTable.letter = '*'; //mark non leaf node huffTable.weight = 0; huffTable.PA = -1; //mark non used node huffTable.left = -1; huffTable.right = -1; } } int leftIndex = 0, rightIndex = 0; for (int i = 0; i < 25; i++) { leftIndex = 0, rightIndex = 0; find2Lowest(huffTable, (26 + i), &leftIndex, &rightIndex); //set parent node for 2 smallest element huffTable[leftIndex].PA = 26 + i; huffTable[rightIndex].PA = 26 + i; //set weight ,left and right for new node huffTable[26 + i].weight = huffTable[leftIndex].weight + huffTable[rightIndex].weight; huffTable[26 + i].left = leftIndex; huffTable[26 + i].right = rightIndex; printf("/////////////////////////////////////\n"); for (int i = 0; i < 51; i++) { printf("%d\t%d\t%d\t%d\n", huffTable.weight, huffTable.PA, huffTable.left, huffTable.right); } printf("/////////////////////////////////////\n"); } } int main() { char fileName[10]; //scanf("%s",fileName);// prompt user to input file name. Huff alphabet[26]; for (int i = 0; i < 26; i++) { alphabet.weight = 0; alphabet.letter = 97 + i; } FILE *file; file = fopen("data3.txt", "r"); char check; if (file) { //Read file and count the weight for each lowercase english alphabet while ((check = fgetc(file)) != EOF) { putchar(check); if (check >= 'a' && check <= 'z') { alphabet[check - 97].weight++; } } fclose(file); } printf("\n\n\n"); generateHuffmanTreeTable(alphabet); }
In the 41st iteration of second for loop in generateHuffmanTree
when I supposed to assign "0" and "36" as left and right child for the 41st node, and assign 41 as 0 and 36 parents. Only 0 is working but not 36. This messed the algorithm as it always read node 36 as the smallest element and always try to assign it to the n th node but always fail.
The second problem that i encounter is that sometimes the program got segmentation fault on the 40th iteration of the second loop.
I've been looking carefully for the past hours to at least fix my first problem but cannot to seem find the mistake, I'm assuming because it has something to do with the second problem as well ??