6 Replies - 699 Views - Last Post: 22 November 2011 - 12:01 PM Rate Topic: -----

#1 McSick  Icon User is offline

  • D.I.C Head

Reputation: 33
  • View blog
  • Posts: 179
  • Joined: 02-September 10

String Cat in C

Posted 21 November 2011 - 12:25 PM

So I have a huffTree and I want to traverse it and save its huffcode in a nice array. I thought this would be easy however the string I am using to save the huffcode needs to have only local scope. Right now it is having more of global scope because my function sends char* string. This is bad since I keep strcat either "0" or "1".

void buildCode(huffTree* tree,char* string,huffTree** pointer){
    char one[2] = "1";
    char zero[2] = "0";
   int len;
    if(tree->left == NULL && tree->right == NULL){
        printf("String = %s Char = %c\n",string,tree->character);
        pointer[(int)tree->character]->code = string;
    }else{
        if(tree->left != NULL)buildCode(tree->left,strcat(string,zero),pointer);
        if(tree->right != NULL)buildCode(tree->right,strcat(string,one),pointer);
    }


}




and my output is:

String = 010101 Char = g
String = 01010101 Char = o
String = 01010101010101 Char = r
String = 0101010101010101 Char =
String = 0101010101010101010101 Char =

String = 010101010101010101010101 Char = e
String = 0101010101010101010101010101 Char = h
String = 010101010101010101010101010101 Char = p

when g should be 00... is there maybe a more efficient way of sending the cating of the strings?

Is This A Good Question/Topic? 0
  • +

Replies To: String Cat in C

#2 McSick  Icon User is offline

  • D.I.C Head

Reputation: 33
  • View blog
  • Posts: 179
  • Joined: 02-September 10

Re: String Cat in C

Posted 21 November 2011 - 12:33 PM

Change it around and now getting a segfault probably from the strcat function not having enough space...

void buildCode(huffTree* tree,char* string,huffTree** pointer){
    char one[2] = "1";
    char zero[2] = "0";
    char* temp;
    temp = malloc(300*sizeof(char));
    temp = string;//temp variable to hold the string
    if(tree->left == NULL && tree->right == NULL){
        printf("String = %s Char = %c\n",string,tree->character);
        pointer[(int)tree->character]->code = string;
    }else{
        if(tree->left != NULL)buildCode(tree->left,strcat(temp,zero),pointer);//cat it together with either one or zero.
        if(tree->right != NULL)buildCode(tree->right,strcat(temp,one),pointer);
    }


}


Was This Post Helpful? 0
  • +
  • -

#3 McSick  Icon User is offline

  • D.I.C Head

Reputation: 33
  • View blog
  • Posts: 179
  • Joined: 02-September 10

Re: String Cat in C

Posted 21 November 2011 - 12:40 PM

Never mind, got it using sprintf and a buffer ^.^
Was This Post Helpful? 0
  • +
  • -

#4 McSick  Icon User is offline

  • D.I.C Head

Reputation: 33
  • View blog
  • Posts: 179
  • Joined: 02-September 10

Re: String Cat in C

Posted 21 November 2011 - 01:02 PM

I hate to bring this back up to the top but now I am getting unexpected results...

My build code goes like this

void buildCode(huffTree* tree,char* string,huffTree** pointer){
    char buff1[30];//buffer1 to store left traversal
    char buff2[30];//buffer2 to store right traversal
    int ret;
    int ret2;

    if(tree->left == NULL && tree->right == NULL){//if both children are null, youre at a leaf
        printf("String = %s Char = %c Int = %d\n",string,tree->character,(int)tree->character);
        pointer[(int)tree->character]->code = string;
        printf("Pointed= %s\n",pointer[(int)tree->character]->code);
    }else{
         ret = sprintf(buff1,"%s0",string);
        ret2 = sprintf(buff2,"%s1",string);
        if(tree->left != NULL)buildCode(tree->left,buff1,pointer);
        if(tree->right != NULL)buildCode(tree->right,buff2,pointer);
    }


}




and it actually works great with my input of "go go gopher\n" it build the tree and codes correctly! as seen by the input produced by the build code fcn.

String = 00 Char = g Int = 103
Pointed= 00
String = 01 Char = o Int = 111
Pointed= 01
String = 100 Char = r Int = 114
Pointed= 100
String = 101 Char = Int = 32
Pointed= 101
String = 1100 Char =
Int = 10
Pointed= 1100
String = 1101 Char = e Int = 101
Pointed= 1101
String = 1110 Char = h Int = 104
Pointed= 1110
String = 1111 Char = p Int = 112
Pointed= 1111

but however when going through my array of nodes and looking at the code values again by this loop after the function exits.

 buildCode(tree,"",pointer);
    printtree(tree);
    for(i=0;i<256;i++){
        if(pointer[i]->code != NULL)printf("Char is: %c and Code is %s Int is %d\n",pointer[i]->character,pointer[i]->code,(int)pointer[i]->character);
    }



