[SOLVED] Dynamic arrays of character strings in C

[elija]

I'm just starting to learn C and up to now it has apparently been going quite well. Suddenly, I have hit a brick wall and I am sure I am making a very basic error.

In the book I am using to learn C (Instant C - which is a bit of false advertising ) the current exercise is to do the following

Allow the input of an unknown number of strings and sort them into descending order. Output the results.

Now, if this was a known number of strings it would be easy peasy. This is my code which really doesn't work... Can anyone point me in the right direction with the addToArray function and how to get at the strings?

#include <stdio.h>
#include <stdlib.h>

//	Set up my booleans
#define TRUE	1
#define FALSE	0
#define MAXLEN 80

char* inputArray;

//	Prototypes
int input(char* strOne, int intMaxLen);
void addToArray(char* strOne, int len);

int numElements = 0;
int numAllocated = 0;

//  The function will return abitary input from the keyboard in the memory pointed to by strOne
//		Also returned is the length of the string - hey why not it's known!
int input(char* strOne, int intMaxLen) {
	
	char ch;
	int count = 0;
	
	while (((ch = getchar()) != '\n') && (count < intMaxLen - 2)) {
		*(strOne + count++) = ch;
	}
	
	*(strOne + count) = '\n';	
	
	return count;
	
}

//  The function will add a string pointed at by the arguement to a dynamic array.
//		If required it will increase the size of the array.
void addToArray(char* strOne, int len) {

	int i = 0;

	//  If necessary, increase the size of the array
	if (numAllocated == numElements) {
		
		//  Start with two elements allowed
		if (numElements == 0) {
			numElements = 2;
		} else {
			numElements *= 2;
		}
		
		inputArray = (char*)realloc(inputArray, numElements * (sizeof(char) * MAXLEN));

		
		//  Things can go horribly wrong when allocating memory so handle an error
		if (inputArray == NULL) {
			printf("ERROR: Couldn't realloc memory!");
			exit(2);
		}

	}
	
	for (i=0; i<len; i++) {
			inputArray[numAllocated] = *strOne++;
	}

	numAllocated++;
	
	return;
}

int main() {

	char strIn[MAXLEN];
	char* pStrIn = strIn;
	
	int len = -1;
	int i = 0;

	printf("Enter some strings. Press enter to finish:\n");
	while (len != 0) {		
		len = input(pStrIn, MAXLEN);
		if (len > 0) {
			addToArray(strIn, len);
		}
	}
	
	//  Now parrot them back to make sure the strings were added
	for (i = 0; i < numAllocated; i++) {
		printf("--&#37;s--\n", (inputArray + (MAXLEN *i)));
	}

	free(inputArray);

	return 0;

}

[scm]

I'd do it with an array of pointers to the strings - that way you only have to allocate memory for the length of each string you're using, not the max every time. Start with an empty pointer array of, say, 100, and grow it by 100 whenever it fills up. For simplicity you can do the sort by stepping through the string pointers comparing pairs and restarting every time you have to swap a pair of pointers.

[Cabhan]

Your code mostly looks pretty good. For reference, in the future, you should tell us exactly what's not working, so that we have some idea of what to look for.

In this particular case, scm is correct, but I thought I would explain a bit more.

The problem here has to do with your datatype of inputArray. The datatype of an array of type "foo" is *foo. Similarly, the datatype of an array of type "*char" is "**char". Which is, a pointer to a pointer to a character.

Pointers to pointers is one of the more difficult concepts to work with, but I think you will find that it makes sense. Let us examine this code:

char **inputArray;

...

char *str1 = "Hello";
char *str2 = "Goodbye";
inputArray[0] = str1;
inputArray[1] = str2;

This would not work in your code, because in your code "inputArray[0]" is a char, not a string.

I hope that this helps!

[elija]

Your code mostly looks pretty good. For reference, in the future, you should tell us exactly what's not working, so that we have some idea of what to look for.

It's good to know I'm not barking up completely the wrong tree. In my defence, by the time I posted this I had tied mself up such knots that I didn't know what was and what wasn't working... In retrospect, this is the input, this is what I want out and this is what I get out would probably have helped.

In this particular case, scm is correct, but I thought I would explain a bit more.

The problem here has to do with your datatype of inputArray. The datatype of an array of type "foo" is *foo. Similarly, the datatype of an array of type "*char" is "**char". Which is, a pointer to a pointer to a character.

Pointers to pointers is one of the more difficult concepts to work with, but I think you will find that it makes sense. Let us examine this code:

char **inputArray;

...

char *str1 = "Hello";
char *str2 = "Goodbye";
inputArray[0] = str1;
inputArray[1] = str2;

