Checking an array of data for similar elements in C

Question

Hi,

I created an "address" structure. Each address (xx.yy.zz.mm) consists of an xx, yy, zz and mm element, all of which are ints. Each address also has a "name" element associated with it.

I have an array of up to 100 addresses called "network". Here is an example of some elements in network:

186.88.1.21 Tyler
186.88.9.11 Bob
101.21.0.13 Tom
111.11.3.89 Chuck
101.21.5.99 Luke

I need to check each address and see if there are other addresses from the same location. Two addresses are from the same location if elements xx and yy are identical. If there are 1 or more addresses from the same location, I need to output this information.

Below is some code I wrote to try to do this:

char temp[11];
int nameCount;
for (i = 0; i < count; i++)
{
    char names[100][10] = {};
    strcpy(temp, network[i].name);
    temp[11] = '\0';
    nameCount = 0;
    for (j = i + 1; j < count; j++)
    {
        if (network[i].xx == network[j].xx && network[i].yy == network[j].yy)
        {
            strcpy(names[nameCount], network[j].name);
            nameCount++;
        } 
    }
    if (nameCount == 0)
        printf("No matches for %s.\n", temp);
    else
    {
        printf("%s ", temp);
        for (j = 0; j < nameCount; j++)
            printf("and %s ", names[i]);
        printf("are from the same location.\n\n");
    }
}

This code works for the first two addresses in the array which are from the same location, but it doesn't work for the rest (although it looks like it almost does -- it's printing blanks instead of names, but it has the right number of blanks). The output for the addresses I listed above is (sorry for the bad formatting):

Tyler  
 and Bob  
 are from the same location.  

No matches for Bob  
.  
Tom  
 and [space] and [space] are from the same location.  

No matches for Chuck  
.  
Luke  
 and [space] are from the same location.  

No matches for Nick  
.

It also seems like there is a newline character that has been added to the end of each name.

Any ideas?

Answer 1

Avoid using strcpy and use strncpy instead. This will prevent you from buffer overflow problems, which is what I think is happening here.

Array temp has size 11, and you copy a 10-character string into it and add a trailing '\0' (correctly). The elements of names[100][] are only 10 characters long, so when you write a 10-character string into one you will write a NULL character into the first character of the next array element. When you later try to read this element, it will appear empty (which would explain the blank names you are seeing).

Regarding the extra newlines, I would re-examine the way you are reading in your data. If you are reading it in from a text file, you are probably reading in the newline at the end of each line of the file. A way around this is to replace the newline with a NULL (since that's typically the end of the string) with something like

char* pEndl = strchr(input_string,'\0');
if (pEndl != NULL)
  *pEndl = '\0';

Answer 2

I'd change this quite a bit. I'd start by sorting the array of addresses/names based on the xx and yy values. Then you can walk through the array, and all the people who are from the same location will be right next to each other...

Answer 3

There are at least several problems here.

0: temp[11] is the twelfth element in a char array you've defined to be 11 elements long. This is a buffer overrun.

1: names[100][10] should be names[100][11], so that each element is large enough to store a value from temp.

2: you're using strcpy(), then inserting a terminating character, presumably in case you copied more than 10 characters from strcpy(). In that case, you have a data overflow. You want to use strncpy(), and then terminate the string.

strcpy(temp, network[i].name);
temp[11] = '\0';

with

strncpy(temp, network[i].name, sizeof(temp) - 1);
temp[sizeof(temp) - 1] = '\0';

and replace

        strcpy(names[nameCount], network[j].name);
        nameCount++;

with

        strncpy(names[nameCount], network[j].name, sizeof(names[nameCount] - 1);
        names[nameCount][sizeof(nameCount) - 1] = '\0';
        nameCount++;

3: the loop where you print the "and %s " list is dereferencing the array using the wrong variable. You're iterating using 'j', but pulling the 'i'th element out.

4: as far as the newline goes, it's very likely the case that network[i].name (for any i) contains a newline character that you're copying in.

5: if you have three things from the same location, you'll probably list them in a way you may not want.

1.1.1.1 chuck
1.1.2.2 larry
1.1.3.3 biff

will likely output (once the other bugs are fixed)

chuck and larry and biff are from the same location
larry and biff are from the same location
No matches for biff.

Fixing that problem is left as an exercise.

Answer 4

It also seems like there is a newline character that has been added to the end of each name.

Apparently, you use fgets() to read the data from the file. fgets() retains the final newline. You can remove it with, for example:

fgets(buf, sizeof buf, file);
if (buf[0] != '\0') buf[strlen(buf) - 1] = '\0';

---

You other problem is a wrong index

    for (j = 0; j < nameCount; j++)
        printf("and %s ", names[i]);
    /*                         ^^^ should be j */

Answer 5

Here's some iteratively different steps I took at modifying your code. I haven't run any of this, but I expect it to be mostly right (except for the last one, I haven't touched the C qsort() function in a long time). The first two have complexity O(n^2), while the last is complexity O(n*log(n)). This would matter on "large" networks.

Unless you have a particular need to make all those copies, you really should stay away from it.

The last version of the code below also modifies the order of the array. (It sorts it).

---

for (int i = 0; i < count; i++) { 
    bool any_matches = false;

    for (int j = i + 1; j < count; j++) {
        if (network[i].xx == network[j].xx && network[i].yy == network[j].yy) {
            if (!any_matches) {
                 printf("%s ", network[i].name);               
                 any_matches = true;
            }

            printf("and %s ", network[j].name);
        }
    }

    if (any_matches == false)
        printf("No matches for %s.\n", network[i].name);
    else
        printf("are from the same location.\n\n");
}

---

for (int i = 0; i < count; i++) { 
    bool any_matches = false;

    for (int j = i + 1; j < count; j++) {
        printf("%s matches: ", network[i].name);               

        if (network[i].xx == network[j].xx && network[i].yy == network[j].yy)
            printf("%s, ", network[j].name);
    }
}

---

int compare_networks(struct Network *left, struct Network *right) {
    if (left->xx < right->xx)
        return -1;
    if (left->xx > right->xx)
        return 1;
    if (left->yy < right->yy)
        return -1;
    if (left->yy > right->yy)
        return 1;
    return 0;
}

// Sort the list
qsort(network, count, sizeof(network), compare_networks);

printf("%s matches: ", network[0].name);
for (int i=1; i<count; ++i) {
    if (network[i-1].xx == network[i].xx && network[i-1].yy == network[i].yy)
        printf("%s, ", network[i].name);
    else
        printf("\n%s matches: ", network[i].name);
}

Answer 6

You might want to try using more abstraction. Your problem is essentially identical to the "fingerprint groups" problem that I posed in an introductory homework assignment. On the same web site you can find a solution that is implemented using Dave Hanson's C Interfaces and Implementations library.

The essential idea is to use a Table with the location (xx and yy elements) as the key and the list of addresses with that key as the value. The fingerprint groups program then tells you exactly when multiple addresses have the same location. If you like, download the solution and adapt it.