Как мне использовать сортировку слиянием для сортировки имен с одинаковой фамилией?

ProgramBox

Как мне использовать сортировку слиянием для сортировки имен с одинаковой фамилией?

Post author:admin
Запись опубликована:26 февраля, 2023
Post category:Вопросы по программированию

#c #mergesort

#c #сортировка слиянием

Вопрос:

Наш инструктор дал нам файл csv, в котором мы должны отсортировать имена в алфавитном порядке на основе их фамилий. Но есть имена с одинаковой фамилией, и мой код работает только для их фамилии. Я не знаю, что добавить, чтобы отсортировать их по именам, когда у них одинаковая фамилия.

Это мой код:

 #include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define people 11

struct list_people {
    char FirstName[20];
    char LastName[20];
    char Name[20];
    char Age[5];
};

typedef struct list_people Details;

int merge_sort();
int merge(Details *[11], int, int, int);

int main() {
    FILE *info;
    int i, j;
    Details A[people];
    Details *cell[people];
    
    for (i = 0; i < (people   1); i  ) {
       cell[i] = amp;A[i];
    }
    
    info = fopen("people.csv", "r");
    for (i = 0; i < people; i  ) {
       fscanf(info," %[^,], %[^,], %8s", A[i].LastName, A[i].FirstName, A[i].Age);
    }
    fclose(info);
    
    merge_sort(cell, 1, people - 1);
    for (i = 1; i < people; i   ) {
        printf( "t %-20s %-20s Age:%-20s n", A[i].FirstName, A[i].LastName, A[i].Age);
    }
}
    
int merge_sort(Details *A[], int low, int high) {
    int mid;
    if (low < high) {
        mid = (low   high) / 2;
        merge_sort(A, low, mid);
        merge_sort(A, mid   1, high);
        merge(A, low, mid, high);
    }
    return 0;
}
    
int merge(Details *A[], int low, int mid, int high) {
    int leftIndex = low;
    int rightIndex = mid   1;
    int combinedIndex = low;
    int i, j;
    Details tempA[people];
    
    while (leftIndex <= mid amp;amp; rightIndex <= high) {
        if (strcasecmp((A[leftIndex]->LastName), (A[rightIndex]->LastName)) <= 0) {
            tempA[combinedIndex] = *(*(A   leftIndex));
            combinedIndex  ;
            leftIndex  ;
        } else {
            tempA[combinedIndex] = *(*(A   rightIndex));
            combinedIndex  ;
            rightIndex  ;
        }
    }
    if (leftIndex == mid   1) {
        while (rightIndex <= high) {
            tempA[combinedIndex] = *(*(A   rightIndex));
            combinedIndex  ;
            rightIndex  ;
        }
    } else {
        while (leftIndex <= mid) {
            tempA[combinedIndex] = *(*(A   leftIndex));
            combinedIndex  ;
            leftIndex  ;
        }
    }
    
    for (i = low; i <= high; i  ) {
       *(*(A   i)) = tempA[i];
    }
    return 0;
}

Ответ №1:

Вы могли бы сравнить элементы, используя что-то вроде этого:

         int cmp;
        // compare the last names
        cmp = strcasecmp( ( A[leftIndex]->LastName), ( A[rightIndex]->LastName) );
        if (cmp == 0)
        {
            // last names are identical so compare the first names
            cmp = strcasecmp( ( A[leftIndex]->FirstName), ( A[rightIndex]->FirstName) );
        }
        if (cmp <= 0)
        {
            // ...
        }
        else
        {
            // ...
        }

Ответ №2:

В коде есть несколько проблем:

размер массива people равен, поэтому цикл инициализации должен исключать значение индекса people . Вместо for (i = 0; i < (people 1); i ) вы должны написать:
```
   for (i = 0; i < people; i  )
  
```
чтобы избежать переполнения буфера, вы должны указать максимальное количество байтов для чтения для каждого целевого массива в fscanf() :
```
   fscanf(info," [^,], [^,], %4s", A[i].LastName, A[i].FirstName, A[i].Age);
  
```
Вы также должны проверить возвращаемое значение fscanf() , чтобы обнаружить недопустимый ввод.
чтобы упорядочить элементы с одинаковой фамилией, вы должны использовать функцию сравнения и сравнить LastName , затем FirstName , затем Age , возвращая первый неравный результат.

Вот пример:

 int compareDetails(const Details *a, const Details *b) {
    int res, age_a, age_b;
    if ((res = strcasecmp(a->LastName, b->LastName)) != 0)
        return res;
    if ((res = strcasecmp(a->FirstName, b->FirstName)) != 0)
        return res;
    age_a = atoi(a->Age);
    age_b = atoi(a->Age);
    return (age_a > age_b) - (age_a < age_b);
}

Массивы в C основаны на нуле, поэтому значения индекса должны начинаться с 0 . В C также идиоматично указывать фрагмент массива с включенным первым индексом и исключенным последним индексом. Это позволяет использовать пустые фрагменты и упрощает merge_sort код, избегая ошибок 1 / -1 корректировок.

Массив cell указателей является избыточным, поскольку вы сортируете массив Details на месте. Вы можете упростить код таким образом:

 #include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define PEOPLE 11

struct list_people {
    char FirstName[20];
    char LastName[20];
    char Name[20];
    char Age[5];
};

typedef struct list_people Details;

int merge_sort(Details A[], int low, int high);

int main() {
    FILE *info;
    int i, j, n;
    Details A[PEOPLE];
    
    info = fopen("people.csv", "r");
    if (info == NULL)
        return 1;

    for (n = 0; n < PEOPLE; n  ) {
       if (fscanf(info," [^,], [^,], %4s", A[n].LastName, A[n].FirstName, A[n].Age) != 3)
           break;
    }
    fclose(info);
    
    merge_sort(A, 0, n);
    for (i = 0; i < n; i  ) {
        printf( "t %-20s %-20s Age:%-20s n", A[i].FirstName, A[i].LastName, A[i].Age);
    }
    return 0;
}
    