This would not work in your code, because in your code "inputArray[0]" is a char, not a string.

I hope that this helps!

I think that makes sense, well more sense than what I read in the book anyway. I'm going to try and apply it to what I am doing. I have no doubt I will be back.

Thanks for the pointers* guys


* Sorry, I couldn't resist.

[elija]

OK, I'm still not quite getting this...

//  This program uses a function to compare two strings input by the user
//  and return the greater.


#include <stdio.h>
#include <stdlib.h>

//	Set up my booleans
#define TRUE	1
#define FALSE	0
#define MAXLEN 80

char** inputArray;

//	Prototypes
int input(char* strOne, int intMaxLen);
void addToArray(char* pStr);

int numElements = 0;
int numAllocated = 0;

//  The function will return abitary input from the keyboard in the memory pointed to by strOne
//		Also returned is the length of the string - hey why not it's known!
int input(char* strOne, int intMaxLen) {
	
	char ch;
	int count = 0;
	
	while (((ch = getchar()) != '\n') && (count < intMaxLen - 2)) {
		*(strOne + count++) = ch;
	}
	
	*(strOne + count) = '\0';	
	return count;
	
}

//  The function will add a string pointed at by the arguement to a dynamic array.
//		If required it will increase the size of the array.
void addToArray(char* pStr) {

	//  If necessary, increase the size of the array
	if (numAllocated == numElements) {
		
		//  Start with two elements allowed
		if (numElements == 0) {
			numElements = 2;
		} else {
			numElements *= 2;
		}
		
		inputArray = (char**)realloc(inputArray, numElements * sizeof(char*));
		
		//  Things can go horribly wrong when allocating memory so handle an error
		if (inputArray == NULL) {
			printf("ERROR: Couldn't realloc memory!");
			exit(2);
		}

	}
	
	inputArray[numAllocated++] = pStr;
	
	printf("----DEBUG OUTPUT----\n");
	printf("$$&#37;s$$\n", pStr);
	int i;
	for (i = 0; i < numAllocated; i++) {
		printf("!!%d=%s!!\n", i, inputArray[i]);
	}
	printf("-------------------\n");
	
	return;
}




int main() {

	char strIn[MAXLEN];
	char* pStrIn = strIn;
	
	int len = -1;
	int i = 0;

	printf("Enter some strings. Press enter to finish:\n");
	while (len != 0) {		
		len = input(pStrIn, MAXLEN);
		if (len > 0) {
			addToArray(pStrIn);
		}
	}
	
	//  Now parrot them back to make sure the strings were added
	//for (i = 0; i < numAllocated; i++) {
	//	printf("--%s--\n", inputArray[i]);
	//}

	free(inputArray);

	return 0;

}

The for loop in the debug code shows that every element is the last string passed in. I can't see where I am going wrong.

I'm sure it is a simple thing

[Cabhan]

Ah, sorry. This is actually my fault for not pointing out the problem with assigning pointers to pointers.

The issue here is that you write each string to the same memory location. And because the input array just stores a memory location, it's storing the same memory location in each address. So each time you overwrite that address, every member of the array gets changed.

I see two possibilities here: one that works with your current implementation, and one which doesn't (but which involves what I suspect are improvements to your program).

1) Instead of pointing the array at the string, we actually copy the string into the array:

char *string = "hello";
inputArray[i] = malloc(sizeof(char) * (strlen(string) + 1));
strcpy(inputArray[i], string);

We have allocated new memory for the array, and now we copy the characters into that memory. Now inputArray[i] and string are different values.

A different option wil simplify your program dramatically. You see, it turns out that your input() function replicates the standard function fgets() (there is a function called gets(). NEVER use it.). You could make an fgets() call like so:

fgets(inputArray[i], MAXLEN, stdin)

This will read up to the first newline OR the first (MAXLEN - 1) characters, and store them in the given buffer.

It's up to you to use this piece of code correctly (you will still need to realloc()), but this function has the power to simplify your program dramatically.

[elija]

It's funny, I woke up this morning with the phrase, "they're pointers you moron! Think about it!" rattling around in my brain. I don't actually know if that is in itself sadder than thinking about it over breakfast and coming to the realisation that I would have to copy the input strings somewhere else. It is gratifying that you have said the same thing and proves the old adage... "Sleep on it!"

I do like the idea of using the string functions, but having sneaked a peek ahead in "Instant C", they are not covered until the next chapter so I had better stick with what has been covered so far.

None of the many other languages I have worked in have had anything like these pointers. Well, the old BASICs on the VIC20 and Atari ST had sadd and varptr but even they were nothing like these

Thanks for your patience and I have no doubt that I will be trying it some more later on.