C - join arrays

Question

why can't i use Join? it doesn't have the 4 (e) from set B... why?

#include <stdio.h>

#define SIZEOF_A 6
#define SIZEOF_B 6

typedef enum {
        a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z
} set;

void dispSet(set numbers[], int size_numbers) {
  int i;
  printf("[ ");
  for (i = 0; i < size_numbers-1; i++) {
    printf("%d, ", numbers[i]);
  }
  printf("%d ]", numbers[size_numbers-1]);
  printf("\n");
}

int in_arr(int A, set B[], int B_size) {
    int res = 0;
    int counter;
    for (counter = 0; counter < B_size; counter++) {
        if (A == B[counter]) {
            res = 1;
            break;
        }
    }
    return res;
}

int arr_in_arr(set smaller[], int smaller_size, set bigger[], int bigger_size) {
    int res = 1;
    int counter;
    for (counter = 0; counter < smaller_size; counter++) {
        if (in_arr(smaller[counter], bigger, bigger_size)) {
            continue;
        }
        else {
            res = 0;
            break;
        }
    }
    return res;
}

int size_c(set arr1[], int arr1_size, set arr2[], int arr2_size) {
    int i;
    int newsize = 0;
    for (i = 0; i < arr1_size; i++) {
        if (!in_arr(arr1[i], arr2, arr2_size)) {
            newsize++;
        }
    }
    for (i = 0; i < arr2_size; i++) newsize++;
    printf("\nSIZE OF C: %d\n", newsize);
    return newsize;
}

int Join(set arr1[], int arr1_size, set arr2[], int arr2_size, set arr3[], int arr3_size) {
    int i, j;
    for (i = 0; i < arr1_size; i++) {
        arr3[i] = arr1[i];
    }
    for (i = 0; i < arr2_size; i++) {
        j = i+arr2_size;
        if (!in_arr(arr2[i], arr3, arr3_size)) {
            arr3[j] = arr2[i];
        }
    }
}

int main () {
    set A[SIZEOF_A] = {c, d, f, a, b, j};
    set B[SIZEOF_B] = {a, b, c, d, e, f};
    int SIZEOF_C = size_c(A, SIZEOF_A, B, SIZEOF_B);
    int counter;
    printf("For the sets,\n");
    printf("A: ");
    dispSet(A, SIZEOF_A);
    printf("B: ");
    dispSet(B, SIZEOF_B);
    printf("C: ");
    set C[SIZEOF_C];
    Join(A, SIZEOF_A, B, SIZEOF_B, C, SIZEOF_C);
    dispSet(C, SIZEOF_C);
    printf("%s\n", (arr_in_arr(A, SIZEOF_A, B, SIZEOF_B) == 1)?"B contains A":"B does not contain A");
}

Didn't look further than in_arr. You are missing the initialization for res. — pmg
– pmg, Commented May 1, 2011 at 18:48
okay i added the initialization, compiled, and all that changed was the addition of 0 to C — tekknolagi
– tekknolagi, Commented May 1, 2011 at 18:50
please turn on warnings on your compiler and fix what it reports. Edit this when you've fixed them (for example, res is not initialized in in_arr if the value is not found, printf("", smaller[counter]); isn't valid) — Mat
– Mat, Commented May 1, 2011 at 18:50

Jonathan Leffler · Accepted Answer · 2011-05-01 19:28:48Z

The main problem is the assignment indexing in the second loop of the Join() function:

int Join(set arr1[], int arr1_size, set arr2[], int arr2_size, set arr3[], int arr3_size)
{
    int i;
    for (i = 0; i < arr1_size; i++)
        arr3[i] = arr1[i];
    for (i = 0; i < arr2_size; i++)
    {
        if (!in_arr(arr2[i], arr3, arr3_size))
            arr3[i+arr1_size] = arr2[i];
    }
}

