English 中文(简体)
Checking an array of data for similar elements in C
原标题:

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] =   ;
    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.
", temp);
    else
    {
        printf("%s ", temp);
        for (j = 0; j < nameCount; j++)
            printf("and %s ", names[i]);
        printf("are from the same location.

");
    }
}

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.

最佳回答

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] =   ;

with

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

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] =   ;
        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.

问题回答

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...

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] !=   ) buf[strlen(buf) - 1] =   ;

You other problem is a wrong index

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

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 (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,  );
if (pEndl != NULL)
  *pEndl =   ;

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.
", network[i].name);
    else
        printf("are from the same location.

");
}

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("
%s matches: ", network[i].name);
}

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.





相关问题
Fastest method for running a binary search on a file in C?

For example, let s say I want to find a particular word or number in a file. The contents are in sorted order (obviously). Since I want to run a binary search on the file, it seems like a real waste ...

Print possible strings created from a Number

Given a 10 digit Telephone Number, we have to print all possible strings created from that. The mapping of the numbers is the one as exactly on a phone s keypad. i.e. for 1,0-> No Letter for 2->...

Tips for debugging a made-for-linux application on windows?

I m trying to find the source of a bug I have found in an open-source application. I have managed to get a build up and running on my Windows machine, but I m having trouble finding the spot in the ...

Trying to split by two delimiters and it doesn t work - C

I wrote below code to readin line by line from stdin ex. city=Boston;city=New York;city=Chicago and then split each line by ; delimiter and print each record. Then in yet another loop I try to ...

Good, free, easy-to-use C graphics libraries? [closed]

I was wondering if there were any good free graphics libraries for C that are easy to use? It s for plotting 2d and 3d graphs and then saving to a file. It s on a Linux system and there s no gnuplot ...

Encoding, decoding an integer to a char array

Please note that this is not homework and i did search before starting this new thread. I got Store an int in a char array? I was looking for an answer but didn t get any satisfactory answer in the ...

热门标签