this output something different in my pointers array. like so

Char is:
and Code is 1110 Int is 10
Char is: and Code is 111 Int is 32
Char is: e and Code is 1111 Int is 101
Char is: g and Code is 10 Int is 103
Char is: h and Code is 1110 Int is 104
Char is: o and Code is  Int is 111
Char is: p and Code is 1111 Int is 112
Char is: r and Code is Int is 114


and to note each ascii value in the pointers array determines which character and location in the array for simpleness. As you can see, values got messed up with g no longer having a code of 00 and there are two 1111 codes! I just cant see where the code goes haywire from such a short transition...
Was This Post Helpful? 0
  • +
  • -

#5 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5874
  • View blog
  • Posts: 12,754
  • Joined: 16-October 07

Re: String Cat in C

Posted 21 November 2011 - 01:13 PM

You seemed to have the idea of using a length in the first one. You could simple pass that around, starting at 0.
int buildCode(huffTree* tree, char* string, huffTree** pointer, int len){
	if(tree->left == NULL && tree->right == NULL){
		string[len]=0;
		printf("String = %s Char = %c\n",string,tree->character);
		pointer[(int)tree->character]->code = string;
	} else {
		if(tree->left != NULL) { 
			string[len]='0';
			len = buildCode(tree->left, string, pointer, len+1);
		}
		if(tree->right != NULL) {
			string[len]='1';
			len = buildCode(tree->right, string, pointer, len+1);
		}
	}
	return len;
}



I'd probably just make struct for it:
typedef struct {
	int len;
	char buff[MAX_SIZE];
	char treeChar;
} BuildCodeResult;

void buildCode(huffTree* tree, BuildCodeResult *br){
	if(tree->left == NULL && tree->right == NULL){
		br->buff[br->len]=0;
	} else {
		if(tree->left != NULL) { 
			br->buff[br->len++]='0';
			buildCode(tree->left, br);
		}
		if(tree->right != NULL) {
			br->buff[br->len++]='1';
			buildCode(tree->left, br);
		}
	}
}

BuildCodeResult res;
res.len = 0;
buildCode(tree, &res);
printf("String = %s Char = %c\n",res.buff, res.treeChar);


Was This Post Helpful? 0
  • +
  • -

#6 McSick  Icon User is offline

  • D.I.C Head

Reputation: 33
  • View blog
  • Posts: 179
  • Joined: 02-September 10

Re: String Cat in C

Posted 21 November 2011 - 01:45 PM

Hmm well I finally got it to work by making my buffers dynamic that way theyd malloc. It works now however I am scared because I have used malloc so much in my program...I fear lots of leaky memory may be around. Oh well for now...

Heres what I did.

void buildCode(huffTree* tree,char* string,huffTree** pointer){
    char* buff1;//buffer1 to store left traversal
    char* buff2;//buffer2 to store right traversal
        int ret;
    int ret2;
   int i;
    buff1 = malloc(30*sizeof(char));
    buff2 = malloc(30*sizeof(char));
    if(tree->left == NULL && tree->right == NULL && pointer[(int)tree->character]->code == NULL){//if both children are null, youre at a leaf
       // printf("String = %s Char = %c Int = %d\n g= %s",string,tree->character,(int)tree->character,pointer[103]->code);
        pointer[(int)tree->character]->code = string;
       // printf("Pointed= %s\n",pointer[(int)tree->character]->code);
    }else{
         ret = sprintf(buff1,"%s0",string);
        ret2 = sprintf(buff2,"%s1",string);
        if(tree->left != NULL)buildCode(tree->left,buff1,pointer);
        if(tree->right != NULL)buildCode(tree->right,buff2,pointer);
    }
}


Was This Post Helpful? 0
  • +
  • -

#7 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5874
  • View blog
  • Posts: 12,754
  • Joined: 16-October 07

Re: String Cat in C

Posted 22 November 2011 - 12:01 PM

You really are working too hard...

I thought I'd play with this. This is what traversal might look like:
void huffTreePrintNode(HuffNode *node, char *buff, int depth) {
	if (node->left==NULL && node->right==NULL) {
		buff[depth]=0;
		printf("%c %s\n", node->symbol, buff);
	} else {
		buff[depth]='0'; huffTreePrintNode(node->left, buff, depth+1);
		buff[depth]='1'; huffTreePrintNode(node->right, buff, depth+1);
	}
}

void huffTreePrint(HuffTree *ht) {
	char buff[256];
	huffTreePrintNode(ht->head, buff, 0);
}



That buff[256] stupid large, of course. But it's still tiny and easier than malloc all the time. Still, there's no reason what you couldn't do something like:
void huffTreePrint(HuffTree *ht) {
	char *buff = malloc(huffTreeMaxDepth(ht)+1);
	huffTreePrintNode(ht->head, buff, 0);
	free(buff);
}



For that pointer[(int)tree->character]->code = string;... well, string can change, can't it? Copy that thing! malloc the size of string then strcpy.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1