You need to keep a counter that progresses through the arr3 array properly even when i is reset to zero (and some of the i values are not added). The function is declared to return a value but does not do so - another bug. Either return the actual size of the result array (shown below) or declare the function to return void. Since the returned value is not used, the second option might be better. This might do the job:

int Join(set arr1[], int arr1_size, set arr2[], int arr2_size, set arr3[], int arr3_size)
{
    int i;
    int k = 0;
    for (i = 0; i < arr1_size; i++)
        arr3[k++] = arr1[i];
    for (i = 0; i < arr2_size; i++)
    {
        if (!in_arr(arr2[i], arr3, arr3_size))
            arr3[k++] = arr2[i];
    }
    assert(k <= arr3_size);
    return k;
}

One minor (performance rather than correctness) issue:

int newsize = 0;
for (i = 0; i < arr1_size; i++) 
{
    if (!in_arr(arr1[i], arr2, arr2_size)) 
        newsize++;
}
for (i = 0; i < arr2_size; i++) 
    newsize++;

The second loop can be written more succinctly as:

newsize += arr2_size;

Or, indeed, you could initialize newsize = arr2_size; and then count the extras.

int newsize = arr2_size;
for (i = 0; i < arr1_size; i++) 
{
    if (!in_arr(arr1[i], arr2, arr2_size)) 
        newsize++;
}

There's a dubious printf() statement in arr_in_arr():

int arr_in_arr(set smaller[], int smaller_size, set bigger[], int bigger_size)
{
    int res = 1;
    int counter;
    for (counter = 0; counter < smaller_size; counter++)
    {
        if (in_arr(smaller[counter], bigger, bigger_size))
            printf("%d ", smaller[counter]);
        else
        {
            res = 0;
            break;
        }
    }
    return res;
}

Either, it should have '%d' in the format string or the conditional should be inverted and the whole function simplified:

int arr_in_arr(set smaller[], int smaller_size, set bigger[], int bigger_size)
{
    int counter;
    for (counter = 0; counter < smaller_size; counter++)
    {
        if (!in_arr(smaller[counter], bigger, bigger_size))
            return 0;
    }
    return 1;
}

The variable counter in main() is not used.

Looked at structurally, your 'set' abstraction is not great; you have to pass an array and a size every time you call a function. Also, you can have a variable set x; which contains a single element (rather than a set). You could improve this with a structure, but that might get you into too much memory allocation for the time being.

There is also no code to ensure that the sets contain no duplicates. That is, if you defined a set:

set D[] = { a, c, a, d };

The result set of the Join() operation where this was the left (first) operand would contain two elements a in the output. Incidentally, the Join() operation could also be regarded as a set union, a ∪ b.

I ended up with this code:

#include <stdio.h>
#include <assert.h>

#define SIZEOF_A 6
#define SIZEOF_B 6

typedef enum
{
        a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z
} set;

static void dispSet(set numbers[], int size_numbers)
{
    int i;
    printf("[ ");
    for (i = 0; i < size_numbers-1; i++)
        printf("%d, ", numbers[i]);
    printf("%d ]", numbers[size_numbers-1]);
    printf("\n");
}

static int in_arr(set A, set B[], int B_size)
{
    int res = 0;  // XXX: uninitialized
    int counter;
    for (counter = 0; counter < B_size; counter++)
    {
        if (A == B[counter])
        {
            res = 1;
            break;
        }
    }
    return res;
}

static int arr_in_arr(set smaller[], int smaller_size, set bigger[], int bigger_size)
{
    int counter;  // XXX: simplified
    for (counter = 0; counter < smaller_size; counter++)
    {
        if (!in_arr(smaller[counter], bigger, bigger_size))
            return 0;
    }
    return 1;
}

static int size_c(set arr1[], int arr1_size, set arr2[], int arr2_size)
{
    int i;
    int newsize = arr2_size;    // XXX: compacted
    for (i = 0; i < arr1_size; i++)
    {
        if (!in_arr(arr1[i], arr2, arr2_size))
            newsize++;
    }
    printf("\nSIZE OF C: %d\n", newsize);
    return newsize;
}

