如何使用mergesort对具有相同姓氏的姓名进行排序？

Question

我们的讲师给了我们一个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] = &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 && 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;
}

Answer 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
        {
            // ...
        }

Answer 2

代码中有多个问题：

• 数组大小为people，因此初始化循环应排除索引值people。你应该这样写，而不是for (i = 0; i < (people + 1); i++)：

对于(i = 0；i< people；i++)

• 为避免缓冲区溢出，应指定要为fscanf()中的每个目标数组读取的最大字节数：

fscanf(info，“%19^，，%19^，，%4s"，Ai.LastName，Ai.FirstName，Ai.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调整。

由于对Details数组进行了就地排序，因此cell指针数组是多余的。您可以通过以下方式简化代码：

#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," %19[^,], %19[^,], %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 && rightIndex < high) {
        if (compareDetails(&A[leftIndex], &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;
}

Answer 3

如果您有两个相等的姓氏，则需要与另一个属性进行比较，并使用该属性来确定排序方式。

首先，为了让事情更清晰，我们将从条件表达式中删除对strcasecmp的调用，并将其结果保存到某个变量中：

while ( leftIndex <= mid  &&  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  &&  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 && firstNameResult < 0);

如果左LastName小于右LastName，或者如果姓氏相等且左FirstName小于右FirstName，则LastName变量将设置为true (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