problem with solution to exam question

[atikot]

hi, i have C exam next week, so i started solving questions from previous years exams and run into this question, the answer i come up to is far far from having reasonable length, it's too complicated and long , but i can't come up anything shorter.

the question is: write a function that receives an array of letters , and a pointer to final result string that hasn't allocated yet, the function supposed to take the array of letters and count the appearance of every letter and make the final result string look like that:

received array of letters : "abbacdeefg"
result string: "a 2;b 2;c 1;d 1;e 2;f 1;g 1"
in the result it should be alphabetically printed

here is the code that i wrote, it just doesn't makes sense that this is the actual solution:

void sortarray(char str[],char * final)
{
	int i = 1,j, extra = 0;
	char * letters, *lerrptr;
	int * count, * cerrptr;
	int size = 0, flag = 0;

	// allocate memory for one array storing letter and one for storing it's appearance
	letters = (char *) malloc(sizeof(char) * 1);
	if(letters == NULL) exit(1);
	count = (int *) malloc(sizeof(int) * 1);
	if(count == NULL) exit(1);

	// fill the first letter to array
	letters[0] = str[0];
	count[0] = 1;
	size++;

	// scan the whole string
	while(str[i] != 0)
	{
		// initiate flag for new run
		flag = 0;

		for(j = 0 ; j < size ; j++)
		{
			// if the letter already appeared before just increment the count and raise the flag that no new allocating is necessary
			if(str[i] == letters[j]) 
			{
				count[j]++;
				flag = 1;
			}
		}	
		// if the flag of already appeared hasn't been raised make new allocation for new letter
		if(!flag)
		{
			flag = 0 ;
			size++;
			lerrptr = letters;
			letters = (char *) realloc(letters,sizeof(char) * size);
			if(letters == NULL)
			{
				free(lerrptr);
				free(count);
				exit(1);
			}
			cerrptr = count;
			count = (int *) realloc(count,sizeof(int) * size);
			if(letters == NULL)
			{
				free(cerrptr);
				free(letters);
				exit(1);
			}
			// insert new letter and 1 for the count
			letters[size-1] = str[i] ;
			count[size-1] = 1 ;
				
		}

		i++;
	}
		
	// bubble sort the letters 
	for(i = 0 ; i < size - 1; i++)
	{
		for(j = 0 ; j < size - 1 - i ; j++)
		{
			if(letters[j] < letters[j - 1])
			{
				letters[j] ^= letters[j+1];
				letters[j+1] ^= letters[j];
				letters[j] ^= letters[j+1];
				count[j] ^= count[j+1];
				count[j+1] ^= count[j];
				count[j] ^= count[j+1];
			}
		}
	}
	
	// check for more 9 appearances to reserve more letters for one more digit
	for(i = 0 ; i < size ; i++) if(count[i] > 9) extra++;

	// allocate the memory for the final array that is going to be printed
	final = (char *) malloc(sizeof(char) * (size * 4) + extra + 1);
	
	j = 0;
	for(i = 0 ; i < size ; i++)
	{
		// insert the letter
		final[i*4 + j] = letters[i];
		// insert space
		final[i*4 + 1 + j] = ' ';

		// if more then one digit used for the count of appearances
		if(count[i] > 9)
		{
			// first digit
			final[i*4 + 2 + j] = count[i]/10 + 48;
			j++;
			// second
			final[i*4 + 2 + j] = count[i]%10 + 48 ;
		}
		else final[i*4 + 2 + j] = count[i]  + 48;
		
		// print ; 
		final[i*4 + 3 + j] = ';';
	}

	// add terminating character
	final[i*4 + j] = 0;
	// print the result
	printf(" %s ", final);
}

can anyone help me come up with more reasonable solution?

[shacktar]

If "array of letters" means it can only contain a-z and A-Z, then you could create two int arrays of length 26 (one to count the lowercases and one to count the uppercases).

#include <string.h> //for memset

void sortarray(char str[],char * final)
{
     //been a while since I've done C. You may not need to explicitly cast these
     const int ASCII_a = (int)'a';
     const int ASCII_z = (int)'z';
     const int ASCII_A = (int)'A';
     const int ASCII_Z = (int)'Z';

     const int LETTER_COUNT = 26;
     int count_lowercase[LETTER_COUNT]; //index 0 = 'a', 1 = 'b', ...
     int count_uppercase[LETTER_COUNT]; //index 0 = 'A', 1 = 'B', ...
     int i = 0;

     memset(count_lowercase, 0, LETTER_COUNT * sizeof(int));
     memset(count_uppercase, 0, LETTER_COUNT * sizeof(int));

     while(str[i] != 0)
     {
          if((str[i] >= ASCII_a) && (str[i] <= ASCII_z))
          {
               count_lowercase[str[i] - ASCII_a]++;
          }
          else
          {
               count_uppercase[str[i] - ASCII_A]++;
          }

          i++;
     }
}

Having the counts of the letters stored like this greatly reduces the complexity of the memory allocation and the final string determination part, which you could code yourself.

[binarybob350]

I have not studied the entire function but one problem I see it a classic beginners problem. Good test question to see if you really understand pointers.

You stated the following: "and a pointer to final result string that hasn't allocated yet"

Declaring as void sortarray(char str[],char * final) is wrong.
You need to declare it as void sortarray(char str[],char ** final)
Notice extra * in from of final, pointer to a pointer

And then inside the function

*final = (char *) malloc(sizeof(char) * (size * 4) + extra + 1);
Notice how you have to dereference (* in front of final) the pointer to a pointer when allocating memory.

If you want to get fancy you could write it as void sortarray(char str[],char *& final) A reference to a pointer (read right to left) Then you would not have to dereference final during allocation.

[shacktar]

If you want to get fancy you could write it as void sortarray(char str[],char *& final) A reference to a pointer (read right to left) Then you would not have to dereference final during allocation.

Except this is a C course. References are a C++ thing.