How to properly allocate a struct array of strings

Question

/The first part of this message is solved, I added an edit below/

I need to malloc an array of strings, and its relative strings. I searched around a bit, but the problem was a little different. What I need to do is ask the user for a value, then check if the value is present in the previous positions of the array. To do this I was using binary search in this way:

BinarySearch(stringa** array, char* value, 0, i)

Where i is the iteration index.

I was getting a segfault in the strcmp() inside of the binary search. With a bit of debug, I understood that the problem isn't in the binary search but in the way I malloc the array of strings. This is a simple code I am using for debug reasons.

Definition of struct:

typedef struct _stringa {
char* string;
int freq;
} stringa;

Then inside the main:

scanf("%d", &n); // Number of strings

stringa** array;
array = (stringa**)malloc(n*sizeof(char*));

for (i=0; i<n; i++) {
    char* value = (char*) malloc(101* sizeof(char));
    scanf("%s", value);

    array[i]->string = (char*)malloc(101 * sizeof(char) );
    array[i]->string = value;
    array[i]->freq = 1;
}

I get my segfault:

array[i]->string = (char*)malloc(101 * sizeof(char) );

So my guess is that it doesn't think that in array[i]->string there should be a string. How can I fix this? Sorry, I am at the start yet of my programming

Thank you in advance!

EDIT: I now fixed the array of strings as suggested in the comments, but I get a similar segfault in my binary search: int BinarySearch(stringa* array, char* string, int left, int right) {

int middle;

if (left==right) {
    if (strcmp(string,array[left].string)==0) {
        return left;
    } else {
        return -1;
    }
}

middle = (left+right)/2;
if ((strcmp(string,array[middle].string)<0) || (strcmp(string,array[middle].string)==0) ) {
    return BinarySearch(array, string, left, middle);
} else {
    return BinarySearch(array, string, middle+1, right);
}

}

The problem is at the line:

if ((strcmp(string,array[middle].string)<0) || (strcmp(string,array[middle].string)==0) ) {

or here:

 if (left==right) {
        if (strcmp(string,array[left].string)==0) {

Why in your opinion?

Don't cast malloc in C: http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc — Barmar, Jul 05 '14 at 08:05
I would also suggest using calloc instead of malloc; similar cost, and protects against certain null-termination problems — tucuxi, Jul 05 '14 at 08:14
@Barmar and tucuxi, thank you for the useful advices. I still need to learn how to properly use malloc and pointers. By the way, I added an extra problem in the edit — Roberto, Jul 05 '14 at 08:20
Can `left`, `right`, `middle` ever exceed `n - 1` (the number of structs (-1 for 0 index))? — David C. Rankin, Jul 05 '14 at 09:16
Hey @DavidC.Rankin I don't think they can - but I actually need the right side to be `i`, which is the index of the for loop. Because if I set the right side to `n`, I would have a segmentation fault, as I haven't stored yet any value in the remaining `n-i` elements. — Roberto, Jul 05 '14 at 09:36
So your segfault occurs right away? first element or so -- well before any chance of exceeding the number of structs? That points to a problem in your search. Where is `string` coming from in `strcmp (string,...` How is it allocated or assigned? — David C. Rankin, Jul 05 '14 at 09:48
Yes, in the first element, in the case `left == right`. About the allocation problem, I don't know - I guess that if the function gets an array in his arguments, that array should be already defined (and I did so in the main). So the strings should also be defined — Roberto, Jul 05 '14 at 09:55

score 3 · Answer 1 · answered Jul 05 '14 at 08:13

array should just be an array of stringa, not an array of pointers.

scanf("%d", &n); // Number of strings

stringa* array;
array = malloc(n*sizeof(stringa));

for (i=0; i<n; i++) {
    char* value = malloc(101* sizeof(char));
    scanf("%s", value);

    array[i].string = value;
    array[i].freq = 1;
}

But if you really want an array of pointers to stringa, the code would be:

stringa** array;
array = malloc(n * sizeof(stringa*)); // Allocate array of pointers

for (i = 0; i < n; i++) {
    stringa[i] = malloc(sizeof(stringa)); // Allocate this struct
    char* value = malloc(101* sizeof(char)); // Allocate the string
    scanf("%s", value);

    array[i]->string = value;
    array[i]->freq = 1;
}

Thank you! I indeed needed to use just a * in my stringa* array! — Roberto, Jul 05 '14 at 08:16

score 1 · Answer 2 · answered Jul 05 '14 at 08:11

1

You didn't deal with stringa correctly. As long as you've enclosed a char* inside stringa, you only need stringa * to represent an array of string.

stringa* array = malloc(n*sizeof(stringa));

for (i=0; i<n; i++) {
    char value[101];
    scanf("%s", value);

    array[i].string = malloc(101 * sizeof(char));
    strcpy(array[i].string, value);
    array[i].freq = 1;
}

answered Jul 05 '14 at 08:11

timrau

22,578
4
51
64

It works while I get the strings, but when I try to BinarySearch them I still get another segmentation fault, I added the code in the original post – Roberto Jul 05 '14 at 08:30

score 1 · Answer 3 · answered Jul 05 '14 at 09:04

1

Well there are a couple of errors in your code. Here is an example with comments:

int main (void)
{
    char value[101];
    int n = 0;
    char strip;

    printf ("Enter the number of structures to create: ");
    scanf("%d", &n); // Number of strings
    strip = getchar(); while (strip != '\n') strip = getchar(); // flush stdin

    stringa **array = NULL;
    array = malloc ( n * sizeof (struct _stringa *) );

    int i = 0;

    for (i=0; i<n; i++) {

        array[i] = malloc (sizeof (struct _stringa));
        array[i]->string = malloc (sizeof (value));   // example only (strdup allocates)

        printf ("Enter the text of array[%d]->string : ", i);
        scanf("%s", value);
        strip = getchar(); while (strip != '\n') strip = getchar(); // flush stdin

        array[i]->string = strdup(value);   // dup content of value
        array[i]->freq = 501;               // dummy value

        printf ("  array[%d]->string: %s  array[%d]->freq: %d\n",
                i, array[i]->string, i, array[i]->freq);
    }

    while (--n >= 0) {
        if (array[n]->string) free (array[n]->string);
        if (array[n]) free (array[n]);
    }

    if (array) free (array);

    return 0;
}

output:

Enter the number of structures to create: 4
Enter the text of array[0]->string : my
    array[0]->string: my  array[0]->freq: 501
Enter the text of array[1]->string : dog
    array[1]->string: dog  array[1]->freq: 501
Enter the text of array[2]->string : has
    array[2]->string: has  array[2]->freq: 501
Enter the text of array[3]->string : fleas
    array[3]->string: fleas  array[3]->freq: 501

answered Jul 05 '14 at 09:04

David C. Rankin

81,885
6
58
85

Hello, to be honest I never used the get char and strdup functions, as I am still at the beginning. May I ask you where is the mistake in calling the binary search in my previous function? – Roberto Jul 05 '14 at 09:37
I've been looking at it and I left a comment. The only thing I can see from the code posted would be if `left` `middle` or `right` ever exceeded the number of structures allocated. As for the `strdup` and `getchar`, `getchar` is just there to strip any remaining chars from the input buffer after you read `n` and each `string`. Your choice of `scanf` is a little dubious. Especially if you ever need a string with spaces. `getline()` is much better. The point with `strdup` is there is no need to allocate `array[i]->string` when using `strdup` it does it for you. – David C. Rankin Jul 05 '14 at 09:45
I know `scanf` isn't really the best in these cases, but in my class, they told us to use that at the moment, because at the exam, the computer will check our program with an input txt file, and other functions might cause problems. As I replied in the other comment above, it shouldn't exceed the number of structs, and it stops to the `i` iteration. and `i` can be at maximum `n`, which is the total amount of structures – Roberto Jul 05 '14 at 09:49
That is what I think the problem is. If it stops as `n` and attempts to read `array[n]->string` or `array[n]->freq` you **will** segfault because you have only defined `array[0] -to- array[n-1]` – David C. Rankin Jul 05 '14 at 09:55
yes but it will never attempt to read array[n]->string, because it reads each time array[i]->string, and i is an integer that goes from `[0..n-1]`. But it stops at `i=0`, so the problem maybe is in that `left==right` condition – Roberto Jul 05 '14 at 13:14

How to properly allocate a struct array of strings

3 Answers3