Проверка массива данных для похожих элементов в C

Question

Я создал «адресную» структуру. Каждый адрес (xx.yy.zz.mm) состоит из элементов xx, yy, zz и mm, каждый из которых является целым числом. С каждым адресом также связан элемент «name».

У меня есть массив до 100 адресов, который называется "сеть". Вот пример некоторых элементов в сети:

186.88.1.21 Тайлер
186.88.9.11 Боб
101.21.0.13 Том
111.11.3.89 Чак
101.21.5.99 Люк

Мне нужно проверить каждый адрес и посмотреть, есть ли другие адреса из того же места. Два адреса находятся в одном месте, если элементы xx и yy идентичны. Если в одном и том же месте есть 1 или более адресов, мне нужно вывести эту информацию.

Ниже приведен код, который я написал, чтобы попытаться сделать это:

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");
    }
}

Этот код работает для первых двух адресов в массиве, которые находятся в одном и том же месте, но в остальном он не работает (хотя выглядит так, как будто почти - он печатает пробелы вместо имен, но имеет правильное количество заготовок). Вывод адресов, которые я перечислил выше, (извините за неправильное форматирование):

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  
.

Также кажется, что в конце каждого имени добавлен символ новой строки.

Answer 1

Также кажется, что в конце каждого имени добавлен символ новой строки.

Видимо, вы используете fgets() для чтения данных из файла. fgets() сохраняет последний перевод строки. Вы можете удалить его, например:

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

---

У вас другая проблема - неверный индекс

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

Answer 2

Здесь как минимум несколько проблем.

0: temp[11] - двенадцатый элемент массива char, который вы определили как 11 элементов. Это переполнение буфера.

1: names[100][10] должно быть names[100][11], чтобы каждый элемент был достаточно большим для хранения значения из temp.

2: вы используете strcpy (), а затем вставляете завершающий символ, предположительно, если вы скопировали более 10 символов из strcpy (). В этом случае у вас есть переполнение данных. Вы хотите использовать strncpy (), и затем завершит строку.

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

с

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

и заменить

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

с

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

3: цикл, в котором вы печатаете список «и% s», разыменовывает массив, используя неверную переменную. Вы используете итерацию «j», но извлекаете элемент «i».

4: что касается перехода на новую строку, очень вероятно, что network [i] .name (для любого i) содержит символ новой строки, который вы копируете.

5: если у вас есть три вещи из одного и того же места, вы, вероятно, перечислите их так, как вы этого не хотите.

1.1.1.1 chuck
1.1.2.2 larry
1.1.3.3 biff

скорее всего выведет (как только другие ошибки будут исправлены)

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

Решение этой проблемы оставлено в качестве упражнения.

Answer 3

Я бы немного изменил это. Я бы начал с сортировки массива адресов / имен по значениям xx и yy. Тогда вы можете пройти через массив, и все люди, находящиеся в одном месте, будут рядом друг с другом ...

Answer 4

Вы можете попробовать использовать больше абстракций. Ваша проблема по существу идентична проблеме «групп отпечатков пальцев», которую я поставил во вводном домашнем задании . На том же веб-сайте вы можете найти решение , которое реализовано с использованием C-интерфейса Дэйва Хансона и библиотеки .

Основная идея заключается в использовании Table с местоположением (элементы xx и yy) в качестве ключа и списком адресов с этим ключом в качестве значения. Затем программа групп отпечатков пальцев точно сообщает, когда несколько адресов находятся в одном месте. Если хотите, скачайте решение и адаптируйте его.

Answer 5

Вот несколько итеративно разных шагов, которые я предпринял при модификации вашего кода. Я не запускал ничего из этого, но я ожидаю, что это будет в основном правильно (за исключением последнего, я долгое время не касался функции C qsort ()). Первые два имеют сложность O (n ^ 2), а последний - сложность O (n * log (n)). Это будет иметь значение для "больших" сетей.

Если у вас нет особой необходимости делать все эти копии, вам действительно стоит держаться подальше от этого.

Последняя версия кода ниже также изменяет порядок массива. (Это сортирует).

---

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

Избегайте использования strcpy и используйте strncpy. Это предотвратит проблемы переполнения буфера, что, как мне кажется, происходит здесь.

Массив temp имеет размер 11, и вы копируете в него 10-символьную строку и добавляете завершающий '\0' (правильно). Элементы names[100][] имеют длину всего 10 символов, поэтому, когда вы записываете 10-символьную строку в одну, вы пишете NULL-символ в первый символ следующего элемента массива. Когда вы позже попытаетесь прочитать этот элемент, он окажется пустым (что объясняет пустые имена, которые вы видите).

Что касается дополнительных новых строк, я бы еще раз проверил, как вы читаете свои данные. Если вы читаете его из текстового файла, вы, вероятно, читаете в новой строке в конце каждой строки файла. Чтобы обойти это, нужно заменить символ новой строки на NULL (так как обычно это конец строки) на что-то вроде

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