int compareDetails(const Details *a, const Details *b) {
    int res, age_a, age_b;

    if ((res = strcasecmp(a->LastName, b->LastName)) != 0)
        return res;
    if ((res = strcasecmp(a->FirstName, b->FirstName)) != 0)
        return res;
    age_a = atoi(a->Age);
    age_b = atoi(a->Age);
    return (age_a > age_b) - (age_a < age_b);
}

void merge(Details A[], int low, int mid, int high) {
    int leftIndex = low;
    int rightIndex = mid;
    int combinedIndex = 0;
    int i, j;
    Details tempA[high - low];
    
    while (leftIndex < mid amp;amp; rightIndex < high) {
        if (compareDetails(amp;A[leftIndex], amp;A[rightIndex]) <= 0) {
            tempA[combinedIndex] = A[leftIndex];
            combinedIndex  ;
            leftIndex  ;
        } else {
            tempA[combinedIndex] = A[rightIndex];
            combinedIndex  ;
            rightIndex  ;
        }
    }
    while (leftIndex < mid) {
        tempA[combinedIndex] = A[leftIndex];
        combinedIndex  ;
        leftIndex  ;
    }
    while (rightIndex < high) {
        tempA[combinedIndex] = A[rightIndex];
        combinedIndex  ;
        rightIndex  ;
    }
    for (i = low; i < high; i  ) {
        A[i] = tempA[i - low];
    }
}

int merge_sort(Details A[], int low, int high) {
    if (high - low >= 2) {
        int mid = low   (high - low) / 2;
        merge_sort(A, low, mid);
        merge_sort(A, mid, high);
        merge(A, low, mid, high);
    }
    return 0;
}

Ответ №3:

Если у вас две одинаковые фамилии, вам нужно сравнить с другим атрибутом и использовать его, чтобы определить, какой способ сортировки.

Во-первых, чтобы сделать вещи немного более разборчивыми, мы собираемся использовать вызовы strcasecmp из выражений условий и сохранить их результат в некоторой переменной:

 while ( leftIndex <= mid  amp;amp;  rightIndex <= high )
{
  int lastNameResult = strcasecmp( A[leftIndex]->LastName, A[rightIndex]->LastName );

Затем в качестве первого шага мы собираемся разделить <= 0 регистр на два отдельных случая:

   if ( lastNameResult < 0 )
  {
    // left < right, process as before
  }
  else if ( lastNameResult == 0 )
  {
    // new case to handle same last names
  }
  else
  {
    // left > right, process as before 
  }

Теперь в этом новом случае нам нужно сравнить со вторым атрибутом; обычный выбор будет FirstName :

   ...
  else if ( lastNameResult == 0 )
  {
    int firstNameResult = strcasecmp( A[leftIndex]->FirstName, A[rightIndex]->FirstName );

    if ( firstNameResult < 0 )
    {
      // left < right, handle the same way you did for LastName
    }
    else if ( firstNameResult == 0 )
    {
      // left == right, need to compare against another attribute
    }
    else
    {
      // left > right, handle the same way you did for LastName
    }
  }
  ...

Если вы столкнулись с двумя записями с одинаковыми именами, вам нужно будет выбрать другой атрибут для сравнения (например, Age ) и поместить его в else if ( firstNameResult == 0 ) ветку. С другой стороны, вы можете объединить < регистры == и и просто позволить повторяющимся записям попадать туда, куда они попадают.

Очевидно, что этот подход не очень хорошо масштабируется для более чем пары атрибутов, и вы заканчиваете дублированием кода. Лучший способ сделать это — отделить сравнения от слияний. Добавьте новую переменную, назовем ее mergeLeft , для которой установлено значение true (отличное от нуля), если вам нужно объединить из левого списка, false ( 0 ), если вам нужно объединить справа. Мы можем вычислить это без необходимости использовать целую цепочку if-else:

 while ( leftIndex <= mid  amp;amp;  rightIndex <= high )
{
  int lastNameResult = strcasecmp( A[leftIndex]->LastName, A[rightIndex]->LastName );
  int firstNameResult = strcasecmp( A[leftIndex]->FirstName, A[rightIndex]->FirstName );

  /**
   * Yes, you can use logical expressions outside of an if condition.  The
   * parentheses aren't necessary in this case, but it should make the
   * expression easier to understand.  The result of this expression
   * will either be 0 or 1.  
   */
  int mergeLeft = lastNameResult < 0 || (lastNameResult == 0 amp;amp; firstNameResult < 0);

mergeLeft Переменной будет присвоено значение true ( 1 ), если левое LastName меньше правого LastName , или если фамилии равны, а левое FirstName меньше правого FirstName . Пуф, этот уродливый вложенный if оператор волшебным образом исчезает, и мы остаемся с этим в качестве тела вашего while цикла:

   if ( mergeLeft )
  {
    tempA[combinedIndex  ] = *A[leftIndex  ];  // I've combined the updates
  }                                            // of combinedIndex and leftIndex
  else                                         // within these statements, 
  {                                            // just to save a little space
    tempA[combinedIndex  ] = *A[rightIndex  ]; // I also replaced pointer
  }                                            // notation with array notation
}                                              // because it's less eye-stabby

Вопрос:

Комментарии:

Ответ №1:

Ответ №2:

Ответ №3:

Вам также может понравиться

Как объединить 2 фрейма данных по столбцам в pandas

Можем ли мы использовать многопоточность для преобразования документа Microsoft Word в HTML на C #?

Нравится / не нравится функциональность в AngularJS