static int Join(set arr1[], int arr1_size, set arr2[], int arr2_size, set arr3[], int arr3_size)
{
    int i;
    int k;  // XXX: fixed
    for (i = 0; i < arr1_size; i++)
        arr3[k++] = arr1[i];
    for (i = 0; i < arr2_size; i++)
    {
        if (!in_arr(arr2[i], arr3, arr3_size))
            arr3[k++] = arr2[i];
    }
    assert(k <= arr3_size);
    return k;
}

int main(void)
{
    set A[SIZEOF_A] = {c, d, f, a, b, j};
    set B[SIZEOF_B] = {a, b, c, d, e, f};
    int SIZEOF_C = size_c(A, SIZEOF_A, B, SIZEOF_B);
    printf("For the sets,\n");
    printf("A: ");
    dispSet(A, SIZEOF_A);
    printf("B: ");
    dispSet(B, SIZEOF_B);
    printf("C: ");
    set C[SIZEOF_C];
    Join(A, SIZEOF_A, B, SIZEOF_B, C, SIZEOF_C);
    dispSet(C, SIZEOF_C);
    printf("%s\n", (arr_in_arr(A, SIZEOF_A, B, SIZEOF_B) == 1)?"B contains A":"B does not contain A");
}

The functions are made static because there is no other file using them nor any header declaring them (and that shuts up the compiler warnings from -Wmissing-prototypes). I compiled it (on MacOS X 10.6.7 using Apple's GCC 4.2.1) using:

gcc -g -std=c99 -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes join.c -o join

The output is:

SIZE OF C: 7
For the sets,
A: [ 2, 3, 5, 0, 1, 9 ]
B: [ 0, 1, 2, 3, 4, 5 ]
C: [ 2, 3, 5, 0, 1, 9, 4 ]
B does not contain A

Jordan · Accepted Answer · 2011-05-01 18:59:24Z

3

your issue is that you are using i to place the new element into array 3 and access the elements from array 2. Make a new variable say j that is used to access the elements from array 3.

This worked for me.

int Join(set arr1[], int arr1_size, set arr2[], int arr2_size, set arr3[], int arr3_size) {
    int i;
    int j = 0; /*NEW VARIABLE*/
    for (i = 0; i < arr1_size; i++) {
        arr3[i] = arr1[i];
    }

    for (i = 0; i < arr2_size; i++) {
        if (!in_arr(arr2[i], arr3, arr3_size)) {
            arr3[j+arr1_size] = arr2[i]; /*USE j TO ADD ELEMENT TO arr3*/
        j++; /*INCREMENT EACH TIME THIS IS DONE*/
        }
    }
}

answered May 1, 2011 at 18:59

Jordan

5,0584 gold badges29 silver badges39 bronze badges

Comments

Zilchonum · Accepted Answer · 2011-05-01 19:15:10Z

Let's run through the code at the point where join tries to but e into the union:

for (i = 0; i < arr2_size; i++) {
    if (!in_arr(arr2[i], arr3, arr3_size)) {
        arr3[i+arr1_size] = arr2[i];
    }
}

In this case, the index of e in arr2 is equal to 4. It's not in arr3, so we try to put it in arr3 at position i+arr1_size. Here's the problem - i+arr1_size is 6+4, or 10. size_c looks correct, so arr3_size ought to be 7. (--> 7 is less than 10)

So the code is recognizing that e isn't in arr3 yet, and it is attempting to put it in arr3, but it fails in this regard because the index at which it tries to place e is outside the bounds of the array.

You'll have to keep track of the number of elements in arr3 separately.

[edit]Ah, I guess this is pretty much what Yoel was talking about, I didn't read it very well the first time[/edit]

Collectives™ on Stack Overflow

C - join arrays

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related